前言

這裡是我寫Leetcode總結核心概念的地方，不同的情境會使用到的武器不同，這裡我會描述在什麼樣的情境滿足下，適合的資料結構或是演算法。而這個演算法的核心概念是什麼，同時我也會紀錄一些我在刷題時的心得，以及刷題的時間，來慢慢看到成長與進步。

Leetcode時間紀錄

Hash Table

情境1: 快速找元素

  • 通常使用 Hash 的關鍵在於要用 O(1) 的時間複雜度來查找元素，這樣就可以不用遍歷整個 list 從 O(n) 變成 O(1) 的時間內完成整個問題。
  • 相關題目：

情境2: 比對無序的東西

  • 如果要比對兩個無序的東西，像是兩個字串是否是 Anagram，這時候可以使用 Hash 來記錄每個字元出現的次數，然後比對兩個 Hash 是否相同。
  • 相關題目：

情境3: 找連續的不重複元素

  • 找連續的數字，核心關鍵就是指標的移動，如果想要確保時間複雜度為O(n)表示每個數字只會被遍歷一次，肯定要使用 Hash 的方式來找。
  • 題目有可能會搭配 sliding window，像是有的題目會要求從字串找出不重複的子字串，這時候就可以使用 Hash 來記錄出現過的元素，並且在遇到重複的元素時，可以快速的移動左指針。
  • 相關題目：

情境4:替換原本的node

  • 如果今天有需求把 old_node 變成 new_node 簡單來說就是建立一個一模一樣的 linked list，可以使用 HashTable 直接把 old_node 當作 key，new_node 當作 value。這樣不管是串 next 還是串 random 都只要拿 old_node 去找，就可以找到 new_node，然後開始串。
  • 相關題目：

Stack & Queue

