Zako's Blog

Leetcode 題型難度 & 投資報酬率 類型 學習難度 投資報酬率 Tree BFS 低 高 Linked List 低 高 Two Pointers 中 高 Tree DFS 中 高 Graph BFS 中 高 Hash 中 高 Graph DFS 中 中 Combinatorial DFS 中 中 Heap 中 中 Binary Search 中 中 Trie 中 中 Union Find 中 低 Greedy 高 低 Dynamic Programming 高 低 Divide and Conquer 高 低

模板左閉右開 選擇 [left, right) 左閉右開的原因 : 因為 while 判斷式為 left < right, 當跳出迴圈時, left == right, 不用考慮說是要返回 left 還是 right, 因為兩者相等 g(x) 為一 function, 找到一元素 m 滿足： x ≥ m 時, g(x) > 0, 也就是 g(x) = true x < m 時, g(x) ≤ 0, 也就是 g(x) = false ➔ 這樣做的用意是：找到一個臨界點 m, 能使區間 [m, ∞) 中的任意元素 x 皆滿足 g(x) > 0 且區間 (-∞, m) 中的任意元素 x 皆滿足 g(x) ≤ 0 簡易模板：704. Binary Search 除非是特殊情況, 不然不要在 while 中做任何 return 的動作, 這樣做很有可能導致出錯 為何 while 判斷式為 left < right ? 這種時候「考慮 edge case」就對了 e.g. nums = [1], target = 1 ➔ g(x) ...

模板void slidingWindow(const string& s){ int left = 0, right = 0; unordered_map<char, int> window; while (right < s.size()) { // 擴大窗口 winodw.add(s[right]); right++; // 判斷窗口是否要收縮 while (left < right && window needs shrink) { // 縮小窗口 winodw.remove(s[left]); left++; } }} 核心概念 先透過擴大窗口來找到一個「可行解」 然後透過縮小窗口來優化這個「可行解」，進而找到最優解 Tip 區間為左閉右開 [left, right), 因為若為左閉右閉, 則 w ...

套路一：基本 1 型（時間序列）觀念： 給一 sequence, 每個元素可以被視為一天, 且「今天」的狀態只取決於「昨天」的狀態 套路： 定義 dp[i][j] 代表第 i 輪的第 j 個狀態 想辦法將 dp[i][j] 與前一輪的狀態 dp[i - 1][j] 產生關聯 最終的結果是 dp[last][j] 中的某種 aggregation（min, max, sum…） 例題： 198. House Robber 213. House Robber II 121. Best Time to Buy and Sell Stock 123. Best Time to Buy and Sell Stock III 309. Best Time to Buy and Sell Stock with Cooldown 376. Wiggle Subsequence 256. Paint House 487. Max Consecutive Ones II 1186. Maximum Subarray Sum with One Deletion 903.Valid Permutation ...

核心概念 窮舉所有可能 透過「撤銷選擇」的方式回到上次做出選擇的分歧點 root，以繼續遍歷其他選擇 套路一：排列void dfs(選擇, 選擇列表){ if (滿足終止條件) { // 要處裡越界情況 res.add(路徑); return; } for (const auto& 選擇 : 選擇列表) { 做選擇; dfs(選擇, 選擇列表); 撤銷選擇; }} 經典例題 46. Permutations 51. N-Queens 47. Permutations II 77. Combinations 37. Sudoku Solver 79. Word Search 17. Letter Combinations of a Phone Number 131. Palindrome Partitioning 套路二：組合／子集寫法一：void dfs(選擇, 選擇列表){ if (滿足終止條件) & ...