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

看板 Tech_Job
作者
時間
留言 220則留言,214人參與討論
推噓 206  ( 208推 2噓 10→ )
※ [本文轉錄自 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
1FFTICR: 感謝分享! 07/23 17:30
2FCCWck: 推 07/23 17:31
3Fhsujerry: 不明覺厲 07/23 17:32
4Fhukung: 推 07/23 17:32
5Fimba8591: 推 07/23 17:32
6Fangensun: 看不懂還是給推 07/23 17:35
7Fhellomen: 推 07/23 17:35
8Fdrajan: 感謝分享 07/23 17:35
9FEngineerChen: 推神人 07/23 17:39
10Fslirne: 推 07/23 17:42
11Fyjl930: 推 07/23 17:52
12Fbirka1222: 推分享 07/23 17:55
13Featon1202: 先推 07/23 17:56
14Fa71245969: 推推 07/23 18:01
15Fjason50715: 推 07/23 18:03
16FInglenook: 推 07/23 18:07
17Fpmrhappy: 推神人!!! 07/23 18:10
18Fxrae00429: 推 07/23 18:11
19Fyumei2333: 推 07/23 18:11
20Fjason840226: 神神神 07/23 18:11
21Fzxc917382465: 推 07/23 18:16
22FShenJing: 推,感謝好心分享 07/23 18:19
23Fcanis831025: 推一個分享 謝謝! 07/23 18:22
24Fiamala: 看不懂XD但感謝分享 07/23 18:28
25Fwilly6708: 推! 07/23 18:29
26Fxxomg: 好猛 07/23 18:29
27FYujjlin: 推推 07/23 18:31
28Fshancool: 推,謝謝分享 07/23 18:33
29Flovemost: 先推再看 07/23 18:33
30Flovelight: 大好人啊~~~~~ 07/23 18:35
31Fmarinsky: 推 07/23 18:37
32Fwei666666: 推 07/23 18:37
33FwaterCoka: 推 07/23 18:38
34Fzzihan: 推 07/23 18:39
35Fa731977: 推 07/23 18:42
36Fjero8818: 推,好心分享 07/23 18:43
37Fj821005: 推好人 07/23 18:46
38Fcloud777717: 推推 07/23 18:49
39Fhao134: 感恩 07/23 18:50
40Fsanchi: 排版超簡潔分明,這用心推爆 07/23 18:53
41Flouie537: 推 07/23 18:55
42FNoAfraid: 雖然我是硬體 但還是推 07/23 18:57
43FHideOnATC: 推推~ 07/23 18:58
44FHaqua: 看不懂但推 07/23 19:00
45Fts05593818: 推 07/23 19:00
46FFVCC: 推分享! 07/23 19:01
47Fkoi074: 神 07/23 19:08
48Fy956403: 推 tips蠻有趣的 07/23 19:10
49Feamoed: 感謝分享 向你看齊 07/23 19:17
50Foldelette: 遠端考試 大家都會考很好推 07/23 19:18
51Foldelette: 上面留錯篇 不好意思造成困擾 07/23 19:18
52Fcyl61123: 推 07/23 19:21
53Fshashayou: 推 07/23 19:23
54Fyfourone: 太神了 07/23 19:24
55Fromeie06: 雖然我廢物 但還是推 07/23 19:27
56Fcvsh: 推 07/23 19:31
57Fpurpleboy01: 推 07/23 19:35
58Fzikehung: 讚 07/23 19:37
59Flukuboy: 只能推!!! 07/23 19:42
60Flai526: 推 07/23 19:49
61Fxf413: 推 07/23 19:50
62Fdsa561320: 推 07/23 19:54
63Fbreaker9527: 推 07/23 19:57
64Faupo: 推 07/23 19:57
65Felvincwong: 神篇 留言 07/23 19:58
66Fbest1013: 推,感謝分享 07/23 20:11
67Fipoop4u: 推 07/23 20:18
68Fmoboo: 推!! 07/23 20:24
69Fccutebenbi: 推 07/23 20:26
70Fatrix: 推 07/23 20:28
71Fk078787878: 推強者 07/23 20:31
72Faiueokaki: 推 07/23 20:35
73Fwww17010: 推 07/23 20:36
74Fchaahk2012: 推 07/23 20:36
75FyuffieAK47: PUSH 07/23 20:36
76Feju901677: 推 07/23 20:37
77Fquestionboy: 有看有推 謝謝大大 07/23 20:39
78Fe04rank: 推 07/23 20:40
79Fjimmy983: 推 07/23 20:41
80Flingerptt: 真棒的分享 07/23 20:49
81Fgigibouz: 推 謝謝分享 07/23 20:49
82Flucifer5566: 雖然我看不懂但還是要推 強者不吝分享 07/23 20:51
83Fbrightest: 推 07/23 20:53
84Fjaping: 推 07/23 21:03
85Fmisomochi: 好文推 07/23 21:03
86Fdosmark9: 推 07/23 21:04
87Fchiel: 推推 07/23 21:14
88Fkyrie77: 推 07/23 21:16
89FHsieHsieH: 長知識了 大推 07/23 21:18
90Fskysurf: 一定要推感謝一下 07/23 21:33
91Fllltt123: 推 07/23 21:35
92Fjackie0804: 大神推推 07/23 21:40
93Fshuan0713: 推!謝謝分享! 07/23 21:40
94Frefusekkk: 推 07/23 21:43
95Fthinkdeeply: 願樓主一生平安、上廁所有衛生紙、隨時有車可以上 07/23 21:54
96Fivenuss: 謝謝 幫助很大 07/23 21:57
97Fa78998042a: 推 07/23 21:57
98Ferial: 好心 07/23 22:03
99Fkaishu77: 好文推推 07/23 22:05
100Fbj78947: 跪了 07/23 22:06
101Fcrazyanight: 推大神 跪了 07/23 22:09
102FPsyman: 太神了,推! 07/23 22:11
103Fa88484486: 推! 07/23 22:12
104Fxjiang: 推!! 07/23 22:18
105Fejnfu: 推分享,刷起來 07/23 22:19
106Fdsct: 推 07/23 22:27
107Fyabie0229: 好心!推!! 07/23 22:27
108Fs01229: 看不懂推 07/23 22:34
109FLittleYueh: 推用心 07/23 22:38
110FDoD2: 11 07/23 22:42
111Fpumpkin534: 強強的 07/23 22:47
112FRoubooLM: 推 07/23 22:50
113Fsmartree: 感謝您的分享 07/23 22:56
114Fdenyy555: 很有趣的學問 07/23 23:06
115Fa1l2m3m4: 推!祝大大一生平安喜樂 07/23 23:19
116Fkevin9527: 推 07/23 23:22
117Fthomaskov: 好人! 07/23 23:23
118Fsiba727: 推分享! 07/23 23:24
119Fdavid10ne: 推 07/23 23:26
120Fzzz499: 推 07/23 23:34
121Fvlstone: 推 感謝分享 07/23 23:37
122Fzorogto: 強 07/23 23:46
123Flonglyeagle: 像是 for i, (a, b) in enumerate(paris): 就超級常 07/23 23:55
124Fd880126d: 推推 最近剛好也在用python刷leetcode 07/23 23:56
125Flonglyeagle: pairs 07/23 23:56
感謝!完全沒發現打錯 XD
126Flonglyeagle: 寫得真好 07/24 00:00
127Fapple222286: 推 07/24 00:09
128Fsgfisme: 感謝分享 07/24 00:12
129FSteveZen: 感謝分享! 07/24 00:17
130Ftenpoinyuki: 推 07/24 00:20
131Ftransonic: 先推 07/24 00:22
132Fblazers08: 推推推~! 07/24 00:38
133Facer368: 感謝分享 07/24 00:43
134Fzzzone: 太用心了!推! 07/24 00:46
135Ft106310218: 感謝大大 07/24 00:46
136Fhappyendless: 感謝大神 07/24 01:00
137Fqqq8525q: 謝謝大神! 07/24 01:00
138FEthical: 推,有空看 07/24 01:15
139FDemonElf: 感謝分享! 07/24 01:24
140Fsc1: 有不錯的咖哩味 07/24 01:31
141Ftransforman: 只能推惹 07/24 01:43
142Fsh3424000: 推 07/24 01:57
143Fcyuan830: 推,感謝分享 07/24 02:03
144Fhaha248787: 推,謝謝 07/24 02:22
145Fcahry: 推 07/24 02:41
146Fweplay: 推 07/24 02:56
147Frhythmfang: 推! 07/24 03:04
148Fcathy9553: 推! 07/24 03:15
149Forafrank: 哇賽 ,可以出書了。 07/24 03:36
150FBaGaJohn5566: 太神啦 07/24 03:37
151Fasdg62558: 謝謝分享 07/24 03:38
152Fkinglinest: 推 07/24 03:38
153FproPenciLead: 推 07/24 03:58
154Fas209099: 推推 07/24 03:59
155Fpig2014: 我愛你,但是8用xor應該較好 07/24 04:09
讚讚,又學到一招,討論區竟然沒看到有人用過 XD 我猜也有可能跟我只看 py 的文章有關
156Fwang20010522: 推 07/24 04:22
157Fpoem5566: 推 07/24 06:41
158Fchih2loveu: 神 07/24 06:43
159Fabc95007: 感謝 07/24 07:01
160FrootAtaabu: 推神人 07/24 07:42
161Fmchotbird: 推 07/24 07:46
162Fjijdamonjij: 推,正在努力刷python3 07/24 08:03
163FAlvin6713: 強者 推! 07/24 08:04
164Fkonkona: 真高手 07/24 08:07
165Fhuiyu8794: 推大神 07/24 08:16
166Fjohn520: 推 07/24 08:18
167Fwulouise: sign跟xor有什麼關係? 07/24 08:50
168FLucifer10896: 推 07/24 09:02
169Fchenteddy: 推 07/24 09:26
170Fandiran: 感謝大神 07/24 09:39
171Fqwp8510: 推 07/24 09:53
172Fguf60152: 推好心人 07/24 09:53
173Fkivvq98: 推一個說到做到 07/24 10:00
174Fgocreating: 感謝分享,很實用! 07/24 10:35
175Fdt9150813: 朝聖 07/24 10:51
176Flianteh: 強! 07/24 11:08
177Fgiyaniga: 感謝大大 07/24 11:14
178FTimoBall: 負數第一位是1呀,所以 xor 後檢查是不是負數就知道 07/24 11:15
179FTimoBall: 同號不同號 07/24 11:15
180FTimoBall: 推推大大 07/24 11:23
181Ftanger101: 感謝神人分享! 07/24 11:38
182Fhyoga0123: 感謝分享 07/24 11:48
183Fbug2: 謝謝你的熱心分享~~ 07/24 11:51
184Fdantevergil: 推 07/24 12:15
185FlENis: 推,感謝分享 07/24 12:37
186Floloman: 這個真的出書是可以賺錢的,要我就會花錢買 07/24 13:34
出書真的過譽了,在行家眼中這份解答可能有些地方還是坑坑洞洞的吧。 也請板友不吝告知內容有誤的地方,我會儘快更正!
187Fyannkea: 佛心推推 07/24 13:55
188Ft1232936: 推推 07/24 14:00
189FGway: 推一個 真強者! 07/24 15:08
190FIncentive: 感謝分享~ 07/24 15:27
191Fjjhchris: 感謝強者分享!! 07/24 15:28
192Fmarco79811: 可惡 看不懂QQ 07/24 15:51
193FTLIN: 推 07/24 15:52
194Fnoddy0303: 推 07/24 17:15
195Fcobrasgo: 幹我真的過時了,資工出身裡面竟然有幾個名詞沒看 07/24 17:31
196Fcobrasgo: 過.., 07/24 17:31
197FSt3480: 推 07/24 17:53
198FPompelmousJ: 推 07/24 18:08
199Foverleaf: 推分享 07/24 18:13
200Fjoe3381: 推 07/24 20:52
201Feleghost: 感謝分享 07/24 21:05
202Fa2768387: 怒推 07/24 21:10
203FYunyung: 推 07/24 22:05
204Ffuvincent: 感謝 07/24 22:37
205Fcoquelicot: 紅明顯 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
206Fqazujm1997: 推大神分享 07/25 09:39
207Fvenroxas: 強 07/25 10:03
208Fccjfapin: 推呀 感謝大神 也想追隨大神的道路 07/25 10:26
209FAmazonite96: 推葵花寶典! 07/25 10:55
210Fsqt: 謝謝分享,祝平安健康,事業順遂 07/25 12:43
211Fben83530: 推 07/25 16:27
212FDoBahaha: 推 07/25 19:59
213FAtchoo: 推 07/25 21:02
214Fbag0831: 推 07/25 22:19
215FSMInice: 實在推 07/26 09:34
216FBlazarArc: 推 07/26 12:20
217Flin512: 推一個 07/26 14:42
218FChiaoShin369: 感謝分享 07/26 14:51
219Fchinker: 推 07/26 21:37
220FRRay: 推 07/27 08:39

tech_job 最新熱門文章

25 [請益] 台積 IT offer請益
78 tech_job 2021-09-24 23:04
74 [討論] 我這樣算黑掉嗎
187 tech_job 2021-09-24 18:44