leetcode-python

刷題清單：

https://docs.google.com/spreadsheets/d/1YhwajjbZDVFHxEZS3k9z-LbWwe2LK8x5XIaFThKZL9I/edit?usp=sharing

解題觀念：

Two Pointer

1. 同向 Two Pointer

• Pseudo Code:

  1. initialize two pointer: i = 0, j = 0 
  2. while j < len(arr):
       if need arr[j]:
         then we assign arr[i] = arr[j], i++, j++
       else: 
         j++

2. 反向 Two Pointer

• Pseudo Code:

  1. initialize two pointer: i = 0, j = len(arr) - 1
  2. while i <= j:
      decide what should do based on arr[i], arr[j]
      move at least one pointer

Binary Search

1. 針對排序好的區間做O(log(n))的搜尋。
2. 必須把握以下兩個原則：

• 每次都要縮減區域。
• 每次縮減不能排除可能的答案。

3. 分為精確搜尋和模糊搜尋：

• 找一個精確值：
  • 循環條件：l <= r
  • 縮減搜尋空間： l = mid + 1, r = mid - 1
• 找模糊值(某個數字出現的第一個位置 or 最後一個位置)：
  • 循環條件：l < r
  • 縮減搜尋空間： l = mid, r = mid - 1 or l = mid + 1, r = mid
• 找最接近某個數字：
  • 循環條件： l < r - 1
  • 縮減搜尋空間： l = mid, r = mid

Linked List

1. 通常用同向的 Tow Pointer 來解

• 一個快一個慢，距離隔開多少
• 兩個指針的移動速度

Recursion

1. Pseudo Code:

- Ask for subproblem result.
- Do something in current level or recursion.
- Return result

Tree BFS

1. BFS (寬度優先搜尋演算法): 是按照 '層' 的概念進行搜尋算法
2. 幾乎所有 BFS 題目都可以用 Queue 來記錄被展開的 TreeNode
3. Pseudo Code:

- Initialize Queue with tree root node.
- While Queue is not empty
  - for each node in the current queue
  - pull out the node
  - expand the node, push children to the Queue in order
  - increase level

Tree DFS

1. DFS (深度優先搜尋演算法): 是依照 Recursive 的概念進行搜尋算法，偏向於垂直的概念
2. DFS 分為三種:
   • Preorder Traversal

   def dfs(node):
      if node is None:
          return
      print(node.val)
      dfs(node.left)
      dfs(node.right)

   • Inorder Traversal

   def dfs(node):
      if node is None:
          return
      dfs(node.left)
      print(node.val)
      dfs(node.right)

   • Postorder Traversal

   def dfs(node):
      if node is None:
          return
      dfs(node.left)
      dfs(node.right)
      print(node.val)

3. Button Up DFS (建議從中間狀態構建思路):
   • 把值從下(subproblem)往上傳遞
   • 當前遞歸層利用subproblem 傳上來的計算當前層的新值並返回
   • 一定有返回值
   • Pseudo Code:

- Base Case
- 向子問題要答案(return value)
- 利用子問題的答案構建當前問題的答案
- 返回答案給父問題

5. Top Down DFS:

• 把值透過參數的形式往下傳遞
• top down dfs 一般來說不返回值
• Pseudo Code:

- Base Case
- 利用父問題傳下來的值做計算
- 把值傳給子問題做 recursion

Stack

1. Last in first out.
2. 適用於記住之前的狀態，必要的時候可以回到之前的狀態，或者利用之前的值
3. Monotone stack: 單調遞增或單調遞減
   • Pseudo Code:

   - Initialize stack
   - For each arr element backwards
   - Pop element until stack is empty or top of element > arr[i]
   - Push element to stack

Ref:

2020 前端工程師面試 準備與心得
[心得] COVID期間拿到Google FB 微軟 Offer
如何高效運用LeetCode | 我的secret spreadsheet
https://po-jen-lai.gitbook.io/coding-practice-advanced-topics/