[心得] Leetcode 刷題解答與 Python 3 小技巧分享
嗨，大家週末愉快！
不知道還記不記得之前小弟有分享面試 Google TW SWE 的心得，
最後有提到小弟當初有發願，如果順利進去要把過去寫過題目留存的解答整理分享出來，
最近終於施工完了，提供給有需要的人可以自由取用。
這份解答內涵蓋了 781 題的 Python 3 解法（太早期刷的題目就沒留解法了 QQ），
寫這些解答的目的是為了還願並且回饋給還在努力的板友，
唯一的使用限制就是請不要拿來作商業用途，讓知識無償分享出去，感謝大家。
https://www.notion.so/lenchen/LeetCode-47d625b874894484af7c055b024b9817
內容主要分成四大類，
1. 資料結構
主題涵蓋常用於 Leetcode 內解題的資料結構，
較常見的：Array/String, Matrix, Linked List, HashSet/Map, Stack, Queue, Heap
較高階的：DSU, Trie, BIT
還有偶爾會用到 Deque 跟 sortedcontainers，但數量比較少就沒特別分類。
2. 演算法
這邊其實是我自己的歸類，不一定只有這些 XD
內容涵蓋有：
greedy, multiple pointers, sliding window, sort, DFS/BFS, backtracking,
sweep line, rolling sum, binary search, dynamic programming, minimax
有趣的是這邊沒列 divide and conquer 這個經典分類，
因為好像幾乎沒遇到過哪題是只能使用 divide and conquer 解的，
所以就沒有讓它自成一個分類了。
但若有題目也可以用 divide and conquer 解的話，
我也有寫下來，所以還是可以再自行了解下。
3. 圖
圖相關的問題因為太經典所以自成一個主題，
整理了我所遇到的常見圖論演算法，還有 topological sort 的兩種方式，
最重要的是 tree 相關的分類也包含在這一部分內。
4. 其他
數學、隨機、位元操作相關的題目都會在這裡。
大致上就分這四個部分，每個解答底下都有一行字總結這題的解題概念，
因為跨越了兩年半所以 coding style 可能也有些不一樣，
但保證其中 99% 的內容都是我親手一個個字元打出來的，
希望能幫助到有需要的人 :)
另外順便再分享一些我覺得使用 Python 3 刷題時可以用的一些小技巧，
可以讓你的 code 變得更精簡，大家可以看看然後挑自己喜歡的來使用：
1. 用 next 搭配 generator comprehension 來獲取第一個滿足條件的元素，
像是 next(ele for ele in arr if ele > 0)，就可以拿到 arr 中的第一個正數。
2. 解對稱性題目時，可以把引數調換 call 一次，減少重複的 code，像是：
def foo(a, b):
if a > b: return foo(b, a)
...
就可以讓你接下來維持在 a <= b 的前提下繼續寫 code，或者直接 swap 引數也可以：
def foo(a, b):
if a > b: a, b = b, a
...
3. python dict 可以使用 tuple 作 multikey，像是 d[k1, k2, k3]，
如此一來就不用巢狀 dict 了（d[k1][k2][k3]）
4. 可以使用 unpacking 來抽取出需要的參數，像是：
A = [1, 2, 3, 4, 5]
foo, *B, bar = A
可以得到 foo == 1, B == [2, 3, 4], bar == 5
另外還可以用巢狀 unpacking，
像是 for i, (a, b) in enumerate(pairs): 就超級常用。
5. Python 3.8 跟 3.9 有多了一些不錯的東西，
像是 3.8 的 assignment expression(:=) 跟 3.9 的 dict shallow merge(|)
都有機會可以讓 code 更精簡。
6. 有些 matrix 或是 grid 的題目，兩個 dimension 長度有可能為 0，
可以用 if not any(matrix): return xxx 來處理（感謝 Stefan Pochmann）
7. in 也會消費 iterator，
所以如果想知道某個 str s2 是不是另一個 str s1 的 subsequence 可以這麼做，
I = iter(s1)
return all(c in I for c in s2)
（再次感謝 Stefan Pochmann）
8. 想要測兩個數是不是同正負可以用 (a > 0) is (b > 0)，記得事先檢查 0
板友提供 (credit to @pig2014)： a ^ b > 0 更好
9. 想要攤平巢狀 list 可以用 sum(L, []) <- 不建議！途中 list 會一直重新 alloc
(credit to @coquelicot)
參考 stack overflow：https://bit.ly/3rz8UqH
建議的替代：
9.1. list comprehension: A = [ele for sub in arr for ele in sub]
9.2. itertools: A = list(itertools.chain.from_iterable(arr))
9.3. reduce: A = functools.reduce(operator.iconcat, arr, [])
10. 某些要提供 factory function 的地方，可以遞迴給自己，像是：
trie = lambda: collections.defaultdict(trie)
11. itemgetter 在某些需要 key 的 builtin function 很好用，像是：
sorted(A, key=itemgetter(1))，等同於寫 key=lambda x: x[1]
12. 因為 Python list 提供 negative indexing，
在某些情況可以用 ~i 來獲得對應於 i 的反向 indexing，像是：
for i in range(len(A)):
A[i] += xxx # A[0], A[1], A[2] , ...
A[~i] += ooo # A[-1], A[-2], A[-3], ...
大概就是這些東西了吧，這些技巧有些人喜歡有些人不喜歡，
我覺得沒有對錯啦，就挑自己覺得不錯的用吧 XD
happy coding！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.161.76.160 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1627032495.A.65E.html
推
07/23 17:37,
2年前
, 1F
07/23 17:37, 1F
推
07/23 17:38,
2年前
, 2F
07/23 17:38, 2F
推
07/23 17:44,
2年前
, 3F
07/23 17:44, 3F
推
07/23 17:51,
2年前
, 4F
07/23 17:51, 4F
推
07/23 17:54,
2年前
, 5F
07/23 17:54, 5F
推
07/23 17:58,
2年前
, 6F
07/23 17:58, 6F
推
07/23 18:07,
2年前
, 7F
07/23 18:07, 7F
推
07/23 18:11,
2年前
, 8F
07/23 18:11, 8F
推
07/23 18:14,
2年前
, 9F
07/23 18:14, 9F
推
07/23 18:18,
2年前
, 10F
07/23 18:18, 10F
推
07/23 18:23,
2年前
, 11F
07/23 18:23, 11F
推
07/23 18:26,
2年前
, 12F
07/23 18:26, 12F
推
07/23 18:29,
2年前
, 13F
07/23 18:29, 13F
推
07/23 18:51,
2年前
, 14F
07/23 18:51, 14F
推
07/23 18:53,
2年前
, 15F
07/23 18:53, 15F
推
07/23 18:57,
2年前
, 16F
07/23 18:57, 16F
推
07/23 18:57,
2年前
, 17F
07/23 18:57, 17F
推
07/23 19:07,
2年前
, 18F
07/23 19:07, 18F
推
07/23 19:10,
2年前
, 19F
07/23 19:10, 19F
→
07/23 19:10,
2年前
, 20F
07/23 19:10, 20F
推
07/23 19:13,
2年前
, 21F
07/23 19:13, 21F
推
07/23 19:25,
2年前
, 22F
07/23 19:25, 22F
推
07/23 19:27,
2年前
, 23F
07/23 19:27, 23F
推
07/23 19:33,
2年前
, 24F
07/23 19:33, 24F
推
07/23 19:35,
2年前
, 25F
07/23 19:35, 25F
推
07/23 19:36,
2年前
, 26F
07/23 19:36, 26F
推
07/23 19:41,
2年前
, 27F
07/23 19:41, 27F
推
07/23 19:56,
2年前
, 28F
07/23 19:56, 28F
→
07/23 19:57,
2年前
, 29F
07/23 19:57, 29F
推
07/23 19:58,
2年前
, 30F
07/23 19:58, 30F
推
07/23 19:59,
2年前
, 31F
07/23 19:59, 31F
推
07/23 20:00,
2年前
, 32F
07/23 20:00, 32F
推
07/23 20:01,
2年前
, 33F
07/23 20:01, 33F
推
07/23 20:03,
2年前
, 34F
07/23 20:03, 34F
推
07/23 20:14,
2年前
, 35F
07/23 20:14, 35F
推
07/23 20:14,
2年前
, 36F
07/23 20:14, 36F
推
07/23 20:20,
2年前
, 37F
07/23 20:20, 37F
推
07/23 20:30,
2年前
, 38F
07/23 20:30, 38F
推
07/23 20:34,
2年前
, 39F
07/23 20:34, 39F
還有 117 則推文
還有 4 段內文
推
07/25 20:26,
2年前
, 157F
07/25 20:26, 157F
推
07/25 20:36,
2年前
, 158F
07/25 20:36, 158F
推
07/25 20:41,
2年前
, 159F
07/25 20:41, 159F
推
07/25 21:44,
2年前
, 160F
07/25 21:44, 160F
推
07/25 22:41,
2年前
, 161F
07/25 22:41, 161F
推
07/25 22:49,
2年前
, 162F
07/25 22:49, 162F
推
07/25 23:01,
2年前
, 163F
07/25 23:01, 163F
推
07/25 23:19,
2年前
, 164F
07/25 23:19, 164F
推
07/26 00:06,
2年前
, 165F
07/26 00:06, 165F
推
07/26 00:09,
2年前
, 166F
07/26 00:09, 166F
→
07/26 00:13,
2年前
, 167F
07/26 00:13, 167F
推
07/26 00:28,
2年前
, 168F
07/26 00:28, 168F
推
07/26 00:31,
2年前
, 169F
07/26 00:31, 169F
推
07/26 02:54,
2年前
, 170F
07/26 02:54, 170F
推
07/26 04:03,
2年前
, 171F
07/26 04:03, 171F
推
07/26 07:47,
2年前
, 172F
07/26 07:47, 172F
推
07/26 09:27,
2年前
, 173F
07/26 09:27, 173F
推
07/26 12:22,
2年前
, 174F
07/26 12:22, 174F
推
07/26 13:52,
2年前
, 175F
07/26 13:52, 175F
推
07/26 15:06,
2年前
, 176F
07/26 15:06, 176F
推
07/26 16:09,
2年前
, 177F
07/26 16:09, 177F
推
07/26 22:59,
2年前
, 178F
07/26 22:59, 178F
→
07/26 23:40,
2年前
, 179F
07/26 23:40, 179F
→
07/26 23:40,
2年前
, 180F
07/26 23:40, 180F
→
07/26 23:40,
2年前
, 181F
07/26 23:40, 181F
→
07/26 23:41,
2年前
, 182F
07/26 23:41, 182F
推
07/28 00:18,
2年前
, 183F
07/28 00:18, 183F
→
07/28 16:02,
2年前
, 184F
07/28 16:02, 184F
推
07/28 19:01,
2年前
, 185F
07/28 19:01, 185F
推
07/29 23:39,
2年前
, 186F
07/29 23:39, 186F
推
07/30 00:40,
2年前
, 187F
07/30 00:40, 187F
推
07/30 12:22,
2年前
, 188F
07/30 12:22, 188F
推
08/01 11:14,
2年前
, 189F
08/01 11:14, 189F
推
08/03 02:57,
2年前
, 190F
08/03 02:57, 190F
推
08/03 16:13,
2年前
, 191F
08/03 16:13, 191F
推
08/03 19:10,
2年前
, 192F
08/03 19:10, 192F
推
08/03 23:06,
2年前
, 193F
08/03 23:06, 193F
推
08/04 22:43,
2年前
, 194F
08/04 22:43, 194F
推
08/05 23:08,
2年前
, 195F
08/05 23:08, 195F
推
08/07 18:18,
2年前
, 196F
08/07 18:18, 196F