[心得] Leetcode 刷題解答與 Python 3 小技巧分享
※ [本文轉錄自 Soft_Job 看板 #1W-eklPU ]
嗨，大家週末愉快！
不知道還記不記得之前小弟有分享面試 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！
--
感謝分享！
推
不明覺厲
推
推
看不懂還是給推
推
感謝分享
推神人
推
推
推分享
先推
推推
推
推
推神人！！！
推
推
神神神
推
推，感謝好心分享
推一個分享 謝謝！
看不懂XD但感謝分享
推！
好猛
推推
推，謝謝分享
先推再看
大好人啊~~~~~
推
推
推
推
推
推，好心分享
推好人
推推
感恩
排版超簡潔分明，這用心推爆
推
雖然我是硬體 但還是推
推推~
看不懂但推
推
推分享！
神
推 tips蠻有趣的
感謝分享 向你看齊
遠端考試 大家都會考很好推
上面留錯篇 不好意思造成困擾
推
推
太神了
雖然我廢物 但還是推
推
推
讚
只能推！！！
推
推
推
推
推
神篇 留言
推，感謝分享
推
推！！
推
推
推強者
推
推
推
PUSH
推
有看有推 謝謝大大
推
推
真棒的分享
推 謝謝分享
雖然我看不懂但還是要推 強者不吝分享
推
推
好文推
推
推推
推
長知識了 大推
一定要推感謝一下
推
大神推推
推！謝謝分享！
推
願樓主一生平安、上廁所有衛生紙、隨時有車可以上
謝謝 幫助很大
推
好心
好文推推
跪了
推大神 跪了
太神了，推！
推！
推!!
推分享，刷起來
推
好心！推！！
看不懂推
推用心
11
強強的
推
感謝您的分享
很有趣的學問
推！祝大大一生平安喜樂
推
好人!
推分享！
推
推
推 感謝分享
強
像是 for i, (a, b) in enumerate(paris): 就超級常
推推 最近剛好也在用python刷leetcode
pairs
感謝！完全沒發現打錯 XD
寫得真好
推
感謝分享
感謝分享！
推
先推
推推推~!
感謝分享
太用心了！推！
感謝大大
感謝大神
謝謝大神！
推，有空看
感謝分享!
有不錯的咖哩味
只能推惹
推
推，感謝分享
推，謝謝
推
推
推！
推！
哇賽 ，可以出書了。
太神啦
謝謝分享
推
推
推推
我愛你，但是8用xor應該較好
讚讚，又學到一招，討論區竟然沒看到有人用過 XD 我猜也有可能跟我只看 py 的文章有關
推
推
神
感謝
推神人
推
推，正在努力刷python3
強者 推！
真高手
推大神
推
sign跟xor有什麼關係？
推
推
感謝大神
推
推好心人
推一個說到做到
感謝分享，很實用！
朝聖
強！
感謝大大
負數第一位是1呀，所以 xor 後檢查是不是負數就知道
同號不同號
推推大大
感謝神人分享！
感謝分享
謝謝你的熱心分享～～
推
推，感謝分享
這個真的出書是可以賺錢的，要我就會花錢買
出書真的過譽了，在行家眼中這份解答可能有些地方還是坑坑洞洞的吧。 也請板友不吝告知內容有誤的地方，我會儘快更正！
佛心推推
推推
推一個 真強者！
感謝分享～
感謝強者分享!!
可惡 看不懂QQ
推
推
幹我真的過時了，資工出身裡面竟然有幾個名詞沒看
過..,
推
推
推分享
推
感謝分享
怒推
推
感謝
紅明顯 9 的複雜度是壞的，要小心使用
OMG 非常感謝您的提醒！差點就誤導大家了，真的非常抱歉。 剛才確認 sum(L, []) 的 intermediate list 是會一直重新 allocated 的， 確實不該使用，附上 stack overflow 的傳送門：
https://bit.ly/3rz8UqH建議的替代： 1. list comprehension: A = [ele for sub in arr for ele in sub] 2. itertools: A = list(itertools.chain.from_iterable(arr)) 3. reduce: A = functools.reduce(operator.iconcat, arr, []) 再次感謝 coquelicot 大大的指正！
※ 編輯: wheels (118.161.76.160 臺灣), 07/25/2021 04:14:23推大神分享
強
推呀 感謝大神 也想追隨大神的道路
推葵花寶典！
謝謝分享，祝平安健康，事業順遂
推
推
推
推
實在推
推
推一個
感謝分享
推
推
爆
[心得] COVID期間拿到Google/FB/微軟 Offer Part3如何準備面試和談薪水 上一篇我分享了我在 COVID-19 期間如何拿到 Google 、FB、Microsoft Offer 的經驗。 這篇我會講一下我是如何準備面試和如何談薪水。 面試 — Leetcode 我個人建議是千萬不要盲目的從第一題開始寫，因為每一題並不等價。有些題目是經典中![[心得] COVID期間拿到Google/FB/微軟 Offer Part3](https://img.youtube.com/vi/hnpzNAPiC0E/mqdefault.jpg "[心得] COVID期間拿到Google/FB/微軟 Offer Part3")
31
FB 美國 offer代post 基本資訊: 台灣的私立大學/年資 10+years 數年外商 Offer:27
Re: [討論] 我就問，刷題強者的實務表現?我親身經驗，刷題非常有用 347 top k frequent elements 23 merge k sorted lists 56 merge intervals 一些基本的工具如 recursion , tree , map , deque ，比較稍微難的像line sweep , biwise24
[請益] 面試白板考題目的時間複雜度剛剛編輯文章按到復原草稿 插入很多不必要東西 但用Pitt沒辦法編輯 所以刪除重po不好意思 以下代之前社團認識的學妹代po詢問![[請益] 面試白板考題目的時間複雜度](https://www.facebook.com/images/fb_icon_325x325.png "[請益] 面試白板考題目的時間複雜度")
20
Re: [討論] 演算法不強，還有辦法在資工混下去嗎？你好 是這樣的 在下也曾經迷失在Leetcode題海里 自己摸索了快半年 (= =) 才開始搞懂他的門路 摸索的過程中 還要搭配面試 最後才知道Leetcode到底在玩甚麼 其實最常考的 就是array/list/tree搭配BinarySearch/DFS/BFS 我敢說上面這六個東西佔據了線上測驗跟電話面試其中90%的題目18
Re: [請益] Leetcode找戰友噓 final01: 是想要吸經驗吧XD 05/26 22:51 → final01: 不燃網路那麼多資料還要找啥戰友 其實有差 而且差很多 雖然討論區有很多解答 甚至配合圖跟你解釋他的思路 但是很多人可能英文不夠好 所以看文章會很吃力11
[心得] 北美MLE找工經歷分享前言: 縱使每個人的求職經歷與感受，如人飲水，冷暖自知，但秉著取之於ptt，用之於ptt的精 神，分享一個北美CS博士班找工作的歷程。 背景: CS PhD in MLE@美國東岸大學![[心得] 北美MLE找工經歷分享](https://img.youtube.com/vi/uF1V2MqX2U0/mqdefault.jpg "[心得] 北美MLE找工經歷分享")
3
Re: [問卦] C++到底難學在哪裡因為螞蟻書比較像字典，不太像解釋程式為什麼要加這個變數，要加這幾行code 而語法的解釋也沒有從設計和需求出發，難以吸收... 然後很多C++書，基本上就是教你怎麼使用這個語言，而不是程式問題怎麼思考+拆解 所以大多也不是給沒學過程設的人讀的... 而我認為比較適合初學者的C++書籍如下:X
[問卦] 先有演算法 還是先有資料結構常見的資料結構有 堆疊（Stack）佇列（Queue）陣列（Array）連結串列（Linked List） 樹（Tree）圖（Graph）堆積（Heap）雜湊表（Hash table） 在一段程式的設計 先有考慮演算法? 還是先考慮資料結構?![[問卦] 先有演算法 還是先有資料結構](https://i.imgur.com/2VcNrNcb.jpg "[問卦] 先有演算法 還是先有資料結構")
1
Re: [問卦] leetcode medium看完答案還是寫不出來千萬不要背的 原則上科技巨頭會避開網路上找得到的題目 之前被問的問題隔了五個月後才出現在leetcode 上面 要先熟悉基本的資料結構 hash map, stack, tree, trie,