### 13. Roman to Integer 用 unordered_map 去保存每個字母對應的值,這樣存取數字很方便,剩下就照題目給的規則寫即可。 ### 14. Longest Common Prefix 想法就是先比對前兩個字串的共同字串,之後的字串只要跟此共同字串比對就行了,因為是所有字串的共同字串,所以最後的答案長度一定小於等於目前的共同字串。 ### 20. Valid Parentheses 用 stack 存所有的左括號,每次遇到右括號就檢查 stack 的 top 是否有元素跟該元素是否跟右括號匹配,不匹配就 return false,程式最後要注意 stack 有沒有元素,因為可能後面都只剩左括號沒有右括號,導致雖然沒檢查出有不匹配的括號,但實際上還是有其他 stack 裡的左括號沒有跟右括號匹配到 ### 21. Merge Two Sorted Lists 很簡單,看這篇: https://leetcode.com/problems/merge-two-sorted-lists/solutions/1826666/c-easy-to-understand-2-approaches-recursive-iterative/ ### 27. Remove Elements 與 283 一樣的解法,還比 283 少一個結尾的 for loop ### 29. Divide Two Integers 這篇的解答只要用 `int` 不用 `long`,裡面有影片解說: https://zhenchaogan.gitbook.io/leetcode-solution/leetcode-29-divide-two-integers 這篇解釋也不錯: https://leetcode.com/problems/divide-two-integers/solutions/13407/c-bit-manipulations/ 但我覺得這篇解法比較直觀,但是這篇一些 special case 沒有處理好: https://medium.com/@ChYuan/leetcode-29-divide-two-integers-%E5%BF%83%E5%BE%97-medium-91e5fccb29fa 解法是將除數與被除數用 `abs` 都轉成正數再去做除法,用一個額外的變數記錄商數的正負號,但如果不使用 `long long` 要用 `int`,那用 `abs` 轉正數時會有 overflow 的問題,因此會有要注意的 special case: - `dividend` 等於 `INT_MIN`,同時 `divisor` 等於 `-1`、`大於0`、`小於0` - `divisor` 等於 `INT_MIN` - `divisor` 往左 shift,也就是乘以二時也可能會溢位,所以可以改成 `dividend` 往右 shift,等同於 `divisor` 往左 shift ### 35. Search Insert Position 看影片: https://www.bilibili.com/video/BV1sy4y1q79M?t=0.6&p=51 這題作者對於 L 與 R 要怎麼給值講得很清楚 ### 74. Search a 2D Matrix 有兩種解法,都是用 Binary Search - 第一種是先用二分法判斷 row 的位置,再根據找到的 row 用二分法判斷 col 的位置 - 第二種是直接將一維的二分法去找,每次將 mid index 用公式轉換成二維矩陣的 index ```cpp= n = number of columns row = mid/n; col = mid%n; ``` 影片維第二種解法: https://www.bilibili.com/video/BV1sy4y1q79M?t=0.4&p=53 ### 94. Binary Tree Inorder Traversal 左->中->右 ```cpp= vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> s; vector<int> result; while( !s.empty() || root ){ while( root != NULL ){ s.push(root); root = root->left; } root = s.top(); s.pop(); result.push_back(root->val); root = root->right; } return result; } ``` ### 141. Linked List Cycle Floyd’s Cycle-Finding Algorithm: 龜兔賽跑算法。顧名思義,這個演算法會假設一隻烏龜和一隻兔子在這個許多節點構成的List結構進行賽跑,烏龜每次只能走一個節點,而兔子只能走二個節點,如果List結構存在著循環,他們只要跑下去肯定能到循環裡,並且他們肯定能在循環中碰面或者在循環內的某一點會合。 ```cpp= ListNode *fast = head; ListNode *slow = head; while( fast!=NULL && fast->next!=NULL ){ // 如果兔子沒路可走那就代表沒環 fast = fast->next->next; // 一次走兩格 slow = slow->next; // 一次走一格 if( fast == slow ){ // 相遇 => 有環 return true; } } return false; // 跳出迴圈 => 沒環 ``` ### 144. Binary Tree Preorder Traversal 中->左->右 ```cpp= vector<int> preorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> s; TreeNode* t; if( root != NULL ){ s.push(root); } while( s.size() > 0 ){ t = s.top(); result.push_back(t->val); s.pop(); if( t->right != NULL ){ s.push(t->right); } if( t->left != NULL ){ s.push(t->left); } } return result; } ``` ### 145. Binary Tree Postorder Traversal 左->右->中,還有用兩個 stack 的版本,個人認為兩個 stack 比較直覺 ```cpp= vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*> s; vector<int> result; TreeNode* lastVisited = NULL; while( !s.empty() || root ){ if( root != NULL ){ s.push(root); root = root->left; } else { TreeNode* peekNode = s.top(); if( peekNode->right != NULL && lastVisited != peekNode->right ){ root = peekNode->right; } else { s.pop(); result.push_back(peekNode->val); lastVisited = peekNode; } } } return result; } ``` ### 160. Intersection of Two Linked Lists 這題關鍵是,兩個 list 如果有 intersection,那這個 intersection node 的記憶體位置是一樣的,所以不是以 value 去比對是不是同一個 node,而是用 pointer 去比對是不是指向同一個 node,藉此判斷有沒有 intersection,那這就變成步數問題,解釋為: >You can prove that: say A length = a + c, B length = b + c, after switching pointer, pointer A will move another b + c steps, pointer B will move a + c more steps, since a + c + b + c = b + c + a + c, it does not matter what value c is. Pointer A and B must meet after a + c + b (b + c + a) steps. If c == 0, they meet at NULL. >或是 >https://medium.com/@ChYuan/leetcode-no-160-intersection-of-two-linked-lists-%E5%BF%83%E5%BE%97-10a32c1ac8a8 此方法 $O(m + n)$ time and use only $O(1)$ memory ### 162. Find Peak Element 用 Binary Search 看影片: https://www.bilibili.com/video/BV1sy4y1q79M?t=577.6&p=52 ### 169. Majority Element 有 4 種解法: Divivde and Conquer: https://www.bilibili.com/video/BV1sy4y1q79M?t=0.4&p=62 剩下三種: Sorting、Hash map、Moore Voting Algorithm: https://leetcode.com/problems/majority-element/solutions/3676530/3-method-s-beats-100-c-java-python-beginner-friendly/ ### 203. Remove Linked List Elements 新建一個 Dummy Node 指向 head node,然後直接從 head node 開始檢查是否要移除,最後回傳 Dummy Node 的 next 即可 ### 206. Reverse Linked List 分兩種方法: 迴圈 跟 遞迴 - 迴圈從第一個 node 開始反轉,每次反轉一個 node 時,保留下一個 node 的位置以便存取。 - 遞迴: https://youtu.be/iT1YrvSNtlw?t=384 ### 209. Minimum Size Subarray Sum 用 Sliding Window 做 看影片: https://www.bilibili.com/video/BV1sy4y1q79M?t=197.0&p=55 ### 215. Kth Largest Element in an Array 用 priority_queue 去存每個 input array 的每個數字,最後 pop k 減 1 次,用 top() 取 queue 頂端的元素 ### 217. Contains Duplicate 用 unordered_set 直接把有出現過的元素加進 set 裡,在遍歷所有輸入時,檢查元素是否已經加進 set 裡,如果已經加進 set 了就可以直接 return ### 234. Palindrome Linked List :::info 用 slow fast pointer 可以不用額外考慮奇數偶數長度的判斷。 ::: #### 第一種 要比對是不是 Palindrome 一定要後半的元素跟前半比對,想要 $O(n)$ time 可以瀏覽 list 把值放入 stack,再從 stack pop 出後半的 list 內容,但這樣會 $O(n)$ space,因為要額外用 stack 存 list。 #### 第二種 把後半段的 list 做反轉,要怎麼找到中間的 node ? 用 slow fast pointer,走到中間用 slow 開始對後半段的 list 存取與翻轉,記得中間的 node 的 next 要指向 null,避免最後比較的時候無法終止,額外用 prev 變數存前一個 node、temp 做 slow 跟 prev 反轉時會用的,做完反轉後 prev 會跑到最後一個 node,用 prev 跟 head 分別初始化 fast 跟 slow,之後就可以開始檢查,終止條件是 fast!=NULL,因為 fast 從尾巴開始走,會走到中間指向 null 的 node,這方法可以達到 $O(n)$ time and $O(1)$ space。 :::info 偶數長度的 list,slow 會走到 $\frac{n}{2}+1$ 個 node,ex: n=6,走到第4個 node。 基數長度的 list,slow 會走到 $ceil(\frac{n}{2})$ 個 node,ex: n=7,走到第4個 node。 ::: ### 344. Reverse String 很簡單,用 while loop 與對撞雙指標就好 遞迴寫法只是多寫一個遞回函式,然後將對撞雙指標以及 string reference 寫進遞回函式的參數,每次呼叫下一層遞回函式將對撞雙指標加一與減一即可,終止條件與 while loop 的寫法一樣,最後遞回函式不需要返回值 ### 283. Move Zeros https://www.bilibili.com/video/BV1sy4y1q79M?t=2.1&p=8 ### 389. Find the Difference 第一種是用 map 存 string s 裡所有字母出現的個數,然後遍歷 string t 的字母並減去 map 裡的對映字母的 value,最後檢查 map 裡的元素的次數哪個不為 0 即可 第二種是用 array 去存字母的出現次數,用字母減掉 'a' 的數字作為 array 的 index,此 array 就變成另類的 hash table 了,而且字母才 26 種,所以 array 的大小也固定了 ### 496. Next Greater Element I 這題重點在於使用 Monotonic stack Monotonic stack 介紹筆記: https://hackmd.io/@meyr543/rkjS-x6wY > stack中保持著一定的順序,例如遞增或是遞減。 如果要新增的element比top還大/小。就把top pop出去。然後繼續往下比,直到保持一定的遞增或是遞減的順序。通常是找序列中比自己後面,但是值比自己還大/小的題目。 此題講解影片: https://www.bilibili.com/video/BV1sy4y1q79M?t=0.8&p=29 ### 692. Top K Frequent Words 用 hash map 去存每個 word 出現的次數,用 priority queue 去根據 word 出現次數進行排序,由於相同出現次數的 words 要用字母順序去排列,所以要自訂 compare function,有分用 max heap 與 min heap 的寫法,底下是用 max heap 的版本 ::: info [C++ 定义实用比较函数(Custom Compare Function) 注意点](https://blog.csdn.net/myth_HG/article/details/48734561) 在幫 pq 寫 cmp function 時,判定式要注意一下,要 reverse 判定結果 [Comparator function in Priority Queue](https://stackoverflow.com/questions/64746871/comparator-function-in-priority-queue) > Note that the Compare parameter is defined such that it returns true if its first argument comes before its second argument in a weak ordering. But because the priority queue outputs largest elements first, the elements that "come before" are actually output last. That is, the front of the queue contains the "last" element according to the weak ordering imposed by Compare. ::: ```cpp= bool cmp (const pair<string, int> lhs, const pair<string, int> rhs) { if (lhs.second != rhs.second) { return !(lhs.second > rhs.second); } else { return !( lhs.first < rhs.first ); } } class Solution { public: vector<string> topKFrequent(vector<string>& words, int k) { unordered_map<string, int> m; for(auto it=words.begin(); it != words.end(); it++){ m[*it]++; } priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(&cmp)> pq(cmp); for(auto it=m.begin(); it != m.end(); it++){ pq.push(*it); } vector<string> ans; while(k>0){ ans.push_back(pq.top().first); pq.pop(); k--; } return ans; } }; ``` ### 704. Binary Search 用 Binary Search 去搜即可,注意的是在 assgin 新 index 值給 left 或 right 時,要用 left = med + 1 與 rigth = med - 1 其中一個或兩個都用,否則如果 array 裡面沒有要找的值的話會進入無限迴圈 ### 705. Design HashSet 用 vector<list<int>> 作為 hash set,用 key % prime 作為 hash function,先設定 prime 的值並初始化 prime 個 list,用 hash function 得到的 hash value 作為 vector 的 index ### 881. Boats to Save People 先對 array 做排序,排序好後用對撞雙指標從頭跟尾開始檢查,假如頭尾相加的體重不超過 limit,則頭尾指標都移動,如果超過 limit,則移動尾指標即可,因為只能載最重的人走,當頭指標大於尾指標時再離開迴圈即可 ### 933. Number of Recent Calls 用 queue 存 time stamp,從 queue 的頭開始檢查,超過 range 的 queue 元素就丟掉 ### 1456. Maximum Number of Vowels in a Substring of Given Length 用最簡單的 sliding window 解就完事