Hot 100里的普通數(shù)組與矩陣專題看起來是整個(gè)清單里最樸素的板塊實(shí)際上卻是面試出場(chǎng)率最高的一批題。我見過太多次這樣的場(chǎng)景面試官先用一道“輪轉(zhuǎn)數(shù)組”或“矩陣置零”熱場(chǎng)然后順著你的實(shí)現(xiàn)一路追問復(fù)雜度與邊界條件。如果你只背過答案而沒想清楚背后的算法思維往往會(huì)在追問環(huán)節(jié)露餡。這篇內(nèi)容不是單純列題解而是把這九道題串成一張“能力圖譜”講清楚每道題在練什么、用什么套路、面試怎么講以及我反復(fù)提交過程中踩過的坑。無論你是剛開始刷題的新人還是準(zhǔn)備沖刺面試的老手普通數(shù)組與矩陣專題都值得單獨(dú)花時(shí)間梳理。它不考復(fù)雜的貪心或深?yuàn)W的圖論卻集中考察幾類最底層的算法能力動(dòng)態(tài)規(guī)劃的狀態(tài)定義、排序后的貪心、原地修改的空間設(shè)計(jì)、邊界收縮的循環(huán)不變量。這些能力是所有后續(xù)難題的“地基”地基不牢遇到真正高難度的題目就會(huì)露怯。1. 這個(gè)專題到底在考什么普通數(shù)組與矩陣的能力圖譜先說一個(gè)很多人忽略的事實(shí)Hot 100里這兩類題加在一起有九道左右數(shù)量并不多但每一道都對(duì)應(yīng)一種獨(dú)立的算法思想幾乎沒有重復(fù)考察同一個(gè)套路的題。這和我最初預(yù)想的“簡單題合集”完全相反。數(shù)組和矩陣本身是最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)正因?yàn)榛A(chǔ)才能在一道題里干凈利落地考察某個(gè)單一算法點(diǎn)不摻雜其他干擾。普通數(shù)組里的五道題分別對(duì)應(yīng)五種不同的能力題目核心考察點(diǎn)最常用解法最大子數(shù)組和動(dòng)態(tài)規(guī)劃狀態(tài)定義一趟掃描維護(hù)“以當(dāng)前元素結(jié)尾”的最大和合并區(qū)間排序 貪心按起點(diǎn)排序逐段合并輪轉(zhuǎn)數(shù)組原地操作的數(shù)學(xué)規(guī)律三次翻轉(zhuǎn)除自身以外數(shù)組的乘積前綴積 / 后綴積兩次遍歷填答案數(shù)組缺失的第一個(gè)正數(shù)原地哈希空間極限利用把每個(gè)數(shù)放到它“該在”的位置上矩陣四道題則更聚焦兩個(gè)方向一個(gè)是“如何用常數(shù)額外空間完成標(biāo)記”典型代表是矩陣置零另一個(gè)是“如何用循環(huán)不變量描述二維遍歷”典型代表是螺旋矩陣、旋轉(zhuǎn)圖像。搜索二維矩陣 II 則把二維問題降維成一維考察的是觀察能力。把這九道題放在一起看能提煉出兩個(gè)共同的底層邏輯。第一絕大多數(shù)數(shù)組題暴力解都很容易想到真正的門檻在于“優(yōu)化空間或優(yōu)化時(shí)間”時(shí)的臨時(shí)狀態(tài)設(shè)計(jì)。比如最大子數(shù)組和暴力枚舉所有子數(shù)組是 O(n^2)但你一旦把“以 i 結(jié)尾”作為狀態(tài)整個(gè)問題就變成了 O(1) 額外空間的一趟掃描。這就是狀態(tài)定義的價(jià)值。第二矩陣題的核心挑戰(zhàn)永遠(yuǎn)是“坐標(biāo)變換不要亂”。不管是螺旋矩陣的邊界收縮還是旋轉(zhuǎn)圖像的轉(zhuǎn)置本質(zhì)上都是在維護(hù)一套一致的坐標(biāo)變換規(guī)則。很多人在白板上能寫對(duì)整體邏輯但一到邊界就亂套歸根結(jié)底是沒有把“循環(huán)不變量”定義清楚。我在刷完這一批題之后最大的感受是它們幾乎不需要背誦你只需要想清楚“我究竟在維護(hù)一個(gè)什么狀態(tài)”其他一切都順理成章。2. 普通數(shù)組五連從最大子數(shù)組和到缺失正數(shù)這一節(jié)我把五道題逐個(gè)拆開重點(diǎn)不是貼完代碼就完事而是講清楚每道題方案的由來——為什么這么做是對(duì)的以及換一個(gè)條件它為什么就不成立。搞清楚了這些面試追問環(huán)節(jié)你才能不慌。2.1 最大子數(shù)組和一道題吃透動(dòng)態(tài)規(guī)劃的“以誰結(jié)尾”思維最大子數(shù)組和是動(dòng)態(tài)規(guī)劃入門的經(jīng)典題但它真正的考點(diǎn)不是遞推公式本身而是“為什么狀態(tài)只能定義為以 i 結(jié)尾的最大和而不是前 i 個(gè)元素的最大和”。你可以試一下如果定義 dp[i] 為“前 i 個(gè)元素里某個(gè)子數(shù)組的最大和”那么你根本沒法遞推因?yàn)槟悴恢肋@個(gè)最大和的子數(shù)組從哪里開始也無法判斷要不要把 nums[i] 接上去。但你一旦定義 dp[i] 為“以 nums[i] 結(jié)尾的最大子數(shù)組和”遞推關(guān)系就非常自然要么自己單獨(dú)成為子數(shù)組要么接上 dp[i-1]。nums [-2, 1, -3, 4, -1, 2, 1, -5, 4] # dp[i] max(nums[i], dp[i-1] nums[i]) # 空間優(yōu)化只用兩個(gè)變量即可 cur 0 best nums[0] for x in nums: cur max(x, cur x) best max(best, cur) print(best) # 6對(duì)應(yīng)子數(shù)組 [4, -1, 2, 1]一個(gè)特別容易踩的坑是 best 的初始值。如果你把它設(shè)成 0而數(shù)組全是負(fù)數(shù)最終答案會(huì)錯(cuò)誤地變成 0。所以要么初始化為第一個(gè)元素要么用負(fù)無窮。我第一次提交就是在全負(fù)數(shù)組上掛掉的這個(gè)問題在面試現(xiàn)場(chǎng)也很容易在邊界測(cè)試?yán)锉┞?。平時(shí)練習(xí)時(shí)可以順便想一想它的變體如果數(shù)組是環(huán)形的允許首尾相連該怎么辦思路是把問題拆成“普通最大子數(shù)組和”和“數(shù)組總和減去最小子數(shù)組和”兩種情況取最大值。這就是面試?yán)锍Ｒ姷摹白穯柾卣埂狈较颉?.2 合并區(qū)間排序之后的貪心為什么永遠(yuǎn)有效合并區(qū)間這題幾乎所有人第一反應(yīng)都是“先排序再遍歷合并”。但面試官更想聽的是你解釋清楚為什么排序之后貪心就一定正確。關(guān)鍵點(diǎn)在于重疊關(guān)系。我們把所有區(qū)間按左端點(diǎn)升序排列后任意兩個(gè)區(qū)間如果左端點(diǎn)小的在前那么只有當(dāng)后一個(gè)區(qū)間的左端點(diǎn)不超過前一個(gè)區(qū)間的右端點(diǎn)時(shí)它們才可能重疊。此時(shí)合并區(qū)間只需要把右端點(diǎn)更新為兩者中的較大值然后繼續(xù)和下一個(gè)比較。因?yàn)榕判蛞呀?jīng)保證了左端點(diǎn)的有序性所以貪心合并時(shí)“左邊已經(jīng)處理過的區(qū)間不會(huì)和更后面的區(qū)間發(fā)生意外的重疊漏判”。def merge(intervals): intervals.sort(keylambda x: x[0]) res [] for start, end in intervals: if not res or start res[-1][1]: res.append([start, end]) else: res[-1][1] max(res[-1][1], end) return res我實(shí)際寫代碼時(shí)的一個(gè)經(jīng)驗(yàn)先在紙上畫幾條不同位置關(guān)系的線段比如完全不相交、包含、交叉、緊挨著但沒完全重疊然后再動(dòng)手寫邏輯準(zhǔn)確率會(huì)明顯提高。這題有個(gè)常用變體是“插入?yún)^(qū)間”要求在一個(gè)已經(jīng)合并好的區(qū)間列表里插入一個(gè)新區(qū)間再合并。如果你理解了“排序后貪心”的本質(zhì)插入?yún)^(qū)間的解法其實(shí)就是在有序數(shù)組上做一次二分定位再合并復(fù)雜度可以壓到 O(n)。還有一個(gè)容易被追問的細(xì)節(jié)區(qū)間本身已經(jīng)按左端點(diǎn)排序了還需要重新排序嗎答案是仍然需要因?yàn)檩斎霐?shù)據(jù)可能并未保證有序。面試時(shí)主動(dòng)說出“我先假設(shè)輸入是無序的所以排序是必要步驟”會(huì)顯得思路完整。2.3 輪轉(zhuǎn)數(shù)組三次翻轉(zhuǎn)的數(shù)學(xué)直覺輪轉(zhuǎn)數(shù)組這題最容易想到的解法是開辟一個(gè)新數(shù)組把每個(gè)元素放到 (i k) % n 的位置時(shí)間復(fù)雜度 O(n)空間復(fù)雜度 O(n)。但題目如果要求原地完成三次翻轉(zhuǎn)就是最優(yōu)解。三次翻轉(zhuǎn)為什么成立你可以從元素位置移動(dòng)的角度來看。整體翻轉(zhuǎn)一次后每個(gè)元素的位置相對(duì)整個(gè)數(shù)組發(fā)生了鏡像變化。前 k 個(gè)元素被翻轉(zhuǎn)到數(shù)組尾部后 n-k 個(gè)元素被翻轉(zhuǎn)到數(shù)組頭部。此時(shí)再分別對(duì)這兩段做翻轉(zhuǎn)就把整段元素從“鏡像后再鏡像”變回了正確的相對(duì)順序。def rotate(nums, k): n len(nums) k % n # 關(guān)鍵k 可能大于 n nums.reverse() nums[0:k] reversed(nums[0:k]) nums[k:n] reversed(nums[k:n])這里 k % n 這一步極端重要。k 可能比 n 大很多直接翻轉(zhuǎn)時(shí)如果忘記取模結(jié)果會(huì)出錯(cuò)。我見過不止一個(gè)人在面試中寫完整段邏輯唯獨(dú)漏了這一行最后被面試官抓住。還有一個(gè)容易弄混的細(xì)節(jié)三次翻轉(zhuǎn)的順序有三種等價(jià)寫法。比如可以先翻轉(zhuǎn)前 n-k 個(gè)再翻轉(zhuǎn)后 k 個(gè)最后整體翻轉(zhuǎn)。哪種寫起來不容易錯(cuò)就見仁見智了。我的習(xí)慣是“整體翻轉(zhuǎn)、前 k 個(gè)、后 n-k 個(gè)”因?yàn)楹?k 直接相關(guān)的那段放在最前面思考起來更直觀。2.4 除自身以外數(shù)組的乘積前綴和后綴的雙向掃描這道題有一個(gè)明顯的“陷阱”如果你直接想到用所有數(shù)的乘積除以每個(gè)元素那么當(dāng)數(shù)組中有 0 時(shí)這個(gè)方案立刻失效。所以正確思路是避開除法用“前綴積 × 后綴積”的組合來構(gòu)造答案。基礎(chǔ)做法是用兩個(gè)數(shù)組pre[i] 表示 nums[0] 到 nums[i-1] 的乘積suf[i] 表示 nums[i1] 到 nums[n-1] 的乘積然后 answer[i] pre[i] * suf[i]。但面試的加分項(xiàng)是把額外空間從 O(n) 壓到 O(1)也就是只用一個(gè)答案數(shù)組再在反向遍歷時(shí)用一個(gè)變量滾動(dòng)記錄后綴積。def productExceptSelf(nums): n len(nums) ans [1] * n left 1 for i in range(n): ans[i] left left * nums[i] right 1 for i in range(n - 1, -1, -1): ans[i] * right right * nums[i] return ans第一次正向遍歷時(shí)ans[i] 存的是 i 左邊所有元素的積第二次反向遍歷時(shí)乘上右邊所有元素的積得到的就是除自身外的乘積。這個(gè)寫法的巧妙之處在于它完全沒有用到除法所以不會(huì)掉進(jìn) 0 的坑里。我刷題時(shí)習(xí)慣把一個(gè)特殊場(chǎng)景記在筆記里如果數(shù)組里有兩個(gè) 0那么所有答案都應(yīng)該是 0。如果你選擇了“先算乘積再除”的方案這個(gè)場(chǎng)景會(huì)讓你徹底翻車。用前綴后綴法的話這個(gè)結(jié)論會(huì)從代碼邏輯中自然體現(xiàn)完全不需要單獨(dú)處理。2.5 缺失的第一個(gè)正數(shù)原地哈?？臻g極限的經(jīng)典設(shè)計(jì)缺失的第一個(gè)正數(shù)是這批數(shù)組題里我公認(rèn)最難的一道也是區(qū)分“背過答案”和“真懂原理”的分水嶺。題目限定時(shí)間復(fù)雜度 O(n)、額外空間 O(1)這個(gè)限制基本堵死了排序和哈希表的常規(guī)路。真正正確的做法是“原地哈?！奔热灰业氖侨笔У淖钚≌麛?shù)那答案一定落在 1 到 n1 這個(gè)范圍內(nèi)n 是數(shù)組長度。所以我們可以讓數(shù)組下標(biāo)和值形成一對(duì)一的對(duì)應(yīng)關(guān)系把 1 放到下標(biāo) 0把 2 放到下標(biāo) 1……遍歷結(jié)束后第一個(gè)“下標(biāo) i 上的值不是 i1”的位置就是缺失的那個(gè)數(shù)。def firstMissingPositive(nums): n len(nums) for i in range(n): while 1 nums[i] n and nums[nums[i] - 1] ! nums[i]: idx nums[i] - 1 nums[i], nums[idx] nums[idx], nums[i] for i in range(n): if nums[i] ! i 1: return i 1 return n 1這里采用 while 而不是 if是因?yàn)榻粨Q過來的新值可能仍然在 1 到 n 范圍內(nèi)且不在正確位置需要繼續(xù)處理直到當(dāng)前位置變成正確值或遇到無效值為止。寫代碼的時(shí)候要注意交換順序先用 idx 保存目標(biāo)位置再交換否則先修改 nums[i] 會(huì)導(dǎo)致目標(biāo)下標(biāo)計(jì)算錯(cuò)誤。這個(gè)思路本質(zhì)上是用數(shù)組本身充當(dāng)哈希表我每次想到它都會(huì)感慨空間復(fù)雜度的極致利用。如果面試時(shí)你能把“為什么答案一定不超過 n1”作為開場(chǎng)白講出來整個(gè)答題節(jié)奏就穩(wěn)了。3. 矩陣四題循環(huán)不變量與降維打擊矩陣題的共性比數(shù)組題更明顯它們基本都在考察“坐標(biāo)變換的控制力”。代碼本身不長真正的敵人是邊界混亂和空間復(fù)雜度過高。3.1 矩陣置零把標(biāo)記藏在邊界空間從 O(mn) 降到 O(1)最直觀的做法是開兩個(gè)數(shù)組分別記錄哪些行、哪些列需要置零額外空間是 O(mn)。這道題的進(jìn)階要求是原地完成也就是額外空間只有 O(1)。關(guān)鍵洞察是第一行和第一列本身就可以充當(dāng)標(biāo)記數(shù)組。我們遍歷整個(gè)矩陣時(shí)如果發(fā)現(xiàn)某個(gè)位置 matrix[i][j] 是 0不需要立刻修改它而是把“i 行需要置零”的信息記錄在 matrix[i][0]“j 列需要置零”的信息記錄在 matrix[0][j]。但這里有個(gè)經(jīng)典的坑第一行和第一列本身也可能一開始就有 0如果你直接用它們做標(biāo)記原始信息就被覆蓋了。所以必須先單獨(dú)記錄第一行和第一列是否原本包含 0最后再補(bǔ)處理。def setZeroes(matrix): m, n len(matrix), len(matrix[0]) first_row_has_zero any(x 0 for x in matrix[0]) first_col_has_zero any(matrix[i][0] 0 for i in range(m)) for i in range(1, m): for j in range(1, n): if matrix[i][j] 0: matrix[i][0] 0 matrix[0][j] 0 for i in range(1, m): for j in range(1, n): if matrix[i][0] 0 or matrix[0][j] 0: matrix[i][j] 0 if first_row_has_zero: for j in range(n): matrix[0][j] 0 if first_col_has_zero: for i in range(m): matrix[i][0] 0這個(gè)方案我最開始看的時(shí)候只覺得精妙后來親手寫一遍才發(fā)現(xiàn)還有很多細(xì)節(jié)值得體悟第一遍標(biāo)記時(shí)要從下標(biāo) 1 開始不能把第一行第一列自己標(biāo)記成 0 的信息和原有信息搞混。第二遍置零時(shí)同樣要從 1 開始最后再單獨(dú)處理邊界。這個(gè)順序不能亂否則很容易把正確的標(biāo)記覆蓋掉。3.2 螺旋矩陣四條邊收縮時(shí)循環(huán)不變量怎么定螺旋矩陣要求按順時(shí)針螺旋順序輸出矩陣所有元素。這個(gè)題沒有算法難度純粹考驗(yàn)?zāi)隳芊窬S護(hù)好四個(gè)邊界top、bottom、left、right。我見得最多的錯(cuò)誤寫法是每走完一條邊就盲目執(zhí)行下一條邊的循環(huán)導(dǎo)致在只有一行或只有一列時(shí)下邊的循環(huán)和左邊的循環(huán)會(huì)重復(fù)讀取已經(jīng)訪問過的元素。正確的做法是在每一輪循環(huán)里走完上邊和右邊后用 if 語句檢查 top bottom、left right 是否仍然成立再?zèng)Q定是否走下邊和左邊。def spiralOrder(matrix): res [] if not matrix: return res m, n len(matrix), len(matrix[0]) top, bottom, left, right 0, m - 1, 0, n - 1 while top bottom and left right: for j in range(left, right 1): res.append(matrix[top][j]) top 1 for i in range(top, bottom 1): res.append(matrix[i][right]) right - 1 if top bottom: for j in range(right, left - 1, -1): res.append(matrix[bottom][j]) bottom - 1 if left right: for i in range(bottom, top - 1, -1): res.append(matrix[i][left]) left 1 return res這里循環(huán)不變量是“每一輪循環(huán)遍歷一圈完整的螺旋圈”并且每走完一條邊就收縮對(duì)應(yīng)的邊界。寫完代碼之后建議用一個(gè) 1×3 的矩陣和 3×1 的矩陣做測(cè)試這兩個(gè)特殊形狀最容易暴露重復(fù)訪問的 bug。我還試過另一種寫法用 move 數(shù)組進(jìn)行方向切換碰到邊界或已訪問元素就轉(zhuǎn)向。這種模擬寫法的優(yōu)點(diǎn)是邏輯簡單缺點(diǎn)是需要額外開一個(gè) visited 數(shù)組空間復(fù)雜度會(huì)變成 O(mn)。如果題目沒有特別要求空間模擬法也是可以接受的但既然能零額外空間做出來我建議優(yōu)先掌握邊界收縮法。3.3 旋轉(zhuǎn)圖像轉(zhuǎn)置加翻轉(zhuǎn)為什么是對(duì)角線旋轉(zhuǎn)圖像要求把 n×n 矩陣順時(shí)針旋轉(zhuǎn) 90 度而且必須原地操作。兩種主流解法里我認(rèn)為“先轉(zhuǎn)置再水平翻轉(zhuǎn)”最不容易出錯(cuò)因?yàn)樗讯S變換拆成了兩步大家都熟悉的一維操作。為什么是轉(zhuǎn)置加水平翻轉(zhuǎn)而不是轉(zhuǎn)置加垂直翻轉(zhuǎn)你可以拿一個(gè) 2×2 的矩陣手推一遍。順時(shí)針旋轉(zhuǎn) 90 度等價(jià)于沿著主對(duì)角線做鏡像轉(zhuǎn)置再沿垂直中線做鏡像水平翻轉(zhuǎn)。反方向的話逆時(shí)針 90 度就是先轉(zhuǎn)置再垂直翻轉(zhuǎn)。def rotate(matrix): n len(matrix) for i in range(n): for j in range(i 1, n): matrix[i][j], matrix[j][i] matrix[j][i], matrix[i][j] for i in range(n): for j in range(n // 2): matrix[i][j], matrix[i][n - 1 - j] matrix[i][n - 1 - j], matrix[i][j]另一個(gè)原地方案是按“環(huán)”處理每個(gè)環(huán)上做四元素輪換。這個(gè)寫法更省常數(shù)時(shí)間但坐標(biāo)容易搞亂。我的經(jīng)驗(yàn)是面試中時(shí)間緊張選擇不容易寫錯(cuò)的方法更重要。你可以先說出“有轉(zhuǎn)置加翻轉(zhuǎn)和四元素輪換兩種方案我先用轉(zhuǎn)置法更直觀”然后順手寫出來再補(bǔ)充說明另一種方法的存在— 效果非常好。3.4 搜索二維矩陣 II從右上角出發(fā)把二維問題降成一維搜索二維矩陣 II 的矩陣每行從左到右遞增每列從上到下遞增要求高效查找目標(biāo)值。你如果試圖對(duì)每一行二分復(fù)雜度是 O(m log n)雖然是可行的但沒抓住這道題最有價(jià)值的觀察。最有名的解法被稱為“靠右上角逐步逼近”從右上角開始當(dāng)前值大于 target 就向左移動(dòng)一列小于 target 就向下移動(dòng)一行。這么做之所以可行是因?yàn)橛疑辖堑脑厥撬谛械淖畲笾怠⑺诹械淖钚≈稻拖褚粋€(gè)“決策邊界”。向左移動(dòng)可以排除一整列向下移動(dòng)可以排除一整行。def searchMatrix(matrix, target): m, n len(matrix), len(matrix[0]) r, c 0, n - 1 while r m and c 0: if matrix[r][c] target: return True if matrix[r][c] target: c - 1 else: r 1 return False我之前一直以為這個(gè)矩陣題可以直接用二分后來在面試模擬中發(fā)現(xiàn)直接二分因?yàn)閺?fù)雜度不是最優(yōu)容易被認(rèn)為沒有抓住題目的特殊結(jié)構(gòu)。從右上角出發(fā)的做法時(shí)間復(fù)雜度只有 O(mn)而且代碼極其短在面試中寫出來會(huì)讓面試官明顯感受到“你理解了這個(gè)矩陣的排序含義”。如果面試官追問“為什么從左上角不行”答案是左上角是全局最小值向右向下都比它大沒法做任何排除決策。這類題拿到手之后第一件事永遠(yuǎn)是觀察數(shù)據(jù)的特殊性質(zhì)而不是立刻套用通用算法。4. 兩周刷題計(jì)劃從零到專題內(nèi)化很多讀者問過我這九道題到底該怎么安排練習(xí)節(jié)奏。我給的建議很簡單不要平均發(fā)力按“難度螺旋上升”的順序兩周內(nèi)完成第一輪完整刷寫。第一周算法思維建立期。每天刷一至兩道順序建議是最大子數(shù)組和、合并區(qū)間、除自身以外數(shù)組的乘積、輪轉(zhuǎn)數(shù)組、搜索二維矩陣 II。這五道題相對(duì)友好能讓你先建立“狀態(tài)定義”“排序貪心”“前綴積”“原地翻轉(zhuǎn)”“降維觀察”這五種基礎(chǔ)思維的直覺。每道題寫完不算完要把官方題解里比你更好的實(shí)現(xiàn)也手抄一遍并對(duì)比自己寫的版本差在哪里。第二周復(fù)現(xiàn)與變體擴(kuò)展期。剩下的四道題缺失的第一個(gè)正數(shù)、矩陣置零、螺旋矩陣、旋轉(zhuǎn)圖像放在這個(gè)階段因?yàn)樗鼈兏简?yàn)邊界控制和空間優(yōu)化。前三天每天一道硬骨頭后兩天把九道題全部重新盲寫一遍。這里的盲寫是指不看任何提示直接寫出核心代碼并跑通測(cè)試用例。以下是我自己實(shí)測(cè)比較舒服的時(shí)間分配表格天數(shù)任務(wù)目標(biāo)第 1 天最大子數(shù)組和 合并區(qū)間掌握狀態(tài)定義和排序貪心第 2 天除自身以外數(shù)組的乘積理解前綴積雙向掃描第 3 天輪轉(zhuǎn)數(shù)組 搜索二維矩陣 II掌握原地翻轉(zhuǎn)和降維觀察第 4 天復(fù)習(xí)前五題限時(shí) 20 分鐘/題第 5 天矩陣置零 螺旋矩陣吃透標(biāo)記復(fù)用和循環(huán)不變量第 6 天旋轉(zhuǎn)圖像 缺失的第一個(gè)正數(shù)突破坐標(biāo)變換和原地哈希第 7 天全部九道題盲寫檢驗(yàn)真實(shí)掌握程度這個(gè)計(jì)劃里最容易被忽略的是“限時(shí)”。在完全沒有時(shí)間壓力的情況下人的大腦很容易陷入“慢慢調(diào)代碼直到通過”的狀態(tài)這在真實(shí)面試中是致命的。所以第二周開始我強(qiáng)烈要求自己每道題從讀題到跑通不超過 25 分鐘。如果超時(shí)說明沒吃透標(biāo)記下來第二天重刷。刷完之后我還建議做一次“同類擴(kuò)展”把最大子數(shù)組和改成環(huán)形數(shù)組和把合并區(qū)間改成插入?yún)^(qū)間把螺旋矩陣改成逆時(shí)針遍歷。這些變體題常作為追問出現(xiàn)提前練習(xí)過面試時(shí)的反應(yīng)速度和信心都會(huì)完全不一樣。5. 面試現(xiàn)場(chǎng)這些題出現(xiàn)在白板上時(shí)怎么講刷題和面試是兩回事。代碼寫得對(duì)不代表你能在短時(shí)間內(nèi)讓面試官相信你寫得對(duì)。這里總結(jié)我自己的實(shí)戰(zhàn)表達(dá)結(jié)構(gòu)直接套用即可。第一步復(fù)述題意并確認(rèn)條件。比如輪轉(zhuǎn)數(shù)組需要先確認(rèn)是否能使用額外空間、k 是否可能大于 n比如矩陣置零需要確認(rèn)空間復(fù)雜度要求。這個(gè)步驟很多人跳過但它是展示你專業(yè)性的好機(jī)會(huì)。第二步先說暴力方案再說優(yōu)化方案。哪怕你腦子里已經(jīng)知道最優(yōu)解也建議先花一分鐘陳述暴力解的時(shí)間復(fù)雜度再引出優(yōu)化方案。這不是廢話而是向面試官展示你有“從樸素到優(yōu)化”的思考習(xí)慣。比如除自身以外數(shù)組的乘積先提“總乘積除以自身”被 0 破壞因此要避開的理由再提前綴后綴法。第三步寫代碼前先描述狀態(tài)或循環(huán)不變量。我通常在寫任何代碼之前用一兩句話告訴面試官“我準(zhǔn)備維護(hù)一個(gè)什么狀態(tài)”。比如最大子數(shù)組和我會(huì)說“維護(hù)以當(dāng)前元素結(jié)尾的最大子數(shù)組和每次取當(dāng)前元素和累加和的較大值”。這句話一出口面試官就知道你沒在背答案。第四步寫代碼時(shí)邊寫邊做小的解釋但不要每行都解釋。注釋關(guān)鍵步驟比如輪轉(zhuǎn)數(shù)組的 k % n或者矩陣置零里最后單獨(dú)恢復(fù)第一行第一列。這些地方大概率是面試官想考察的邊界點(diǎn)主動(dòng)說出來比等他問要好。第五步跑一個(gè)小的測(cè)試用例。白板代碼不需要真跑程序但你可以手動(dòng)模擬一個(gè) 3×3 矩陣或一個(gè)長度為 5 的數(shù)組帶大家走一遍代碼的核心邏輯。這個(gè)動(dòng)作非常加分因?yàn)樗C明了你的代碼是“真正可以運(yùn)行的邏輯”而不是默寫出來的行尸走肉。這五步說完之后面試官通常只剩一兩個(gè)追問點(diǎn)要么是空間復(fù)雜度的進(jìn)一步優(yōu)化要么是某個(gè)邊界場(chǎng)景的處理。只要你對(duì)每道題的原理理解到位這一關(guān)基本穩(wěn)過。6. 提交記錄里的避坑清單這九道題我前前后后提交了很多次把踩過的坑整理成了一份自己的清單。寫在這里希望能幫你少交幾次學(xué)費(fèi)。數(shù)組越界輪轉(zhuǎn)數(shù)組忘記對(duì) k 取模導(dǎo)致整體翻轉(zhuǎn)后分段翻轉(zhuǎn)的下標(biāo)超出數(shù)組范圍。任何寫數(shù)組翻轉(zhuǎn)的地方都要先想一下 k 與 n 的關(guān)系。缺失的第一個(gè)正數(shù)中交換數(shù)組元素的下標(biāo)由 nums[i] - 1 得到必須先確保 nums[i] 在 [1, n] 范圍內(nèi)才能做這個(gè)下標(biāo)運(yùn)算。初始值錯(cuò)誤最大子數(shù)組和的 best 初始值設(shè)為 0導(dǎo)致全負(fù)數(shù)數(shù)組返回錯(cuò)誤結(jié)果。統(tǒng)一初始化為數(shù)組第一個(gè)元素或負(fù)無窮。合并區(qū)間的 res 為空時(shí)不能直接比較 res[-1]要先判斷 res 是否為空。邊界污染矩陣置零如果先處理第一行和第一列的原始狀態(tài)再用它們做標(biāo)記原始信息會(huì)丟失。正確順序是先記錄、再標(biāo)記、再補(bǔ)處理邊界。旋轉(zhuǎn)圖像轉(zhuǎn)置時(shí)內(nèi)層循環(huán)要從 i 1 開始如果從 0 開始等于把同一個(gè)元素交換兩次矩陣根本不會(huì)發(fā)生變化。重復(fù)訪問螺旋矩陣在單行或單列情況下不加 if 判斷直接走下邊和左邊會(huì)把已經(jīng)輸出的元素再走一遍。代碼里 top bottom、left right 這兩個(gè)檢查不能省。貪心前提遺漏合并區(qū)間如果跳過排序直接合并結(jié)果不可能正確。就算題目給的示例恰好是有序的也要在代碼里先 sort。這份清單里的大部分錯(cuò)誤我都犯過不止一次后來形成習(xí)慣每寫完一道題先主動(dòng)檢查上述幾類問題再提交。這樣不僅能提升通過率還能在面試時(shí)主動(dòng)避坑比返工調(diào)試更有底氣。如果把這九道題當(dāng)作一個(gè)整體來看它們其實(shí)共同指向一個(gè)核心能力面對(duì)一個(gè)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)你能不能找到一條從暴力到最優(yōu)的升級(jí)路徑并把它清楚地表達(dá)出來。數(shù)組和矩陣是最容易出這類考察的數(shù)據(jù)結(jié)構(gòu)所以它出現(xiàn)在面試開場(chǎng)的頻率才會(huì)那么高。把這一批題吃透你收獲的不僅是九道題的解法更是一整套處理數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)問題的思維方式。