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

[wheels ()]

※ [本文轉錄自 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(paris): 就超級常用。


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)


9. 想要攤平巢狀 list 可以用 sum(L, [])


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       : 感謝分享！
推 CCWck       : 推
推 hsujerry    : 不明覺厲
推 hukung      : 推
推 imba8591    : 推
推 angensun    : 看不懂還是給推
推 hellomen    : 推
推 drajan      : 感謝分享
→ EngineerChen: 推神人
推 slirne      : 推
推 yjl930      : 推
推 birka1222   : 推分享
推 eaton1202   : 先推
推 a71245969   : 推推
推 jason50715  : 推
推 Inglenook   : 推
推 pmrhappy    : 推神人！！！
推 xrae00429   : 推
推 yumei2333   : 推
推 jason840226 : 神神神
推 zxc917382465: 推
推 ShenJing    : 推，感謝好心分享
推 canis831025 : 推一個分享  謝謝！
推 iamala      : 看不懂XD但感謝分享
推 willy6708   : 推！
推 xxomg       : 好猛
推 Yujjlin     : 推推
推 shancool    : 推，謝謝分享
推 lovemost    : 先推再看
推 lovelight   : 大好人啊~~~~~
推 marinsky    : 推
推 wei666666   : 推
推 waterCoka   : 推
推 zzihan      : 推
推 a731977     : 推
推 jero8818    : 推，好心分享
推 j821005     : 推好人
推 cloud777717 : 推推
推 hao134      : 感恩
推 sanchi      : 排版超簡潔分明，這用心推爆
推 louie537    : 推
推 NoAfraid    : 雖然我是硬體  但還是推
推 HideOnATC   : 推推~
推 Haqua       : 看不懂但推
推 ts05593818  : 推
推 FVCC        : 推分享！
推 koi074      : 神
推 y956403     : 推 tips蠻有趣的
推 eamoed      : 感謝分享 向你看齊
推 oldelette   : 遠端考試 大家都會考很好推
→ oldelette   : 上面留錯篇 不好意思造成困擾
推 cyl61123    : 推
推 shashayou   : 推
推 yfourone    : 太神了
推 romeie06    : 雖然我廢物 但還是推
推 cvsh        : 推
推 purpleboy01 : 推
推 zikehung    : 讚
推 lukuboy     : 只能推！！！
推 lai526      : 推
推 xf413       : 推
推 dsa561320   : 推
推 breaker9527 : 推
推 aupo        : 推
推 elvincwong  : 神篇 留言
推 best1013    : 推，感謝分享
推 ipoop4u     : 推
推 moboo       : 推！！
推 ccutebenbi  : 推
推 atrix       : 推
推 k078787878  : 推強者
推 aiueokaki   : 推
推 www17010    : 推
推 chaahk2012  : 推
推 yuffieAK47  : PUSH
推 eju901677   : 推
推 questionboy : 有看有推 謝謝大大
推 e04rank     : 推
推 jimmy983    : 推
推 lingerptt   : 真棒的分享
推 gigibouz    : 推 謝謝分享
推 lucifer5566 : 雖然我看不懂但還是要推 強者不吝分享
推 brightest   : 推
推 japing      : 推
推 misomochi   : 好文推
推 dosmark9    : 推
推 chiel       : 推推
推 kyrie77     : 推
推 HsieHsieH   : 長知識了 大推
內文改個錯字 XD
※ 編輯: wheels (118.161.76.160 臺灣), 07/23/2021 21:21:18