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