基於時間的鍵值對儲存 | Medium | LeetCode#981. Time Based Key-Value Store
題目敘述 題目難度：Medium 題目描述： 題目要求設計一個 time-based 的 key-value 儲存結構，可以相同key可以儲存多種值並且對於相同Key可以有多個不同的timestamp，並且用戶可以透過特定 timestamp 獲取值 請實踐一個 TimeMap class: TimeMap() 用於初始化物件 void set(String key, String value, int timestamp): 在給定 timestamp 條件下， 儲存 value 到對應到特定的 key 上 String get(String key, int timestamp): 回傳先前透過 set 函數儲存的值，並且請找出小於等於當前 timestamp 的timestamp。如果有多個值，請回傳具有最大但小於 timestamp 的 timestamp 值。若沒有值，則回傳 "" 解法我的解法123456789101112131415161718192021222324252627282930313233343536373839404...
尋找 K 對最小總和 | Medium | LeetCode#373. Find K Pairs with Smallest Sums
題目敘述 題目難度：Medium 題目描述： 題目給定兩個陣列 nums1 以及 nums2，兩者都以 non-decreasing order 排序，並且給定整數 k，題目要求你從兩個陣列中個取出一個整數，定義成 pair (u, v) 請找出 k 具有最小總和的 pair u1, v1), (u2, v2), ..., (uk, vk) 解法一開始的想法一開始的想法比較暴力一點，一共三步： 兩個陣列都各自迭代找出所有 pair 組合 定義 minHeap 和 comparator 來比較pair之間誰的總和比較小 pop k 次 123456789101112131415161718192021222324252627282930class Solution {public: vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) { vector<v...
Top k 個頻繁元素 | Medium | LeetCode#347. Top K Frequent Elements
題目敘述 題目難度：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 | LeetCode#621. Task Scheduler
題目敘述 題目難度：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},{...
K個距離原點最近的點 | Medium | LeetCode#973. K Closest Points to Origin
題目敘述 題目難度：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>...
陣列中第K大的元素 | Medium | LeetCode#215. Kth Largest Element in an Array
題目敘述 題目難度：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]); &#...
字流中第K大的元素 | Easy | LeetCode#703. Kth Largest Element in a Stream
題目敘述 題目難度：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 | LeetCode#48. Rotate Image
題目敘述 題目難度: 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 | LeetCode#189. Rotate Array
題目敘述 題目難度：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(); ...
BST的最小共同祖先(LCA) | Medium | LeetCode#235. Lowest Common Ancestor of a Binary Search Tree
題目敘述 題目難度：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...