情境1: 後進先出問題

  • 如果處理對稱性問題，像是括號匹配，先進後出的特性可以使用stack，{[()]} 可以觀察到 ( 是最後進去，但是也是第一個 pop 出來（LIFO）。
  • 在簡化路徑的題目中，會有很多 .. 這種代表往上一層的目錄，這時候也可以使用stack，把目錄放入stack，遇到 .. 就 pop 出來，因為當前的目錄已經不會再用到了。
  • 相關題目：

情境2: 數字計算，括弧的優先

  • 像是逆波蘭這樣的題目，關鍵就是當計算完後，要把結果再 push 回去 stack 裡面，這樣下次遇到運算符號時，才可以再次的把上一次的計算結果一起pop出來。
  • 或是要處理括號優先計算的問題，如果當前的 ( 還沒結果就碰到新的(，我們可以把計算到一半的數值 push 進 stack，等到出現 ) 再把結果 pop 出來，進行計算。
  • 相關題目：

情境3: 時間複雜度O(1)卻能取得Max或Min

  • 如果要設計一個 Stack 的資料結構，可以取得最小值的 stack getMin()，並且getMin()要求時間複雜度為 O(1)。這樣的設計最大的困難在於，pop 或 add 時， min 也要有所更新。因此，我們可以另外建立一個 min_stack 凡是碰到更小的就塞進去，這樣就可以在 pop 的時候，一起把 min_stack 也 pop，以取得第二小的值。
  • 相關題目：

Linked List

情境1: 判斷是否有循環

  • 可以使用兩個pointer，一個走比較快，一個走比較慢，如果有循環，兩個pointer一定會相遇。
  • 相關題目：

情境2: dummy head 的使用

  • 如果題目需要碰到多個 listNode 的操作，並且把兩個 ListNode 進行整合，變成一個新的 ListNode導致原本的head不是原本的head時，可以考慮使用 dummy_head，最後回傳的時後回傳 dummy_node.next 這樣就不用特別處理第一個node。
  • 我們最怕的是在取listNode的值時發現他是None而導致錯誤，因此我們可以使用 digit1 = list1.val if list1 else 極值 的方式，儘管遇到 none 仍然可以繼續執行迴圈，直到兩個 list1 跟 list2 都觸底，以避免 None 的問題。
  • 相關題目：

情境3: 雙指針法

  • 反轉操作：
    • 如果今天要空間複雜度為O(1)的情況下，想要透過反轉的方式做某些操作，例如反轉linked list，或是取得倒數第n個node，這時候就可以使用雙指針法。只是怎麼跑這個指針的方式不一樣，一種是某個指針一直往前跑，然後到目標位置執行操作。另一個是比速度的，要快的指針比慢的指針快n個位置，以取得倒數第n個node。
    • 這真的經典，今天要有順序的進行反轉或是整批的改變位置移動，雙指針會是一個Linked List的重點。想像有兩個指針，一個指針cur慢往前，另一個指針會是目標節點target (在這裡是next)，target 會串到想要放的目標 location(在這裡是pre.next)，cur 會一直往前移動(cur.next 變成 pre.next)，直到達到目標節點，這樣就可以完成操作。
  • 依序比較：
    • 如果只是在有序的linkedlist中比較隔壁的元素關係使用1個pointer以比較鄰居就好，另一個pointer放previous的訊息，到時候滿足條件時，就要把pre.next串到 cur 或 cur.next也就是當前的節點上。
  • 相關題目：

情境4: 排序

  • 如果今天碰到比 x 小的節點都放在前面，比 x 大的節點都放在後面，這時候可以使用兩個linked list，一個是小於 x 的 linked list，一個是大於等於 x 的 linked list，最後再將兩個linked list合併即可。
  • 相關題目：

情境2: 環繞節點

  • 如果今天要回傳經歷過k次循環的linked list，這時候可以直接去思考最後的樣子長如何，當k是linked list的長度的倍數時，linked list會回到原本的樣子，因此我們可以先計算出linked list的長度，然後取餘數，這樣就可以得到我們要旋轉的步數。最後 len - k - 1這個節點的next是最後一個節點。
  • 相關題目：

Recursion

回到核心，我們應該要知道最小問題的狀況是什麼，以及小問題與大問題相同的關聯性，這個關聯性就是要回傳的答案，裡面不確定的東西可以先假設已經得知，通常這個假設就是呼叫Recursion的地方，舉例來說：
樹的左右子樹關係

Binary Tree

情境1: 空間O(1)做成list

  • 要非常熟悉DFS的演算法，同時如果要求O(1)的空間複雜度，可以使用Morris Traversal，這樣可以在O(1)的空間複雜度下完成整個遍歷，只是他會改變樹的結構。
  • 相關題目：

情境2: DFS 走到樹的最深處

  • 從底往上找到某個節點：例如要在BST(二元搜尋樹)找到第k小的節點，我們需要先走到最left的節點，然後開始往上爬並計數是否已經達到k了。這時候我們的程式邏輯應該是 inorder: 走到左最底 > 計數(中間) > 換右邊。或是我們要找最小值，這時候他們都有個共通點，為了不要遍歷所有的inorder節點，我們應該先使用recursion(cur.left)到最底，往下的過程要做紀錄stack.append(cur)，但是每次從cur = stack.pop()的時候，也要考慮到cur.right有沒有滿足條件。
  • 共同的祖先節點：給p,q兩個節點，找到他們最近的共同parent。我們從也是從底下往上，當發現當前節點左右子樹同時存在q或p時，就代表當前節點就是parent，如果只有一邊的子樹找到，那就回傳最先碰到的節點，也就是說p或q就是祖先，只是看誰比較高。
  • inorder, postorder, preorder特性：有些題目會給你任意一種order，請你組出一個binary tree，這時候就要非常熟悉inorder, postorder, preorder的特性，inorder是左中右，postorder是左右中，preorder是中左右，這樣就可以很快的組出一個binary tree。

情境2: BFS - level order

  • 水平操作：如果有題目要把node指向隔壁的時候，就要想到BFS。
  • 取得每層的特定節點：如果需要取得每層最右邊的節點，優先走右邊，並且把最右邊的節點記錄，如果發現右邊已經觸底了，那就換左樹走，但是只有當高度比右樹高時，才要記錄。

Dynamaic Programming

我覺得大部分DP問題，他的重點順序是：Recursive -> Recursive + Memo -> Iterative + Tabular -> Iterative + Tabular + Space Optimized，因此很多時候我認為需要進展到Iterative的狀態，才能說是完美的解完一題DP問題。大概會有以下情境：

情境1: 當前『取』和『不取』的問題

  • 從最小到最大找到最佳解：會建議先從背包最小的開始找，然後慢慢增加背包的大小，這樣可以確保每個背包的解都是最佳解。常見題目以下都是需要考量到前一個的最佳解+是否要取目前的值，更簡單的就是說Take與Not_Take的問題：
    • leetcode-322-Coin-Change：找到最少的硬幣數量可以湊成目標值，雙層for loop，從1開始找到amount，然後每個amount都找到最佳的配置coin數量。dp[amount] 標示目前 amount 的最佳數量。透過比較min(dp[i], dp[i-cur] + 1) 來更新最佳解，比較若是取了當前的coindp[i-cur]+1會不會更新最佳解？
    • leetcode-198-House-Robber：不能連續偷兩間，找到最大的總和。max(這間不偷+偷上間, 這間偷+偷上上間)，dp[i]表示偷到第i間的最大總和。
    • leetcode-139-Word-Break：找到是否可以拆分成字典中的字，紀錄每個長度單字的最佳數量，dp[i+len(w)]為True的條件是dp[i]為True表示前面s[:i]是可比拆分，且s[i:i+len(w)]有包含w時，表示當前的字串可以被拆分。
    • leetcode-120-Triangle：找到最小的路徑和，從最底層往上找，每次都找到最佳的路徑和
    • leetcode-123-124-Best-Time-to-Buy-and-Sell-Stock: 在 k 次的交易中，找出買故掉和賣掉股票的最佳時機點，可以攥到最多的錢。他也是一個Take與Not_Take的問題，只是他有兩個狀態，一個是buy，一個是sell。
      • do_action = (sell if have_stack else prices[idx]) + helper(idx+1, not have_stack, count) 表示賣掉當前的股票
      • not_do_action = helper(idx+1, have_stack, count) 什麼都不做
      • min(dp[i][0], p - dp[i-1][1]) 表示當前最希望的成本，dp[i][0]表示當前的最佳成本，p - dp[i-1][1]表示當前的價格減去上一次的賣掉的所賺到的利潤。
    • leetcode-300-Longest-Increasing-Subsequence: 給定一個整數數組 nums，找到一個最長的遞增子序列的長度。也因此，我們總是要考慮是否要拿當前的值，來找到最長的遞增子序列。但最重要的可以使用Patience Sort去解。
      • 取：1 + helper(cur, i+1)
      • 不取：helper(last, i+1)
      • max(take, not_take)

情境2: 走地圖

  • 找到最佳路徑，又或是找到最大的正方形在一個matrix裡面找到最佳解的題目也是DP，通常從左下角或是右上角開始思考，並且挑選要從左下角或是右上角開始時，要記得選擇周邊的 cell 必須是已經計算過的，這樣才能透過小問題解決大問題。
  • 相關題目
    • leetcode-221-Maximal-Square: 從左下角或是右上角開始思考，然後找出規律，dp[i][j]表示走到i,j的最佳解，並且挑選要從左下角或是右上角開始時，要記得選擇周邊的 cell 必須是已經計算過的，這樣才能透過小問題解決大問題。dp[1][j] = 1 + min(dp[0][j], dp[0][j-1], dp[1][j-1])是邊長的最佳解。
    • leetcode-72-Edit-Distance: 兩個單詞 word1 和 word2，找到將 word1 轉換為 word2 所需的最小操作數，也有走地圖的感覺，需要把整個Table繪製出來。
    • leetcode-63-Unique-Paths-II/: 找到最短路徑，但是中間可能會有石頭。因此碰到障礙物就要記得把路徑設定為 0，其他的就是從上面或是左邊來的路徑和
    • leetcode-64-Minimum-Path-Sum: 也是從左上角到右下角，找到最小的路徑和，這時候只要考慮上面或是左邊的路徑和即可。

情境3: 回文字串

  • leetcode-5-Longest-Palindromic-Substring: 找到最長的回文字串，如果我們鎖定一個中心點，然後往外擴展，當發現不是回文時，就立刻換下一個中心點，但是要記得考慮奇數偶數的問題。

Two Pointer

情境1: Sliding Window

  • 我們要先知道 Sliding Window 的三個關鍵步驟：
    • Expand out Window 擴展窗口的時機
    • Meet the condition and process the window 滿足條件並處理當前窗口的方式
    • Shrink the window 收縮窗口的時機

情境2: 已經排序的陣列

  • 如果一個陣列已經排序，我們要從陣列中找出滿足條件的兩個數字，這時候可以使用兩個指標，一個指向頭，一個指向尾，然後根據條件來移動指標。當兩個指標向中間移動時，我們可以確保指標外的數字絕對不會是答案，因為他是已經排序的陣列！
  • 相關題目：
    • leetcode-167-two-sum-ii-input-array-is-sorted
    • leetcode-11-container-with-most-water 儘管高度無序，但是距離是有序的，決定是否要移動 pointer 時，只要考慮高度即可，height[left] < height[right]，那麼我們就移動 left pointer，因為 height[left] 是最小的，所以我們要找更大的 height。移動的過程中透過max_area來紀錄最大的面積。
    • leetcode-15-3sum 這題是要找到三個數字相加等於0，這時候可以先固定一個數字，然後使用兩個指標來找另外兩個數字，這樣就可以把三個數字的問題轉換成兩個數字的問題。

情境3: 子字串問題

  • 如果今天題目是要從字串中找到一個子字串，這時候可以使用兩個指標，一個指向子字串，一個指向母字串，然後根據條件來移動指標。
  • 相關題目：
    • leetcode-392-is-subsequence：i是子字串j是母字串，起點相同，如果發現i的字元等於j的字元，就把i往前移動，最後如果i走到底，就代表是子字串。
    • leetcode-209-minimum-size-subarray-sum：找到最短的子字串，使得子字串的和大於等於目標值，他是 two pointer 從左到右來擴展跟收縮 window，要檢查到 right pointer 觸底為止，所以不需要 while。
      • 停止擴展？ window sum >= target 時
      • 處理當前window? 計算當前 window 的總和數，以及當前 window 的長度是否有小於最小長度
      • 收縮window? 當前 window sum >= target，就開始透過移動 left 收縮 window
      • 隨時記錄最佳解？min_len 來記錄最佳解
    • leetcode-30-substring-with-concatenation-of-all-words：這題很難，提供words與s找出s中所有words的連續子串的起始索引。透過移動i來擴展window。
      • 停止擴展？ 當前的 window 不合法，也就是 i 是不合法的，我們要往下一個開始檢查
      • 處理當前window? 當前 window 是合法的，我們要檢查是否已經找到所有的 words 且數量沒超過
      • 收縮window? 當前的window還在合法範圍，只是數量不夠繼續擴張

常用演算法

摩爾投票法：找到最大宗

題目：leetcode-169-majority-element
使用情境：如果想要知道最大宗是哪一類的，這樣可以在空間複雜度為O(1)的情境下，找到最大宗的族群。

這是1980 由 Boyer 和 Moore 兩人所提出的算法：英文是 Boyer-Moore Majority Vote Algorithm。這個函數實現了 Boyer-Moore 多數投票算法，這是一種在線性時間和常數空間內找到多數元素的方法。

他的思想很簡單，假設存在一個數字超過半數，而每個數字代表一個生物組群好了。(e.g. 1 = 恐龍, 2 = 獅子, 3 = 老虎, …) 現在有一組串列，[1, 1, 2, 3, 1] 透過指標的方式，循序比較，遇到自己人就+1，遇到其他物種就開打，因為戰鬥力一樣所以雙方人馬都一起滅絕，經過物競天擇後，數量仍然 > 1的就是倖存者也就是數量最多的族群。

1
2
3
4
5
6
7
8
def majorityElement(nums):
    count = 0
    candidate = None
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    return candidate

Morris Traversal：BST to 遞增排序

這是一種在O(1)的空間複雜度下完成遍歷的演算法，他的核心概念是在遍歷的過程中，把右子樹的最左邊節點指向當前的節點，這樣就可以在O(1)的空間複雜度下完成遍歷。
很多時候題目會要求 O(1) 空間複雜度，這時候我們可以使用 Morris Traversal 來達成，但是此方法直接修改原始樹，但可以保證空間複雜度為 O(1)，因此使用的時候要注意是否可以改動到原始樹。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
    1
   / \
  2   5
 / \   \
3   4   6

// 將 1 的 left sub-tree 插入 right sub-tree 的地方
    1
     \
      2         5
     / \         \
    3   4         6        

// 將原本的right sub-tree 接到 left sub-tree 的最右邊節點
    1
     \
      2          
     / \          
    3   4  
         \
          5
           \
            6

 // 將 2 的 left sub-tree 插入 right sub-tree 的地方
    1
     \
      2          
       \          
        3       4  
                 \
                  5
                   \
                    6   

 // 將原本的 right sub-tree 接到 left sub-tree 的最右邊節點
    1
     \
      2          
       \          
        3      
         \
          4  
           \
            5
             \
              6         

......

程式碼 preorder-morris-traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def flatten2(self, root: Optional[TreeNode]) -> TreeNode:
    cur = root
    while cur:
        if cur.left:
            # 1. 先找到左樹最右邊的node rightmost
            rightmost = cur.left
            while rightmost.right:
                rightmost = rightmost.right

            # 2. 把 cur 的右樹接到 rightmost.right, 然後再把 cur.right 接到 left
            rightmost.right = cur.right
            cur.right = cur.left
            cur.left = None

        # 3. cur 換成 cur.right
        cur = cur.right

DFS 跟 BFS

DFS 跟 BFS 是最常見的兩種遍歷方式，DFS 是深度優先搜尋，BFS 是廣度優先搜尋，他們的核心概念是一樣的，只是遍歷的方式不同，DFS 是一直往下走，直到底部，然後再往上走，BFS 是一層一層的往下走，直到底部，然後再往下走。

建議直接看LeetCode 課前預習 - 掌握 BFS 與 DFS 指南

Patience Sort：最長的遞增子序列

有些題目需要找到最長的遞增子序列，我們需要先了解一下一個超級神奇的演算法！叫做Patience Sort，他是一個卡牌遊戲，可以幫助我們找到最長的遞增子序列。我們先來介紹卡牌遊戲的規則：

首先，我們有一組卡牌，規則是：

  • 如果當前的卡牌比piles的最後一張卡牌還要大，那就直接放到最後一張卡牌的後面
  • 如果當前的卡牌比piles的最後一張卡牌還要小，那就要找到一張比當前卡牌還要大的卡牌，然後放在上面，如果找不到的話，就要開一個新的pile

最後你會發現，每個piles最上面的卡牌由左到右是遞增的

更神奇的事情發生了，這個piles的數量就是最長的遞增子序列的長度！因為每個piles一定可以找到一張牌可以排出遞減的牌組

相關題目：