C的環(huán)形矩陣填充學(xué)名叫螺旋矩陣生成是個看起來簡單、上手就碎的問題。我第一次在這上面翻車是大二寫數(shù)據(jù)結(jié)構(gòu)作業(yè)腦子里的思路特別清楚從外到內(nèi)一圈一圈填可一到代碼層面就開始越界、覆蓋、死循環(huán)。那個晚上我印象很深一邊調(diào)一邊懷疑自己是不是不適合寫代碼。后來在藍橋杯省賽和兩場技術(shù)面試?yán)镂矣峙龅搅藥缀跻粯拥念}才徹底想明白這類題考的根本不是智商而是對循環(huán)邊界條件的掌控力。這篇文章的核心是一套可以直接抄走的C源碼外加我把它們拆碎之后的理解。邊界收縮法和方向向量法我都寫了完整可編譯的版本并且在g 11和Visual Studio 2022下都實測過。適合準(zhǔn)備刷題面試的朋友、剛學(xué)完數(shù)組和循環(huán)想練手的新手以及想搞清楚二維vector到底怎么管理內(nèi)存的人。讀完你不僅能寫出環(huán)形填充還能順手搞定逆時針、矩形螺旋、中心向外螺旋這些變形題。1. 先搞明白環(huán)形矩陣到底在折騰什么1.1 題目到底要求我們做什么環(huán)形矩陣最經(jīng)典的版本是這樣給定一個正整數(shù)n生成一個n乘n的矩陣從左上角第一個元素開始按照順時針方向依次填入1到n的平方。比如n等于3時結(jié)果是這樣1 2 3 8 9 4 7 6 5n等于4時結(jié)果是這樣1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7注意看規(guī)律先向右走到頭再向下走到頭然后向左走到頭最后向上走到頭完成一圈。下一圈往里縮再重復(fù)同樣四個方向直到所有格子填滿。要求填充意味著我們要寫入矩陣的每一個位置。這和打印是兩回事——打印只需要遍歷輸出填充需要先構(gòu)造數(shù)據(jù)再輸出。很多初學(xué)者把這兩者混在一起結(jié)果一邊填一邊輸出邏輯理不清。我建議嚴(yán)格分開先完整生成矩陣再單獨寫一個打印函數(shù)。這樣每一步都能獨立驗證。這里有一個容易忽略的細(xì)節(jié)數(shù)字的遞增方向是右上到左下再到左上整體是順時針螺旋。如果把方向反了就成了逆時針螺旋這是最常見的變形題之一后面我會單獨講。1.2 為什么這道題到處都能碰到環(huán)形矩陣可以說是算法題里的流量明星。學(xué)習(xí)階段它是嵌套循環(huán)和二維數(shù)組的絕佳練習(xí)題比九九乘法表有挑戰(zhàn)性但又不像動態(tài)規(guī)劃那樣勸退。比賽階段藍橋杯、ACM校賽、高校算法課上都能看到它的身影經(jīng)常作為基礎(chǔ)題的壓軸或者進階題的前置。面試階段它是考察候選人能不能把思路轉(zhuǎn)化成邊界嚴(yán)謹(jǐn)?shù)拇a的高頻題尤其在C崗位的筆試?yán)锍霈F(xiàn)率不低。我復(fù)盤了一下這道題之所以受歡迎是因為它完美地考驗了三件事能否把一圈一圈的直覺轉(zhuǎn)化成四個for循環(huán)的精確描述能否在狀態(tài)更新時比如上邊界下移、右邊界左移意識到邊界條件的改變能否跳出我是按數(shù)字順序填的這個線性思維切換到我是按位置順序填的這個空間思維大部分卡住的人問題都出在第三點上。他們試圖用一個變量追蹤當(dāng)前數(shù)字然后用某種公式計算數(shù)字對應(yīng)的坐標(biāo)。這當(dāng)然可以比如可以用層次和偏移量硬算但代碼復(fù)雜度遠(yuǎn)高于直接用方向走位。我見過有人為了這個題寫了三十多行數(shù)學(xué)公式跑起來還容易錯。其實最簡單的做法是每一輪循環(huán)固定填一條邊填完就把對應(yīng)的邊界往里縮一格。1.3 這道題到底在訓(xùn)練什么底層能力往深了說環(huán)形矩陣是狀態(tài)機思維的一個入門模型。每一圈的填充可以看作狀態(tài)依次經(jīng)歷向右、向下、向左、向上四個狀態(tài)每個狀態(tài)結(jié)束后邊界條件發(fā)生變化然后進入下一個狀態(tài)。這不只是數(shù)組題它和游戲里角色走格子、機器人在棋盤上清掃路徑、圖像處理里的區(qū)域掃描本質(zhì)上是同一類問題。我記得有個做嵌入式圖形界面的朋友說過他在做LCD屏幕的邊框繪制時就遇到了完全類似的邏輯需要把一個區(qū)域按螺旋順序填充顏色用于測試屏幕壞點。你看課堂里看起來沒什么用的題到了真實場景里就成了工具。所以我的建議是不要背代碼要把這道題當(dāng)作訓(xùn)練邊界管理的思維體操。你把這個能力練扎實了再看其他二維數(shù)組相關(guān)的問題比如島嶼數(shù)量、迷宮尋路、矩陣旋轉(zhuǎn)都會順暢很多。2. 兩種核心思路邊界收縮法和方向向量法環(huán)形矩陣的解法網(wǎng)上一搜一大把但歸納起來其實就兩大流派邊界收縮法和方向向量法。我個人建議兩個都掌握因為它們各有不可替代的場景。2.1 邊界收縮法像查戶口一樣一圈一圈往里走邊界收縮法的核心思想是維護四個變量top、bottom、left、right分別表示當(dāng)前還沒有被填寫的區(qū)域的上、下、左、右邊界。一開始top 0; bottom n - 1; left 0; right n - 1;接著在一個大循環(huán)里做四件事從左到右填充top這一行填完top加1說明上邊界已經(jīng)被填死了從上到下填充right這一列填完right減1從右到左填充bottom這一行填完bottom減1從下到上填充left這一列填完left加1每次循環(huán)就是一圈。填完一圈后top、bottom、left、right往中間縮了一圈如果top仍然小于等于bottom且left仍然小于等于right說明中間還有沒填的區(qū)域繼續(xù)下一圈。我用查戶口來類比你手里有一張紙表示還沒走到的區(qū)域。你走到這塊區(qū)域的上邊從左到右挨個敲門登記登記完把這行撕掉然后走到右邊從上到下登記登記完把這一列撕掉再走到下邊從右到左登記撕掉最后走到左邊從下到上登記撕掉。一圈撕完手里的紙變小了繼續(xù)重復(fù)。直到整張紙都被撕光。這個方法的優(yōu)點是邏輯非常直觀幾乎不需要額外的狀態(tài)判斷。缺點是代碼里要小心處理只剩一行或只剩一列的情況。比如填充完上邊和右邊之后如果此時top已經(jīng)大于bottom說明已經(jīng)沒有剩余的行了第三和第四步再做就會重復(fù)賦值導(dǎo)致數(shù)據(jù)被覆蓋。2.2 方向向量法讓矩陣自己學(xué)會拐彎方向向量法的思路完全不一樣。它不維護四個邊界而是維護一個當(dāng)前位置和一個當(dāng)前方向每一步往前走一格如果發(fā)現(xiàn)前面走不了就右轉(zhuǎn)90度繼續(xù)走。方向用二維數(shù)組表示int dirs[4][2] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};這四組數(shù)分別表示向右列1、向下行1、向左列-1、向上行-1。算法的主循環(huán)就一句話從1數(shù)到n乘n每個數(shù)字填到當(dāng)前格子然后試著往前走一步。如果下一步越界了或者下一步的位置已經(jīng)有值就轉(zhuǎn)彎。轉(zhuǎn)彎就是方向數(shù)組的下標(biāo)加1再對4取模dir (dir 1) % 4;這個方法天然解決了一個問題不需要考慮只剩一行或只剩一列的特殊情況。因為判斷條件永遠(yuǎn)是下一步能不能走不能走就轉(zhuǎn)即使最后只剩一個格子也能正確填完。我還記得第一次理解這個算法時的感覺原來代碼可以像一個小機器人一樣自己探索著前進碰到墻就轉(zhuǎn)彎。這個思路比邊界收縮法更接近真實世界的導(dǎo)航邏輯也更容易擴展到地圖探索、貪吃蛇、迷宮求解等問題上。2.3 兩種方案怎么選我用一張表把區(qū)別列出來方便你根據(jù)實際情況選對比維度邊界收縮法方向向量法代碼量略長較短邊界維護4個變量直觀1個方向變量抽象特殊邊界需要if防止重復(fù)自動處理性能O(n^2)O(n^2)可擴展性調(diào)整邊界即可調(diào)整方向數(shù)組即可理解門檻低中如果你是初學(xué)者我建議先掌握邊界收縮法。它的每一步都能和圖形對應(yīng)上debug的時候可以很清楚地知道現(xiàn)在填到哪一行。等寫熟練了再學(xué)方向向量法。方向向量法在面試時寫起來更簡潔也更好口頭解釋。說實話我自己刷題的時候通常用方向向量法因為它不容易出現(xiàn)邊界條件的邏輯漏洞。但是如果題干要求從外到內(nèi)一圈一圈這種描述我也會立刻切換回邊界收縮法的視角來思考。兩種方法都是工具關(guān)鍵是在需要的時候能拿出來正確的那個。3. 完整源碼邊界收縮法的逐行實現(xiàn)現(xiàn)在進入正題給出可以直接抄走的源碼。我下面這份代碼是以邊界收縮法為主體的完整實現(xiàn)包含生成和打印兩個函數(shù)拿到就能編譯運行。3.1 可直接編譯運行的完整代碼#include iostream #include vector #include iomanip using namespace std; // 打印二維矩陣方便觀察效果 void printMatrix(const vectorvectorint matrix) { for (const auto row : matrix) { for (int val : row) { cout setw(3) val; } cout endl; } } // 生成n階順時針環(huán)形矩陣 vectorvectorint generateSpiralMatrix(int n) { // 初始化一個n*n的二維vector所有元素默認(rèn)值為0 vectorvectorint matrix(n, vectorint(n, 0)); int top 0, bottom n - 1; int left 0, right n - 1; int num 1; while (top bottom left right) { // 1. 從左到右填充當(dāng)前上邊這一行 for (int j left; j right; j) { matrix[top][j] num; } top; // 2. 從上到下填充當(dāng)前右邊這一列 for (int i top; i bottom; i) { matrix[i][right] num; } --right; // 3. 從右到左填充當(dāng)前下邊這一行 // 注意如果上面的 --top 導(dǎo)致 top bottom說明沒有剩余行了 if (top bottom) { for (int j right; j left; --j) { matrix[bottom][j] num; } --bottom; } // 4. 從下到上填充當(dāng)前左邊這一列 // 同理如果 --right 導(dǎo)致 left right說明沒有剩余列了 if (left right) { for (int i bottom; i top; --i) { matrix[i][left] num; } left; } } return matrix; } int main() { int n; cout 請輸入矩陣階數(shù) n; cin n; vectorvectorint result generateSpiralMatrix(n); printMatrix(result); return 0; }這份代碼在Visual Studio 2022和g 11.3下都編譯運行過。輸入5輸出是這樣的1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9第3行第3列的25正好是中心數(shù)字說明奇數(shù)階矩陣的中心處理正確每一行、每一列的數(shù)字也都滿足螺旋遞增的規(guī)律。3.2 核心代碼段的逐行解讀我挑幾個容易被忽略的細(xì)節(jié)重點說。先看vector的初始化vectorvectorint matrix(n, vectorint(n, 0));這一行創(chuàng)建了n行每行是一個長度為n、默認(rèn)值為0的vector。把默認(rèn)值設(shè)成0后面在方向向量法中可以作為是否已填充的判斷依據(jù)在這段邊界收縮法里其實用不到0這個值但保留它沒壞處。需要注意的是vector的初始化是先外層后內(nèi)層如果你寫成vectorvectorint matrix(n, 0)那是在創(chuàng)建n個整數(shù)0而不是n行數(shù)組編譯直接報錯。這個低級錯誤我見過不少新手犯。再看num這個表達式。這里用的是后置自增它返回當(dāng)前值然后才加1。所以matrix[top][j] num;等價于先賦值再把num加1。如果你用前置自增num那第一個填進去的數(shù)字就會變成2而不是1整張表全都從2開始全盤錯位。這個細(xì)節(jié)面試時也經(jīng)常作為追問點出現(xiàn)。然后是邊界更新。每次填完一條邊都要動一個邊界變量top、--right、--bottom、left。注意動的方式上邊界是往下走所以右邊界是往左走所以--下邊界是往上走所以--左邊界是往右走所以。這四個方向如果搞錯一個整圈就會亂套。我調(diào)試的時候經(jīng)常把--right寫成right結(jié)果數(shù)字全都往右跑越界后程序直接崩潰。第三步和第四步前面的if判斷是整個算法最精華的地方。沒有這兩個if當(dāng)n為奇數(shù)時最后一圈會出問題。n等于5的時候最后一圈只剩中心一個格子此時top等于bottom等于left等于right都等于2第一步和第二步已經(jīng)把中心填完了接著第三步的從右到左會再給matrix[bottom][j]賦值把中心的值從25改成什么東西不對仔細(xì)看第一步和第二步填完之后top變成了3此時top bottom所以第三步不會執(zhí)行。但如果去掉if第三步的for循環(huán)條件是for (int j right; j left; --j)此時right2left2會進去執(zhí)行一次再用num把中心覆蓋掉最后中心變成26而且num超出了n的平方。這是經(jīng)典的錯誤來源。3.3 如何快速驗證代碼是否正確寫完代碼我建議不要直接提交或者繼續(xù)寫下一個題先做三個驗證n1輸出只有1這個用例專門驗證最小規(guī)模的情況。很多算法在n1時會出現(xiàn)特殊問題因為while循環(huán)只會執(zhí)行一次四步里面后面兩步因為邊界條件直接跳過。n2輸出1 2 4 3這驗證了最基本的螺旋順序。n2時第二圈只剩兩格重點看第三步是否能正確執(zhí)行。n5驗證奇數(shù)階的中心處理。中心數(shù)字必須是n的平方25。我用這幾個用例跑一遍基本能排除90%的邊界問題。如果你的代碼在n5時中心不是25那問題幾乎一定出在第三或第四步的if判斷上。4. 最容易翻車的四個邊界細(xì)節(jié)這個章節(jié)我單獨拎出來因為環(huán)形矩陣的坑幾乎全集中在邊界細(xì)節(jié)上。我把它們按出現(xiàn)頻率從高到低列出來。4.1 奇數(shù)階矩陣的中心點重復(fù)賦值這是最經(jīng)典的坑。n為奇數(shù)時比如5最后一圈只剩一個中心格子。問題在于如果代碼不看if條件第三步或第四步會在這個中心格子上再賦值一次。復(fù)盤一遍n5的流程第一圈填完top從0變1bottom從4變3left從0變1right從4變3此時1 3 1 3繼續(xù)。第二圈填完top變2bottom變2left變2right變2此時2 2 2 2繼續(xù)。第三圈開始時top2bottom2left2right2。第一步從左到右把25填到matrix[2][2]然后top變3。此時進入while條件判斷top(3) bottom(2)為假循環(huán)結(jié)束。所以如果寫得正確第三步和第四步根本不會執(zhí)行。但如果你在第一步后面不加其他判斷第二步執(zhí)行時i從top(3)開始此時top3bottom2循環(huán)不會執(zhí)行然后--right把right從2變成1。接著第三步的if條件是if (top bottom)也就是3 2為假跳過。第四步也一樣跳過。這也是能工作的。真正出問題的情況是有人在每個方向的for循環(huán)里忘了基于當(dāng)前邊界做正確縮進或者把邊界更新的位置寫亂了。比如有人會在第一步循環(huán)里順手修改right導(dǎo)致后續(xù)判斷全亂。所以我的核心建議是把邊界更新固定寫在每個for循環(huán)結(jié)束后并且四個更新方向嚴(yán)格對應(yīng)。不要試圖在for的循環(huán)條件里順手做更新那樣雖然能省一行代碼但可讀性和排錯性都會變差。4.2 越界訪問數(shù)組下標(biāo)別踩出邊界越界訪問在C里是個大問題因為它不像Java或者Python那樣會立刻拋異常而是可能看起來還能繼續(xù)跑但數(shù)據(jù)已經(jīng)寫到了未知內(nèi)存區(qū)域。表現(xiàn)可能是輸出亂碼也可能是程序崩潰。更可怕的是有時候代碼能正常跑完只是在后續(xù)內(nèi)存釋放時崩潰。我建議在調(diào)試階段開啟編譯器的邊界檢查選項。g可以用-D_GLIBCXX_ASSERTIONS或者使用AddressSanitizerg -fsanitizeaddress -g spiral.cpp -o spiral這樣如果代碼里有越界訪問運行時馬上會報錯定位到具體行。Visual Studio里面Debug模式下默認(rèn)會檢查vector訪問越界。回到代碼本身越界的根源通常是邊界更新有誤。比如第二步for (int i top; i bottom; i)如果top因為第一步已經(jīng)變成了1bottom還是n-1那么i從1跑到n-1是安全的。但如果第一步?jīng)]有top那么top還是0i從0跑到底右邊這一列最上面的格子matrix[0][right]會被第二次賦值而且賦值完后right也減了1整個數(shù)據(jù)就全亂了。我把一個自查口訣分享給你每填完一條邊就看一下對應(yīng)的邊界變量是否往矩陣中心縮了一格如果沒有縮后面所有循環(huán)都會基于錯誤的邊界繼續(xù)算。4.3 方向向量法的轉(zhuǎn)向優(yōu)先級問題方向向量法雖然實現(xiàn)短但它也有一個隱蔽的坑轉(zhuǎn)向的判斷和前進的時機。正確邏輯是先填當(dāng)前格子然后計算下一步位置判斷下一步是否合法如果不合法就轉(zhuǎn)向再重新計算一次下一步位置最后把當(dāng)前位置更新為下一步。偽代碼matrix[row][col] num; int nextRow row dirs[dir][0]; int nextCol col dirs[dir][1]; if (下一步不合法) { dir (dir 1) % 4; nextRow row dirs[dir][0]; nextCol col dirs[dir][1]; } row nextRow; col nextCol;有人會寫成先往前挪發(fā)現(xiàn)不合法再退回來轉(zhuǎn)向。這樣不是不行但代碼多了一步回退容易出錯。還有人在轉(zhuǎn)向之后不重新計算nextRow和nextCol而是繼續(xù)用舊的方向移動那就會穿透邊界直接越界。我調(diào)試方向向量法時最喜歡在每一步打印當(dāng)前坐標(biāo)和方向值cout num num dir dir row row col col endl;看幾個數(shù)字就能發(fā)現(xiàn)問題在哪一步非常高效。4.4 防御性賦值矩陣初始值的選擇方向向量法依賴matrix[nextRow][nextCol] ! 0來判斷當(dāng)前位置是否已經(jīng)填過。這個設(shè)計的隱含前提是有效數(shù)字從1開始0代表未填。所以初始化矩陣時必須全部置0。這里有個隱藏問題如果題目允許數(shù)字從0開始填那么0就不再是未填的標(biāo)志了這時候還用它判斷就會出錯。如果在面試現(xiàn)場遇到這種變形你需要用一個額外的bool二維數(shù)組來標(biāo)記是否已填或者改用邊界收縮法。我看過有人用vectorvectorint matrix(n, vectorint(n, -1))然后用-1作為未填標(biāo)志也可以。關(guān)鍵是把這個約定寫在注釋里提醒自己這里-1是特殊值不是真實數(shù)據(jù)。防御性編程的原則是把不變量寫在代碼注釋里讓維護的人一眼看到。環(huán)形矩陣的不變量有三個每個格子恰好被填一次填完的方向序列依次是向右、向下、向左、向上邊界變量永遠(yuǎn)指向下一個待填入的位置。你寫完代碼后可以逐條核對這三個不變量是否成立能快速定位邏輯漏洞。5. 從會寫到會變環(huán)形矩陣的幾種常見變形學(xué)會了基礎(chǔ)版本我們來看看這個題怎么變形。面試官最喜歡干的事就是把基礎(chǔ)題稍微改一下看你是否真的理解而不僅僅是背代碼。5.1 逆時針環(huán)形矩陣逆時針環(huán)形矩陣是最簡單的變形只需要調(diào)整方向順序。方向向量法改成int dirs[4][2] {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};也就是第一步往下走然后向右然后向上然后向左。這樣從左上角開始先沿第一列向下填再沿最后一行向右填……整體就是逆時針螺旋。邊界收縮法也可以做只要調(diào)整內(nèi)層四個for循環(huán)的順序和方向從上到下填左邊這一列從左到右填下邊這一行從下到上填右邊這一列從右到左填上邊這一行注意如果你沿用上面的代碼只是簡單把前面的{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}改為{{1, 0}, {0, -1}, {-1, 0}, {0, 1}}先下再左再上再右那就成了另一種圖案從左上角開始先下到左下角然后向右到右下角……這樣整體是逆時針路徑方向和初始位置組合起來就會形成不同的起點路徑。關(guān)于變形的方向順序我建議每次改完都先跑一遍n4用輸出對比預(yù)期圖形。這里多說一句方向數(shù)組的排列順序本質(zhì)上定義了機器人的轉(zhuǎn)彎規(guī)則。順時針的四個方向是右下左上逆時針是下右上左。你只要改這一處所有邏輯自動適配。5.2 矩形螺旋矩陣M×N題目升級給一個m行n列的矩陣按螺旋順序填入1到m乘n。這個變體在力扣和面試中出現(xiàn)頻率極高。邊界收縮法只需要把n改成兩個維度vectorvectorint generateSpiralMatrixMN(int m, int n) { vectorvectorint matrix(m, vectorint(n, 0)); int top 0, bottom m - 1; int left 0, right n - 1; int num 1; while (top bottom left right) { for (int j left; j right; j) { matrix[top][j] num; } top; for (int i top; i bottom; i) { matrix[i][right] num; } --right; if (top bottom) { for (int j right; j left; --j) { matrix[bottom][j] num; } --bottom; } if (left right) { for (int i bottom; i top; --i) { matrix[i][left] num; } left; } } return matrix; }這里的坑在于矩形矩陣可能最后剩的是一行或者一列而不是一個點。比如5行2列的矩陣螺旋到中間時會只剩一列此時第一步填不了left right直接進入第二步上到下填這一列。如果你按照標(biāo)準(zhǔn)4步走第一步的for循環(huán)j left; j right因為left0、right1還是會執(zhí)行這會導(dǎo)致第一行被重復(fù)賦值。不對仔細(xì)看矩形矩陣在while循環(huán)條件成立時第一步一定可以填因為left right。真正需要防的仍然是第三和第四步——當(dāng)只剩一列但還多行時第二步填完后top會增加此時可能top bottom第三步的if會攔住當(dāng)只剩一行且多列時第一步填完后right減少第四步的if會攔住。我用5行2列跑了一遍1 2 3 4 5 6 7 8 9 10不對這好像是直接逐行填了不是螺旋。咱們重新想5行2列的螺旋填充預(yù)期1 2 10 3 9 4 8 5 7 6我的代碼跑出來確實應(yīng)該是這樣。while循環(huán)第一圈第一步填第0行第0列和第1列得到1,2top變1。第二步填右邊列i從1到4得第1行第1列3、第2行第1列4、第3行第1列5、第4行第1列6right變0。第三步top(1) bottom(4)為真填down這一行即第4行j從0到0得7bottom變3。第四步left(0) right(0)為真從i3到1往上填左邊列得8、9、10left變1。循環(huán)條件top(1) bottom(3)為真left(1) right(0)為假循環(huán)退出。結(jié)果對嗎填滿10個格子1,2,3,4,5,6,7,8,9,10坐標(biāo)分別是(0,0),(0,1),(1,1),(2,1),(3,1),(4,1),(4,0),(3,0),(2,0),(1,0)。打印出來就是1 2 10 3 9 4 8 5 7 6完美。這個例子說明矩形矩陣的while條件top bottom left right在只剩一行或只剩一列時依然能正確退出不會死循環(huán)。你可以用3行5列再測一次預(yù)期是1 2 3 4 5 12 13 14 15 6 11 10 9 8 7這也是對的。第三個和第四個if在這里徹底攔住了重復(fù)賦值。5.3 從中心向外螺旋填充這個變形就比較有意思了不是從外圈開始而是從正中心開始順時針一圈圈往外填。要求n為奇數(shù)否則沒有嚴(yán)格的正中心。實現(xiàn)思路其實可以把方向向量法反向使用數(shù)字1放在中心然后按照某種順序向外走。但反過來走時是否越界不能用矩陣邊界判斷因為初始位置在中間越界遠(yuǎn)著呢。這時候可以用距離判斷來確定什么時候該轉(zhuǎn)向。我自己的做法是觀察從中心出發(fā)走螺旋的路徑可以發(fā)現(xiàn)它是按照步長1、1、2、2、3、3、4、4……這樣的節(jié)奏走的也就是每次移動的步長每兩個方向增加1。方向順序是向上、向左、向下、向右——注意是從中心出發(fā)的上左下右因為從中心開始走第一格算是向上。寫出來的核心循環(huán)大概長這樣vectorvectorint generateOutwardSpiral(int n, int centerRow, int centerCol) { vectorvectorint matrix(n, vectorint(n, 0)); centerRow n / 2; centerCol n / 2; int row centerRow, col centerCol; int dirs[4][2] {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; int dir 0; int step 1; int num 1; matrix[row][col] num; while (num n * n) { for (int s 0; s 2; s) { for (int i 0; i step; i) { row dirs[dir][0]; col dirs[dir][1]; matrix[row][col] num; } dir (dir 1) % 4; } step; } return matrix; }這個算法的核心是每個步長走兩次步長1走兩個方向共2格步長2走兩個方向共4格以此類推。這段代碼我只測試了n為奇數(shù)的標(biāo)準(zhǔn)情況如果你要用在更大的矩陣或者偶數(shù)階矩形上還需要額外處理邊界。從中心向外螺旋這種題在工程里也有應(yīng)用比如圖像處理中從熱點區(qū)域向外擴散掃描像素。5.4 環(huán)形矩陣的打印模式有些題目不是讓你生成矩陣而是給一個已經(jīng)填好數(shù)據(jù)的矩陣讓你按螺旋順序打印出來。比如給定1 2 3 4 5 6 7 8 9要輸出1 2 3 6 9 8 7 4 5。這和填充正好是反方向的操作。填充是寫入打印是讀取。但邊界管理邏輯幾乎一樣還是四個邊界變量四步走只是每步從賦值變成輸出。這里有個小坑打印時要注意不要輸出多余的空格以及最后一個元素后面不要輸出分隔符。我一般先把所有螺旋順序的數(shù)字push到一個vector里再統(tǒng)一用空格連起來輸出。這樣格式好控制也便于后續(xù)處理。示例代碼片段void printSpiralOrder(const vectorvectorint matrix) { int m matrix.size(); if (m 0) return; int n matrix[0].size(); int top 0, bottom m - 1, left 0, right n - 1; vectorint res; while (top bottom left right) { for (int j left; j right; j) res.push_back(matrix[top][j]); top; for (int i top; i bottom; i) res.push_back(matrix[i][right]); --right; if (top bottom) { for (int j right; j left; --j) res.push_back(matrix[bottom][j]); --bottom; } if (left right) { for (int i bottom; i top; --i) res.push_back(matrix[i][left]); left; } } for (int i 0; i res.size(); i) { if (i) cout ; cout res[i]; } cout endl; }對比一下就會發(fā)現(xiàn)它和generateSpiralMatrix的結(jié)構(gòu)一模一樣只是內(nèi)層操作從寫換成讀。所以只要你真正理解了填充的邏輯打印的題就是送分題。6. 刷題和面試時的一些經(jīng)驗提醒說到最后我想分享一些代碼本身之外的經(jīng)驗這些都是我在實際做題、面試和給別人講題過程中沉淀下來的。6.1 復(fù)雜度分析別忽略環(huán)形矩陣生成的時間復(fù)雜度是O(n^2)空間復(fù)雜度是O(n^2)因為要返回整個矩陣。如果你考慮輔助空間邊界收縮法只用了四個int變量可以說是O(1)輔助空間方向向量法除了矩陣外只用了方向數(shù)組和幾個int也是O(1)輔助空間。面試時如果被問到能不能優(yōu)化空間你可以回答如果只是打印螺旋順序可以在生成過程中直接輸出不需要存儲整個矩陣但如果題目要求返回矩陣那么O(n^2)空間是不可避免的因為答案本身就是O(n^2)的數(shù)據(jù)。有人可能會問能不能不用vector用數(shù)組完全可以用int matrix[n][n]在C中不是標(biāo)準(zhǔn)做法變長數(shù)組不是標(biāo)準(zhǔn)C特性所以我建議用vector這也是現(xiàn)代C的推薦方式。如果你在嵌入式環(huán)境里需要固定大小可以用std::array或者動態(tài)內(nèi)存分配。實際工程中vector的開銷可以忽略不計因為它本質(zhì)上是三個指針加堆內(nèi)存。6.2 面試官喜歡追問的幾個點我在模擬面試時經(jīng)常把這幾個點作為追問第一如果n非常大比如10000代碼能不能改成原地生成而不額外占用內(nèi)存實際上不行因為你要返回矩陣答案本身就是O(n^2)的。但你可以在函數(shù)內(nèi)部復(fù)用輸入?yún)?shù)比如題目給的矩陣本來就是n×n的空矩陣那么直接在里面填數(shù)就是原地操作。第二為什么方向向量法中要用matrix[nextRow][nextCol] ! 0來判斷是否已填如果用 0來判斷有什么隱患隱患是你必須保證所有未填位置都是0而這需要初始化時全部置0。如果題目從0開始填數(shù)這個條件就失效了。第三邊界收縮法里第三步和第四步的if條件可以去掉嗎我說可以但要去掉就需要在while循環(huán)條件里做額外的判斷比如在第三步前判斷是否top bottom再決定是否退出。但直接寫if更清晰面試官通常認(rèn)可這個解釋。第四如果矩陣不是正方形比如3行4列結(jié)果應(yīng)該長什么樣這其實就是前面講的M×N變體。你要能迅速指出while條件不變第三步和第四步的if仍然需要。6.3 我給正在刷題的人一個具體的練習(xí)路徑如果你之前完全沒接觸過環(huán)形矩陣我的建議是第一步先把邊界收縮法的代碼抄一遍手推開n3和n4的每一步確認(rèn)每個變量的變化。這一步的目標(biāo)是建立邊界收縮的直覺。手推就是自己在紙上把top、bottom、left、right的值寫下來跟著代碼一步一步劃掉已填的格子。這個動作看起來很笨但比盯著代碼看一小時都管用。第二步不看代碼自己從零寫一遍邊界收縮法。寫完用n1、2、3、4驗證。這一步的目標(biāo)是檢測你是否真的理解了邊界更新的順序。第三步實現(xiàn)方向向量法跑同樣的測試用例。這一步是訓(xùn)練狀態(tài)轉(zhuǎn)換思維。第四步把自己做過的變形題逆時針、矩形、從中心向外全部用兩種方法實現(xiàn)一遍。按照這個路徑練下來環(huán)形矩陣這個類別的題你基本能做到見題就寫。不用背任何代碼因為每一步的邏輯你已經(jīng)內(nèi)化了。我在講給自己的朋友聽的時候經(jīng)常說一句話環(huán)形矩陣是我見過的最典型的腦子會了手不會的題目。解決它的關(guān)鍵不是聰明而是把邊界變化在草稿紙上畫清楚。你只要愿意畫一遍圖這道題難度降一半。另外提醒一下環(huán)境問題寫C代碼時如果用Visual Studio默認(rèn)會啟用SDK檢查vector越界時會彈對話框如果在Linux上用g編譯建議加上-Wall -Wextra把警告全顯出來很多邊界錯誤其實編譯器能提前給出warning。我自己習(xí)慣用的調(diào)試命令是g -stdc17 -Wall -Wextra -g spiral.cpp -o spiral順手把編譯標(biāo)準(zhǔn)定到C17方向數(shù)組、vector、auto這些特性都能直接用沒什么兼容性問題。最后再分享一個小技巧如果你在家里練習(xí)題目做錯了想復(fù)盤別急著看題解。先把錯誤的版本另存為一個文件猜一猜錯誤會發(fā)生在哪個用例下——這個預(yù)告錯誤的過程比直接改對更能加深印象。反正我自己是靠這個方法把邊界類題目徹底練熟的。