::: info 其他人的 STL 筆記 - https://hackmd.io/@Greenleaf/advanced_cpp - https://hackmd.io/@meyr543/BkgMaiV6Y#Vector ::: ### 2. Add Two Numbers 此題想法很簡單，只是要注意做加法會遇到的一些小細節: 1. 當某個 list 已經沒有數字了，另一個數字還有可能因為前面的 carry 而一直進位，舉例: 999 + 99999 = 100998，倒數兩位的 99 就因為 carry 一直是 1 所以一直進位 根據上述情形，所以 while 終止條件除了用 l1、l2 還要用 carry 是否有值去判斷 此題新創一個 List 去存結果比較好，如果把結果存在 l1、l2 還蠻麻煩的。 ```cpp= ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* dummyNode = new ListNode; ListNode* head = dummyNode; ListNode* tail = dummyNode; dummyNode->next = l1; int carry = 0; while( l1 != nullptr || l2 != nullptr || carry ){ int digit1 = (l1 != nullptr) ? l1->val : 0; int digit2 = (l2 != nullptr) ? l2->val : 0; int sum = digit1 + digit2 + carry; ListNode* newNode = new ListNode; newNode->val = sum % 10; carry = (sum > 9) ? 1 : 0; tail->next = newNode; tail = tail->next; l1 = (l1 != nullptr) ? l1->next : nullptr; l2 = (l2 != nullptr) ? l2->next : nullptr; } return head->next; ``` ### 3. Longest Substring Without Repeating Characters 這題想法很簡單，就是用一個 Sliding Window 去存目前有的 Substring，所以會有兩個 pointer `left`、`right` 指著 window 的頭跟尾，每次都移動 `right` pointer，但是我們要怎麼知道目前 Substring 存著那些 character ? 有三種作法: 1. Set: 每次判斷 `right` 指標指向的 character 是否存在在 Set 裡，如果不存在，則將 character 加進 Set 裡，如果存在，則代表是重複字元，先檢測 `right` 減去 `left` 是否大於最大 Substring 長度，接著移動 `left` 直到 `left` 指標指到跟 `right` 指向的同一種字元，並在移動途中把 `left` 指標指向的字元都從 Set 移除，記得 `left` 最後要再向前移動一格。 2. Unordered Map: 用 map 去存每個字元最後一次出現在 string 裡的 index， 3. integer array ### 5. Longest Palindromic Substring 這題太燒腦了，還沒寫出來，要達到 $O(n)$ 就要用 Manacher’s Algorithm，但這很難 還不錯的講解 Manacher’s Algorithm 的文章: - https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/ - https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-2/ ### 7. Reverse Integer 這題如果可以存 64 bit 的值就很簡單，但是題目說不能存 64 bit 的值 非常好解題影片: https://www.youtube.com/watch?v=HAgLH58IgJQ ### 11. Container With Most Water 這題想法很簡單，用頭尾指標指向頭跟尾，然後先計算一次目前高度能得到的面積，然後比較頭尾的高度，將比較矮的指標往前或往後移一格，再計算一次目前高度能得到的面積，直到兩個指標指向相同位置。 那如果兩個指標指向的高度一樣呢? 答案是不管是把左指標往右移還是把右指標往左移都沒有差，還是能算出正確答案，為什麼? 假設目前有4個高度，頭尾指標指向最左與最右的高度，然後最左與最右兩者的高度相同，這時會有考慮四種情況: 1. 第二個高度比最左矮，第三個高度比最右高 2. 第二個高度比最左高，第三個高度比最右矮 3. 兩者都比最左/最右高 4. 兩者都比最左/最右矮 去想一下，會發現不論你是先把最左往右移，還是最右往左移，最後答案都不變 ### 13. Roman to Integer 用 unordered_map 去保存每個字母對應的值，這樣存取數字很方便，剩下就照題目給的規則寫即可。 另一種解法是觀察目前字元是否比下一個數字小，目前字元比下一個字元小就減去目前字元，比較大就加上目前字元的值 https://leetcode.com/problems/roman-to-integer/solutions/5648531/c-soln-roman-to-integer/ ### 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/ ### 22. Generate Parentheses Backtracking 解法看: https://www.bilibili.com/video/BV1sy4y1q79M?t=1.5&p=65 ### 26. Remove Duplicates from Sorted Array 這題超簡單，但不知道為啥我卡超久... https://medium.com/@urdreamliu/26-%E5%9C%96%E8%A7%A3-remove-duplicates-from-sorted-array-cbee5b2d4df8 ### 27. Remove Elements 與 283 一樣的解法，還比 283 少一個結尾的 for loop ### 28. Find the Index of the First Occurrence in a String 此題就是找 `haystack` 裡是否有 `needle` 這個 substring，很簡單 ```cpp= int strStr(string haystack, string needle) { int needle_length = needle.size(); int haystack_length = haystack.size(); int index = 0; int i, j; i = j = 0; bool founded = false; while( index < haystack_length - needle_length + 1){ int j=0; int i=index; while( i < haystack_length && j < needle_length ){ if( haystack[i] == needle[j] ){ i++; j++; } else { break; } } if( j == needle_length ){ founded = true; break; } index++; } return (founded) ? index : -1; } ``` ### 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 要怎麼給值講得很清楚 ### 53. Maximum Subarray 有兩個解法: dp、Divide and Conquer、Kadane's Algorithm - dp - time complexity: $O(n)$ - space complexity: $O(n)$ - https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.md - DnC - time complexity: $O(n\ log(n))$ - space complexity: $O(log(n))$ - https://www.bilibili.com/video/BV1sy4y1q79M?t=0.8&p=63 - https://ithelp.ithome.com.tw/m/articles/10279762 ### 55. Jump Game 假設 `i` 為 index，則 `nums[i] + i` 為從 `i` 這個位置能跳到的最遠 index，先用一個變數 `current_max_jump` 去存目前能跳到的最跳 index，用一個 for loop 去遍歷 nums vector，for loop 的終止條件就是看 `i` 是否 <= `current_max_jump`，因為如果跳不到 `current_max_jump` 則 `current_max_jump` 後面的 index 也不可能跳到，在 loop 內就去比較 `current_max_jump` 與 `nums[i] + i`，看可不可以更新能跳的最遠距離，還要檢測 `current_max_jump` 是否 >= `nums.size() - 1`，如果大於等於則 return true，程式結尾 return false ### 62. Unique Path dp: https://www.bilibili.com/video/BV1sy4y1q79M?p=79 ### 66. Plus One 從 vector 的尾巴元素開使遍歷，如果該數字不是 9 就加一然後跳出迴圈，因為沒有進位，如果是 9 就將該數字改為 0 然後繼續下一個迴圈，因為有進位，迴圈結束後檢查 vector 的第一位是不是 0，因為如果不是 0 就代表沒有進位，如果是 0 就代表有進位，就要在 vector 的開頭 insert 一個 1。 ### 70. Climbing Stairs - dp: - 初始條件: dp[0] = 0, dp[1] = 1 - 轉換方程式: dp[i] = dp[i-1] + dp[i-2] - 終止條件: i > n ```cpp= int climbStairs(int n) { int dp[n+1]; dp[0] = 1; dp[1] = 1; for(int i=2; i<=n; i++){ dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; } ``` - 降低 space complexity 到 $O(1)$ ```cpp= int climbStairs(int n) { int before_2 = 1; int before_1 = 1; int current = 1; for(int i=2; i<=n; i++){ current = before_1 + before_2; before_2 = before_1; before_1 = current; } return current; } ``` ### 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 ### 78. Subsets 有三種解法: 擴展法、回朔法、DFS https://www.bilibili.com/video/BV1sy4y1q79M?t=0.9&p=66 影片中回朔法與 DFS 的解法其實很像，但我認為 dfs 好很多，回朔法有點多此一舉的感覺 還有第四種方法 bit manipulation ### 88. Merge Sorted Array 用 Two pointers 解，這題的重點就是從 vector 的尾巴開始比較，先比較兩者數字最大的數字，把數字比較大的放在 `nums1` 的最後面，然後一一往前比較，這樣就不需要額外複製 `nums1` 的數字。 ### 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; } ``` ### 102. Binary Tree Level Order Traversal 可以用 bfs 跟 dfs bfs 用兩層 while loop 跟 queue，不把 null pointer push 進 queue，用 queue size 知道某一層有幾個 node dfs 看影片吧 https://www.bilibili.com/video/BV1sy4y1q79M?t=573.7&p=71 ### 107. Binary Tree Level Order Traversal II 可以用 bfs 跟 dfs dfs 的方法就是用 102 的解法去解，然後把結果反轉 (reverse) 就是答案 bfs 的方法也是用 102 的解法去解，接著有三種做法 1. 第一是把結果反轉 (reverse) 就是答案 2. 第二是每次遍歷完一層裡所有 node，把結果插入要返回的 vector 的最前面，但是 insert 在 vector 的最前面要花 $O(n)$，所以可以先用 LinkedList 去存每層的結果，因為 insert 在 linked list 的最前面只要花 $O(1)$，最後再把 Linked List 轉乘 vector 回傳 3. 第三種是一開始就先 traverse 樹，計算出樹的深度 (h)，然後先在要返回的 vector 內 allocate 出 h 個 vector，這樣就不用插入，可以直接計算每層的結果在 vector 的 index，底下是用 recursion 的方式計算 height ```cpp= int height(TreeNode* a) { return (!a) ? 0: max(height(a->left),height(a->right))+1; } ``` https://www.bilibili.com/video/BV1sy4y1q79M?t=105.9&p=72 ### 121. Best Time to Buy and Sell Stock - dp: - 初始條件: dp[0] = 0 - 轉換方程式: dp[i] = max( dp[i-1], prices[i] - min_prices) - 終止條件: i = n ```cpp= int maxProfit(vector<int>& prices) { int min_price = prices[0]; int dp[prices.size()]; dp[0] = 0; for(int i=1; i<prices.size(); i++){ dp[i] = max(dp[i-1], prices[i] - min_price); min_price = min( min_price, prices[i] ); } return dp[prices.size()-1]; } ``` - Kadane's Algorithm: - 其實跟上面 dp 的方法一樣，只是改用一個變數 max_profit 去存現在可以得到的做高 profit，這樣就把 space complexity 改成: $O(1)$ ```cpp= int maxProfit(vector<int>& prices) { int min_price = prices[0]; int max_profit = 0; for(int i=1; i<prices.size(); i++){ max_profit = max(max_profit, prices[i] - min_price); min_price = min( min_price, prices[i] ); } return max_profit; } ``` ### 137. Signle Number https://leetcode.com/problems/single-number/solutions/1771720/c-easy-solutions-sorting-xor-maps-or-frequency-array/ 用 XOR 特性，天才，注意: (A\^A\^B) = (B\^A\^A) = (A\^B\^A) = B This shows that position doesn't matter. ### 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/ ### 200. Number of Islands 有三種解法，dfs、bfs、Union Find，dfs 用 recursion，bfs 用 while loop + queue，dfs 跟 bfs 都是透過將原本 grid 內的 '1' 改成 '0' 來確認陸地是否探索過 union fold 解法: https://www.bilibili.com/video/BV1sy4y1q79M?t=1329.1&p=69 ### 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 ### 221. Maximal Square 用 dp 解，這題跟本想不出來，https://anj910.medium.com/leetcode-221-maximal-square-%E4%B8%AD%E6%96%87-f0ec3c11b592 ### 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。 ::: ### 279. Perfect Squares 用 dp 解這題蠻 trick 的，解說: https://kevinchung0921.medium.com/leetcode-%E8%A7%A3%E9%A1%8C%E7%B4%80%E9%8C%84-279-perfect-squares-f81925868b41 - dp: - 初始條件: dp[0] = 0, dp[1] = 1 - 轉換方程式: dp[i] = min(dp[i], dp[i-jxj]+1) - 終止條件: i > n, j <= 0 ### 283. Move Zeros https://www.bilibili.com/video/BV1sy4y1q79M?t=2.1&p=8 ### 322. Coin Change 用 dp 解，注意要把 dp table 的 size 設為 amount+1，還要把裡面的元素初始成夠大的值，我是設 amount+1，https://medium.com/@cutesciuridae/dynamic-programming-%E6%B7%B1%E5%85%A5%E6%B7%BA%E5%87%BA-%E4%BB%A5coin-change%E7%82%BA%E4%BE%8B-4a4f3e7d98ea ### 344. Reverse String 很簡單，用 while loop 與對撞雙指標就好 遞迴寫法只是多寫一個遞回函式，然後將對撞雙指標以及 string reference 寫進遞回函式的參數，每次呼叫下一層遞回函式將對撞雙指標加一與減一即可，終止條件與 while loop 的寫法一樣，最後遞回函式不需要返回值 ### 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 ### 547. Number of Provinces 用 union find 解 ### 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 ### 725. Split Linked List in Parts 題目是要平均分配 node 數量，所以用除法分配數量，用餘數查看有剩下哪些 ```cpp= int average = length / k; int leftover = length % k; ``` 方法就是創建一個新 `vector`，然後把 head node 加進 vector 裡，用 `average` 跟 `leftover` 計算該 part 有幾個 node，接著根據該 part 的 node 數量 traverse list，讓 head node 指到該 part 的最後一個 node，接著把該 node 指向 null，把 head 改成 node->next，接著就跑下一個迴圈，注意每個 part 最多大於其他 part 一個 node。 ```cpp= for(int i=0; i<k; i++){ int n_of_nodes = (leftover > 0) ? average+1 : average; leftover--; v.push_back(head); while(n_of_nodes > 1 && head != nullptr){ head = head->next; n_of_nodes--; } if( head != nullptr ){ ListNode* temp = head->next; head->next = nullptr; head = temp; } } ``` ### 874. Walking Robot Simulation 先看這篇，有非常基本的概念 https://youtu.be/wpglWC6mnLg?si=FvLbHxiuiayDWDBY 在改變方向向量時有個非常好的方法就是用 `%` ```cpp= case -2: // left 90 degree d = (d+1) % 4; break; case -1: // right 90 degree d = (d+3) % 4; break; ``` 這題加速的重點就是在每次判斷新的位置時，如何快速的從 obstacles 合集找出是否有擋住的 obstacle 我的作法是用 pair stl 存每個 obstacles 的座標，然後用 set 去儲存每個 pair 元素 ```cpp= set<pair<int, int>> st; for(auto it: obstacles) st.insert({it[0], it[1]}); ``` 然後每次從 set 去找是否有該座標的 pair 存在在 set 裡 ```cpp= if( st.find({newX, newY}) != st.end() ){ break; } ``` 應該有更快的方法 ### 881. Boats to Save People 先對 array 做排序，排序好後用對撞雙指標從頭跟尾開始檢查，假如頭尾相加的體重不超過 limit，則頭尾指標都移動，如果超過 limit，則移動尾指標即可，因為只能載最重的人走，當頭指標大於尾指標時再離開迴圈即可 ### 933. Number of Recent Calls 用 queue 存 time stamp，從 queue 的頭開始檢查，超過 range 的 queue 元素就丟掉 ### 938. Range Sum of BST 可以用 DFS 與 BFS 解，dfs 就用遞迴，bfs 用 queue https://www.bilibili.com/video/BV1sy4y1q79M?t=5.0&p=68 ### 1217. Minimum Cost to Move Chips to The Same Position 很簡單與匪夷所思的一道簡單題 https://leetcode.jp/leetcode-1217-play-with-chips-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF%E5%88%86%E6%9E%90/ ### 1367. Linked List in Binary Tree 暴力解的解法: `isSubPath` 每次以某一個 node 為出發點，檢測從此 node 開始是否可以找出與 list 相等的 path，如果找不到，則從該 node 的左右 child 為出發點在去檢測是否有 path，`檢測從此 node 開始是否可以找出與 list 相等的 path` 這一段會用額外一個 `check` function 去寫，有找到則回傳 true，沒找到則回傳 false，`isSubPath` 就根據 `check` function 去判定是否要 return true。 有 recursive 的寫法跟 iterative 的寫法，第三種用 kmp 的寫法我不會，recursive 是將 `isSubPath` 與 `check` function 用遞迴的方式寫，iterative 則是用 stack + while loop 去取代遞迴的寫法 ### 1456. Maximum Number of Vowels in a Substring of Given Length 用最簡單的 sliding window 解就完事 ### 1945. Sum of Digits of String After Convert 由於 string 最大長度是 100，如果一開始直接把每個字元轉換成的數字串接在一起，則每個數字串接就會是 100 位，這樣不管是各種型別的變數都裝不下，由於 k 至少等於 1，所以可以在第一次遍歷整個字串時就計算此字元的數字總和，遍歷完字串後再執行 k-1 次 Sum of Digits 就可以。