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

[wheels ()]

嗨，大家週末愉快！


不知道還記不記得之前小弟有分享面試 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
推 yupog2003: 還沒看內容，先大推，感謝
推 EngineerChen: 推神人
推 Csir: 神QQ
推 kiki86151: 推 python很多技巧真的很好用
推 mathbookh2o2: 感覺實用
推 Lyumin: 推爆
推 hanamini: 推
推 jamfly: 大推
推 KingSteven: 推
推 longint: 推
推 kyrie77: 推
推 MoonCode:
推 cossetannie: 推
推 sph113: 推
推 parsons12342: 推好心
推 k798976869: 推
推 chatnoir: 大推
推 UnReal5566: 有神
推 eggy1018: 真的是有刷的很深的才知道的python3小技巧！ 推一本effe
→ eggy1018: ctive python 90 method
推 CKNTUErnie: 推
推 Findagreen: 太佛了 在這邊祝福原po上廁所都有衛生紙
推 luweber88: 推
推 oopssugar: 推推
推 duck10704: 推  神人
推 TAMSHUI: 推！
推 ZuiYang: 推
推 HMW: push
→ gaowei16: 推
推 Kagami3421: 推
推 alpe: 大推
推 phys: 推
推 WaterLengend: 只能推了
推 rumrumrum: 推推
推 kangan987: 太強了！推
推 unmolk: 推….
推 ttsung2: 推
推 underwater: 雖然不是用python,還是大推
推 littleshin: 推
推 onthesea: 太神了
推 knme: 推
推 bowin: 推分享
推 itis0423: 推
推 lingege32: 推大神
推 jinmin88: 太猛啦
推 llltt123: 推 感謝大神
推 OSDBNetwork: 推 大神
推 leewei05: 推
推 ericx790101: 推！感謝無私分享！
推 tnfshjcc: 推推 實用Python技巧
推 EntHeEnd: 讚喔
推 caeserhaha: 推爆
推 nicehorse06: 大神推
推 tw11509: 推，太神啦
推 aassdd926: 看完覺得我不會寫Python…
推 DCTmaybe: 也太神了吧
推 devilkool: 厲害
推 bjocke831010: 感謝大神～
推 Luke3723: 太神了 推！！
→ yesgowow: 推 謝謝分享
→ tommytyc: 推
推 birdman: 推分享
推 ss8651twtw: 學到了好多技巧 推推
推 juju123: 推推
推 yoshonabee: 推
推 cacadeon: 感謝詳細分享
推 f8210440: 感謝 分享
推 charle0911: 娘子出來看善心的耶穌
推 vincent0965: 推
推 s1020824: 推
推 cococing: 推推
推 la197352: 謝謝分享
→ mirror0227: 有些技巧讓可讀性降低了 寧願不用
→ mirror0227: Code寫得快沒錯 但好讀重要很多吧
同意，所以我文中有說有些人喜歡有些人不喜歡，選自己喜歡的用就好，

像是我個人比較偏好用 dict.setdefault 建 trie 而不是用 defauldict，

但這些技巧的背後都代表著一些語言特性，了解一下並不吃虧。

而且說句實在話，限制短時間的面試 跟 長期維護的產品，出發點並不能一概而論。

推 dog661121: 推爆
推 jack529: 讚
推 arunaway: 謝謝分享
推 hydradevil: 推佛心
推 davidpanda: 下面的小技巧要慎用, 主要是你需要解釋給面試官聽
→ davidpanda: 不是寫得快就好
→ davidpanda: leetcode的題目其實討論區都有很好的答案
→ davidpanda: 想不出來的時候其實不妨看看討論區
→ davidpanda: 最後就是要融會貫通, 如果自己當過面試官就知道
→ davidpanda: 其實很容易可以看出來面試者是真的懂還是背答案
沒錯，絕對不要背答案，一個變化就倒了，該學習的是每題背後用到的觀念。

然後這份的解法就是揉合了討論區跟解答寫出來的 XD

因為發現有時候 leetcode 解答反而不是最佳解，

像是 Morris traversal 就只有少數幾篇解答有提到，但超多題目其實都可以用。

推 papaya0807: 推好神
推 kiillen: 太佛拉
推 j6004j6: 推起來~ 太佛了
推 mike8469: 推
推 jimjim951357: 推
推 HelloPTT: 推
推 julian9925: 好佛，謝謝大大分享
→ Rayishere: 大推~~~ 感謝大大的無私分享
推 swinds24: 推分享！
推 elseif: 感謝分享! 來拜讀!
推 FireKingStar: 謝謝大大的分享，我會仔細的研讀它。
推 loveu8: 推分享~
推 angellee0102: 感謝分享！
推 sarsman: 推
推 windmax1: 天啊 大神太偉大了
推 tinwen: 推~
推 ID3238: 謝謝分享 這對求職面試幫助很大
推 stu51211: 謝謝！
推 Raymond0710: 感謝無私分享
推 hortune: 推！
推 nba887215: 推
推 AgileSeptor: 推
推 snowm: 謝謝分享！
推 euleramon: 想請問一下大大是不是有做過 AI相關的領域？
沒有耶，在學期間是有修過幾門 AI/ML 相關的課程，

