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