作者:
wheels 2021-07-23 17:28:13嗨,大家週末愉快!
不知道還記不記得之前小弟有分享面試 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!
作者:
Csir (張胖胖)
2021-07-23 17:44:00神QQ
作者: mathbookh2o2 2021-07-23 17:54:00
感覺實用
作者:
Lyumin (玉米)
2021-07-23 17:58:00推爆
作者:
jamfly (jamfly)
2021-07-23 18:11:00大推
作者: longint (數整的長長) 2021-07-23 18:18:00
推
作者:
kyrie77 (NTU KI)
2021-07-23 18:23:00推
作者: cossetannie (paa) 2021-07-23 18:29:00
推
作者: sph113 (sph) 2021-07-23 18:51:00
推
作者: k798976869 (kk) 2021-07-23 18:57:00
推
作者:
eggy1018 (羅密æèˆ‡è±¬éŽå¤œ)
2021-07-23 19:10:00真的是有刷的很深的才知道的python3小技巧! 推一本effective python 90 method
作者:
CKNTUErnie (德田田馥甄)
2021-07-23 19:13:00推
作者: oopssugar (ratio) 2021-07-23 19:33:00
推推
作者:
TAMSHUI (讓我醉æ»åœ¨å¤¢è£¡~)
2021-07-23 19:36:00推!
作者: ZuiYang (Zui) 2021-07-23 19:41:00
推
作者:
HMW (捷安特)
2021-07-23 19:56:00push
作者:
alpe (薛丁格的貓)
2021-07-23 19:59:00大推
作者: phys (jl) 2021-07-23 20:00:00
推
作者:
unmolk (UJ)
2021-07-23 20:14:00推….
作者:
ttsung2 (宗宗)
2021-07-23 20:20:00推
作者: underwater (underwater) 2021-07-23 20:30:00
雖然不是用python,還是大推
作者: onthesea (i am telegrammed) 2021-07-23 20:45:00
太神了
作者:
knme (knem)
2021-07-23 20:48:00推
作者:
bowin (盡其在我)
2021-07-23 20:49:00推分享
作者: lingege32 (MUDA) 2021-07-23 20:57:00
推大神
作者:
llltt123 (aka yoko)
2021-07-23 20:59:00推 感謝大神
作者: leewei05 (摳摳) 2021-07-23 21:02:00
推
作者:
tnfshjcc (↖煞气a攜阿攜↘)
2021-07-23 21:14:00推推 實用Python技巧
作者: caeserhaha (凱薩沙拉) 2021-07-23 21:49:00
推爆
作者:
tw11509 (John-117)
2021-07-23 22:02:00推,太神啦
作者: aassdd926 (打東東) 2021-07-23 22:10:00
看完覺得我不會寫Python…
作者:
Luke3723 (Banana)
2021-07-23 23:39:00太神了 推!!
作者: yesgowow (荷包蛋) 2021-07-23 23:47:00
推 謝謝分享
作者:
tommytyc (75303301)
2021-07-24 00:16:00推
作者:
birdman (阿丸)
2021-07-24 01:03:00推分享
作者:
juju123 (華爾騎莉亞)
2021-07-24 01:32:00推推
作者:
f8210440 (Bl_20111022)
2021-07-24 01:57:00感謝 分享
作者: charle0911 2021-07-24 02:01:00
娘子出來看善心的耶穌
作者:
s1020824 (HowardW)
2021-07-24 02:26:00推
作者: la197352 2021-07-24 03:02:00
謝謝分享
有些技巧讓可讀性降低了 寧願不用Code寫得快沒錯 但好讀重要很多吧
作者: dog661121 (完美不完美) 2021-07-24 03:31:00
推爆
作者:
jack529 (Jack)
2021-07-24 03:51:00讚
作者: arunaway (哎喲) 2021-07-24 04:36:00
謝謝分享
下面的小技巧要慎用, 主要是你需要解釋給面試官聽不是寫得快就好leetcode的題目其實討論區都有很好的答案想不出來的時候其實不妨看看討論區最後就是要融會貫通, 如果自己當過面試官就知道其實很容易可以看出來面試者是真的懂還是背答案
作者: papaya0807 (papaya) 2021-07-24 08:55:00
推好神
作者: kiillen (神龍) 2021-07-24 09:27:00
太佛拉
作者:
j6004j6 (順仔)
2021-07-24 09:34:00推起來~ 太佛了
作者:
mike8469 (mike8469)
2021-07-24 09:35:00推
作者:
Rayishere (Rayishere)
2021-07-24 11:05:00大推~~~ 感謝大大的無私分享
作者:
elseif 2021-07-24 12:12:00感謝分享! 來拜讀!
作者:
loveu8 (RA1-推廣)
2021-07-24 12:25:00推分享~
作者:
sarsman (DeNT15T♠)
2021-07-24 12:55:00推
作者:
windmax1 (I do my best)
2021-07-24 13:52:00天啊 大神太偉大了
作者:
tinwen (卡加ㄅㄨ列島)
2021-07-24 15:10:00推~
作者:
ID3238 (默默)
2021-07-24 15:14:00謝謝分享 這對求職面試幫助很大
作者:
hortune (enutroh)
2021-07-24 15:33:00推!
作者: snowm (snow) 2021-07-24 15:55:00
謝謝分享!
作者: blackdiz 2021-07-24 17:18:00
感謝分享,好人一生平安
作者:
cuh0309 (yo瑋)
2021-07-24 17:41:00推
作者:
vvind (wind)
2021-07-24 18:57:00太棒了
作者:
freedls (é˜¿å¬¤è¦ºå¾—ä½ å†·)
2021-07-24 19:11:00這個必推
作者: jasonwung (路人JJ) 2021-07-24 19:45:00
推推
作者: tigerya (虎Ya) 2021-07-24 21:25:00
推!
作者:
nofeel0 (\Bjergsen最高/)
2021-07-24 22:30:00推,感恩大大
作者: cotbel 2021-07-24 22:59:00
是notion,整理得好乾淨! 推推
作者:
DLHZ ( )
2021-07-24 23:13:00推
作者: hongwl030 (迷途小黑羊) 2021-07-24 23:24:00
推 有實力又好心
作者: kevinfilter (justinyeh1995) 2021-07-24 23:47:00
大推 感謝分享
作者:
shieldsky (Gray wolf)
2021-07-25 00:14:00真的好厲害!感謝分享!技巧很實用!
作者: ob9618 (ob9618) 2021-07-25 00:23:00
推
作者:
f821027 (蛋餅)
2021-07-25 01:01:00推
作者: KindWei (一切都是夢) 2021-07-25 01:14:00
推 python技巧
作者:
amiwry (肥墩墩大人)
2021-07-25 03:20:00感謝分享
作者:
bcjohn (bc)
2021-07-25 08:46:00推
作者: somoo (MMM) 2021-07-25 09:50:00
推神人 感謝無私分享
作者: blueVC (Uncle Carter) 2021-07-25 11:07:00
感謝分享!
作者:
darkch (chang)
2021-07-25 11:14:00這一定要推
作者:
lofu (lofu)
2021-07-25 14:51:00推
作者:
rotalume (rotalume)
2021-07-25 17:12:00推!
作者:
JocMon (晴朗夜晚)
2021-07-25 18:48:00推!
9的話分享個小東西 在整理資料的時候常常用到的主要是好幾種攤平的方法 其實速度上會有差異之前因為有需求有寫過一些比較reduce跟map印象中到了一定的scale後速度頗慢 所以直接棄用 numpy的話如果能指定型別 速度會快上更多不過如果都是python的list的話 就要看了 通常會慢都是混用的鍋像是有時候知道pure python跑比較快的寫法 但拿回來的是巢狀numpy array 光轉成list成本就很大了py真坑XD
作者:
Ekmund (是一隻小叔)
2021-07-25 20:36:00用心分享給推
作者:
xoy232 (鬼島希特勒)
2021-07-25 21:44:00推大神
作者: elvis17 2021-07-25 22:41:00
推 感謝大神分享~
作者:
Ouranos (å—¨)
2021-07-25 22:49:00大推,謝謝分享!
作者: smily134 (father134) 2021-07-25 23:01:00
推
作者: koichip (黑桃) 2021-07-26 00:06:00
推,謝謝大神分享
作者:
hongyan (Yan)
2021-07-26 00:09:00推 謝謝大什!!!神
作者: dannymc 2021-07-26 00:28:00
推推,感謝分享
作者: whatabiggun (奶奶早安) 2021-07-26 00:31:00
感謝
作者: ufap 2021-07-26 04:03:00
謝謝
作者: stone0811 (Stone) 2021-07-26 07:47:00
先推
作者:
BlazarArc (Midnight Sun)
2021-07-26 12:22:00推推
作者:
aacs0130 (æ¹›éˆ)
2021-07-26 13:52:00推推,實用,不過某些特殊的語法要確定自己了解再用
作者: TRESS 2021-07-26 22:59:00
推
作者:
WWIII (東邪西毒)
2021-07-28 16:02:00感動啊 軟體人都是無私奉獻
作者: justboa 2021-07-30 12:22:00
謝謝分享!
作者: tinnnnnngg (jjking) 2021-08-03 02:57:00
推實用
作者: YNNEKUW (YNNEKUW) 2021-08-03 19:10:00
大推
作者:
salamii (saaa)
2021-08-03 23:06:00推
作者:
markbex (馬克杯)
2021-08-04 22:43:00推!感謝分享
作者:
hiarpu (up)
2021-08-07 18:18:00推
作者:
FourZero (親愛的路人)
2021-08-15 00:07:00有神快拜