[心得] 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！ -- 感謝！完全沒發現打錯 XD 讚讚，又學到一招，討論區竟然沒看到有人用過 XD 我猜也有可能跟我只看 py 的文章有關 出書真的過譽了，在行家眼中這份解答可能有些地方還是坑坑洞洞的吧。 也請板友不吝告知內容有誤的地方，我會儘快更正！ 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 大大的指正！
※ 批踢踢實業坊(ptt.cc), 來自: 118.161.76.160 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Tech_Job/M.1627032526.A.554.html

推 FTICR : 感謝分享！ 07/23 17:30

推 CCWck : 推 07/23 17:31

推 hsujerry : 不明覺厲 07/23 17:32

推 hukung : 推 07/23 17:32

推 imba8591 : 推 07/23 17:32

推 angensun : 看不懂還是給推 07/23 17:35

推 hellomen : 推 07/23 17:35

推 drajan : 感謝分享 07/23 17:35

→ EngineerChen: 推神人 07/23 17:39

推 slirne : 推 07/23 17:42

推 yjl930 : 推 07/23 17:52

推 birka1222 : 推分享 07/23 17:55

推 eaton1202 : 先推 07/23 17:56

推 a71245969 : 推推 07/23 18:01

推 jason50715 : 推 07/23 18:03

推 Inglenook : 推 07/23 18:07

推 pmrhappy : 推神人！！！ 07/23 18:10

推 xrae00429 : 推 07/23 18:11

推 yumei2333 : 推 07/23 18:11

推 jason840226 : 神神神 07/23 18:11

推 zxc917382465: 推 07/23 18:16

推 ShenJing : 推，感謝好心分享 07/23 18:19

推 canis831025 : 推一個分享 謝謝！ 07/23 18:22

推 iamala : 看不懂XD但感謝分享 07/23 18:28

推 willy6708 : 推！ 07/23 18:29

推 xxomg : 好猛 07/23 18:29

推 Yujjlin : 推推 07/23 18:31

推 shancool : 推，謝謝分享 07/23 18:33

推 lovemost : 先推再看 07/23 18:33

推 lovelight : 大好人啊~~~~~ 07/23 18:35

推 marinsky : 推 07/23 18:37

推 wei666666 : 推 07/23 18:37

推 waterCoka : 推 07/23 18:38

推 zzihan : 推 07/23 18:39

推 a731977 : 推 07/23 18:42

推 jero8818 : 推，好心分享 07/23 18:43

推 j821005 : 推好人 07/23 18:46

推 cloud777717 : 推推 07/23 18:49

推 hao134 : 感恩 07/23 18:50

推 sanchi : 排版超簡潔分明，這用心推爆 07/23 18:53

推 louie537 : 推 07/23 18:55

推 NoAfraid : 雖然我是硬體 但還是推 07/23 18:57

推 HideOnATC : 推推~ 07/23 18:58

推 Haqua : 看不懂但推 07/23 19:00

推 ts05593818 : 推 07/23 19:00

推 FVCC : 推分享！ 07/23 19:01

推 koi074 : 神 07/23 19:08

推 y956403 : 推 tips蠻有趣的 07/23 19:10

推 eamoed : 感謝分享 向你看齊 07/23 19:17

推 oldelette : 遠端考試 大家都會考很好推 07/23 19:18

→ oldelette : 上面留錯篇 不好意思造成困擾 07/23 19:18

推 cyl61123 : 推 07/23 19:21

推 shashayou : 推 07/23 19:23

推 yfourone : 太神了 07/23 19:24

推 romeie06 : 雖然我廢物 但還是推 07/23 19:27

推 cvsh : 推 07/23 19:31

推 purpleboy01 : 推 07/23 19:35

推 zikehung : 讚 07/23 19:37

推 lukuboy : 只能推！！！ 07/23 19:42

推 lai526 : 推 07/23 19:49

推 xf413 : 推 07/23 19:50

推 dsa561320 : 推 07/23 19:54

推 breaker9527 : 推 07/23 19:57

推 aupo : 推 07/23 19:57

推 elvincwong : 神篇 留言 07/23 19:58

推 best1013 : 推，感謝分享 07/23 20:11

推 ipoop4u : 推 07/23 20:18

推 moboo : 推！！ 07/23 20:24

推 ccutebenbi : 推 07/23 20:26

推 atrix : 推 07/23 20:28

推 k078787878 : 推強者 07/23 20:31

