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