1. 算法面試精講數(shù)組旋轉(zhuǎn)、股票買賣與鏈表操作實(shí)戰(zhàn)今天要拆解的三道經(jīng)典算法題恰好覆蓋了面試中最常出現(xiàn)的三大數(shù)據(jù)結(jié)構(gòu)數(shù)組、動(dòng)態(tài)規(guī)劃和鏈表。189題考察數(shù)組旋轉(zhuǎn)的多種解法121題是動(dòng)態(tài)規(guī)劃的入門必刷題19題則檢驗(yàn)對(duì)鏈表指針操作的熟練度。這三道題在各大廠面試中出現(xiàn)頻率極高掌握它們能顯著提升面試通過(guò)率。我在面試候選人和被面試的過(guò)程中發(fā)現(xiàn)很多工程師對(duì)這類基礎(chǔ)題存在一看就會(huì)一寫就廢的情況。本文將結(jié)合代碼實(shí)現(xiàn)、復(fù)雜度分析和實(shí)際面試案例帶大家徹底吃透這三道題的核心考點(diǎn)。無(wú)論你是準(zhǔn)備面試的新手還是想鞏固基礎(chǔ)的資深工程師都能從中獲得可直接復(fù)用的解題模板。2. 189. Rotate Array - 數(shù)組旋轉(zhuǎn)的三種解法對(duì)比2.1 問(wèn)題重述與邊界條件給定一個(gè)整數(shù)數(shù)組nums將數(shù)組向右旋轉(zhuǎn)k個(gè)位置其中k是非負(fù)數(shù)。要求使用O(1)的額外空間原地修改。關(guān)鍵邊界條件當(dāng)k大于數(shù)組長(zhǎng)度時(shí)實(shí)際有效旋轉(zhuǎn)次數(shù)是k % nums.length空數(shù)組或單元素?cái)?shù)組旋轉(zhuǎn)后不變需要處理k0的特殊情況實(shí)際面試中約30%的候選人會(huì)忽略k大于數(shù)組長(zhǎng)度的情況這是面試官常設(shè)的陷阱。2.2 暴力解法與優(yōu)化思路最直觀的方法是每次旋轉(zhuǎn)一個(gè)元素重復(fù)k次def rotate(nums, k): n len(nums) k % n for _ in range(k): previous nums[-1] for i in range(n): nums[i], previous previous, nums[i]時(shí)間復(fù)雜度O(n*k)空間復(fù)雜度O(1)。當(dāng)n較大時(shí)性能極差但適合作為討論優(yōu)化的起點(diǎn)。2.3 三次反轉(zhuǎn)法推薦這是最優(yōu)的原地解法def rotate(nums, k): def reverse(start, end): while start end: nums[start], nums[end] nums[end], nums[start] start 1 end - 1 n len(nums) k % n reverse(0, n-1) # 反轉(zhuǎn)整個(gè)數(shù)組 reverse(0, k-1) # 反轉(zhuǎn)前k個(gè) reverse(k, n-1) # 反轉(zhuǎn)剩余部分時(shí)間復(fù)雜度O(n)空間復(fù)雜度O(1)。關(guān)鍵在于理解反轉(zhuǎn)順序整體反轉(zhuǎn)[1,2,3,4,5] → [5,4,3,2,1]前k個(gè)反轉(zhuǎn)[5,4,3,2,1] → [4,5,3,2,1] (k2)剩余反轉(zhuǎn)[4,5,3,2,1] → [4,5,1,2,3]2.4 環(huán)狀替換法的陷阱另一種思路是將元素直接放到最終位置def rotate(nums, k): n len(nums) k % n start count 0 while count n: current, prev start, nums[start] while True: next_idx (current k) % n nums[next_idx], prev prev, nums[next_idx] current next_idx count 1 if start current: break start 1雖然也是O(n)時(shí)間但實(shí)現(xiàn)復(fù)雜且容易出錯(cuò)。面試時(shí)除非特別要求建議優(yōu)先使用反轉(zhuǎn)法。3. 121. Best Time to Buy and Sell Stock - 動(dòng)態(tài)規(guī)劃入門3.1 問(wèn)題建模給定數(shù)組prices其中prices[i]是某股票第i天的價(jià)格。只能完成一次交易買一次賣一次求最大利潤(rùn)。示例 輸入[7,1,5,3,6,4] 輸出5第2天買入第5天賣出3.2 暴力解法的局限雙重循環(huán)枚舉所有買賣組合def maxProfit(prices): max_profit 0 for i in range(len(prices)): for j in range(i1, len(prices)): profit prices[j] - prices[i] if profit max_profit: max_profit profit return max_profit時(shí)間復(fù)雜度O(n2)在LeetCode上會(huì)超時(shí)。需要更優(yōu)解法。3.3 動(dòng)態(tài)規(guī)劃思路維護(hù)兩個(gè)變量min_price遍歷過(guò)程中的最低價(jià)max_profit當(dāng)前能獲得的最大利潤(rùn)def maxProfit(prices): min_price float(inf) max_profit 0 for price in prices: if price min_price: min_price price elif price - min_price max_profit: max_profit price - min_price return max_profit時(shí)間復(fù)雜度O(n)空間復(fù)雜度O(1)。這是動(dòng)態(tài)規(guī)劃的簡(jiǎn)化形式本質(zhì)上是在遍歷時(shí)不斷更新?tīng)顟B(tài)。3.4 常見(jiàn)錯(cuò)誤分析沒(méi)有處理空數(shù)組情況應(yīng)返回0將max_profit初始化為極小負(fù)數(shù)而非0股票可以不買把min_price更新和max_profit更新放在同一個(gè)if分支邏輯錯(cuò)誤4. 19. Remove Nth Node From End of List - 鏈表雙指針技巧4.1 問(wèn)題描述給定一個(gè)鏈表刪除鏈表的倒數(shù)第n個(gè)節(jié)點(diǎn)并返回頭節(jié)點(diǎn)。示例 輸入1-2-3-4-5, n2 輸出1-2-3-54.2 雙指針解法使用快慢指針快指針先走n步def removeNthFromEnd(head, n): dummy ListNode(0) dummy.next head fast slow dummy for _ in range(n): fast fast.next while fast.next: slow slow.next fast fast.next slow.next slow.next.next return dummy.next時(shí)間復(fù)雜度O(L)空間復(fù)雜度O(1)其中L是鏈表長(zhǎng)度。4.3 邊界條件處理使用dummy節(jié)點(diǎn)處理刪除頭節(jié)點(diǎn)的情況確保n不超過(guò)鏈表長(zhǎng)度題目通常保證鏈表長(zhǎng)度為1時(shí)刪除后返回None4.4 遞歸解法了解即可雖然可以遞歸解決但空間復(fù)雜度O(L)def removeNthFromEnd(head, n): def remove(node): if not node: return 0, node i, node.next remove(node.next) return i1, (node, node.next)[i1 n] return remove(head)[1]面試中通常要求最優(yōu)解遞歸可作為備選方案討論。5. 面試實(shí)戰(zhàn)技巧與組合題5.1 面試回答策略先確認(rèn)題目條件和邊界如k是否可能大于數(shù)組長(zhǎng)度從暴力解法開(kāi)始逐步優(yōu)化解釋每種解法的時(shí)間/空間復(fù)雜度最后選擇最優(yōu)解法實(shí)現(xiàn)5.2 常見(jiàn)follow-up問(wèn)題Rotate Array 如果要求左旋轉(zhuǎn)怎么做 → 反轉(zhuǎn)順序變?yōu)楹髇-k個(gè)→前k個(gè)→整體Best Time to Buy and Sell Stock 如果可以交易多次呢 → 貪心法累加所有上升段Remove Nth Node 不用dummy節(jié)點(diǎn)怎么處理 → 需要額外判斷頭節(jié)點(diǎn)情況5.3 組合題示例給定一個(gè)價(jià)格序列你可以在旋轉(zhuǎn)后的任意位置買入賣出一次求最大可能利潤(rùn)解法思路找出旋轉(zhuǎn)點(diǎn)類似旋轉(zhuǎn)數(shù)組問(wèn)題將數(shù)組分為兩個(gè)有序部分分別在兩部分用股票問(wèn)題的解法比較兩種情況的利潤(rùn)取最大值6. 代碼模板與記憶要點(diǎn)6.1 旋轉(zhuǎn)數(shù)組模板def rotate(nums, k): k % len(nums) nums.reverse() nums[:k] reversed(nums[:k]) nums[k:] reversed(nums[k:])6.2 股票問(wèn)題模板def maxProfit(prices): min_price float(inf) max_profit 0 for price in prices: min_price min(min_price, price) max_profit max(max_profit, price - min_price) return max_profit6.3 鏈表刪除模板def removeNthFromEnd(head, n): dummy ListNode(0, head) slow fast dummy for _ in range(n): fast fast.next while fast.next: slow, fast slow.next, fast.next slow.next slow.next.next return dummy.next6.4 復(fù)雜度對(duì)比表題目最優(yōu)解法時(shí)間復(fù)雜度空間復(fù)雜度189三次反轉(zhuǎn)O(n)O(1)121動(dòng)態(tài)規(guī)劃O(n)O(1)19雙指針O(L)O(1)7. 避坑指南與調(diào)試技巧7.1 旋轉(zhuǎn)數(shù)組常見(jiàn)bug忘記處理kn的情況 → 添加k % n反轉(zhuǎn)區(qū)間寫錯(cuò) → 記住是[0,k-1]和[k,n-1]修改了原數(shù)組但忘記返回 → 注意題目是否要求返回void7.2 股票問(wèn)題調(diào)試要點(diǎn)初始化min_price為INFmax_profit為0先更新min_price再計(jì)算profit空數(shù)組直接返回07.3 鏈表問(wèn)題調(diào)試技巧使用dummy節(jié)點(diǎn)避免頭節(jié)點(diǎn)特殊處理畫圖輔助理解指針移動(dòng)測(cè)試用例要包含刪除頭節(jié)點(diǎn)刪除尾節(jié)點(diǎn)單節(jié)點(diǎn)鏈表常規(guī)情況我在面試中遇到過(guò)一位候選人在旋轉(zhuǎn)數(shù)組問(wèn)題上花了20分鐘調(diào)試最后發(fā)現(xiàn)是因?yàn)樵赑ython中直接對(duì)切片賦值創(chuàng)建了新對(duì)象而非原地修改。正確的做法是使用nums[:] reversed(nums[:])或者按照我們之前的分段反轉(zhuǎn)方法。這種語(yǔ)言特性造成的陷阱特別值得注意。