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