前兩天刷題碰到一道字符串處理的經(jīng)典題——拼數(shù)number。題面包裝得很像課堂作業(yè)小 r 正在學(xué)習(xí)字符串處理小 x 給了小 r 一個(gè)字符串 s里面是一串由空格隔開的數(shù)字要求把它們?nèi)科唇映梢粋€(gè)整數(shù)并且拼出來(lái)的數(shù)要盡量大。我一開始覺得這就是排序題把數(shù)字從大到小排一遍就完了結(jié)果樣例就把我的想法打回去了。仔細(xì)想了一圈才發(fā)現(xiàn)這道題把字符串處理、貪心思想和逆向思維全擰在了一塊兒順手還牽扯出排序?qū)懛ɡ锏脑S多坑。也因?yàn)檫@道題我把最近刷題清單里的六個(gè)高頻專題——字符串處理、貪心思想、逆向思維、二叉排序樹、鏈表模式匹配、圖形打印——重新整理了一遍寫成這篇手記。想沖擊機(jī)試、面試手撕算法或者刷題剛起步的朋友都可以參考一下。1. 字符串處理很多算法題的入場(chǎng)券1.1 拼數(shù)這題考的不只是“排序”先把題意說(shuō)清楚。給定 n 個(gè)非負(fù)整數(shù)比如3、30、34、5、9目標(biāo)是把它們按某種順序首尾相接得到一個(gè)盡可能大的整數(shù)。題目描述里為什么會(huì)涉及字符串 s因?yàn)槠唇雍蟮慕Y(jié)果位數(shù)可能上百位早就不在一個(gè)int或long long能裝下的范圍內(nèi)所以這道題天然就是用字符串來(lái)做的。你拿到的一開始就是字符串或者你得先把數(shù)字轉(zhuǎn)成字符串再處理拼接和比較。我最初的錯(cuò)誤做法非常典型按每個(gè)數(shù)的數(shù)值從大到小排序。用3、30一試就露餡——數(shù)值上 3 比 30 小如果讓 30 排在前面得到303讓 3 排在前面得到330明顯330 303。也就是說(shuō)3雖然數(shù)值小卻必須先放。再看34、3、30這一組按數(shù)值降序是34、30、3拼出來(lái)34303可實(shí)際上34、3、30能拼成34330后者更大。這說(shuō)明“盡量把數(shù)值大的放前面”這個(gè)直覺完全不靠譜。正確的比較方式也來(lái)自很樸素的嘗試兩個(gè)數(shù)字 x、y 誰(shuí)在前直接比較 x 拼在 y 前面和 y 拼在 x 前面誰(shuí)更大就行。如果x y y x那 x 應(yīng)該在前否則 y 在前。把這種兩兩比較抽象成自定義排序規(guī)則對(duì)整個(gè)數(shù)組排一次序最后得到的拼接結(jié)果就是答案。這里有兩個(gè)隱秘的坑第一x y不能用整數(shù)相加否則一旦超過(guò)類型范圍就會(huì)溢出必須保留字符串拼接形式第二排序比較器必須滿足嚴(yán)格弱序用而不是否則標(biāo)準(zhǔn)庫(kù)排序的行為是未定義的。很多初學(xué)的朋友在這里寫掛不是思路想錯(cuò)而是對(duì)字符串作為“比較載體”這件事不夠重視。1.2 字符串處理最容易翻車的幾個(gè)細(xì)節(jié)第一個(gè)細(xì)節(jié)是拼接方向。比較a b和b a時(shí)兩邊都得真的拼出來(lái)再比不要只拼一邊或者想當(dāng)然地認(rèn)為“字典序大的在前”。字符串的字典序和數(shù)值序并不等價(jià)比如9的字典序大于10但數(shù)值上 9 小于 10。所以拼數(shù)這類場(chǎng)景里唯一可靠的基準(zhǔn)就是完整拼接后的字符串。第二個(gè)細(xì)節(jié)是 C 比較器的寫法。我見過(guò)不少人把函數(shù)簽名寫成bool cmp(string a, string b)雖然也能跑但每次排序調(diào)用都會(huì)發(fā)生兩次字符串拷貝數(shù)據(jù)量一大性能立刻變差。正確姿勢(shì)是傳const string如下#include bits/stdc.h using namespace std; bool cmp(const string a, const string b) { return a b b a; } int main() { int n; cin n; vectorstring v(n); for (int i 0; i n; i) cin v[i]; sort(v.begin(), v.end(), cmp); if (v[0] 0) { cout 0 endl; return 0; } for (const string s : v) cout s; cout endl; return 0; }注意最后這個(gè)v[0] 0的判斷。如果排序后第一項(xiàng)還是0說(shuō)明輸入的所有數(shù)字都是 0此時(shí)正確輸出應(yīng)該是單個(gè)0。如果不做這個(gè)特判你會(huì)拼出一長(zhǎng)串000...0樣例可能看不出來(lái)大數(shù)據(jù)直接判錯(cuò)。第三個(gè)細(xì)節(jié)是語(yǔ)言層面的字符串拼接成本。Python 里字符串是不可變對(duì)象循環(huán)里反復(fù)執(zhí)行ans s會(huì)產(chǎn)生大量臨時(shí)對(duì)象復(fù)雜度變得很難看。正確做法是先把所有片段放進(jìn)列表最后統(tǒng)一用.join(list)。C 的vectorstring再拼接也要注意性能好在題目通常不會(huì)卡到這一步但養(yǎng)成好習(xí)慣不吃虧。2. 貪心思想不只是“每步選最大”2.1 怎么判斷一道題能不能貪貪心思想的定義誰(shuí)都會(huì)背每一步都做當(dāng)前看起來(lái)最好的選擇希望最終結(jié)果全局最優(yōu)。但真正做題時(shí)很多人栽在“看起來(lái)能貪其實(shí)不能貪”的題上。我的經(jīng)驗(yàn)是看到一道題先用三件事去試能不能把決策分解成一系列獨(dú)立的“誰(shuí)先誰(shuí)后”選擇有沒(méi)有一個(gè)清晰的可比較優(yōu)先級(jí)交換任意兩個(gè)相鄰決策會(huì)不會(huì)影響其它部分的結(jié)果。如果一個(gè)選完就影響后續(xù)所有選擇那多半不是簡(jiǎn)單貪心能解決的可能得上動(dòng)態(tài)規(guī)劃。拼數(shù)為什么能貪因?yàn)樗鼭M足一個(gè)很關(guān)鍵的性質(zhì)任意兩個(gè)數(shù)字的相對(duì)順序只影響這兩個(gè)數(shù)字拼接出來(lái)的那一段結(jié)果不影響它們前后其它數(shù)字的內(nèi)部順序。換句話說(shuō)當(dāng)你把3放在30前面更好時(shí)這個(gè)“好”是穩(wěn)定的不會(huì)因?yàn)榕赃叢辶艘粋€(gè)34而改變。這也解釋了為什么最后能用一個(gè)全局排序搞定而不是做動(dòng)態(tài)規(guī)劃。這里必須強(qiáng)調(diào)貪心不是“憑感覺選最優(yōu)”而是“先證明局部最優(yōu)能被安全傳遞”。常見的證明手段有交換論證、反證法、數(shù)學(xué)歸納法。拿零錢兌換舉例在人民幣面值體系下用盡量少?gòu)垟?shù)的策略確實(shí)可以貪但如果自定義一套奇怪面值貪心會(huì)失敗。做題時(shí)不能因?yàn)轭}目長(zhǎng)得像貪心就硬去貪先找反例找不到再用找到反例立刻換思路。2.2 交換論證與拼數(shù)排序規(guī)則交換論證是貪心題最常用也最像“數(shù)學(xué)題”的一種證明方式。對(duì)拼數(shù)來(lái)說(shuō)假設(shè)最優(yōu)排列中存在相鄰兩項(xiàng) x、y且按我們的規(guī)則應(yīng)該讓 x 在前但實(shí)際排列是 y 在前也就是x y y x但 y 被放在了 x 前面。把 x 和 y 交換觀察整個(gè)拼接結(jié)果的變化x、y 前面的部分和后面的部分都沒(méi)有變只有中間這一段從y x變成x y。因?yàn)檎當(dāng)?shù)的大小由“前綴 中間 后綴”決定前后綴沒(méi)動(dòng)中間值變大了整體自然變大。這就和“最優(yōu)排列”矛盾了。所以最優(yōu)排列里任何相鄰兩項(xiàng)都必須滿足x y y x。接下來(lái)再補(bǔ)一個(gè)傳遞性的問(wèn)題。自定義比較器要在std::sort里安全使用必須滿足傳遞性也就是說(shuō)如果a應(yīng)該排在b前b應(yīng)該排在c前那么a一定應(yīng)該排在c前。這個(gè)性質(zhì)可以從字符串拼接的角度嚴(yán)格推出來(lái)大體思路是把數(shù)字看成帶位權(quán)的字符串形式比較ab和ba本質(zhì)上是在比較某個(gè)加權(quán)字典序。競(jìng)賽中你不需要每次手推但面試時(shí)如果被追問(wèn)能說(shuō)出“交換論證 比較關(guān)系可傳遞”這兩點(diǎn)就夠了。代碼上還有一個(gè)容易被忽略的點(diǎn)比較器寫作a b b a相等時(shí)返回false這才是嚴(yán)格弱序。如果寫成程序可能在某些編譯器上陷入未定義行為排序結(jié)果甚至可能打亂我第一次寫拼數(shù)時(shí)就被這種細(xì)節(jié)坑過(guò)。3. 逆向思維正面走不通就反著來(lái)3.1 逆向思維在算法題里長(zhǎng)什么樣逆向思維不是一種具體的數(shù)據(jù)結(jié)構(gòu)而是一種視角切換。我總結(jié)了幾種常見的“反面”形態(tài)從結(jié)果反推原因、從最終狀態(tài)倒推初始狀態(tài)、從問(wèn)題補(bǔ)集入手、從結(jié)尾往前處理。拼數(shù)里的逆向體現(xiàn)在一個(gè)很小的點(diǎn)上——不要問(wèn)“哪個(gè)數(shù)字大”而要問(wèn)“兩個(gè)數(shù)字誰(shuí)拼在前面更好”。這個(gè)問(wèn)題一反過(guò)來(lái)整道題的解法就從“數(shù)值排序”跳到了“拼接比較”。另一個(gè)很常見的逆向形態(tài)是“正難則反”。比如一個(gè)圖不斷刪點(diǎn)問(wèn)每次刪完還剩多少個(gè)連通塊。正著做每次都要重新計(jì)算很麻煩。如果先把所有要?jiǎng)h的點(diǎn)全部刪掉得到最終圖然后倒著把點(diǎn)一個(gè)一個(gè)加回去用并查集維護(hù)連通塊每個(gè)點(diǎn)的加入只需要處理幾條鄰邊復(fù)雜度直線下降。這種“最終狀態(tài)倒推”在網(wǎng)上被叫“離線逆向并查集”原理并不復(fù)雜但沒(méi)見過(guò)的人第一次很難想到。還有一類是“從右往左想”。很多單鏈表、后綴類的問(wèn)題正著掃描時(shí)要記錄各種信息一旦從右往左掃描信息的傳遞立刻變得自然。最典型的是“找出右邊第一個(gè)比自己小的元素”正著做用暴力是 O(n2)反著用單調(diào)棧每個(gè)元素進(jìn)棧出棧一次整體 O(n)。我第一次學(xué)單調(diào)棧時(shí)最大的感慨就是原來(lái)有些事?lián)Q一個(gè)方向會(huì)這么順。3.2 三個(gè)值得收藏的逆向處理場(chǎng)景第一個(gè)場(chǎng)景是刪除轉(zhuǎn)添加。前面說(shuō)的并查集逆向就是這個(gè)套路適用于“不斷刪除”的題目。拿到題先別急著模擬刪除花兩分鐘想想如果反過(guò)來(lái)按時(shí)間倒序處理所有刪除操作就變成了插入操作而插入恰好是并查集最擅長(zhǎng)的。第二個(gè)場(chǎng)景是刪數(shù)問(wèn)題的“保留視角”。題目是這樣的給定一個(gè)數(shù)字串刪掉 k 個(gè)數(shù)字使剩下的數(shù)字組成的數(shù)最小數(shù)字相對(duì)順序不能變。正向想“刪哪 k 個(gè)”會(huì)非常亂但換一個(gè)說(shuō)法——從原串里保留 len-k 個(gè)數(shù)字——思路就順了。維護(hù)一個(gè)棧從左到右掃描如果當(dāng)前數(shù)字比棧頂小說(shuō)明棧頂這個(gè)“更大的數(shù)字”留著不如刪掉于是彈出棧頂。整個(gè)過(guò)程始終在決定“保留誰(shuí)”而不是“刪掉誰(shuí)”。string removeKdigits(string num, int k) { string stk; for (char c : num) { while (k 0 !stk.empty() stk.back() c) { stk.pop_back(); k--; } stk.push_back(c); } while (k--) stk.pop_back(); int pos 0; while (pos stk.size() stk[pos] 0) pos; return pos stk.size() ? 0 : stk.substr(pos); }第三個(gè)場(chǎng)景是拼數(shù)里的“想要最大就反向比較”。拼最大數(shù)用a b b a拼最小數(shù)就把規(guī)則反轉(zhuǎn)成a b b a。很多題把最大換成最小就讓人懵了其實(shí)就是比較符號(hào)一個(gè)反轉(zhuǎn)的事。這正好體現(xiàn)逆向思維的實(shí)用價(jià)值一旦你理解了正向規(guī)則的本質(zhì)反向規(guī)則根本不需要重新想。4. 二叉排序樹把動(dòng)態(tài)有序性握在手里4.1 BST 的核心性質(zhì)與三個(gè)基礎(chǔ)操作二叉排序樹Binary Search TreeBST的定義看起來(lái)很短對(duì)于任意節(jié)點(diǎn)左子樹所有節(jié)點(diǎn)的值小于當(dāng)前節(jié)點(diǎn)右子樹所有節(jié)點(diǎn)的值大于當(dāng)前節(jié)點(diǎn)。由這個(gè)性質(zhì)可以推出一個(gè)重要結(jié)論中序遍歷 BST 得到的結(jié)果一定是有序的。這意味著 BST 天生就是為“動(dòng)態(tài)維護(hù)一組有序數(shù)據(jù)”設(shè)計(jì)的插入、刪除、查找都只跟樹的高度有關(guān)。三個(gè)基礎(chǔ)操作必須滾瓜爛熟。插入從根開始比當(dāng)前節(jié)點(diǎn)小就向左大就向右走到空位置就掛上新節(jié)點(diǎn)。查找同樣是從根開始每走一步就可以排除整棵子樹。刪除稍麻煩分三種情況沒(méi)有孩子直接刪只有一個(gè)孩子把孩子提上來(lái)有兩個(gè)孩子一般用右子樹的最小節(jié)點(diǎn)或左子樹的最大節(jié)點(diǎn)替代被刪節(jié)點(diǎn)再刪掉那個(gè)替身。我自己經(jīng)常用的插入代碼長(zhǎng)這樣struct Node { int val; Node *left, *right; Node(int v) : val(v), left(nullptr), right(nullptr) {} }; Node* insert(Node* root, int val) { if (!root) return new Node(val); if (val root-val) root-left insert(root-left, val); else root-right insert(root-right, val); return root; }注意這里else部分包含了“等于”的情況我默認(rèn)重復(fù)值插入右子樹。不同題目對(duì)重復(fù)值的處理要求不同有的要求去重有的要求計(jì)數(shù)寫之前一定要看清題。如果要求嚴(yán)格不重復(fù)插入前先查找一次如果允許重復(fù)就要明確所有相等值都去同一側(cè)否則樹的中序遍歷會(huì)丟數(shù)據(jù)。4.2 手寫 BST 的幾個(gè)關(guān)鍵坑第一個(gè)坑是退化。BST 的復(fù)雜度是期望 O(log n)但這個(gè)結(jié)論建立在插入序列足夠隨機(jī)的前提下。如果數(shù)據(jù)恰好有序輸入比如1、2、3、4、5依次插入樹會(huì)退化成一棵單鏈查找和插入全部變成 O(n)。很多題的數(shù)據(jù)就是喜歡給你這種“有序”序列專門卡不寫平衡樹的人。所以在競(jìng)賽里能直接用std::set、std::map就用它們內(nèi)部是紅黑樹自動(dòng)保證平衡如果需要手寫也要意識(shí)到數(shù)據(jù)結(jié)構(gòu)本身并沒(méi)有承諾最壞情況復(fù)雜度。第二個(gè)坑是刪除操作的實(shí)現(xiàn)細(xì)節(jié)。刪除有兩個(gè)孩子的節(jié)點(diǎn)時(shí)如果你選擇用右子樹最小節(jié)點(diǎn)替代必須先找到這個(gè)“最小節(jié)點(diǎn)”再遞歸刪除它。因?yàn)樽钚」?jié)點(diǎn)位于右子樹的左下角它最多只有一個(gè)右孩子刪除邏輯會(huì)簡(jiǎn)單很多。手寫時(shí)最容易出錯(cuò)的地方是遞歸返回值沒(méi)有接收導(dǎo)致刪除后父節(jié)點(diǎn)指針還指向原來(lái)的節(jié)點(diǎn)樹直接斷掉。建議寫完用一組包含各種形態(tài)的數(shù)據(jù)反復(fù)測(cè)試刪根、刪葉子、刪只有一個(gè)孩子的節(jié)點(diǎn)、刪有兩個(gè)孩子的節(jié)點(diǎn)。第三個(gè)坑是和字符串處理的結(jié)合。BST 的節(jié)點(diǎn)值不一定非是整數(shù)也可以是字符串。比如給你一批單詞要求去重并按字典序輸出最直觀的做法就是建一棵字符串 BST中序遍歷就是字典序。C 里直接用string的operator就能比較比手寫strcmp省心不少。這種場(chǎng)景能幫你把“有序性”這個(gè)抽象概念從數(shù)字?jǐn)U展到文本遇到“動(dòng)態(tài)維護(hù)字典序集合”的題會(huì)更有感覺。5. 鏈表模式匹配沒(méi)有隨機(jī)訪問(wèn)的匹配戰(zhàn)5.1 鏈表匹配為什么不能直接套 KMP在數(shù)組里判斷一個(gè)串是否是另一個(gè)串的子串經(jīng)典算法是 KMP復(fù)雜度做到 O(n m)。它能高效的根本原因有兩個(gè)數(shù)組支持隨機(jī)訪問(wèn)失配時(shí)可以直接跳回某個(gè)位置繼續(xù)比較數(shù)組長(zhǎng)度固定所有回溯操作都在常數(shù)時(shí)間內(nèi)完成。鏈表不一樣單鏈表只能沿著next指針往前走不能后退也沒(méi)有下標(biāo)索引。你想讓模式串回退到某個(gè)位置除非額外存下沿途所有節(jié)點(diǎn)否則做不到。所以鏈表上的模式匹配最常見——也最容易被接受——的方案是暴力雙指針。外面用一個(gè)指針遍歷主鏈表每到一個(gè)節(jié)點(diǎn)就把它當(dāng)成匹配起點(diǎn)內(nèi)層再用一個(gè)指針按模式鏈表往后走。如果匹配成功就返回 true失敗就把外層指針往前挪一格再重新開始。最壞情況是主鏈每個(gè)位置都比較到模式末尾才發(fā)現(xiàn)失敗復(fù)雜度 O(n × m)。對(duì)于鏈表這種結(jié)構(gòu)這個(gè)復(fù)雜度很多時(shí)候是能接受的因?yàn)轭}目給的數(shù)據(jù)規(guī)模通常不會(huì)太大。另一個(gè)常見思路是“轉(zhuǎn)數(shù)組再匹配”。先遍歷一遍主鏈表把節(jié)點(diǎn)值存進(jìn)一個(gè) vector再把模式鏈表也存進(jìn)去然后直接套字符串匹配或std::search。思路簡(jiǎn)單、不容易出錯(cuò)代價(jià)是額外 O(n) 空間。還有一種更進(jìn)階的思路是哈希把模式鏈的每個(gè)節(jié)點(diǎn)值滾成哈希值再在主鏈上滑動(dòng)窗口比對(duì)能把復(fù)雜度降到近似 O(n m)但哈希沖突、取模、長(zhǎng)度對(duì)齊這些細(xì)節(jié)足夠讓你寫半個(gè)小時(shí)筆試時(shí)間緊張時(shí)性價(jià)比不高。5.2 三種實(shí)戰(zhàn)思路與一個(gè)常被忽略的坑先給一個(gè)最干脆的暴力模板struct Node { int val; Node* next; }; bool matchList(Node* head, Node* pattern) { if (!pattern) return true; if (!head) return false; Node* cur head; while (cur) { Node* a cur; Node* b pattern; while (a b a-val b-val) { a a-next; b b-next; } if (!b) return true; cur cur-next; } return false; }這個(gè)函數(shù)的時(shí)間復(fù)雜度要看主鏈?zhǔn)Ｓ嚅L(zhǎng)度和模式長(zhǎng)度的乘積。有一個(gè)很容易被忽略的優(yōu)化先掃一遍兩條鏈的長(zhǎng)度如果主鏈?zhǔn)Ｓ喙?jié)點(diǎn)數(shù)少于模式鏈長(zhǎng)度直接不用比了或者先數(shù)出模式鏈總長(zhǎng)在主鏈上只走到n - m的位置。這樣能擋掉一大批無(wú)意義的比較。接下來(lái)是轉(zhuǎn)數(shù)組方案。把主鏈和模式鏈都轉(zhuǎn)成vectorint然后比較所有長(zhǎng)度相等的子數(shù)組。這么做有個(gè)好處你可以在轉(zhuǎn)數(shù)組的過(guò)程中順手做“翻轉(zhuǎn)鏈表的回文判斷”之類的事但要注意如果匹配要求的是節(jié)點(diǎn)對(duì)象地址相同而不是值相同轉(zhuǎn)數(shù)組就幫不上忙因?yàn)閿?shù)組比較的是值。最后一個(gè)必須提的坑是環(huán)。如果主鏈表內(nèi)部有環(huán)暴力雙指針會(huì)進(jìn)入死循環(huán)——外層指針沿著環(huán)永遠(yuǎn)走不完。所以在做任何鏈表匹配之前先判斷有沒(méi)有環(huán)用快慢指針如果有環(huán)先處理環(huán)的問(wèn)題再談模式匹配。我第一次在做鏈表題時(shí)忽略了這個(gè)調(diào)試了一個(gè)小時(shí)才發(fā)現(xiàn)根本不是匹配邏輯的問(wèn)題而是數(shù)據(jù)里藏了一個(gè)環(huán)。這個(gè)教訓(xùn)告訴我鏈表類題目開場(chǎng)第一句一定是問(wèn)自己這里會(huì)不會(huì)有環(huán)6. 圖形打印老題新看輸出類問(wèn)題的一招鮮6.1 圖形打印的本質(zhì)是坐標(biāo)映射圖形打印類題目常出現(xiàn)在筆試和機(jī)試的入門部分比如輸出菱形、回形矩陣、三角形、楊輝三角。很多人一看到這種題就開始逐行cout 一個(gè)個(gè)空格去湊結(jié)果把自己繞暈。我的經(jīng)驗(yàn)是先把圖形看成一個(gè)二維字符矩陣然后逐行逐列遍歷所有坐標(biāo)判斷“這個(gè)坐標(biāo)該放什么字符”。判斷條件通常可以被總結(jié)成數(shù)學(xué)關(guān)系式而不是老老實(shí)實(shí)模擬畫圖的過(guò)程。舉一個(gè)最經(jīng)典的菱形例子。假設(shè)要輸出一個(gè)由星號(hào)組成的菱形總行數(shù)為奇數(shù)比如 5 行。把圖形放在一個(gè) 5×5 的坐標(biāo)棋盤上中心點(diǎn)坐標(biāo)為(r0, c0)。一個(gè)位置(r, c)屬于菱形當(dāng)且僅當(dāng)它到中心的曼哈頓距離小于等于某個(gè)半徑。所謂曼哈頓距離就是abs(r - r0) abs(c - c0)。你根本不需要關(guān)心每一行有幾個(gè)空格只需要在雙重循環(huán)里用這個(gè)條件判斷即可。void printDiamond(int n) { int c n / 2; for (int r 0; r n; r) { for (int col 0; col n; col) { if (abs(r - c) abs(col - c) c) cout *; else cout ; } cout \n; } }我第一次用這個(gè)模板做菱形時(shí)最大的收獲不是記住代碼而是理解“圖形 坐標(biāo)集合”。你只要能把圖形的輪廓轉(zhuǎn)換成一個(gè)不等式剩下的代碼就是雙重循環(huán)的問(wèn)題。三角形、平行四邊形、X型圖案全部是這類思想先定位再判斷最后輸出。6.2 菱形與回形兩個(gè)生成模板比起菱形回形矩陣也叫蛇形填數(shù)復(fù)雜一點(diǎn)它是按一定方向在二維數(shù)組里填入 1 到 n2 的數(shù)字碰到邊界或已經(jīng)填過(guò)的格子就轉(zhuǎn)向。經(jīng)典做法是用方向數(shù)組int dx[4] {0, 1, 0, -1}; int dy[4] {1, 0, -1, 0}; int dir 0; int x 0, y 0; for (int num 1; num n * n; num) { a[x][y] num; int nx x dx[dir]; int ny y dy[dir]; if (nx 0 || nx n || ny 0 || ny n || a[nx][ny] ! 0) { dir (dir 1) % 4; nx x dx[dir]; ny y dy[dir]; } x nx; y ny; }這里最核心的技巧是“先探路再移動(dòng)”每次填完數(shù)字先嘗試按當(dāng)前方向走出一步如果下一步越界或者已經(jīng)被填過(guò)就轉(zhuǎn)向再重新計(jì)算下一步。這樣代碼非常統(tǒng)一不需要為四個(gè)方向各寫一遍判斷。我見過(guò)不少同學(xué)用 if-else 把四個(gè)方向分開寫代碼又長(zhǎng)又容易漏方向數(shù)組就是來(lái)一勞永逸解決這件事的。圖形打印還有一個(gè)很多人不在意的輸出細(xì)節(jié)行尾空格。某些 C 判斷系統(tǒng)對(duì)輸出非常嚴(yán)格每行末尾多一個(gè)空格可能直接判 Wrong Answer。如果題目沒(méi)有明確說(shuō)允許行尾空格建議要么用二維字符數(shù)組先全部填充再一次行輸出要么在循環(huán)里控制最后一個(gè)字符后不打印空格。我踩過(guò)一次這個(gè)坑從那以后所有輸出類題目我都會(huì)額外檢查一遍行尾有沒(méi)有多余字符。這個(gè)習(xí)慣在圖形打印題里尤其重要。最后再分享一個(gè)小技巧圖形打印題的調(diào)試不要只看最終輸出把行號(hào)和列號(hào)標(biāo)出來(lái)按坐標(biāo)對(duì)照題目給的示意圖能很快就定位是條件寫反了還是邊界算錯(cuò)了。配上abs或方向數(shù)組的模板圖形打印題真的是算法題里最容易拿到滿分的類型千萬(wàn)別在這上面丟分。寫完這些專題我最大的體會(huì)是它們單獨(dú)拎出來(lái)都不難真正難的是組合。拼數(shù)這道題外殼是字符串內(nèi)核是貪心鑰匙是逆向構(gòu)造比較規(guī)則二叉排序樹是動(dòng)態(tài)有序性的骨架鏈表把模式匹配從“能隨機(jī)訪問(wèn)”的世界拽回“只能往前走”的世界圖形打印練的是把思路落成輸出代碼的手感。刷題別只背結(jié)論多問(wèn)一句這個(gè)題反過(guò)來(lái)想行不行、換成鏈表還能不能做、數(shù)據(jù)順序會(huì)不會(huì)卡掉樹結(jié)構(gòu)這樣刷一道題的收獲會(huì)比趕十幾道題的進(jìn)度更大。