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)對鏈表指針操作的熟練度。這三道題在各大廠面試中出現(xiàn)頻率極高掌握它們能顯著提升面試通過率。我在面試候選人和被面試的過程中發(fā)現(xiàn)很多工程師對這類基礎(chǔ)題存在一看就會一寫就廢的情況。本文將結(jié)合代碼實(shí)現(xiàn)、復(fù)雜度分析和實(shí)際面試案例帶大家徹底吃透這三道題的核心考點(diǎn)。無論你是準(zhǔn)備面試的新手還是想鞏固基礎(chǔ)的資深工程師都能從中獲得可直接復(fù)用的解題模板。2. 189. Rotate Array - 數(shù)組旋轉(zhuǎn)的三種解法對比2.1 問題重述與邊界條件給定一個(gè)整數(shù)數(shù)組nums將數(shù)組向右旋轉(zhuǎn)k個(gè)位置其中k是非負(fù)數(shù)。要求使用O(1)的額外空間原地修改。關(guān)鍵邊界條件當(dāng)k大于數(shù)組長度時(shí)實(shí)際有效旋轉(zhuǎn)次數(shù)是k % nums.length空數(shù)組或單元素?cái)?shù)組旋轉(zhuǎn)后不變需要處理k0的特殊情況實(shí)際面試中約30%的候選人會忽略k大于數(shù)組長度的情況這是面試官常設(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 問題建模給定數(shù)組prices其中prices[i]是某股票第i天的價(jià)格。只能完成一次交易買一次賣一次求最大利潤。示例 輸入[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上會超時(shí)。需要更優(yōu)解法。3.3 動(dòng)態(tài)規(guī)劃思路維護(hù)兩個(gè)變量min_price遍歷過程中的最低價(jià)max_profit當(dāng)前能獲得的最大利潤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ī)劃的簡化形式本質(zhì)上是在遍歷時(shí)不斷更新狀態(tài)。3.4 常見錯(cuò)誤分析沒有處理空數(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 問題描述給定一個(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是鏈表長度。4.3 邊界條件處理使用dummy節(jié)點(diǎn)處理刪除頭節(jié)點(diǎn)的情況確保n不超過鏈表長度題目通常保證鏈表長度為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ù)組長度從暴力解法開始逐步優(yōu)化解釋每種解法的時(shí)間/空間復(fù)雜度最后選擇最優(yōu)解法實(shí)現(xiàn)5.2 常見follow-up問題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)后的任意位置買入賣出一次求最大可能利潤解法思路找出旋轉(zhuǎn)點(diǎn)類似旋轉(zhuǎn)數(shù)組問題將數(shù)組分為兩個(gè)有序部分分別在兩部分用股票問題的解法比較兩種情況的利潤取最大值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 股票問題模板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ù)雜度對比表題目最優(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ù)組常見bug忘記處理kn的情況 → 添加k % n反轉(zhuǎn)區(qū)間寫錯(cuò) → 記住是[0,k-1]和[k,n-1]修改了原數(shù)組但忘記返回 → 注意題目是否要求返回void7.2 股票問題調(diào)試要點(diǎn)初始化min_price為INFmax_profit為0先更新min_price再計(jì)算profit空數(shù)組直接返回07.3 鏈表問題調(diào)試技巧使用dummy節(jié)點(diǎn)避免頭節(jié)點(diǎn)特殊處理畫圖輔助理解指針移動(dòng)測試用例要包含刪除頭節(jié)點(diǎn)刪除尾節(jié)點(diǎn)單節(jié)點(diǎn)鏈表常規(guī)情況我在面試中遇到過一位候選人在旋轉(zhuǎn)數(shù)組問題上花了20分鐘調(diào)試最后發(fā)現(xiàn)是因?yàn)樵赑ython中直接對切片賦值創(chuàng)建了新對象而非原地修改。正確的做法是使用nums[:] reversed(nums[:])或者按照我們之前的分段反轉(zhuǎn)方法。這種語言特性造成的陷阱特別值得注意。