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

看板Tech_Job作者時間2年前 (2021/07/23 17:28), 2年前編輯推噓206(208推 2噓 10→)
留言220則, 214人參與, 2年前最新討論串1/1
※ [本文轉錄自 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
推
07/23 17:30, 2年前 , 1F
感謝分享！
07/23 17:30, 1F
推
07/23 17:31, 2年前 , 2F
推
07/23 17:31, 2F
推
07/23 17:32, 2年前 , 3F
不明覺厲
07/23 17:32, 3F
推
07/23 17:32, 2年前 , 4F
推
07/23 17:32, 4F
推
07/23 17:32, 2年前 , 5F
推
07/23 17:32, 5F
推
07/23 17:35, 2年前 , 6F
看不懂還是給推
07/23 17:35, 6F
推
07/23 17:35, 2年前 , 7F
推
07/23 17:35, 7F
推
07/23 17:35, 2年前 , 8F
感謝分享
07/23 17:35, 8F
→
07/23 17:39, 2年前 , 9F
推神人
07/23 17:39, 9F
推
07/23 17:42, 2年前 , 10F
推
07/23 17:42, 10F
推
07/23 17:52, 2年前 , 11F
推
07/23 17:52, 11F
推
07/23 17:55, 2年前 , 12F
推分享
07/23 17:55, 12F
推
07/23 17:56, 2年前 , 13F
先推
07/23 17:56, 13F
推
07/23 18:01, 2年前 , 14F
推推
07/23 18:01, 14F
推
07/23 18:03, 2年前 , 15F
推
07/23 18:03, 15F
推
07/23 18:07, 2年前 , 16F
推
07/23 18:07, 16F
推
07/23 18:10, 2年前 , 17F
推神人！！！
07/23 18:10, 17F
推
07/23 18:11, 2年前 , 18F
推
07/23 18:11, 18F
推
07/23 18:11, 2年前 , 19F
推
07/23 18:11, 19F
推
07/23 18:11, 2年前 , 20F
神神神
07/23 18:11, 20F
推
07/23 18:16, 2年前 , 21F
推
07/23 18:16, 21F
推
07/23 18:19, 2年前 , 22F
推，感謝好心分享
07/23 18:19, 22F
推
07/23 18:22, 2年前 , 23F
推一個分享 謝謝！
07/23 18:22, 23F
推
07/23 18:28, 2年前 , 24F
看不懂XD但感謝分享
07/23 18:28, 24F
推
07/23 18:29, 2年前 , 25F
推！
07/23 18:29, 25F
推
07/23 18:29, 2年前 , 26F
好猛
07/23 18:29, 26F
推
07/23 18:31, 2年前 , 27F
推推
07/23 18:31, 27F
推
07/23 18:33, 2年前 , 28F
推，謝謝分享
07/23 18:33, 28F
推
07/23 18:33, 2年前 , 29F
先推再看
07/23 18:33, 29F
推
07/23 18:35, 2年前 , 30F
大好人啊~~~~~
07/23 18:35, 30F
推
07/23 18:37, 2年前 , 31F
推
07/23 18:37, 31F
推
07/23 18:37, 2年前 , 32F
推
07/23 18:37, 32F
推
07/23 18:38, 2年前 , 33F
推
07/23 18:38, 33F
推
07/23 18:39, 2年前 , 34F
推
07/23 18:39, 34F
推
07/23 18:42, 2年前 , 35F
推
07/23 18:42, 35F
推
07/23 18:43, 2年前 , 36F
推，好心分享
07/23 18:43, 36F
推
07/23 18:46, 2年前 , 37F
推好人
07/23 18:46, 37F
推
07/23 18:49, 2年前 , 38F
推推
07/23 18:49, 38F
推
07/23 18:50, 2年前 , 39F
感恩
07/23 18:50, 39F
還有 143 則推文
還有 2 段內文
推
07/24 11:51, 2年前 , 183F
謝謝你的熱心分享～～
07/24 11:51, 183F
推
07/24 12:15, 2年前 , 184F
推
07/24 12:15, 184F
推
07/24 12:37, 2年前 , 185F
推，感謝分享
07/24 12:37, 185F
推
07/24 13:34, 2年前 , 186F
這個真的出書是可以賺錢的，要我就會花錢買
07/24 13:34, 186F
出書真的過譽了，在行家眼中這份解答可能有些地方還是坑坑洞洞的吧。 也請板友不吝告知內容有誤的地方，我會儘快更正！
→
07/24 13:55, 2年前 , 187F
佛心推推
07/24 13:55, 187F
推
07/24 14:00, 2年前 , 188F
推推
07/24 14:00, 188F
推
07/24 15:08, 2年前 , 189F
推一個 真強者！
07/24 15:08, 189F
推
07/24 15:27, 2年前 , 190F
感謝分享～
07/24 15:27, 190F
推
07/24 15:28, 2年前 , 191F
感謝強者分享!!
07/24 15:28, 191F
推
07/24 15:51, 2年前 , 192F
可惡 看不懂QQ
07/24 15:51, 192F
推
07/24 15:52, 2年前 , 193F
推
07/24 15:52, 193F
推
07/24 17:15, 2年前 , 194F
推
07/24 17:15, 194F
→
07/24 17:31, 2年前 , 195F
幹我真的過時了，資工出身裡面竟然有幾個名詞沒看
07/24 17:31, 195F
→
07/24 17:31, 2年前 , 196F
過..,
07/24 17:31, 196F
推
07/24 17:53, 2年前 , 197F
推
07/24 17:53, 197F
推
07/24 18:08, 2年前 , 198F
推
07/24 18:08, 198F
推
07/24 18:13, 2年前 , 199F
推分享
07/24 18:13, 199F
推
07/24 20:52, 2年前 , 200F
推
07/24 20:52, 200F
推
07/24 21:05, 2年前 , 201F
感謝分享
07/24 21:05, 201F
推
07/24 21:10, 2年前 , 202F
怒推
07/24 21:10, 202F
推
07/24 22:05, 2年前 , 203F
推
07/24 22:05, 203F
推
07/24 22:37, 2年前 , 204F
感謝
07/24 22:37, 204F
噓
07/25 01:27, 2年前 , 205F
紅明顯 9 的複雜度是壞的，要小心使用
07/25 01:27, 205F
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
推
07/25 09:39, 2年前 , 206F
推大神分享
07/25 09:39, 206F
推
07/25 10:03, 2年前 , 207F
強
07/25 10:03, 207F
推
07/25 10:26, 2年前 , 208F
推呀 感謝大神 也想追隨大神的道路
07/25 10:26, 208F
推
07/25 10:55, 2年前 , 209F
推葵花寶典！
07/25 10:55, 209F
推
07/25 12:43, 2年前 , 210F
謝謝分享，祝平安健康，事業順遂
07/25 12:43, 210F
推
07/25 16:27, 2年前 , 211F
推
07/25 16:27, 211F
推
07/25 19:59, 2年前 , 212F
推
07/25 19:59, 212F
推
07/25 21:02, 2年前 , 213F
推
07/25 21:02, 213F
推
07/25 22:19, 2年前 , 214F
推
07/25 22:19, 214F
→
07/26 09:34, 2年前 , 215F
實在推
07/26 09:34, 215F
推
07/26 12:20, 2年前 , 216F
推
07/26 12:20, 216F
推
07/26 14:42, 2年前 , 217F
推一個
07/26 14:42, 217F
推
07/26 14:51, 2年前 , 218F
感謝分享
07/26 14:51, 218F
推
07/26 21:37, 2年前 , 219F
推
07/26 21:37, 219F
推
07/27 08:39, 2年前 , 220F
推
07/27 08:39, 220F
‣ 更多 wheels 的文章
文章代碼(AID): #1W-elELK (Tech_Job)