推 aiueokaki : 推 07/23 20:35

推 www17010 : 推 07/23 20:36

推 chaahk2012 : 推 07/23 20:36

推 yuffieAK47 : PUSH 07/23 20:36

推 eju901677 : 推 07/23 20:37

推 questionboy : 有看有推 謝謝大大 07/23 20:39

推 e04rank : 推 07/23 20:40

推 jimmy983 : 推 07/23 20:41

推 lingerptt : 真棒的分享 07/23 20:49

推 gigibouz : 推 謝謝分享 07/23 20:49

推 lucifer5566 : 雖然我看不懂但還是要推 強者不吝分享 07/23 20:51

推 brightest : 推 07/23 20:53

推 japing : 推 07/23 21:03

推 misomochi : 好文推 07/23 21:03

推 dosmark9 : 推 07/23 21:04

推 chiel : 推推 07/23 21:14

推 kyrie77 : 推 07/23 21:16

推 HsieHsieH : 長知識了 大推 07/23 21:18

推 skysurf : 一定要推感謝一下 07/23 21:33

推 llltt123 : 推 07/23 21:35

推 jackie0804 : 大神推推 07/23 21:40

推 shuan0713 : 推！謝謝分享！ 07/23 21:40

推 refusekkk : 推 07/23 21:43

推 thinkdeeply : 願樓主一生平安、上廁所有衛生紙、隨時有車可以上 07/23 21:54

推 ivenuss : 謝謝 幫助很大 07/23 21:57

推 a78998042a : 推 07/23 21:57

推 erial : 好心 07/23 22:03

推 kaishu77 : 好文推推 07/23 22:05

推 bj78947 : 跪了 07/23 22:06

→ crazyanight : 推大神 跪了 07/23 22:09

推 Psyman : 太神了，推！ 07/23 22:11

推 a88484486 : 推！ 07/23 22:12

推 xjiang : 推!! 07/23 22:18

推 ejnfu : 推分享，刷起來 07/23 22:19

推 dsct : 推 07/23 22:27

推 yabie0229 : 好心！推！！ 07/23 22:27

推 s01229 : 看不懂推 07/23 22:34

推 LittleYueh : 推用心 07/23 22:38

推 DoD2 : 11 07/23 22:42

推 pumpkin534 : 強強的 07/23 22:47

推 RoubooLM : 推 07/23 22:50

推 smartree : 感謝您的分享 07/23 22:56

推 denyy555 : 很有趣的學問 07/23 23:06

推 a1l2m3m4 : 推！祝大大一生平安喜樂 07/23 23:19

推 kevin9527 : 推 07/23 23:22

推 thomaskov : 好人! 07/23 23:23

推 siba727 : 推分享！ 07/23 23:24

推 david10ne : 推 07/23 23:26

推 zzz499 : 推 07/23 23:34

推 vlstone : 推 感謝分享 07/23 23:37

推 zorogto : 強 07/23 23:46

推 longlyeagle : 像是 for i, (a, b) in enumerate(paris): 就超級常 07/23 23:55

推 d880126d : 推推 最近剛好也在用python刷leetcode 07/23 23:56

→ longlyeagle : pairs 07/23 23:56

推 longlyeagle : 寫得真好 07/24 00:00

推 apple222286 : 推 07/24 00:09

推 sgfisme : 感謝分享 07/24 00:12

推 SteveZen : 感謝分享！ 07/24 00:17

推 tenpoinyuki : 推 07/24 00:20

推 transonic : 先推 07/24 00:22

推 blazers08 : 推推推~! 07/24 00:38

推 acer368 : 感謝分享 07/24 00:43

推 zzzone : 太用心了！推！ 07/24 00:46

推 t106310218 : 感謝大大 07/24 00:46

推 happyendless: 感謝大神 07/24 01:00

推 qqq8525q : 謝謝大神！ 07/24 01:00

推 Ethical : 推，有空看 07/24 01:15

推 DemonElf : 感謝分享! 07/24 01:24

→ sc1 : 有不錯的咖哩味 07/24 01:31

推 transforman : 只能推惹 07/24 01:43

推 sh3424000 : 推 07/24 01:57

推 cyuan830 : 推，感謝分享 07/24 02:03

推 haha248787 : 推，謝謝 07/24 02:22

推 cahry : 推 07/24 02:41

推 weplay : 推 07/24 02:56

推 rhythmfang : 推！ 07/24 03:04

