前言

這裡是我寫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，可以考慮使用 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也就是當前的節點上。
  • 相關題目：

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數量。
    • leetcode-198-House-Robber：不能連續偷兩間，找到最大的總和。max(這間不偷+偷上間, 這間偷+偷上上間)
    • leetcode-139-Word-Break：找到是否可以拆分成字典中的字，紀錄每個長度單字的最佳數量
    • leetcode-120-Triangle：找到最小的路徑和，從最底層往上找，每次都找到最佳的路徑和

常用演算法

摩爾投票法：找到最大宗

題目：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一定可以找到一張牌可以排出遞減的牌組

相關題目：