1. 六道題為什么值得反復(fù)做從刷完到刷透的分水嶺面試算法題這個東西很多人刷了幾百道真到面試現(xiàn)場還是卡殼。問題不在于題量而在于有沒有把一類題做透。我前后帶過幾個準(zhǔn)備校招的朋友也自己復(fù)盤過不少次面試經(jīng)歷發(fā)現(xiàn)一個規(guī)律真正拉開差距的不是誰刷的題多而是誰能把一組有代表性的題吃干榨凈從每道題里抽出可遷移的思維模型。這次拿到的六道題來源是常見的面試題庫平臺覆蓋了鏈表、二叉樹、動態(tài)規(guī)劃、雙指針、棧與隊列這幾大高頻板塊。它們看起來是六道獨立的題但如果你只把它們當(dāng)成六個孤立的練習(xí)做完就忘那基本等于白做。我的做法是把六道題當(dāng)成一個最小完備集每道題都追問三個問題——這道題考的是什么底層能力它的暴力解和最優(yōu)解差在哪里如果面試官把條件改一改我還能不能接住這篇文章就是圍繞這三個問題展開的。我會逐題拆解思路、給出可運行的代碼、標(biāo)注容易踩的坑更重要的是分享我在實際做題和面試中總結(jié)出來的遷移套路。適合正在準(zhǔn)備技術(shù)面試的在校生、想跳槽的開發(fā)者也適合單純想把算法基本功重新?lián)炱饋淼娜?。哪怕你現(xiàn)在連鏈表和數(shù)組的區(qū)別都說不利索跟著走一遍也能有收獲因為我會把每一步的為什么講清楚而不是甩一段代碼讓你自己悟。先說一個總的原則面試算法題考的不是你會不會寫代碼而是你能不能在有限時間內(nèi)把一個模糊問題拆成清晰的步驟并且用代碼準(zhǔn)確表達(dá)出來。所以刷題時最忌諱的就是看一眼題解哦原來是這樣下一道。正確的姿勢是先自己想卡住了記錄卡在哪再看題解然后合上題解自己重寫一遍最后隔兩天再默寫一遍。這六道題我就是按這個流程過的下面逐一說。2. 鏈表類題目的通用拆解框架2.1 鏈表題為什么總在指針上翻車鏈表題是面試?yán)锏某？鸵驗樗貏e能暴露一個人對指針操作的理解深度。數(shù)組你可以靠下標(biāo)隨便訪問鏈表不行你只能順著 next 指針一格一格走。很多人寫鏈表題翻車根本原因就一個在移動指針之前沒有先把下一步需要的信息保存下來。舉個最常見的場景——反轉(zhuǎn)鏈表。新手容易寫成這樣讓當(dāng)前節(jié)點的 next 指向前一個節(jié)點然后想移動到下一個節(jié)點結(jié)果發(fā)現(xiàn)下一個節(jié)點已經(jīng)找不到了因為它的指針剛被你改掉了。這就是典型的順序錯誤。正確的做法是三步走先存下一個節(jié)點再改當(dāng)前節(jié)點的指向最后移動前驅(qū)和當(dāng)前指針。這個先存后改再移的口訣幾乎能套用到所有鏈表指針操作題上。我在實際做題時養(yǎng)成了一個習(xí)慣每寫一行涉及指針賦值的代碼就在腦子里畫一遍當(dāng)前鏈表的狀態(tài)。畫不了就說明你沒想清楚。這個習(xí)慣幫我避開了至少一半的鏈表 bug。2.2 反轉(zhuǎn)鏈表的迭代與遞歸兩套寫法反轉(zhuǎn)鏈表這道題迭代和遞歸兩種寫法都得會因為面試官經(jīng)常追問你能用遞歸再寫一遍嗎。迭代版本的核心就是三個指針prev前驅(qū)、curr當(dāng)前、next暫存。初始時 prev 為空curr 指向頭節(jié)點。循環(huán)體里先把 curr.next 存到 next再把 curr.next 指向 prev然后 prev 移到 currcurr 移到 next。循環(huán)結(jié)束時 curr 為空prev 就是新的頭節(jié)點。def reverse_list(head): prev None curr head while curr: next_node curr.next # 先存 curr.next prev # 再改 prev curr # 后移 curr next_node return prev遞歸版本稍微繞一點但理解了就很簡單。遞歸的思路是假設(shè)從第二個節(jié)點開始往后的部分已經(jīng)反轉(zhuǎn)好了我只需要把第二個節(jié)點的 next 指向頭節(jié)點頭節(jié)點的 next 指向空然后返回新的頭節(jié)點。def reverse_list_recursive(head): if not head or not head.next: return head new_head reverse_list_recursive(head.next) head.next.next head head.next None return new_head這里有個坑head.next None這行千萬別漏。漏了的話原來的頭節(jié)點和第二個節(jié)點之間會形成環(huán)整個鏈表就廢了。我見過不少人遞歸寫對了大半就栽在這一行上。2.3 快慢指針鏈表題的萬能鑰匙除了反轉(zhuǎn)鏈表題里另一個高頻套路是快慢指針。判斷鏈表有沒有環(huán)、找鏈表中點、找倒數(shù)第 k 個節(jié)點全靠它。判斷有環(huán)的邏輯很直觀快指針每次走兩步慢指針每次走一步。如果鏈表有環(huán)快指針一定會在環(huán)里追上慢指針如果沒環(huán)快指針會先走到空。這個追上的直覺很好理解——就像兩個人在環(huán)形跑道上跑步跑得快的人遲早會從后面追上慢的人。找中點也是同理快指針走到頭的時候慢指針剛好在中間。這里有個細(xì)節(jié)要注意當(dāng)節(jié)點數(shù)是偶數(shù)時快慢指針的初始化方式?jīng)Q定了慢指針最終停在前半段的最后一個還是后半段的第一個。這個差異在做重排鏈表這類題時非常關(guān)鍵寫之前一定要想清楚你要的是哪個。提示快慢指針的初始化常見有兩種——都從頭節(jié)點出發(fā)或者快指針先走一步。選哪種取決于題目要求的中點是偏左還是偏右別死記畫個四節(jié)點和五節(jié)點的鏈表自己推一遍就明白了。3. 二叉樹遍歷遞歸思維與迭代實現(xiàn)的取舍3.1 前中后序遍歷的遞歸本質(zhì)二叉樹是算法面試的另一座大山。前序、中序、后序遍歷遞歸寫法幾乎是本能反應(yīng)因為它們的定義本身就是遞歸的前序是根左右中序是左根右后序是左右根。你只要把訪問根節(jié)點的位置換一下三行代碼就能切換三種遍歷。def inorder(root): if not root: return inorder(root.left) # 左 print(root.val) # 根 inorder(root.right) # 右遞歸寫法的好處是簡潔、不易出錯壞處是當(dāng)樹很深時會爆棧。所以面試官經(jīng)常會追問能用迭代寫嗎這時候就考驗?zāi)銓f歸本質(zhì)上是棧這句話的理解了。3.2 用顯式棧模擬遞歸調(diào)用迭代實現(xiàn)遍歷核心是用一個棧來模擬系統(tǒng)調(diào)用棧。前序遍歷最簡單先把根壓棧然后循環(huán)彈出節(jié)點、訪問、再把右孩子和左孩子依次壓棧注意順序因為棧是后進先出想先訪問左孩子就得后壓左孩子。中序遍歷稍微難一點因為要先一路走到最左邊。思路是用一個指針從根開始只要指針不為空就壓棧并往左走指針為空了就彈出棧頂訪問然后轉(zhuǎn)向右孩子。def inorder_iterative(root): stack [] curr root while curr or stack: while curr: stack.append(curr) curr curr.left curr stack.pop() print(curr.val) curr curr.right后序遍歷的迭代是最繞的因為它要求左右根而棧天然適合處理根左右。有個取巧的辦法按根右左的順序遍歷最后把結(jié)果反轉(zhuǎn)就得到左右根了。這個技巧我第一次見的時候覺得挺妙后來發(fā)現(xiàn)面試?yán)镉贸鰜砻嬖嚬偻鶗c頭。3.3 層序遍歷與BFS的邊界處理層序遍歷用的是隊列而不是棧屬于廣度優(yōu)先搜索BFS。它的經(jīng)典寫法是每輪循環(huán)先記錄當(dāng)前隊列的長度這個長度就是當(dāng)前層的節(jié)點數(shù)然后一次性處理完這一層的所有節(jié)點把它們的左右孩子入隊。from collections import deque def level_order(root): if not root: return [] result [] queue deque([root]) while queue: level_size len(queue) level [] for _ in range(level_size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result這里的關(guān)鍵是level_size len(queue)這一行。如果你不記錄這個長度直接while queue里逐個處理就沒法區(qū)分哪些節(jié)點屬于同一層。這個分層的技巧在二叉樹的最大寬度鋸齒形層序遍歷等題里都會用到值得單獨記一下。注意層序遍歷里判斷左右孩子是否存在再入隊比入隊后再判斷空要清晰。雖然兩種寫法都對但前者能少一次循環(huán)內(nèi)的空判斷代碼也更易讀。4. 動態(tài)規(guī)劃從暴力遞歸到狀態(tài)轉(zhuǎn)移的進化路徑4.1 動態(tài)規(guī)劃到底在規(guī)劃什么動態(tài)規(guī)劃DP是很多人面試時的噩夢因為它不像鏈表、二叉樹那樣有直觀的圖形可以畫。但其實 DP 的核心思想非常樸素如果一個問題的解可以由它的子問題的解推導(dǎo)出來并且這些子問題會被重復(fù)計算那就把子問題的解存起來避免重復(fù)勞動。理解 DP 最好的路徑是三步走先寫出暴力遞歸再發(fā)現(xiàn)重疊子問題最后用記憶化或遞推消除重復(fù)計算。跳過第一步直接看狀態(tài)轉(zhuǎn)移方程是很多人學(xué)不會 DP 的根本原因——你連暴力解都沒想清楚怎么可能直接寫出優(yōu)化解4.2 爬樓梯與斐波那契DP的入門模型爬樓梯是最經(jīng)典的 DP 入門題每次可以爬 1 階或 2 階問爬到第 n 階有多少種方法。暴力遞歸的思路是到達(dá)第 n 階要么從第 n-1 階爬 1 階上來要么從第 n-2 階爬 2 階上來所以f(n) f(n-1) f(n-2)。但直接遞歸會重復(fù)計算大量子問題時間復(fù)雜度是指數(shù)級的。用記憶化自頂向下或者遞推自底向上就能降到 O(n)。def climb_stairs(n): if n 2: return n prev, curr 1, 2 for _ in range(3, n 1): prev, curr curr, prev curr return curr這里用兩個變量滾動更新把空間復(fù)雜度壓到了 O(1)。這個滾動數(shù)組的技巧在 DP 里非常常用只要狀態(tài)轉(zhuǎn)移只依賴前幾個狀態(tài)就能用有限變量代替整個數(shù)組。4.3 狀態(tài)定義與轉(zhuǎn)移方程DP的兩大命門DP 題難難在兩件事狀態(tài)怎么定義轉(zhuǎn)移方程怎么寫。狀態(tài)定義決定了你的 dp 數(shù)組每個位置代表什么含義轉(zhuǎn)移方程決定了這些位置之間怎么推導(dǎo)。以最長遞增子序列為例。狀態(tài)定義是dp[i]表示以第 i 個元素結(jié)尾的最長遞增子序列長度。轉(zhuǎn)移方程是對于每個 i遍歷它前面所有的 j如果nums[j] nums[i]那么dp[i] max(dp[i], dp[j] 1)。最后答案是 dp 數(shù)組里的最大值而不是 dp[n-1]因為最長遞增子序列不一定以最后一個元素結(jié)尾。def length_of_lis(nums): if not nums: return 0 dp [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)這個 O(n2) 的解法面試?yán)飰蛴昧说绻嬖嚬僖髢?yōu)化到 O(n log n)就得用貪心 二分查找的思路維護一個遞增的輔助數(shù)組。這個進階解法我建議先理解 O(n2) 版本再去看優(yōu)化否則容易兩頭都記不牢。提示寫 DP 時先確定答案對應(yīng) dp 數(shù)組的哪個位置。很多題答案是 dp[n-1]但像最長遞增子序列、最大子數(shù)組和這類題答案是整個 dp 數(shù)組的最值。這個細(xì)節(jié)錯了代碼邏輯再對也拿不到分。5. 雙指針與滑動窗口把O(n2)降到O(n)的實戰(zhàn)套路5.1 雙指針的兩種形態(tài)對撞與同向雙指針是性價比極高的技巧因為它往往能把 O(n2) 的暴力解優(yōu)化到 O(n)。它有兩種典型形態(tài)對撞指針一個從頭、一個從尾向中間靠攏和同向指針兩個指針都從頭出發(fā)一快一慢。對撞指針的經(jīng)典應(yīng)用是兩數(shù)之和有序數(shù)組和盛最多水的容器。以兩數(shù)之和為例數(shù)組有序的前提下左指針指向最小值右指針指向最大值如果兩數(shù)之和小于目標(biāo)左指針右移大于目標(biāo)右指針左移。這樣每次移動都能排除掉一整行或一整列的可能性所以是 O(n)。同向指針的經(jīng)典應(yīng)用是刪除有序數(shù)組中的重復(fù)項和移動零。核心思路是用一個慢指針維護已處理好的區(qū)域快指針負(fù)責(zé)掃描?？熘羔樣龅椒蠗l件的元素就把它放到慢指針的位置慢指針前進。5.2 滑動窗口處理子串子數(shù)組問題的利器滑動窗口本質(zhì)上是同向雙指針的一種特化專門用來處理連續(xù)子數(shù)組/子串的問題。它的模板非常固定右指針不斷擴張窗口當(dāng)窗口不滿足條件時左指針收縮窗口過程中記錄答案。以無重復(fù)字符的最長子串為例。右指針向右擴展把字符加入窗口如果遇到重復(fù)字符左指針就向右移動直到窗口內(nèi)不再有重復(fù)。用一個哈希集合記錄窗口內(nèi)的字符就能在 O(1) 時間內(nèi)判斷重復(fù)。def length_of_longest_substring(s): char_set set() left 0 max_len 0 for right in range(len(s)): while s[right] in char_set: char_set.remove(s[left]) left 1 char_set.add(s[right]) max_len max(max_len, right - left 1) return max_len這個模板的通用性極強把判斷窗口是否合法和更新答案這兩處換掉就能解一大類題。我建議把這個模板背下來面試時能省不少思考時間。5.3 窗口收縮時機的判斷邏輯滑動窗口最容易出錯的地方是什么時候收縮左指針。有的題要求窗口恰好滿足某條件有的題要求不滿足就收縮這兩種邏輯寫起來差別很大。我的經(jīng)驗是先明確窗口的合法狀態(tài)是什么。對于最長類問題通常是窗口不合法時收縮對于最短類問題通常是窗口合法時收縮并記錄答案。這個區(qū)分想清楚了代碼結(jié)構(gòu)就清晰了。注意滑動窗口里right - left 1是窗口長度這個 1 千萬別漏。我見過太多人因為漏了這個 1答案永遠(yuǎn)差一位debug 半天才發(fā)現(xiàn)。6. 棧與隊列看似簡單卻暗藏玄機的數(shù)據(jù)結(jié)構(gòu)6.1 用棧實現(xiàn)隊列與用隊列實現(xiàn)棧用兩個棧實現(xiàn)隊列和用兩個隊列實現(xiàn)棧是考察對這兩種數(shù)據(jù)結(jié)構(gòu)本質(zhì)理解的經(jīng)典題。棧是后進先出隊列是先進先出要用一種模擬另一種核心在于倒騰數(shù)據(jù)。用兩個棧實現(xiàn)隊列一個入棧push 時用一個出棧pop 時用。入隊時直接壓入入棧出隊時如果出棧為空就把入棧的所有元素依次彈出并壓入出棧這樣順序就反過來了再從出棧彈出即可。class MyQueue: def __init__(self): self.in_stack [] self.out_stack [] def push(self, x): self.in_stack.append(x) def pop(self): if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack.pop()這個倒騰操作有個關(guān)鍵性質(zhì)每個元素最多被倒騰一次所以均攤時間復(fù)雜度是 O(1)。面試時如果被問到時間復(fù)雜度一定要說均攤而不是簡單說 O(1) 或 O(n)這個細(xì)節(jié)能體現(xiàn)你的嚴(yán)謹(jǐn)。6.2 單調(diào)棧下一個更大元素的通用解法單調(diào)棧是棧的一個高級應(yīng)用專門解決下一個更大/更小元素這類問題。它的核心是維護一個單調(diào)遞增或遞減的棧當(dāng)新元素破壞單調(diào)性時就彈出棧頂并記錄答案。以每日溫度為例給定一個溫度數(shù)組求每一天要等多少天才能遇到更高的溫度。用單調(diào)遞減棧棧里存的是下標(biāo)。遍歷溫度數(shù)組當(dāng)當(dāng)前溫度大于棧頂下標(biāo)對應(yīng)的溫度時說明棧頂那天找到了下一個更高溫度彈出并計算天數(shù)差。def daily_temperatures(temperatures): n len(temperatures) answer [0] * n stack [] for i in range(n): while stack and temperatures[i] temperatures[stack[-1]]: prev stack.pop() answer[prev] i - prev stack.append(i) return answer單調(diào)棧的難點在于想清楚棧里存什么、什么時候彈。我的經(jīng)驗是棧里存下標(biāo)而不是值因為很多時候需要計算距離彈出時機就是找到了答案的時機。把這兩點想清楚單調(diào)棧的題基本都能套。6.3 有效括號棧的入門必修課有效括號是棧最基礎(chǔ)的應(yīng)用但基礎(chǔ)不代表簡單。它的邏輯是遇到左括號就壓棧遇到右括號就看棧頂是不是對應(yīng)的左括號是就彈出不是或棧空就返回 false。遍歷結(jié)束后棧必須為空。def is_valid(s): mapping {): (, ]: [, }: {} stack [] for char in s: if char in mapping: top stack.pop() if stack else # if mapping[char] ! top: return False else: stack.append(char) return not stack這里用了一個小技巧用一個字典把右括號映射到對應(yīng)的左括號這樣判斷邏輯就統(tǒng)一了不用寫一堆 if-else。另外stack.pop() if stack else #這個寫法處理了?？盏那闆r用一個不可能匹配的字符占位避免額外的邊界判斷。提示有效括號的變體很多比如最長有效括號刪除最少括號使字符串有效。這些變體的基礎(chǔ)都是這道題把基礎(chǔ)打牢變體就是加一層邏輯的事。7. 六道題背后的通用能力地圖把這六道題拆完你會發(fā)現(xiàn)它們其實在考同一批底層能力只是換了不同的外衣。題目類型核心考察能力可遷移的思維模型鏈表反轉(zhuǎn)指針操作的順序意識先存后改再移二叉樹遍歷遞歸與迭代的轉(zhuǎn)換用棧/隊列模擬調(diào)用棧動態(tài)規(guī)劃狀態(tài)定義與轉(zhuǎn)移推導(dǎo)暴力遞歸到記憶化再到遞推雙指針/滑動窗口排除法的邊界控制用單調(diào)性排除不可能解棧與隊列數(shù)據(jù)結(jié)構(gòu)的本質(zhì)理解用輔助結(jié)構(gòu)倒騰順序單調(diào)棧維護單調(diào)性的時機判斷彈出即找到答案這張表是我自己復(fù)盤時整理的它幫我意識到面試算法題的數(shù)量是無限的但底層思維模型是有限的。與其盲目刷題不如把每個模型吃透遇到新題時先判斷它屬于哪個模型再套用對應(yīng)的套路。我在實際面試中還有一個體會面試官更看重你的思考過程而不是最終代碼。所以做題時一定要邊寫邊說把你的思路、你的猶豫、你的取舍都表達(dá)出來。哪怕最后代碼沒寫完只要思路清晰面試官也會給不錯的評價。反過來悶頭寫完代碼但講不清楚為什么這么寫反而容易被扣分。最后分享一個我自己的練習(xí)方法每做完一道題合上題解用一句話總結(jié)這道題的核心套路是什么然后把它歸類到上面那張表里。堅持一段時間你會發(fā)現(xiàn)自己看到新題時腦子里會自動跳出這題是滑動窗口或者這題得用單調(diào)棧這種條件反射就是刷題刷到位了的標(biāo)志。