推 cathy9553 : 推！ 07/24 03:15

推 orafrank : 哇賽 ，可以出書了。 07/24 03:36

推 BaGaJohn5566: 太神啦 07/24 03:37

推 asdg62558 : 謝謝分享 07/24 03:38

推 kinglinest : 推 07/24 03:38

推 proPenciLead: 推 07/24 03:58

推 as209099 : 推推 07/24 03:59

噓 pig2014 : 我愛你，但是8用xor應該較好 07/24 04:09

推 wang20010522: 推 07/24 04:22

推 poem5566 : 推 07/24 06:41

推 chih2loveu : 神 07/24 06:43

推 abc95007 : 感謝 07/24 07:01

推 rootAtaabu : 推神人 07/24 07:42

推 mchotbird : 推 07/24 07:46

推 jijdamonjij : 推，正在努力刷python3 07/24 08:03

推 Alvin6713 : 強者 推！ 07/24 08:04

推 konkona : 真高手 07/24 08:07

推 huiyu8794 : 推大神 07/24 08:16

推 john520 : 推 07/24 08:18

推 wulouise : sign跟xor有什麼關係？ 07/24 08:50

推 Lucifer10896: 推 07/24 09:02

推 chenteddy : 推 07/24 09:26

推 andiran : 感謝大神 07/24 09:39

推 qwp8510 : 推 07/24 09:53

推 guf60152 : 推好心人 07/24 09:53

推 kivvq98 : 推一個說到做到 07/24 10:00

推 gocreating : 感謝分享，很實用！ 07/24 10:35

推 dt9150813 : 朝聖 07/24 10:51

推 lianteh : 強！ 07/24 11:08

推 giyaniga : 感謝大大 07/24 11:14

推 TimoBall : 負數第一位是1呀，所以 xor 後檢查是不是負數就知道 07/24 11:15

→ TimoBall : 同號不同號 07/24 11:15

推 TimoBall : 推推大大 07/24 11:23

推 tanger101 : 感謝神人分享！ 07/24 11:38

推 hyoga0123 : 感謝分享 07/24 11:48

推 bug2 : 謝謝你的熱心分享～～ 07/24 11:51

推 dantevergil : 推 07/24 12:15

推 lENis : 推，感謝分享 07/24 12:37

推 loloman : 這個真的出書是可以賺錢的，要我就會花錢買 07/24 13:34

→ yannkea : 佛心推推 07/24 13:55

推 t1232936 : 推推 07/24 14:00

推 Gway : 推一個 真強者！ 07/24 15:08

推 Incentive : 感謝分享～ 07/24 15:27

推 jjhchris : 感謝強者分享!! 07/24 15:28

推 marco79811 : 可惡 看不懂QQ 07/24 15:51

推 TLIN : 推 07/24 15:52

推 noddy0303 : 推 07/24 17:15

→ cobrasgo : 幹我真的過時了，資工出身裡面竟然有幾個名詞沒看 07/24 17:31

→ cobrasgo : 過.., 07/24 17:31

推 St3480 : 推 07/24 17:53

推 PompelmousJ : 推 07/24 18:08

推 overleaf : 推分享 07/24 18:13

推 joe3381 : 推 07/24 20:52

推 eleghost : 感謝分享 07/24 21:05

推 a2768387 : 怒推 07/24 21:10

推 Yunyung : 推 07/24 22:05

推 fuvincent : 感謝 07/24 22:37

噓 coquelicot : 紅明顯 9 的複雜度是壞的，要小心使用 07/25 01:27

推 qazujm1997 : 推大神分享 07/25 09:39

推 venroxas : 強 07/25 10:03

推 ccjfapin : 推呀 感謝大神 也想追隨大神的道路 07/25 10:26

推 Amazonite96 : 推葵花寶典！ 07/25 10:55

推 sqt : 謝謝分享，祝平安健康，事業順遂 07/25 12:43

推 ben83530 : 推 07/25 16:27

推 DoBahaha : 推 07/25 19:59

推 Atchoo : 推 07/25 21:02

推 bag0831 : 推 07/25 22:19

→ SMInice : 實在推 07/26 09:34

推 BlazarArc : 推 07/26 12:20

推 lin512 : 推一個 07/26 14:42

推 ChiaoShin369: 感謝分享 07/26 14:51

推 chinker : 推 07/26 21:37

推 RRay : 推 07/27 08:39