Kevin Liu's 部落格 || Technical || Travel

題目敘述 題目難度：Medium 題目描述： 給定一個整數陣列 nums 以及整數 k 並回傳 nums 中 k 個出現最頻繁的元素，你可以以任意順序回傳答案 本題限制 1 <= nums.length <= 1051 <= k <= nums.length 解法一開始的想法看到這種前 k 個，k個最頻繁，十有八九最佳解會是用 priority queue 去解 我的解法1234567891011121314151617181920212223242526272829class Solution {public: vector<int> topKFrequent(vector<int>& nums, int k) { vector<int> numCount(20001, 0); //store the frequency of each number for(int n: nums){ numCount[...

題目敘述 題目難度：Medium 題目描述：題目給了一個陣列 tasks 裡面有許多不同中類的任務要丟給CPU執行，任務種類有 A~Z，每個 CPU Interval 可以選擇執行完成一個任務或者空閒。任務可以以任何順序執行，但有個條件 任何兩個相同種類的任務，執行時需要相隔 n 個 intervals ， 請回傳完成所有任務時，CPU所需的最少 intervals。 解法一開始的想法一開始比較偏向暴力去解，就是宣告一個 hash table 來儲存每個任務類型的剩餘等待間隔為多少，透過遞迴去找最小intervals 解，但這樣容易 TLE，並且這樣的做法沒有考慮到 到底要不要放idle 這件事。 12345678910111213141516171819202122232425262728293031323334353637class Solution {public: unordered_map<char, int> taskCount = { {'A',0},{...

題目敘述 題目難度：Medium 題目描述： 題目給定一個陣列 points 其中 points[i] = [xi, yi] 代表在X-Y座標軸中任意點的位置，給定整數 k 求 k 個最靠近原點(0,0)的點 兩點之間求距離公式： √(x1 - x2)2 + (y1 - y2)2 解法我一開始的想法會是因為求 k 個距離近的點，而距離近代表離原點數字小，因此要用 max Heap 來解，但是我希望在 maxHeap 中放入的會是座標本身，然後排序方式就用距離大小來排，因此會需要自定義 comparator 這邊關於使用 lambda 語法定義 comparator 可以參考這篇：https://notes.boshkuo.com/docs/C++/STL/priority_queue 我的解法12345678910111213141516171819202122232425class Solution {public: vector<vector<int>> kClosest(vector<vector<int>...

題目敘述 題目難度：Medium 題目描述： 題目給定整數陣列 nums 以及整數 k，請回傳陣列中第 k 個大的元素。特別注意，會是需要由大到小第k個元素，並不是第k大的相異元素 解法我的解法12345678910111213class Solution {public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int, vector<int>, greater<int>> minHeap(nums.begin(), nums.begin()+k); for(int i=k; i<nums.size(); i++){ if(nums[i]>minHeap.top()){ minHeap.pop(); minHeap.push(nums[i]); &#...

題目敘述 題目難度：Easy 題目描述： 你是某大學入學審核辦公室的人，你需要動態即時追縱所有申請裡面前 Kth 個高分的成績， 請設計一個 class，在具有參數整數 k，並在插入新成績後回傳第 k 高分的成績。 請實作 KthLargest class: KthLargest(int k, int[] nums) 負責初始化整數 k 物件以及用來存放考試成績的陣列 nums int add(int val) 負責添加新成績 val 到stream 並且需要再添加成績後回傳到目前為止第k個高分的成績 解法我的解法12345678910111213141516171819202122232425class KthLargest { public: int k; priority_queue<int, vector<int>, greater<int>> minHeap; KthLargest(int k, vector<int>& nums) { ...

題目敘述 題目難度: medium 題目敘述: 題目給定一個 matrix 請將其順時針旋轉一次，並且必須 in-place修改，也就是不能宣告額外二元陣列去儲存元素 解法一開始的想法這題我是畫圖直接看矩陣關係 首先其實觀察 matrix 再經過一次順時針旋轉後的位置，然後比對原本的，可以發現一些關係。旋轉的過程也只是列元素變成行元素，可以觀察到 123- matrix[0][0] = matrix[0][2]- matrix[1][0] = matrix[0][1]- matrix[2][0] = matrix[0][0] 透過上面關係可以發現， 順時鐘旋轉一次，其實只是先將 matrix 相同 column 元素全部 reversed 排列後，再去進行對稱的過程。 我的解法 不過實際在解的時候，如果要對每一個 column 元素進行反序排列，會橫跨不同子陣列的元素交換，處理上比較不直觀， 因此我發現其實也可以先反序排列同一列元素再進行對稱，只不過這樣的結果會是原本 matrix 逆時針轉一次，但是其實逆時針轉三次就等於順時針轉一次。 1234567891011...

題目敘述 題目難度：Medium 題目描述： 題目給定一個整數陣列，請旋轉該陣列元素到右邊 k 次，其中 k 為非負整數 這裡的陣列會是一維陣列，旋轉的意思是尾端元素移動到首端，其餘元素跟著連帶移動。 解法一開始的想法我首先觀察到 k 的範圍會是 0 <= k <= 10^5 因此會需要對 k 取餘數看最少旋轉幾次。另外就是旋轉的方法，最直觀就會是透過迴圈把尾端元素不斷往首端放，但是 nums.length 範圍挺廣，這樣不停移動剩下元素，時間複雜度會到 $O(n^2)$ 肯定會 time limit exceeded。 我想到另一個方法，就是找插入點，看題目給的測資可以發現，旋轉幾次其實只是取末端元素數量不同而已，然後再把末端整組元素接回首端，就能夠完成旋轉。 我的解法123456789101112131415161718class Solution {public: void rotate(vector<int>& nums, int k) { int n=nums.size(); ...

題目敘述 題目難度：Medium 題目描述：給定一個BST, 求在BST內任意兩節點的最小共同祖先，其中自己可以是自己的祖先，求任意兩節點 p, q 的LCA 解法一開始的想法首先一定是先 traversal 查找 p, q 兩節點，而我的想法是，如果用 post-traversal 來走訪測資一，這樣對於任意兩節點，假設是 3,或是 5 這兩個元素的 caller(當前遞迴節點) 會是 4，而對於 5 或是 7 這兩個的caller會是節點 6。因此其實就是要找同時具有 p跟q節點返回值的那層 caller 就會是 LCA 我的解法123456789101112TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == nullptr) return nullptr; if (root == p || root == q) return root; TreeNode *leftNode = lowestCommonAncestor(r...

題目敘述 題目難度：Medium 題目描述： 本題給定 n 個車輛，其中每輛車需要抵達到終點位置 target，第 i 輛車的位置為 position[i] 第 i 輛車的速度為 speed[i]，題目中有個規定 輛車不得超越另一輛車，只能保持相同速度行駛，也就是說如果後車比前車快，那後車只能降速，降到與前車同等速度一同行駛，這樣就形成一個兩輛車行駛的車隊，題目中另外還有說明，單獨一輛車也算是車隊的一部份，題目最終要求，請計算共有多少車隊會抵達終點。 解法一開始的想法核心想法我覺得是首先， 要能夠記錄每輛車當前的位置 ，並且會需要知道每輛車速度與位置之間的關係。但我一開始的想法比較複雜，就是用 pair 或 hasp table 紀錄車輛當前位置跟速度，每一小時就更新車輛位置跟速度，一旦有車隊抵達終點後就不再更新那幾輛車，但這樣可能會有多重迴圈，並且需要額外紀錄是否抵達終點。 我的解法12345678910111213141516171819202122232425class Solution {public: int carFleet(int target, ...

題目敘述 題目難度：Medium 題目描述： 給定一個 m x n 的 matrix，請以螺旋順序回傳 matrix 內的所有元素 看題目的範例應該是要用順時鐘方向然後由外而內來螺旋 解法一開始的想法一開始看到，想說應該要能夠用遞迴方式來逐一存取特定的格子，可能指定 row 跟 column 然後要想某種方式來每次都跑完一層後轉向，但我後來發現這樣的判斷方式會太複雜，因為我原本的想法是每一層遞回要跑一個螺旋邊 (Ex. 最上層的元素依序存入輸出vector) 但這樣遞迴終止條件會太複雜，用來控制轉向的參數也會太多。 後來改成將四個螺旋邊的存取放在相同的遞迴中，螺旋到內圈時才會進到下一層遞迴。 我的解法123456789101112131415161718192021222324252627282930313233class Solution {public: vector<int>output; void helper(vector<vector<int>> & matrix, int top, i...