Copy of 1~20 | Notion

Two Sum
- 題目思維：用Dict
- Tricks
  - 用Key存 target-num[index]
  - 用value存index
  - 用下一個數當key比對dict看有沒有存在東西
    - idx = num[next_idx]
    - if dict[idx]: return next_idx, dict[idx]
Add Two Numbers
- 題目思維
  - 用Linked List
- Tricks
  - answer = output = ListNode()
    - 因為loop output.next 時沒辦法回到開頭
    - 這時return answer.next就會指到output的第一個開始數
  - 用extra variable累積所有的數，就不用另外設兩個變數儲存l1.val, l2.val
    - extra += l1.val
    - extra += l2.val
  - 記得while l1 or l2 OR EXTRA，極端進位問題
  - l1 l2 要分別if判斷有沒有存在
Longest Substring Without Repeating Characters
- 題目思維：
  - 滑動窗口
- Tricks
  - 搭配 for最快 O(n)
    - 照原本的左右指針移動，右指針到每個字符若有重複的話，需一個一個縮減左指針
    - 會略大於O(n)
    - 記得條件 dict_[ch]>=l 才不會讓左指針又回頭
- edge case
  - 最棘手的是連續幾個字元一樣的情況
    - 解法：l = dict[ch]+1
  - edge case
    - ""
Longest Palindromic Substring

Tricks
- 測單數、測偶數不能寫if else，不然就會miss "ccc"這種狀況
- while條件要有等號l≥0 and r≤length-1，不然最左右兩個字會沒有比對結果
- 出while以後要把l, r縮回一格 ⇒ 可以直接放在return裡
- 還是要一格一格找，不然會miss aaaaa
- 速度
  - 把while裡面的if條件合併到while條件
  - while > for enumerate > for range
  - return l, r > return str
edge case
- a
- ac
- ccc
- cbbd
- aaaaa

Container With Most Water

反向指針O(n)
- 從最寬的左右兩側開始
- 決定面積的是高比較小的那個
- 高比較小的那個往內縮（如果移動高比較大的那個，面積只會越來越小）
Trick
- while i<j 改成 for w in range(j, 0, -1)
  - for 一但宣告了就算修改j 也不會影響w原本預設的過程值，省下一個變數width
  - 用w取代省去j-i的運算

3Sum

O(N^3) ⇒ O(N^2)
- 先sort list
- 第一指針i先定位，由左至右
- 如果sum <0 就移動第二指針（左指針）向右，反之第三向左
- j < k
Trick
- sum = 0 時不能就break，不然可能會miss j+1, k-1的sum也等於0的情況
- 注意如何handle重複的情況
  - 用判斷
  - 用set，但比判斷慢很多
    - set不能add list
    - 因為list是mutable, 不能hash
    - 改成tuple

Letter Combinations of a Phone Number

bfs: Queue FIFO O(4^N) or O(4^N*N)
- queue比普通for 快
- Trick
  - 持續從queue pop到什麼時候停？直到queue所有元素其長度都超過現在應該有的 while len(res[0]) == i:
dfs:
- base case
  - if len == 0: reutrn []
  - if len == 1: return list(mapping[])
Trick
- res要先有一個[""]

Remove Nth Node From End of List

Fast Slow ptr 其實比較快
- Trick
  - fast跑完迴圈以後的while條件要注意 while fast.next not while fast 否則會差一個
  - fast跑完迴圈以後要檢查是不是已經到了結尾，不然fast.next會出錯，如果到了結尾代表n == size
DFS