出社會後主要是在做 web/app 的開發。

推 deforest111: 推強者
推 Gaogaigar: 推佛心 可惜我躺平了才看到
推 blackdiz: 感謝分享，好人一生平安
推 cuh0309: 推
推 andy9595995: 推
推 vvind: 太棒了
推 freedls: 這個必推
推 sky80420: 推推
推 jasonwung: 推推
推 playboy007gy: 好人一生平安
推 tigerya: 推！
推 qq9966pp: 必須推
推 nofeel0: 推，感恩大大
推 cotbel: 是notion，整理得好乾淨! 推推
推 DLHZ: 推
推 hongwl030: 推 有實力又好心
推 kevinfilter: 大推 感謝分享
推 a24626296: 感恩，讚歎
推 shieldsky: 真的好厲害！感謝分享！技巧很實用！
推 ob9618: 推
推 f821027: 推
推 KindWei: 推 python技巧
推 amiwry: 感謝分享
推 PonyTail0901: 太強大了 希望我也能早日上岸
※ 編輯: wheels (118.161.76.160 臺灣), 07/25/2021 04:15:03
推 bcjohn: 推
推 apple20132: 推 感謝
推 summerleaves: 推推
推 somoo: 推神人 感謝無私分享
推 cypress5048: 大推！！
推 blueVC: 感謝分享！
推 darkch: 這一定要推
推 kuochuwon: 收藏一下，推
推 lofu: 推
推 gn02335338: 推
推 followmeyo: 高手
推 rotalume: 推！
推 ukuk666888: 推
推 JocMon: 推！
推 world4jason: 9的話分享個小東西 在整理資料的時候常常用到的
→ world4jason: 主要是好幾種攤平的方法 其實速度上會有差異
→ world4jason: 之前因為有需求有寫過一些比較
→ world4jason: reduce跟map印象中到了一定的scale後速度頗慢 所以直
→ world4jason: 接棄用 numpy的話如果能指定型別 速度會快上更多
推 world4jason: 不過如果都是python的list的話 就要看了 通常會慢都
→ world4jason: 是混用的鍋
→ world4jason: 像是有時候知道pure python跑比較快的寫法 但拿回來
→ world4jason: 的是巢狀numpy array 光轉成list成本就很大了
→ world4jason: py真坑XD
推 answermangtr: 超級巧 剛剛看完您的面試心得就發現您發新文章
推 Ekmund: 用心分享給推
推 snow10725: 圍觀感謝
推 xoy232: 推大神
推 elvis17: 推 感謝大神分享～
推 Ouranos: 大推，謝謝分享！
推 smily134: 推
推 tsubasaxxx: 收藏推 謝謝
推 koichip: 推，謝謝大神分享
推 hongyan: 推 謝謝大什!!!
→ hongyan:      神
推 dannymc: 推推，感謝分享
推 whatabiggun: 感謝
推 airforceso: 感恩推推推
推 ufap: 謝謝
推 stone0811: 先推
推 whitecolor: 推
推 BlazarArc: 推推
推 aacs0130: 推推，實用，不過某些特殊的語法要確定自己了解再用
推 maoqq0405: 推推
推 sandy4645: 推 太佛 謝謝分享
推 TRESS: 推
→ howard50009: 推
→ howard50009: 推
→ howard50009: 推
→ howard50009: 推
推 timuwtpirt: 推
→ WWIII: 感動啊 軟體人都是無私奉獻
推 holmes2136: 推分享
推 sars78786: 推
推 NealPope: 推爆啦！
推 justboa: 謝謝分享！
推 hsiaotzu0505: 推！謝謝！
推 tinnnnnngg: 推實用
推 gvles1210: 推
推 YNNEKUW: 大推
推 salamii: 推
推 markbex: 推！感謝分享
推 UlyssesLee: 好久沒來這版 一來就看到神 推推
推 hiarpu: 推
推 FourZero: 有神快拜
推 pupurita: 謝謝神人
推 ywbBetter: Good
推 gogohata: 推
推 Meton: 雖然不是寫python 但還是推！造福版友！
推 RonChen: 感謝分享,這絕對得推
推 zzzz8931: 推
→ MKIU: https://imgur.com/6fNIOWL
推 a24626296: 應該跪才對