[心得] Leetcode 刷題解答與 Python 3 小技巧分享

作者wheels ()

看板Tech_Job

標題[心得] Leetcode 刷題解答與 Python 3 小技巧分享

時間Fri Jul 23 17:28:45 2021

※ [本文轉錄自 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！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.161.76.160 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1627032495.A.65E.html ※ 轉錄者: wheels (118.161.76.160 臺灣), 07/23/2021 17:28:45 ※ 編輯: wheels (118.161.76.160 臺灣), 07/23/2021 17:29:11

推 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

感謝！完全沒發現打錯 XD

推 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

讚讚，又學到一招，討論區竟然沒看到有人用過 XD 我猜也有可能跟我只看 py 的文章有關

推 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

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

推 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