復(fù)試OJ二刷復(fù)盤系列寫到第3篇正好是我把第一輪“背過但沒吃透”的題重新過完近一半的節(jié)點。先說結(jié)論二刷比第一次刷題難受多了因為你會反復(fù)看到某個一刷時“AC了”的題現(xiàn)在連完整的main函數(shù)都憋不出來。那種感覺比第一次見新題還要空虛。但也正是這種“舊題新卡”讓我意識到一刷的通過率有多少水分也讓二刷成了整個復(fù)試機試準(zhǔn)備里最值錢的一段。這篇不打算羅列我又過了多少題而是想把二刷過程中真正改變我做題習(xí)慣的幾個東西寫下來定規(guī)矩、挑錯題、看邊界、摳輸入輸出細(xì)節(jié)以及最后怎么把錯題變成考前能快速翻完的筆記。如果你也在準(zhǔn)備某類復(fù)試OJ或者只是想把算法題從“背模板”提升到“真會做”這篇應(yīng)該對你有用。1. 二刷前我先給自己定了三條規(guī)矩不然就是重復(fù)一刷1.1 規(guī)矩一不看舊AC代碼靠“白紙回憶”起步一刷的時候我大量依賴搜索引擎和題解經(jīng)常是看懂了甚至抄了一遍然后本地跑通就去OJ交。這種代碼屬于“順著題解走的代碼”不是“從題目自己推出來的代碼”。二刷如果還點開自己的提交記錄那等于把一刷的路徑原封不動再走一遍收獲只是多了一點熟練度。我給自己定的規(guī)矩是讀完題之后先把屏幕切到編輯器白紙開始寫不看任何舊代碼。哪怕寫得很爛哪怕寫得比原來的版本長一倍也先寫出來。寫的過程才是真正把“題目的邏輯”和“代碼的表達(dá)”重新接上的過程。有一道很簡單的字符串題一刷我看題解十分鐘就過了二刷讓我在白紙上寫我卡在“怎么處理最后一個單詞”上想了很久。那一刻我才明白一刷的AC本質(zhì)上只是把別人的思路謄寫了一遍。白紙回憶這個動作雖然慢但它能把“背會的”和“真正會的”區(qū)分開。復(fù)試機試考的就是后者所以這條規(guī)矩我一條都沒放松過。1.2 規(guī)矩二跑過樣例不算完必須自問三個“為什么”以前一刷樣例過了就急著提交提交AC了就覺得搞定。這次我強制自己在AC之后多一步自檢這段代碼為什么能在題目數(shù)據(jù)范圍內(nèi)通過我用的算法在時間上是不是最優(yōu)如果不是是大意了還是不會如果把某個輸入換成極端情況n0、全為同一個字符、鏈表只有一個節(jié)點代碼會怎樣這三個問題看起來基礎(chǔ)但二刷時被它們問住的題恰恰是一刷時“背模板”背過的題。比如后面要講的三類翻車題幾乎每一個都是在這三個問題下現(xiàn)出原形的。尤其是第二個問題以前我從來不看題目給的數(shù)據(jù)范圍也不估算復(fù)雜度反正樣例能過就交?，F(xiàn)在我會先問一句這個n最大能到多少我的循環(huán)嵌套扛不扛得住就這一句話已經(jīng)幫我攔下好幾次超時。1.3 規(guī)矩三寧可錯得難看不許抄得順手這里多說一句。很多人二刷維持不住一周就是因為一面是“不會做”的挫敗感一面是“打開題解就能AC”的即時快感后者太誘人了。我后來發(fā)現(xiàn)一個妥協(xié)方案允許自己在卡了二十分鐘后看提示但不允許直接看完整代碼。最多看一眼算法關(guān)鍵詞比如“雙指針”“前綴和”“?！比缓蟀杨}解關(guān)掉繼續(xù)寫。這個方案的好處是既能保證二刷進(jìn)度不被拖死又把“背題解”的空間壓到最小。二刷的意義本來就是把“曾經(jīng)靠提示做出來的題”變成“不靠提示也能安靜寫完的題”。我見過不少人二刷時依然開著一個題解頁面在旁邊那其實只是換了一種方式的一刷。2. 這次重做翻車最多的三類題每一題都是一面鏡子2.1 字符串類一邊循環(huán)走完還要記得補最后的收尾復(fù)試OJ幾乎繞不開字符串題。我這次二刷碰到一道很基礎(chǔ)的題給一段英文文本統(tǒng)計每個單詞出現(xiàn)的次數(shù)不區(qū)分大小寫忽略標(biāo)點符號?？雌饋砗唵挝乙簧蟻砭统隽巳齻€問題用cin s讀入結(jié)果遇到換行和連續(xù)空格直接把一行切得支離破碎判斷“單詞結(jié)束”時等循環(huán)走出去才處理最后一個單詞結(jié)果漏了文本末尾沒有跟隨標(biāo)點的那個單詞把標(biāo)點剔除和大小寫轉(zhuǎn)換寫在同一個位置導(dǎo)致“Hello,”這種帶尾部標(biāo)點的詞被統(tǒng)計成兩個不同的key。正確做法是逐字符讀入而不是按單詞讀入。遇到字母或數(shù)字就把字符轉(zhuǎn)小寫拼進(jìn)當(dāng)前的word遇到非字母數(shù)字就說明一個單詞結(jié)束了此時如果word非空再計數(shù)然后清空word重新拼。這樣“最后一個單詞”只在循環(huán)結(jié)束后補一次即可。#include bits/stdc.h using namespace std; int main() { mapstring, int cnt; char ch; string word; while ((ch getchar()) ! EOF) { if (isalnum(ch)) { word tolower(ch); } else { if (!word.empty()) { cnt[word]; word.clear(); } } } if (!word.empty()) cnt[word]; for (auto kv : cnt) cout kv.first kv.second \n; return 0; }這個解法的時間是O(n)不算map內(nèi)部復(fù)雜度比“先split再排序統(tǒng)計”寫起來短而且邊界天然被“非單詞字符即分隔”這一判斷覆蓋了。最需要注意的是循環(huán)結(jié)束后那一次計數(shù)少了它文本最后一個單詞就會從統(tǒng)計里消失。這種問題如果不二刷根本不會意識到一刷時為什么AC了——因為一刷的樣例恰好沒有“文本末尾直接結(jié)束”的情況。2.2 鏈表類虛擬頭節(jié)點救了我大半條命二刷時我做了一道“合并兩個有序鏈表”的題要求不能額外申請節(jié)點。一刷我記得自己用的是遞歸這次想練非遞歸結(jié)果一上來就出問題不用虛擬頭節(jié)點就得先判斷兩個鏈表的頭誰小誰當(dāng)“結(jié)果鏈的頭”然后還要維護(hù)一個尾指針。代碼寫出來不僅長而且“當(dāng)前鏈沒走完另一條鏈還有剩余”這個收尾邏輯我連續(xù)寫錯兩次。虛擬頭節(jié)點的核心價值是讓“第一個節(jié)點”和“后續(xù)節(jié)點”的插入邏輯完全統(tǒng)一。你不需要單獨討論結(jié)果鏈?zhǔn)遣皇菫榭辗凑齞ummy永遠(yuǎn)在場。寫起來也清爽很多struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail dummy; while (l1 l2) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next l1 ? l1 : l2; return dummy.next; }寫完復(fù)盤時我總結(jié)了一條凡是涉及“結(jié)果鏈的第一節(jié)點需要單獨處理”的鏈表題無腦加一個虛擬頭是性價比最高的做法。還有一個隱形好處是之后寫刪除節(jié)點、反轉(zhuǎn)區(qū)間這類題dummy節(jié)點能一并避免很多空指針夢魘。鏈表題在OJ上出錯很多時候不是思路不對而是空指針訪問直接RE虛擬頭能擋掉一大半。2.3 樹的層序遍歷變體隊列里既要節(jié)點也要知道在哪一層有一道常見的“之字形層序遍歷”題第一層從左到右第二層從右到左交替輸出。我二刷時的第一個版本是用兩個棧來回倒思路是“當(dāng)前層從左到右入棧下一層從右到左入?！苯Y(jié)果順序理了半天發(fā)現(xiàn)自己把左右孩子入棧的順序是否反過來、以及要不要按層輸出徹底搞混了。后來我給隊列里每一層做了計數(shù)一次彈完一整層遇到需要反向的層就臨時用索引倒著填vector代碼簡單多了vectorvectorint zigzag(TreeNode* root) { vectorvectorint ans; if (!root) return ans; queueTreeNode* q; q.push(root); bool leftToRight true; while (!q.empty()) { int sz q.size(); vectorint level(sz); for (int i 0; i sz; i) { TreeNode* cur q.front(); q.pop(); int idx leftToRight ? i : sz - 1 - i; level[idx] cur-val; if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } ans.push_back(level); leftToRight !leftToRight; } return ans; }這種“按層計數(shù)”的隊列寫法比用兩個棧的思路好理解多了。它告訴我一個道理樹這種結(jié)構(gòu)里光知道節(jié)點還不夠?qū)犹柾攀穷}目的隱藏要求。與其費勁在數(shù)據(jù)結(jié)構(gòu)上變換不如在“每層大小”上做文章。這些坑不是第一次寫就發(fā)現(xiàn)的都是二刷時用“不信一刷思路”的顯微鏡照出來的。3. OJ評測的紅綠燈復(fù)雜度和邊界二刷必須開始用眼睛判斷3.1 復(fù)雜度為什么本地秒過評測機卻超時復(fù)試OJ的題目后面通常會寫數(shù)據(jù)范圍比如n≤10^5但一刷的我根本不看這個數(shù)字。二刷時我專門開始練“一看數(shù)據(jù)范圍就能說出目標(biāo)復(fù)雜度”的能力。經(jīng)驗公式大概是n≤10^3時O(n^2)基本可以隨便寫n≤10^5到10^6時O(n log n)安全O(n^2)大概率超時n≤10^8時基本只有O(n)甚至O(log n)能活。為什么一般評測機限時1到2秒可以粗略認(rèn)為每秒處理10^8左右次基礎(chǔ)運算。1e5的平方是1e10次操作也就是一百億次遠(yuǎn)超一秒能承受的量。所以當(dāng)你寫下一個雙重循環(huán)掃一眼n的范圍就該知道結(jié)果。二刷時我遇到一道n2e5的數(shù)組題第一版用雙重循環(huán)求某個子區(qū)間和本地造了個小樣例秒出一提交TLE。改成前綴和后一次掃完AC。這個對比比一百句“要注意復(fù)雜度”都更有說服力。3.2 邊界0、1、最大這三個數(shù)字是評測機的三大最愛一刷最容易丟分的地方不是算法難而是邊界。二刷我有意識地把每個題的邊界條件列成清單當(dāng)n0或輸入為空時你的循環(huán)會不會跑空能不能直接返回預(yù)設(shè)值當(dāng)鏈表只有一個節(jié)點時你的前驅(qū)、后繼指針是否安全當(dāng)所有數(shù)字都相等、所有字符都一樣時你的“嚴(yán)格大于”“非嚴(yán)格大于”用對了嗎當(dāng)答案超過int范圍時你有沒有用long long當(dāng)取模時出現(xiàn)了負(fù)數(shù)你有沒有在最后補上mod我還做了一張“邊界對照小表”貼在筆記里每次提交前都掃一眼輸入場景最容易翻車的點二刷時的自查動作空輸入、空串、n0循環(huán)體內(nèi)訪問首元素前先判空每次循環(huán)前確認(rèn)下標(biāo)可訪問單節(jié)點、單字符對next和prev的引用先畫鏈再寫指針最大數(shù)據(jù)、最壞情況復(fù)雜度或溢出預(yù)估計算量并用long long重復(fù)值、逆序輸入排序與“穩(wěn)定”要求確定用什么比較符這張表看起來簡單但二刷的每一道題我都會在提交前花兩分鐘過一遍。結(jié)果錯題率直接降了一個檔次。OJ不是“過了人類肉眼看到的樣例”就算贏那些隱藏用例真正檢查的往往就是你自己最不想測的那幾個數(shù)值。3.3 不要怕被隱藏用例卡要把AC當(dāng)成一種最低標(biāo)準(zhǔn)這里說點可能不太合群的話如果一個題你AC了但根本不知道數(shù)據(jù)范圍是什么、也沒想過極端輸入那這個AC其實含水量很高。二刷時我不再把“AC了”當(dāng)成“我會了”而是當(dāng)成“至少樣例沒問題”。我會給自己加一分鐘測試時間故意構(gòu)造幾組邊界數(shù)據(jù)跑一下。比如字符串題我輸入空串、純標(biāo)點串、超長單詞鏈表題我輸入空鏈表、單節(jié)點鏈表樹題我輸入空樹、單邊樹。這些事情在正式復(fù)試的時候不是錦上添花而是必須的工序。因為機試的環(huán)境里你不會有太多機會去猜隱藏用例唯一能依賴的就是你在平時把這些用例“預(yù)演”過百遍之后形成的條件反射。4. 這輪刷題里最折磨我的細(xì)節(jié)全和編譯器與輸入輸出有關(guān)4.1 輸入函數(shù)混用是我翻車頻率最高的一類錯誤復(fù)試OJ大多是標(biāo)準(zhǔn)輸入輸出。二刷前我一直覺得“輸入輸出不就是這樣嘛”直到連續(xù)三題栽在“先讀整數(shù)再讀帶空格的字符串”這個場景。問題出在scanf(%d, n)之后輸入流里還停著一個換行符接下來如果直接gets()或getline(cin, s)它讀到的就是一個空行而不是你真正想讀的那行字符串。解決辦法有兩種int n; string line; cin n; getline(cin, line); // 吃掉換行通常是一個空行 getline(cin, line); // 真正讀入目標(biāo)行或者更穩(wěn)的寫法int n; scanf(%d, n); getchar(); // 吞掉換行 char buf[1000]; fgets(buf, sizeof(buf), stdin); // 讀含空格整行這兩種都行但關(guān)鍵在于每次混用不同讀取方式之前心里要清楚輸入流里此刻正在等待、正在殘留的是什么。一刷時我不理解為什么代碼在本地跑得好好的交上去WA得莫名其妙二刷才知道根本不是邏輯錯了是回車鍵被我當(dāng)成普通字符處理了。4.2 多組數(shù)據(jù)的讀入從“不知道”到“條件反射”復(fù)試OJ不少題目會寫“輸入包含多組測試數(shù)據(jù)每組數(shù)據(jù)格式如下”。很多第一次接觸OJ的人包括我一開始會傻傻地只處理一組輸入或者無限循環(huán)讀爆?，F(xiàn)在的標(biāo)準(zhǔn)動作基本是int n; while (cin n) { // 等價于 while (scanf(%d, n) ! EOF) // 處理每一組 n }注意這種寫法本身就是在“檢測是否還有數(shù)據(jù)”讀到文件結(jié)尾就自然結(jié)束。但有個細(xì)節(jié)很容易忽略如果每組數(shù)據(jù)包含字符串而且你用了cin s它按空白字符切分如果題目說“每組一行字符串”你要么用getline要么記得在讀整數(shù)后手動先吞掉換行。除此之外多組數(shù)據(jù)之間可能有空行要不要跳過空行也要看著題目描述來。二刷階段我給自己總結(jié)的口訣是先分清題目是“單組直接算”還是“多組讀到結(jié)束”再決定循環(huán)的寫法。這一步看錯答得再對也是白搭。4.3 大數(shù)與取模別在int上翻車復(fù)試OJ里“結(jié)果對1000000007取?！睅缀跏菢?biāo)配。一刷時我直接int ans 1; 然后for循環(huán)里ans * x; 結(jié)果一旦x或ans稍大中間過程立刻溢出最后模出來的答案跟真實結(jié)果對不上。二刷后我的習(xí)慣是只要題面出現(xiàn)“取?！毕劝阉袇⑴c乘法、累加的變量定為long long并且每次更新后都取模比如const long long MOD 1000000007LL; long long res 1; for (int i 0; i n; i) { res res * a[i] % MOD; }另外做減法取模時比如(a - b) % MODC里結(jié)果可能是負(fù)數(shù)正確寫法是(a - b MOD) % MOD。這個小細(xì)節(jié)我親眼見過很多人在正式機試時丟分不是不懂取模是忘了負(fù)數(shù)的坑。4.4 編譯警告不只是噪音本地編譯器有時候會忽略一些警告直接跑出結(jié)果比如變量未初始化、隱式類型轉(zhuǎn)換、數(shù)組越界前的可疑判斷等。OJ評測用的環(huán)境更嚴(yán)格同一個代碼本地能跑提交后可能變RE或WA。二刷時我把本地的編譯參數(shù)加上了-Wall -Wextra每當(dāng)警告里出現(xiàn)“可能未初始化”“比較有符號與無符號”這類提示我都會隨手修掉而不是關(guān)掉警告繼續(xù)提交。這個習(xí)慣救過我一次有一道題的二維數(shù)組我申請成了“int ma[1000][1000]”但內(nèi)部循環(huán)誤用了“ma[i][1000]”本地小數(shù)據(jù)完全沒事-Wall明確報了越界索引提示才讓我在提交前堵住這個坑。很多人覺得警告只是提示不報錯就不用管但在OJ場景下警告往往是隱藏RE的前兆。5. 二刷復(fù)盤我用一題一表逼自己直面錯誤5.1 我的“一題三列”筆記格式二刷時我發(fā)現(xiàn)如果只記錄“這題我過了”復(fù)盤毫無意義。真正有價值的是記錄“我錯在哪、為什么錯、下次怎么避免”。所以每題我會開一個小表格三列錯誤點寫清楚代碼里哪一行、哪個判斷、哪個循環(huán)出了問題越具體越好根因是沒讀懂題還是忘了復(fù)雜度還是邊界沒考慮還是某種語法細(xì)節(jié)二刷教訓(xùn)用一句能遷移到其他題的話寫下來。比如“字符串統(tǒng)計題最后一個單詞被漏掉”這一行我寫的教訓(xùn)是“凡是以分隔符切分的字符串處理循環(huán)結(jié)束后必須再補一次收尾判斷”。這類句子積累二三十條之后會發(fā)現(xiàn)自己對“輸入掃描類題目”的敏感度一下子提高了。復(fù)試前不需要再看一遍題解只需要翻一遍這些教訓(xùn)就能把自己常踩的坑全部喚醒。5.2 錯誤歸因別把所有錯都推給“粗心”很多人復(fù)盤時愛寫“下次細(xì)心點”這話等于沒說。二刷時我重新對所有錯題做了歸因發(fā)現(xiàn)錯誤大概能分成五類讀題理解錯、邊界條件漏、復(fù)雜度預(yù)估錯、代碼細(xì)節(jié)錯數(shù)組名打錯、變量覆蓋、括號漏掉、思路本身就沒有形成。歸因之后我才能針對性地練。比如連續(xù)幾個“邊界條件漏”那就逼自己在提交前把所有0/1/極端數(shù)據(jù)先跑一遍連續(xù)幾個“復(fù)雜度預(yù)估錯”就逼自己每次讀題后先把n的范圍圈出來。復(fù)盤不是寫日記是在做問題定位。只有把錯誤歸到具體的“行為”上下一步的練習(xí)才有靶子。5.3 給題分檔控制二刷節(jié)奏復(fù)試準(zhǔn)備的時間很緊二刷不能每個題都無限磨。我給自己定的時間預(yù)算是簡單題一看就有思路10分鐘內(nèi)寫完并提交中等題需要想一下數(shù)據(jù)結(jié)構(gòu)20分鐘內(nèi)能寫出可運行版本難題看了題解也不一定馬上懂30分鐘內(nèi)必須決定是繼續(xù)死磕還是標(biāo)記后繞過。實際執(zhí)行中我很少真的卡到30分鐘因為二刷的坑位是固定的一刷已經(jīng)篩過一遍了。如果二刷仍有一道題卡住超過25分鐘我會在表格里記錄“卡在哪個點”先做后面的題第二天再回來重寫一遍。這種“一題一表時間分檔”的方法讓我把二刷從“被動刷題”變成了“主動篩選薄弱點”。6. 復(fù)盤到第3篇我才想明白的三件小事6.1 題量是個數(shù)字掌握量才是底氣二刷這段時間我最大的感受是一刷時我動不動“今天過了十題”二刷之后發(fā)現(xiàn)哪些題是“真掌握”哪些只是“見過”心里有了一桿秤。真正值得秒殺的是那種你能在十分鐘內(nèi)不假思索寫出完整代碼、還能說出每一步為什么這么寫的題。如果你的目標(biāo)是“復(fù)試OJ通過”那么一刷重廣度二刷重精度。寧可二刷只精做三十道把套路理順也不要再盲目追新題數(shù)量。把一個類型的題真正吃透比用五十個半生不熟的方法堆在心里要可靠得多。6.2 筆記是寫給考前幾天翻的不是寫給現(xiàn)在的自己我之前記的筆記有一個通病當(dāng)時看覺得很詳細(xì)過兩周再看發(fā)現(xiàn)“這寫的是什么鬼”。二刷之后我把筆記改成了“面向未來的速查卡”模式一題兩三行突出本次錯誤點和可復(fù)用的結(jié)論而不粘貼大段代碼。這樣考前只需要花一個晚上就能把幾十個坑位過一遍。另外我還會給同類型的題打一個標(biāo)簽比如“字符串分割”“鏈表啞節(jié)點”“層序遍歷按層計數(shù)”等到考前把它們集中在一起快刷比翻幾十個分散頁面高效得多。復(fù)試OJ的題目類型其實就那么幾大類把標(biāo)簽歸好等于給自己做了一張“考前地圖”。6.3 二刷后期要主動模擬考場手感復(fù)試OJ通常有整體時間限制比如一小時內(nèi)做三道題或者兩小時做四道題。二刷如果只是單題練習(xí)很容易忽略“切換題目”帶來的思維負(fù)擔(dān)。我會在狀態(tài)比較好的下午挑三個簡單或中等的舊題設(shè)定好時間一口氣寫完再統(tǒng)一交。哪怕分?jǐn)?shù)不理想這種訓(xùn)練的收益也很大它逼你練習(xí)“先挑軟柿子捏”“該放棄就放棄”“不要在一道題上較勁到最后一秒”。這些考場策略單靠一道一道刷題是練不出來的。二刷到后期技術(shù)上的差距會越來越小真正的勝負(fù)手往往是時間分配和心理穩(wěn)定。最后再說點實在的。二刷到第3篇我不再追求“AC率”這個虛榮指標(biāo)了。每一道被我重寫、被我標(biāo)記、甚至被我放棄的題都像一面鏡子把一刷的僥幸照得清清楚楚。如果你也在準(zhǔn)備一場以機試為核心的復(fù)試建議你從今天開始停掉“打開題解—復(fù)制—提交”的循環(huán)老老實實地做一次二刷。別看舊代碼別跳過邊界用例別放過任何一次WA帶來的反思。復(fù)試那天真正拼的不是誰見過更多題而是誰能在看穿題目之后安靜地把代碼寫對。