PTT推薦

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

看板Tech_Job標題[心得] Leetcode 刷題解答與 Python 3 小技巧分享作者
wheels
()
時間推噓推:208 噓:2 →:10

※ [本文轉錄自 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留言評論
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.161.76.160 (臺灣)
PTT 網址
※ 轉錄者: wheels (118.161.76.160 臺灣), 07/23/2021 17:28:45 ※ 編輯: wheels (118.161.76.160 臺灣), 07/23/2021 17:29:11

FTICR 07/23 17:30感謝分享!

CCWck 07/23 17:31

hsujerry 07/23 17:32不明覺厲

hukung 07/23 17:32

imba8591 07/23 17:32

angensun 07/23 17:35看不懂還是給推

hellomen 07/23 17:35

drajan 07/23 17:35感謝分享

EngineerChen07/23 17:39推神人

slirne 07/23 17:42

yjl930 07/23 17:52

birka1222 07/23 17:55推分享

eaton1202 07/23 17:56先推

a71245969 07/23 18:01推推

jason50715 07/23 18:03

Inglenook 07/23 18:07

pmrhappy 07/23 18:10推神人!!!

xrae00429 07/23 18:11

yumei2333 07/23 18:11

jason840226 07/23 18:11神神神

zxc91738246507/23 18:16

ShenJing 07/23 18:19推,感謝好心分享

canis831025 07/23 18:22推一個分享 謝謝!

iamala 07/23 18:28看不懂XD但感謝分享

willy6708 07/23 18:29推!

xxomg 07/23 18:29好猛

Yujjlin 07/23 18:31推推

shancool 07/23 18:33推,謝謝分享

lovemost 07/23 18:33先推再看

lovelight 07/23 18:35大好人啊~~~~~

marinsky 07/23 18:37

wei666666 07/23 18:37

waterCoka 07/23 18:38

zzihan 07/23 18:39

a731977 07/23 18:42

jero8818 07/23 18:43推,好心分享

j821005 07/23 18:46推好人

cloud777717 07/23 18:49推推

hao134 07/23 18:50感恩

sanchi 07/23 18:53排版超簡潔分明,這用心推爆

louie537 07/23 18:55

NoAfraid 07/23 18:57雖然我是硬體 但還是推

HideOnATC 07/23 18:58推推~

Haqua 07/23 19:00看不懂但推

ts05593818 07/23 19:00

FVCC 07/23 19:01推分享!

koi074 07/23 19:08

y956403 07/23 19:10推 tips蠻有趣的

eamoed 07/23 19:17感謝分享 向你看齊

oldelette 07/23 19:18遠端考試 大家都會考很好推

oldelette 07/23 19:18上面留錯篇 不好意思造成困擾

cyl61123 07/23 19:21

shashayou 07/23 19:23

yfourone 07/23 19:24太神了

romeie06 07/23 19:27雖然我廢物 但還是推

cvsh 07/23 19:31

purpleboy01 07/23 19:35

zikehung 07/23 19:37

lukuboy 07/23 19:42只能推!!!

lai526 07/23 19:49

xf413 07/23 19:50

dsa561320 07/23 19:54

breaker9527 07/23 19:57

aupo 07/23 19:57

elvincwong 07/23 19:58神篇 留言

best1013 07/23 20:11推,感謝分享

ipoop4u 07/23 20:18

moboo 07/23 20:24推!!

ccutebenbi 07/23 20:26

atrix 07/23 20:28

k078787878 07/23 20:31推強者

aiueokaki 07/23 20:35

www17010 07/23 20:36

chaahk2012 07/23 20:36

yuffieAK47 07/23 20:36PUSH

eju901677 07/23 20:37

questionboy 07/23 20:39有看有推 謝謝大大

e04rank 07/23 20:40

jimmy983 07/23 20:41

lingerptt 07/23 20:49真棒的分享

gigibouz 07/23 20:49推 謝謝分享

lucifer5566 07/23 20:51雖然我看不懂但還是要推 強者不吝分享

brightest 07/23 20:53

japing 07/23 21:03

misomochi 07/23 21:03好文推

dosmark9 07/23 21:04

chiel 07/23 21:14推推

kyrie77 07/23 21:16

HsieHsieH 07/23 21:18長知識了 大推

skysurf 07/23 21:33一定要推感謝一下

llltt123 07/23 21:35

jackie0804 07/23 21:40大神推推

shuan0713 07/23 21:40推!謝謝分享!

refusekkk 07/23 21:43

thinkdeeply 07/23 21:54願樓主一生平安、上廁所有衛生紙、隨時有車可以上

ivenuss 07/23 21:57謝謝 幫助很大

a78998042a 07/23 21:57

erial 07/23 22:03好心

kaishu77 07/23 22:05好文推推

bj78947 07/23 22:06跪了

crazyanight 07/23 22:09推大神 跪了

Psyman 07/23 22:11太神了,推!

a88484486 07/23 22:12推!

xjiang 07/23 22:18推!!

ejnfu 07/23 22:19推分享,刷起來

dsct 07/23 22:27

yabie0229 07/23 22:27好心!推!!

s01229 07/23 22:34看不懂推

LittleYueh 07/23 22:38推用心

DoD2 07/23 22:4211

pumpkin534 07/23 22:47強強的

RoubooLM 07/23 22:50

smartree 07/23 22:56感謝您的分享

denyy555 07/23 23:06很有趣的學問

a1l2m3m4 07/23 23:19推!祝大大一生平安喜樂

kevin9527 07/23 23:22

thomaskov 07/23 23:23好人!

siba727 07/23 23:24推分享!

david10ne 07/23 23:26

zzz499 07/23 23:34

vlstone 07/23 23:37推 感謝分享

zorogto 07/23 23:46

longlyeagle 07/23 23:55像是 for i, (a, b) in enumerate(paris): 就超級常

d880126d 07/23 23:56推推 最近剛好也在用python刷leetcode

longlyeagle 07/23 23:56 pairs

感謝!完全沒發現打錯 XD

longlyeagle 07/24 00:00寫得真好

apple222286 07/24 00:09

sgfisme 07/24 00:12感謝分享

SteveZen 07/24 00:17感謝分享!

tenpoinyuki 07/24 00:20

transonic 07/24 00:22先推

blazers08 07/24 00:38推推推~!

acer368 07/24 00:43感謝分享

zzzone 07/24 00:46太用心了!推!

t106310218 07/24 00:46感謝大大

happyendless07/24 01:00感謝大神

qqq8525q 07/24 01:00謝謝大神!

Ethical 07/24 01:15推,有空看

DemonElf 07/24 01:24感謝分享!

sc1 07/24 01:31有不錯的咖哩味

transforman 07/24 01:43只能推惹

sh3424000 07/24 01:57

cyuan830 07/24 02:03推,感謝分享

haha248787 07/24 02:22推,謝謝

cahry 07/24 02:41

weplay 07/24 02:56

rhythmfang 07/24 03:04推!

cathy9553 07/24 03:15推!

orafrank 07/24 03:36哇賽 ,可以出書了。

BaGaJohn556607/24 03:37太神啦

asdg62558 07/24 03:38謝謝分享

kinglinest 07/24 03:38

proPenciLead07/24 03:58

as209099 07/24 03:59推推

pig2014 07/24 04:09我愛你,但是8用xor應該較好

讚讚,又學到一招,討論區竟然沒看到有人用過 XD 我猜也有可能跟我只看 py 的文章有關

wang2001052207/24 04:22

poem5566 07/24 06:41

chih2loveu 07/24 06:43

abc95007 07/24 07:01感謝

rootAtaabu 07/24 07:42推神人

mchotbird 07/24 07:46

jijdamonjij 07/24 08:03推,正在努力刷python3

Alvin6713 07/24 08:04強者 推!

konkona 07/24 08:07真高手

huiyu8794 07/24 08:16推大神

john520 07/24 08:18

wulouise 07/24 08:50sign跟xor有什麼關係?

Lucifer1089607/24 09:02

chenteddy 07/24 09:26

andiran 07/24 09:39感謝大神

qwp8510 07/24 09:53

guf60152 07/24 09:53推好心人

kivvq98 07/24 10:00推一個說到做到

gocreating 07/24 10:35感謝分享,很實用!

dt9150813 07/24 10:51朝聖

lianteh 07/24 11:08強!

giyaniga 07/24 11:14感謝大大

TimoBall 07/24 11:15負數第一位是1呀,所以 xor 後檢查是不是負數就知道

TimoBall 07/24 11:15同號不同號

TimoBall 07/24 11:23推推大大

tanger101 07/24 11:38感謝神人分享!

hyoga0123 07/24 11:48感謝分享

bug2 07/24 11:51謝謝你的熱心分享~~

dantevergil 07/24 12:15

lENis 07/24 12:37推,感謝分享

loloman 07/24 13:34這個真的出書是可以賺錢的,要我就會花錢買

出書真的過譽了,在行家眼中這份解答可能有些地方還是坑坑洞洞的吧。 也請板友不吝告知內容有誤的地方,我會儘快更正!

yannkea 07/24 13:55佛心推推

t1232936 07/24 14:00推推

Gway 07/24 15:08推一個 真強者!

Incentive 07/24 15:27感謝分享~

jjhchris 07/24 15:28感謝強者分享!!

marco79811 07/24 15:51可惡 看不懂QQ

TLIN 07/24 15:52

noddy0303 07/24 17:15

cobrasgo 07/24 17:31幹我真的過時了,資工出身裡面竟然有幾個名詞沒看

cobrasgo 07/24 17:31過..,

St3480 07/24 17:53

PompelmousJ 07/24 18:08

overleaf 07/24 18:13推分享

joe3381 07/24 20:52

eleghost 07/24 21:05感謝分享

a2768387 07/24 21:10怒推

Yunyung 07/24 22:05

fuvincent 07/24 22:37感謝

coquelicot 07/25 01:27紅明顯 9 的複雜度是壞的,要小心使用

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

qazujm1997 07/25 09:39推大神分享

venroxas 07/25 10:03

ccjfapin 07/25 10:26推呀 感謝大神 也想追隨大神的道路

Amazonite96 07/25 10:55推葵花寶典!

sqt 07/25 12:43謝謝分享,祝平安健康,事業順遂

ben83530 07/25 16:27

DoBahaha 07/25 19:59

Atchoo 07/25 21:02

bag0831 07/25 22:19

SMInice 07/26 09:34實在推

BlazarArc 07/26 12:20

lin512 07/26 14:42推一個

ChiaoShin36907/26 14:51感謝分享

chinker 07/26 21:37

RRay 07/27 08:39