[爆卦]LeetCode 題目 整理是什麼?優點缺點精華區懶人包

為什麼這篇LeetCode 題目 整理鄉民發文收入到精華區:因為在LeetCode 題目 整理這個討論話題中,有許多相關的文章在討論,這篇最有參考價值!作者wheels ()看板Soft_Job標題[心得] Leetcode 刷題解答與 Python ...


嗨,大家週末愉快!


不知道還記不記得之前小弟有分享面試 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: 還沒看內容,先大推,感謝 07/23 17:37
EngineerChen: 推神人 07/23 17:38
Csir: 神QQ 07/23 17:44
kiki86151: 推 python很多技巧真的很好用 07/23 17:51
mathbookh2o2: 感覺實用 07/23 17:54
Lyumin: 推爆 07/23 17:58
hanamini: 推 07/23 18:07
jamfly: 大推 07/23 18:11
KingSteven: 推 07/23 18:14
longint: 推 07/23 18:18
kyrie77: 推 07/23 18:23
MoonCode: 07/23 18:26
cossetannie: 推 07/23 18:29
sph113: 推 07/23 18:51
parsons12342: 推好心 07/23 18:53
k798976869: 推 07/23 18:57
chatnoir: 大推 07/23 18:57
UnReal5566: 有神 07/23 19:07
eggy1018: 真的是有刷的很深的才知道的python3小技巧! 推一本effe 07/23 19:10
eggy1018: ctive python 90 method 07/23 19:10
CKNTUErnie: 推 07/23 19:13
Findagreen: 太佛了 在這邊祝福原po上廁所都有衛生紙 07/23 19:25
luweber88: 推 07/23 19:27
oopssugar: 推推 07/23 19:33
duck10704: 推 神人 07/23 19:35
TAMSHUI: 推! 07/23 19:36
ZuiYang: 推 07/23 19:41
HMW: push 07/23 19:56
gaowei16: 推 07/23 19:57
Kagami3421: 推 07/23 19:58
alpe: 大推 07/23 19:59
phys: 推 07/23 20:00
WaterLengend: 只能推了 07/23 20:01
rumrumrum: 推推 07/23 20:03
kangan987: 太強了!推 07/23 20:14
unmolk: 推…. 07/23 20:14
ttsung2: 推 07/23 20:20
underwater: 雖然不是用python,還是大推 07/23 20:30
littleshin: 推 07/23 20:34
onthesea: 太神了 07/23 20:45
knme: 推 07/23 20:48
bowin: 推分享 07/23 20:49
itis0423: 推 07/23 20:53
lingege32: 推大神 07/23 20:57
jinmin88: 太猛啦 07/23 20:58
llltt123: 推 感謝大神 07/23 20:59
OSDBNetwork: 推 大神 07/23 21:02
leewei05: 推 07/23 21:02
ericx790101: 推!感謝無私分享! 07/23 21:12
tnfshjcc: 推推 實用Python技巧 07/23 21:14
EntHeEnd: 讚喔 07/23 21:41
caeserhaha: 推爆 07/23 21:49
nicehorse06: 大神推 07/23 21:56
tw11509: 推,太神啦 07/23 22:02
aassdd926: 看完覺得我不會寫Python… 07/23 22:10
DCTmaybe: 也太神了吧 07/23 22:17
devilkool: 厲害 07/23 22:53
bjocke831010: 感謝大神~ 07/23 23:34
Luke3723: 太神了 推!! 07/23 23:39
yesgowow: 推 謝謝分享 07/23 23:47
tommytyc: 推 07/24 00:16
birdman: 推分享 07/24 01:03
ss8651twtw: 學到了好多技巧 推推 07/24 01:29
juju123: 推推 07/24 01:32
yoshonabee: 推 07/24 01:35
cacadeon: 感謝詳細分享 07/24 01:37
f8210440: 感謝 分享 07/24 01:57
charle0911: 娘子出來看善心的耶穌 07/24 02:01
vincent0965: 推 07/24 02:02
s1020824: 推 07/24 02:26
cococing: 推推 07/24 02:59
la197352: 謝謝分享 07/24 03:02
mirror0227: 有些技巧讓可讀性降低了 寧願不用 07/24 03:17
mirror0227: Code寫得快沒錯 但好讀重要很多吧 07/24 03:17

同意,所以我文中有說有些人喜歡有些人不喜歡,選自己喜歡的用就好,

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

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

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

dog661121: 推爆 07/24 03:31
jack529: 讚 07/24 03:51
arunaway: 謝謝分享 07/24 04:36
hydradevil: 推佛心 07/24 06:24
davidpanda: 下面的小技巧要慎用, 主要是你需要解釋給面試官聽 07/24 07:12
davidpanda: 不是寫得快就好 07/24 07:12
davidpanda: leetcode的題目其實討論區都有很好的答案 07/24 07:13
davidpanda: 想不出來的時候其實不妨看看討論區 07/24 07:13
davidpanda: 最後就是要融會貫通, 如果自己當過面試官就知道 07/24 07:14
davidpanda: 其實很容易可以看出來面試者是真的懂還是背答案 07/24 07:15

沒錯,絕對不要背答案,一個變化就倒了,該學習的是每題背後用到的觀念。

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

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

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

papaya0807: 推好神 07/24 08:55
kiillen: 太佛拉 07/24 09:27
j6004j6: 推起來~ 太佛了 07/24 09:34
mike8469: 推 07/24 09:35
jimjim951357: 推 07/24 09:36
HelloPTT: 推 07/24 10:03
julian9925: 好佛,謝謝大大分享 07/24 11:05
Rayishere: 大推~~~ 感謝大大的無私分享 07/24 11:05
swinds24: 推分享! 07/24 11:50
elseif: 感謝分享! 來拜讀! 07/24 12:12
FireKingStar: 謝謝大大的分享,我會仔細的研讀它。 07/24 12:18
loveu8: 推分享~ 07/24 12:25
angellee0102: 感謝分享! 07/24 12:41
sarsman: 推 07/24 12:55
windmax1: 天啊 大神太偉大了 07/24 13:52
tinwen: 推~ 07/24 15:10
ID3238: 謝謝分享 這對求職面試幫助很大 07/24 15:14
stu51211: 謝謝! 07/24 15:19
Raymond0710: 感謝無私分享 07/24 15:26
hortune: 推! 07/24 15:33
nba887215: 推 07/24 15:40
AgileSeptor: 推 07/24 15:54
snowm: 謝謝分享! 07/24 15:55
euleramon: 想請問一下大大是不是有做過 AI相關的領域? 07/24 16:37

沒有耶,在學期間是有修過幾門 AI/ML 相關的課程,

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

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

你可能也想看看

搜尋相關網站