[心得] Leetcode 刷題解答與 Python 3 小技巧分享
嗨,大家週末愉快!
不知道還記不記得之前小弟有分享面試 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!
--
還沒看內容,先大推,感謝
推神人
神QQ
推 python很多技巧真的很好用
感覺實用
推爆
推
大推
推
推
推
推
推
推好心
推
大推
有神
真的是有刷的很深的才知道的python3小技巧! 推一本effe
ctive python 90 method
推
太佛了 在這邊祝福原po上廁所都有衛生紙
推
推推
推 神人
推!
推
push
推
推
大推
推
只能推了
推推
太強了!推
推….
推
雖然不是用python,還是大推
推
太神了
推
推分享
推
推大神
太猛啦
推 感謝大神
推 大神
推
推!感謝無私分享!
推推 實用Python技巧
讚喔
推爆
大神推
推,太神啦
看完覺得我不會寫Python…
也太神了吧
厲害
感謝大神~
太神了 推!!
推 謝謝分享
推
推分享
學到了好多技巧 推推
推推
推
感謝詳細分享
感謝 分享
娘子出來看善心的耶穌
推
推
推推
謝謝分享
有些技巧讓可讀性降低了 寧願不用
Code寫得快沒錯 但好讀重要很多吧
同意,所以我文中有說有些人喜歡有些人不喜歡,選自己喜歡的用就好, 像是我個人比較偏好用 dict.setdefault 建 trie 而不是用 defauldict, 但這些技巧的背後都代表著一些語言特性,了解一下並不吃虧。 而且說句實在話,限制短時間的面試 跟 長期維護的產品,出發點並不能一概而論。
推爆
讚
謝謝分享
推佛心
下面的小技巧要慎用, 主要是你需要解釋給面試官聽
不是寫得快就好
leetcode的題目其實討論區都有很好的答案
想不出來的時候其實不妨看看討論區
最後就是要融會貫通, 如果自己當過面試官就知道
其實很容易可以看出來面試者是真的懂還是背答案
沒錯,絕對不要背答案,一個變化就倒了,該學習的是每題背後用到的觀念。 然後這份的解法就是揉合了討論區跟解答寫出來的 XD 因為發現有時候 leetcode 解答反而不是最佳解, 像是 Morris traversal 就只有少數幾篇解答有提到,但超多題目其實都可以用。
推好神
太佛拉
推起來~ 太佛了
推
推
推
好佛,謝謝大大分享
大推~~~ 感謝大大的無私分享
推分享!
感謝分享! 來拜讀!
謝謝大大的分享,我會仔細的研讀它。
推分享~
感謝分享!
推
天啊 大神太偉大了
推~
謝謝分享 這對求職面試幫助很大
謝謝!
感謝無私分享
推!
推
推
謝謝分享!
想請問一下大大是不是有做過 AI相關的領域?
沒有耶,在學期間是有修過幾門 AI/ML 相關的課程, 出社會後主要是在做 web/app 的開發。
推強者
推佛心 可惜我躺平了才看到
感謝分享,好人一生平安
推
推
太棒了
這個必推
推推
推推
好人一生平安
推!
必須推
推,感恩大大
是notion,整理得好乾淨! 推推
推
推 有實力又好心
大推 感謝分享
感恩,讚歎
真的好厲害!感謝分享!技巧很實用!
推
推
推 python技巧
感謝分享
太強大了 希望我也能早日上岸
推
推 感謝
推推
推神人 感謝無私分享
大推!!
感謝分享!
這一定要推
收藏一下,推
推
推
高手
推!
推
推!
9的話分享個小東西 在整理資料的時候常常用到的
主要是好幾種攤平的方法 其實速度上會有差異
之前因為有需求有寫過一些比較
reduce跟map印象中到了一定的scale後速度頗慢 所以直
接棄用 numpy的話如果能指定型別 速度會快上更多
不過如果都是python的list的話 就要看了 通常會慢都
是混用的鍋
像是有時候知道pure python跑比較快的寫法 但拿回來
的是巢狀numpy array 光轉成list成本就很大了
py真坑XD
超級巧 剛剛看完您的面試心得就發現您發新文章
用心分享給推
圍觀感謝
推大神
推 感謝大神分享~
大推,謝謝分享!
推
收藏推 謝謝
推,謝謝大神分享
推 謝謝大什!!!
神
推推,感謝分享
感謝
感恩推推推
謝謝
先推
推
推推
推推,實用,不過某些特殊的語法要確定自己了解再用
推推
推 太佛 謝謝分享
推
推
推
推
推
推
感動啊 軟體人都是無私奉獻
推分享
推
推爆啦!
謝謝分享!
推!謝謝!
推實用
推
大推
推
推!感謝分享
好久沒來這版 一來就看到神 推推
推
有神快拜
謝謝神人
Good
推
雖然不是寫python 但還是推!造福版友!
感謝分享,這絕對得推
推
應該跪才對
爆
[心得] COVID期間拿到Google/FB/微軟 Offer Part3如何準備面試和談薪水 上一篇我分享了我在 COVID-19 期間如何拿到 Google 、FB、Microsoft Offer 的經驗。 這篇我會講一下我是如何準備面試和如何談薪水。 面試 — Leetcode 我個人建議是千萬不要盲目的從第一題開始寫,因為每一題並不等價。有些題目是經典中50
[心得] google embedded SWE 面試心得去年面試google時recruiter問要走一般SWE流程還是embedded 當下覺得很難選,上網找又很少embedded SWE面試資訊 事後想想不如自己寫一個吧 板橋辦公室新啟用應該也有些embedded SWE缺吧,面試進來可以把座位填滿XD 主要關注在embedded SWE面起來有什麼差,以及準備過程33
[心得] 我的leetcode刷題清單大家好,最近似乎蠻多刷題進FAANG的討論串 身為刷題仔的一員,在此分享敝人的刷題清單 若不特別針對某公司的歷史題庫下,究竟哪些題目值得優先練習呢? 讚數多通常只是因為該題比較早發表,所以我認為應該用『讚/倒讚比』來排序 但是leetcode沒有提供這個數值,所以我用leetcode的API去把這個資料爬出來:27
Re: [討論] 我就問,刷題強者的實務表現?我親身經驗,刷題非常有用 347 top k frequent elements 23 merge k sorted lists 56 merge intervals 一些基本的工具如 recursion , tree , map , deque ,比較稍微難的像line sweep , biwise24
[請益] 面試白板考題目的時間複雜度剛剛編輯文章按到復原草稿 插入很多不必要東西 但用Pitt沒辦法編輯 所以刪除重po不好意思 以下代之前社團認識的學妹代po詢問20
Re: [討論] 演算法不強,還有辦法在資工混下去嗎?你好 是這樣的 在下也曾經迷失在Leetcode題海里 自己摸索了快半年 (= =) 才開始搞懂他的門路 摸索的過程中 還要搭配面試 最後才知道Leetcode到底在玩甚麼 其實最常考的 就是array/list/tree搭配BinarySearch/DFS/BFS 我敢說上面這六個東西佔據了線上測驗跟電話面試其中90%的題目18
Re: [請益] Leetcode找戰友噓 final01: 是想要吸經驗吧XD 05/26 22:51 → final01: 不燃網路那麼多資料還要找啥戰友 其實有差 而且差很多 雖然討論區有很多解答 甚至配合圖跟你解釋他的思路 但是很多人可能英文不夠好 所以看文章會很吃力17
Fw: [心得] COVID期間拿到Google FB 微軟 Offer Part3作者: ghostreporty (ghost) 看板: Soft_Job 標題: [心得] COVID期間拿到Google FB 微軟 Offer Part 時間: Tue Nov 17 13:13:04 2020 如何準備面試和談薪水 上一篇我分享了我在 COVID-19 期間如何拿到 Google 、FB、Microsoft Offer 的經驗。11
[心得] 北美MLE找工經歷分享前言: 縱使每個人的求職經歷與感受,如人飲水,冷暖自知,但秉著取之於ptt,用之於ptt的精 神,分享一個北美CS博士班找工作的歷程。 背景: CS PhD in MLE@美國東岸大學1
Re: [問卦] leetcode medium看完答案還是寫不出來千萬不要背的 原則上科技巨頭會避開網路上找得到的題目 之前被問的問題隔了五個月後才出現在leetcode 上面 要先熟悉基本的資料結構 hash map, stack, tree, trie,