1. 我重新梳理這套Python算法清單的緣由每隔一段時(shí)間總會有人在群里問一句python經(jīng)典算法大全到底該從哪兒看起python算法有哪些是真正需要花時(shí)間掌握的。這個(gè)問題我回答過不下十遍但每次回答都不太一樣因?yàn)樘釂柕娜吮尘安顒e太大。有的是剛學(xué)完語法想做點(diǎn)練習(xí)的有的是工作兩年突然要準(zhǔn)備技術(shù)考察的還有的是寫業(yè)務(wù)代碼寫久了想回頭把基礎(chǔ)重新打一遍。所以這次索性把我會反復(fù)翻看的那部分算法整理成一份清單把每個(gè)模塊為什么這么選、代碼怎么寫、哪些地方最容易出錯(cuò)都寫清楚。這份內(nèi)容適合誰如果你是剛接觸 Python、能寫函數(shù)但一遇到復(fù)雜度分析就發(fā)懵的新人可以從第 2、3 節(jié)順著讀如果你已經(jīng)有項(xiàng)目經(jīng)驗(yàn)只想找回手感、順手補(bǔ)一下動(dòng)態(tài)規(guī)劃和圖論直接跳到第 4、5 節(jié)也沒問題。我不會把幾十種算法全部羅列一遍那種清單在搜索結(jié)果的首頁能找到一大堆但大多只有名字和一句解釋看完還是不知道該怎么用。我關(guān)注的是那些在真實(shí)場景里被反復(fù)調(diào)用、被反復(fù)寫錯(cuò)、被反復(fù)討論的算法以及圍繞它們的一整套工程習(xí)慣。先交代一個(gè)前提算法清單不應(yīng)該按“考試大綱”來組織而應(yīng)該按“使用頻率 出錯(cuò)代價(jià)”來組織。一個(gè)排序?qū)戝e(cuò)可能只是結(jié)果順序不對一個(gè)二分邊界寫錯(cuò)可能就是線上數(shù)據(jù)查不到一個(gè)并查集漏了路徑壓縮可能就讓程序從毫秒級變成分鐘級。這個(gè)思路決定了下面所有內(nèi)容的排列順序和取舍方式。2. 排序與查找最基礎(chǔ)也是最容易出問題的地方2.1 快速排序、歸并與堆排序之間的選擇排序是所有人學(xué)算法的第一站但真正到了寫代碼的時(shí)候絕大多數(shù)情況直接調(diào)用sorted()就夠了。Python 內(nèi)置的 Timsort 是歸并和插入排序的混合實(shí)現(xiàn)平均和最壞都是 O(n log n)而且對部分有序的數(shù)據(jù)有額外優(yōu)化手寫基本不可能比它快。所以我一般只在兩種情況下手寫排序一是需要理解分治思想二是需要做“部分排序”或者“只取前 K 個(gè)”這類內(nèi)置函數(shù)不方便處理的場景。快速排序值得手寫的核心原因不是它快而是它把“分治 原地交換”這套模式展示得最干凈。我常用的版本做了兩件事三數(shù)取中選基準(zhǔn)以及小區(qū)間切換插入排序。前者用來規(guī)避已經(jīng)有序的輸入導(dǎo)致的 O(n2) 退化后者是因?yàn)檫f歸到 16 個(gè)元素以下時(shí)遞歸開銷已經(jīng)超過比較開銷了。def quick_sort(arr, lo0, hiNone): if hi is None: hi len(arr) - 1 while lo hi: if hi - lo 16: insertion_sort(arr, lo, hi) return mid lo (hi - lo) // 2 # 三數(shù)取中把中位數(shù)換到 lo 位置 if arr[mid] arr[lo]: arr[lo], arr[mid] arr[mid], arr[lo] if arr[hi] arr[lo]: arr[lo], arr[hi] arr[hi], arr[lo] if arr[hi] arr[mid]: arr[mid], arr[hi] arr[hi], arr[mid] arr[lo], arr[mid] arr[mid], arr[lo] pivot arr[lo] i, j lo, hi while i j: while i j and arr[j] pivot: j - 1 arr[i] arr[j] while i j and arr[i] pivot: i 1 arr[j] arr[i] arr[i] pivot # 先遞歸較短的一側(cè)控制棧深度 if i - lo hi - i: quick_sort(arr, lo, i - 1) lo i 1 else: quick_sort(arr, i 1, hi) hi i - 1 return arr這段代碼有兩個(gè)細(xì)節(jié)值得單獨(dú)拿出來說。第一個(gè)是i, j雙指針加“挖坑填數(shù)”的寫法比左右交換的寫法少一半賦值操作實(shí)測在幾十萬級別的列表上差距能到 15% 左右。第二個(gè)是“先遞歸較短的一側(cè)”這個(gè)尾遞歸優(yōu)化它把最壞情況下的遞歸棧深度從 O(n) 壓到 O(log n)避免數(shù)據(jù)量一大就觸發(fā)遞歸深度限制。歸并排序的適用場景和快排不太一樣?？炫攀窃嘏判蚩臻g O(log n)歸并需要額外 O(n) 空間但它是穩(wěn)定排序而且天然適合處理外部排序和鏈表排序。我處理鏈表排序時(shí)基本只用歸并因?yàn)殒湵頉]法隨機(jī)訪問快排的 partition 在鏈表上非常別扭。堆排序的優(yōu)勢在于最壞情況也是 O(n log n) 且空間 O(1)但它不穩(wěn)定、緩存不友好實(shí)際項(xiàng)目里我用它的次數(shù)屈指可數(shù)更多是拿堆這個(gè)結(jié)構(gòu)去做優(yōu)先隊(duì)列而不是拿堆排序去排數(shù)組。下面這張表是我自己整理的選擇依據(jù)遇到具體問題時(shí)可以直接對照場景推薦方案理由通用列表排序內(nèi)置sorted()Timsort 穩(wěn)定且有局部有序優(yōu)化教學(xué) / 理解分治快排原地、思路清晰、參數(shù)少鏈表排序歸并不需要隨機(jī)訪問穩(wěn)定只取前 K 個(gè)heapq.nlargest/ 小頂堆復(fù)雜度 O(n log k)不必全排數(shù)據(jù)量大且內(nèi)存吃緊堆排序原地最壞 O(n log n)注意手寫快排時(shí)不要用arr[0]當(dāng)基準(zhǔn)也不要對已經(jīng)有序的數(shù)據(jù)做測試就下結(jié)論。真實(shí)數(shù)據(jù)里“部分有序”非常常見比如按時(shí)間戳追加的日志這時(shí)候固定基準(zhǔn)會直接退化。2.2 二分查找邊界寫錯(cuò)一次就夠記一輩子二分查找的代碼只有十來行但它是公認(rèn)最容易寫錯(cuò)的算法之一。根因不在算法本身而在于“區(qū)間定義”這件事沒有被統(tǒng)一。我現(xiàn)在的習(xí)慣是全程只用左閉右開區(qū)間[lo, hi)所有變體都在這套約定下推不再混用閉區(qū)間寫法。def lower_bound(arr, target): 返回第一個(gè) target 的下標(biāo)找不到返回 len(arr) lo, hi 0, len(arr) while lo hi: mid lo (hi - lo) // 2 if arr[mid] target: lo mid 1 else: hi mid return lo這個(gè)模板能覆蓋絕大部分需求要判斷存在性就看lo len(arr) and arr[lo] target要找最后一個(gè)小于等于 target 的位置就換成upper_bound再減一要在旋轉(zhuǎn)數(shù)組里查找只改判斷條件不改框架。統(tǒng)一模板的價(jià)值在于你不需要每次重新推導(dǎo)邊界只要記住“循環(huán)結(jié)束時(shí) lo 是答案”這一條。mid lo (hi - lo) // 2這種寫法不是為了好看。在支持 int 溢出的語言里它能防止溢出在 Python 里雖然沒有溢出問題但保持這個(gè)習(xí)慣可以讓你在跨語言寫代碼時(shí)不用重新想一遍。有一個(gè)坑我踩過對浮點(diǎn)數(shù)做二分時(shí)用while lo hi會陷入死循環(huán)因?yàn)閮蓚€(gè)浮點(diǎn)數(shù)之間永遠(yuǎn)存在更近的值。這種情況要么改成固定迭代次數(shù)比如 100 次要么給區(qū)間加一個(gè)精度閾值while hi - lo 1e-7。我一般用固定次數(shù)因?yàn)榫乳撝翟诓煌考壍臄?shù)據(jù)上不好統(tǒng)一。3. 數(shù)據(jù)結(jié)構(gòu)類算法棧、隊(duì)列、哈希與并查集3.1 該用內(nèi)置結(jié)構(gòu)還是自己手寫這個(gè)問題的答案很明確業(yè)務(wù)代碼里全部用內(nèi)置結(jié)構(gòu)。list當(dāng)棧用collections.deque當(dāng)隊(duì)列用dict當(dāng)哈希表用heapq當(dāng)優(yōu)先隊(duì)列用。Python 的內(nèi)置實(shí)現(xiàn)是 C 層優(yōu)化過的手寫一遍性能只會更差。但“用內(nèi)置”不等于“不用懂”。棧和隊(duì)列的價(jià)值在于它們約束了訪問順序這個(gè)約束本身就是算法設(shè)計(jì)的一部分。比如用棧做括號匹配、用單調(diào)棧求下一個(gè)更大元素、用 deque 做滑動(dòng)窗口最大值這些都是把數(shù)據(jù)結(jié)構(gòu)當(dāng)成“狀態(tài)容器”來用而不是簡單地存數(shù)據(jù)。單調(diào)棧這個(gè)模式特別值得單獨(dú)練它的核心是“維護(hù)一個(gè)單調(diào)遞增或遞減的棧入棧前彈掉破壞單調(diào)性的元素”一旦理解了這個(gè)動(dòng)作接雨水、柱狀圖最大矩形、滑動(dòng)窗口最大值這一串題目就是同一套邏輯換個(gè)外套。哈希表這塊我要提醒的是“哈希沖突”和“可哈希性”兩個(gè)概念。Python 的dict用開放尋址法處理沖突平均 O(1)但如果你自定義了__eq__卻沒定義__hash__這個(gè)類就變成不可哈希的塞不進(jìn)set和dict。反過來如果兩個(gè)對象相等但哈希值不同字典查找就會失效。這是一個(gè)很隱蔽的 bug表現(xiàn)出來是“明明放進(jìn)去了卻查不到”。3.2 并查集路徑壓縮不能省并查集是那種“代碼極短、作用極大、細(xì)節(jié)極易漏”的結(jié)構(gòu)典型用于連通性判斷、朋友圈合并、島嶼數(shù)量統(tǒng)計(jì)這類問題。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n self.count n # 連通分量個(gè)數(shù) def find(self, x): # 迭代版路徑壓縮避免遞歸深度問題 root x while self.parent[root] ! root: root self.parent[root] while self.parent[x] ! root: self.parent[x], x root, self.parent[x] return root def union(self, x, y): rx, ry self.find(x), self.find(y) if rx ry: return False # 按秩合并把矮樹掛到高樹下面 if self.rank[rx] self.rank[ry]: rx, ry ry, rx self.parent[ry] rx if self.rank[rx] self.rank[ry]: self.rank[rx] 1 self.count - 1 return True三個(gè)細(xì)節(jié)第一find用迭代不用遞歸因?yàn)槁窂綁嚎s后的樹雖然矮但極端情況下仍可能很深遞歸有棧溢出風(fēng)險(xiǎn)第二路徑壓縮和按秩合并一起用復(fù)雜度才接近常數(shù)只用其中一個(gè)會退化成 O(log n)第三用count維護(hù)連通分量個(gè)數(shù)比每次遍歷統(tǒng)計(jì)快得多這是圖上判環(huán)的關(guān)鍵。我見過一個(gè)真實(shí)案例某項(xiàng)目用并查集做大批量數(shù)據(jù)的分組只做了路徑壓縮沒做按秩合并單次操作平均下來還是很快但在“先大量 union 再集中 find”的模式下性能比兩者都用慢了將近 3 倍。這不是理論問題是實(shí)測出來的。4. 動(dòng)態(tài)規(guī)劃與貪心思路永遠(yuǎn)比代碼重要4.1 動(dòng)態(tài)規(guī)劃的四步定式動(dòng)態(tài)規(guī)劃是很多人卡住的地方卡點(diǎn)通常不是寫不出代碼而是不知道狀態(tài)該怎么定義。我現(xiàn)在的做法是固定走四步定義狀態(tài)、寫轉(zhuǎn)移方程、確定初始值和邊界、確定遍歷順序。這四步里第一步和第四步最容易錯(cuò)代碼反而是最簡單的。以 0-1 背包為例。狀態(tài)定義成dp[i][j]表示“前 i 個(gè)物品、容量 j 時(shí)的最大價(jià)值”轉(zhuǎn)移方程是“不選第 i 個(gè)”和“選第 i 個(gè)”取較大值。到這里還沒完關(guān)鍵在遍歷順序01 背包用一維數(shù)組優(yōu)化時(shí)容量必須從大到小遍歷因?yàn)槊總€(gè)物品只能用一次完全背包則從小到大因?yàn)槲锲房梢灾貜?fù)用。這個(gè)順序差異不是記憶題而是由“當(dāng)前狀態(tài)依賴的是本層還是上一層”決定的。def knapsack_01(weights, values, cap): dp [0] * (cap 1) for i in range(len(weights)): # 倒序遍歷保證每件物品只被選一次 for j in range(cap, weights[i] - 1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[cap]另一個(gè)高頻模式是最長遞增子序列。O(n2) 的寫法是dp[i]表示以 i 結(jié)尾的最長長度狀態(tài)轉(zhuǎn)移要遍歷前面所有元素O(n log n) 的寫法維護(hù)一個(gè)“最小結(jié)尾數(shù)組”用二分插入。后者不好想但它其實(shí)是“貪心 二分”的組合理解了“讓每個(gè)長度的結(jié)尾盡可能小”這個(gè)貪心策略代碼就只是輔助。我在實(shí)際使用中發(fā)現(xiàn)動(dòng)態(tài)規(guī)劃真正難的地方在于“能不能把問題拆成重疊子問題”。有些題看起來像 DP其實(shí)是貪心有些看起來像貪心其實(shí)必須 DP。判斷標(biāo)準(zhǔn)是局部最優(yōu)能不能推出全局最優(yōu)。能就是貪心不能才需要 DP 枚舉所有狀態(tài)。4.2 貪心的適用邊界與驗(yàn)證方法貪心的坑在于“看起來對”但實(shí)際不成立。我驗(yàn)證一個(gè)貪心策略是否正確的土辦法是構(gòu)造三個(gè)反例。第一個(gè)是“相鄰兩項(xiàng)交換后結(jié)果變差”的邊界第二個(gè)是“局部最優(yōu)但全局不是最優(yōu)”的構(gòu)造第三個(gè)是“相等值導(dǎo)致的并列選擇”。三個(gè)都能頂住才敢用。典型的貪心場景包括區(qū)間調(diào)度按結(jié)束時(shí)間排序、分發(fā)餅干雙指針匹配、跳躍游戲維護(hù)最遠(yuǎn)可達(dá)位置。這些問題的共性是存在一個(gè)明確的“排序依據(jù)”排完序之后每一步的最優(yōu)選擇都是確定的。如果沒有明確的排序依據(jù)或者排序依據(jù)需要反復(fù)調(diào)整那多半不是貪心。提示寫完貪心不要急著提交先用小規(guī)模數(shù)據(jù)暴力枚舉所有方案和貪心結(jié)果對比。這一步花不了五分鐘但能省掉一次返工。5. 圖論與字符串工程里真正會碰到的部分5.1 圖遍歷與最短路的選擇圖的表示我一般只用兩種鄰接表用dict[list]存適合稀疏圖鄰接矩陣用二維列表存適合稠密圖或者需要 O(1) 判斷兩點(diǎn)是否相鄰的場景。絕大多數(shù)業(yè)務(wù)問題是稀疏圖所以鄰接表用得最多。BFS 和 DFS 的選擇取決于你要什么。求最短步數(shù)用 BFS因?yàn)樗前磳訑U(kuò)展的第一次訪問到目標(biāo)時(shí)路徑一定最短求所有路徑、做連通性判斷、做拓?fù)渑判蛴?DFS因?yàn)樗倪f歸結(jié)構(gòu)天然適合回溯。這里有個(gè)細(xì)節(jié)BFS 的 visited 標(biāo)記必須在入隊(duì)時(shí)就打上不能等出隊(duì)才打否則同一個(gè)節(jié)點(diǎn)可能被重復(fù)入隊(duì)隊(duì)列會急劇膨脹。這個(gè)錯(cuò)誤在網(wǎng)格類問題上特別常見。Dijkstra 是帶權(quán)最短路的默認(rèn)選擇用heapq實(shí)現(xiàn)優(yōu)先隊(duì)列復(fù)雜度 O((VE) log V)。它的前提是邊權(quán)非負(fù)一旦出現(xiàn)負(fù)權(quán)就必須換 Bellman-Ford 或 SPFA。這一點(diǎn)在實(shí)際項(xiàng)目里要特別注意因?yàn)椤柏?fù)數(shù)權(quán)重”往往不會寫在需求里而是從數(shù)據(jù)里冒出來的。import heapq def dijkstra(graph, start): dist {node: float(inf) for node in graph} dist[start] 0 heap [(0, start)] while heap: d, u heapq.heappop(heap) if d dist[u]: continue # 過期數(shù)據(jù)直接跳過 for v, w in graph[u]: nd d w if nd dist[v]: dist[v] nd heapq.heappush(heap, (nd, v)) return distif d dist[u]: continue這一行是懶刪除的關(guān)鍵。Python 的heapq不支持修改堆中元素的優(yōu)先級所以每次更新距離就重新 push 一份堆里會有歷史數(shù)據(jù)。不做這個(gè)判斷算法仍然正確但會多做很多無用功。5.2 字符串匹配什么時(shí)候該手寫 KMPPython 的str.find和in操作底層是高效的字符串匹配實(shí)現(xiàn)日常開發(fā)直接用它就行。手寫 KMP 的意義在于理解“失配時(shí)利用已有信息”這個(gè)思想以及處理一些內(nèi)置函數(shù)覆蓋不到的需求比如“求所有匹配位置”、“求最小循環(huán)節(jié)”、“求字符串的 border 結(jié)構(gòu)”。KMP 的核心是next數(shù)組也叫失配數(shù)組它記錄的是“到當(dāng)前位置為止前綴和后綴相等的最大長度”。構(gòu)造next的過程本身就是一次自我匹配這一步是整段代碼里最難理解的部分。def build_next(p): nxt [0] * len(p) k 0 for i in range(1, len(p)): while k 0 and p[i] ! p[k]: k nxt[k - 1] if p[i] p[k]: k 1 nxt[i] k return nxt def kmp_search(s, p): if not p: return 0 nxt build_next(p) k 0 for i, ch in enumerate(s): while k 0 and ch ! p[k]: k nxt[k - 1] if ch p[k]: k 1 if k len(p): return i - len(p) 1 return -1k nxt[k - 1]這個(gè)回退動(dòng)作是 KMP 的靈魂。它的含義是“當(dāng)前這個(gè)前綴已經(jīng)對不上了退而求其次看看更短的前綴還能不能對上”。理解了這句話next數(shù)組的構(gòu)造就不需要死記了。6. 常見問題與排查技巧實(shí)錄6.1 復(fù)雜度誤判與性能陷阱最常見的誤判是把“嵌套循環(huán)”直接等同于 O(n2)。實(shí)際上要看內(nèi)層循環(huán)的執(zhí)行次數(shù)總和比如雙指針、單調(diào)棧這些寫法外層是循環(huán)、內(nèi)層是 while但內(nèi)層指針不會回退總執(zhí)行次數(shù)是 O(n)。判斷方法是看“指針是否有單調(diào)性”單調(diào)就是均攤分析不單調(diào)就得老實(shí)算。第二個(gè)高頻陷阱是隱性復(fù)雜度。list.pop(0)是 O(n)在循環(huán)里做就成了 O(n2)x in list是 O(n)換成set就是 O(1)字符串拼接s ch在循環(huán)里是 O(n2)換成.join(parts)是 O(n)。這些問題不會報(bào)錯(cuò)只會讓程序在數(shù)據(jù)量上來之后突然變慢排查起來非常費(fèi)勁。第三個(gè)是遞歸深度。Python 默認(rèn)遞歸深度限制是 1000 左右DFS 遍歷深度較大的樹或圖時(shí)很容易觸發(fā)RecursionError。解決方案要么改成顯式棧的迭代寫法要么用sys.setrecursionlimit調(diào)大限制但后者要配合更大的?？臻g才有意義否則可能直接段錯(cuò)誤?，F(xiàn)象可能原因排查手段數(shù)據(jù)量小時(shí)正常大了就超時(shí)隱性 O(n2)定位內(nèi)層操作看是否有in list、pop(0)、字符串拼接結(jié)果偶爾不對復(fù)現(xiàn)困難相等元素的處理順序用固定隨機(jī)種子跑多組數(shù)據(jù)重點(diǎn)查比較條件里的和程序直接退出無報(bào)錯(cuò)遞歸過深或內(nèi)存溢出加sys.setrecursionlimit或改成迭代哈希結(jié)構(gòu)查不到數(shù)據(jù)自定義類未正確實(shí)現(xiàn)__hash__打印hash(obj)和obj obj2的結(jié)果圖算法結(jié)果偏大邊權(quán)出現(xiàn)負(fù)數(shù)打印最小邊權(quán)負(fù)權(quán)換 Bellman-Ford6.2 我的幾個(gè)實(shí)操心得第一個(gè)心得每寫完一個(gè)算法用三組數(shù)據(jù)驗(yàn)證——空輸入、單元素、含重復(fù)元素。這三組能擋住 80% 的邊界錯(cuò)誤?？蛰斎肟简?yàn)的是提前返回單元素考驗(yàn)的是循環(huán)條件重復(fù)元素考驗(yàn)的是比較符號。第二個(gè)心得不要在沒有性能需求的時(shí)候做“提前優(yōu)化”。我見過有人把所有查找都改成手寫二分結(jié)果代碼可讀性大幅下降而實(shí)際數(shù)據(jù)量只有幾百條in操作完全夠用。算法的選擇要看數(shù)據(jù)規(guī)模n 小于 1000 的時(shí)候常數(shù)因子比復(fù)雜度更重要。第三個(gè)心得復(fù)雜度分析最好寫成注釋。寫# O(n log n)排序 單次遍歷這種比只寫# 排序有用得多。過幾個(gè)月回頭看你能立刻想起當(dāng)時(shí)的取舍理由。第四個(gè)心得動(dòng)態(tài)規(guī)劃的調(diào)試不要靠打印整個(gè) dp 表先手動(dòng)推演前三個(gè)狀態(tài)確認(rèn)初始值對了再看轉(zhuǎn)移方程。絕大多數(shù) DP 的 bug 都在初始值而不是轉(zhuǎn)移方程。第五個(gè)心得圖論題目先把圖畫出來標(biāo)上節(jié)點(diǎn)和邊權(quán)再動(dòng)筆寫代碼。直接在腦子里推演圖的遍歷順序出錯(cuò)概率非常高而且錯(cuò)了很難定位。7. 一個(gè)補(bǔ)充算法清單的練習(xí)節(jié)奏最后分享一點(diǎn)關(guān)于練習(xí)節(jié)奏的體會。我自己的習(xí)慣是每個(gè)模塊只精做五到八道題做完之后隔一周再重寫一遍不看之前代碼。第二遍能獨(dú)立寫出來的才算真的會了寫不出來的說明當(dāng)時(shí)是靠記憶而不是靠理解。排序和二分屬于“必須肌肉記憶”的部分快排模板、二分模板、并查集模板這幾個(gè)要能做到提筆就寫。動(dòng)態(tài)規(guī)劃和圖論屬于“必須理解思路”的部分代碼可以查但狀態(tài)定義和算法選擇必須自己想清楚。字符串算法屬于“知道有這個(gè)東西就行”的部分真要用的時(shí)候再翻文檔沒必要全部背下來。這套清單我前后改過三四版刪掉了很多“考試會考但實(shí)際用不上”的內(nèi)容比如 AVL 樹的完整旋轉(zhuǎn)實(shí)現(xiàn)、紅黑樹的插入刪除這些了解概念即可。留下來的都是會在實(shí)際代碼里反復(fù)出現(xiàn)的或者是在技術(shù)討論中必須能講清楚的。要是你正在按某個(gè)“大全”清單從頭刷不妨先停下來看看自己真正需要的是哪一部分把有限的時(shí)間投在出錯(cuò)代價(jià)最高的地方。