1. 這份筆記從哪來(lái)適合誰(shuí)看把標(biāo)題拆開(kāi)看就一句話(huà)這是一個(gè)C入門(mén)選手寫(xiě)給自己的算法刷題筆記。不是什么系統(tǒng)教材也不是什么大神心得就是我自己邊學(xué)邊記錄、邊踩坑邊修正的東西順手整理出來(lái)分享給同樣在摸索的人。先說(shuō)說(shuō)我自己的情況方便你判斷內(nèi)容適不適合你。我寫(xiě)C寫(xiě)過(guò)一陣子業(yè)務(wù)代碼但算法這塊一直是短板做題基本靠直覺(jué)碰上稍復(fù)雜的就抓瞎。今年決定系統(tǒng)地補(bǔ)一補(bǔ)把力扣、洛谷、?？蜕系念}按專(zhuān)題刷邊刷邊把套路記下來(lái)。這份筆記就是那時(shí)候開(kāi)始攢的到現(xiàn)在已經(jīng)積累了小兩百條還在持續(xù)更新。筆記主要解決三個(gè)問(wèn)題。第一是知識(shí)碎片化——今天學(xué)個(gè)鏈表、明天碰個(gè)DP過(guò)兩周全忘了必須有個(gè)地方把套路固定下來(lái)。第二是代碼模板化——很多算法本質(zhì)上就是幾套固定寫(xiě)法的變種把模板記熟能省掉大量重復(fù)推導(dǎo)時(shí)間。第三是排錯(cuò)經(jīng)驗(yàn)化——算法題里最耗時(shí)間的其實(shí)是各種隱蔽錯(cuò)誤比如數(shù)組越界、死循環(huán)、邊界條件這些坑光靠看書(shū)學(xué)不到必須自己踩一遍才能記住。所以這份筆記的核心價(jià)值不在于系統(tǒng)全面而在于**實(shí)戰(zhàn)可復(fù)現(xiàn)**——每條筆記都對(duì)應(yīng)一個(gè)真實(shí)題目或真實(shí)場(chǎng)景寫(xiě)的時(shí)候就能直接用。筆記默認(rèn)你有基本語(yǔ)法功底知道指針、引用、STL容器是什么但不需要你有算法競(jìng)賽背景零基礎(chǔ)刷題的人跟著這個(gè)框架走完全沒(méi)問(wèn)題。我用的編譯器是GCC 9.4配合VS Code環(huán)境刷題平臺(tái)是力扣和洛谷。后面所有代碼都基于C11標(biāo)準(zhǔn)個(gè)別地方用了C17的特性我會(huì)單獨(dú)標(biāo)注。2. 整體設(shè)計(jì)思路為什么我選擇專(zhuān)題刷題模板沉淀的方式2.1 入門(mén)算法的核心矛盾知識(shí)量大與時(shí)間精力有限的沖突算法題涉及的知識(shí)點(diǎn)非常多數(shù)組、鏈表、棧、隊(duì)列、樹(shù)、圖、排序、搜索、動(dòng)態(tài)規(guī)劃、貪心、回溯、字符串匹配……如果按教材一章一章啃啃到樹(shù)就已經(jīng)想放棄了。但反過(guò)來(lái)看真正筆試面試?？嫉牟](méi)那么玄乎核心其實(shí)就是那幾個(gè)固定專(zhuān)題的排列組合。我統(tǒng)計(jì)過(guò)自己刷的一百多道題出題頻率最高的就這幾類(lèi)雙指針和滑動(dòng)窗口大概占20%二分查找和二分答案差不多15%數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)題15%DFS和BFS搜索15%動(dòng)態(tài)規(guī)劃15%剩下是貪心、回溯和雜題。這個(gè)比例說(shuō)明一件事你把六七個(gè)專(zhuān)題的套路吃透就能覆蓋八成以上的題目。這就是我選擇專(zhuān)題刷題而不是按頁(yè)翻書(shū)的原因。2.2 模板沉淀一篇筆記解決一類(lèi)題一個(gè)很深的體會(huì)是一道題你會(huì)做不代表你掌握了這一類(lèi)題。很多題看起來(lái)不一樣底層解法是同一套東西。比如最長(zhǎng)無(wú)重復(fù)子串、最小覆蓋子串、長(zhǎng)度最小的子數(shù)組表面上三題完全無(wú)關(guān)但全部可以用滑動(dòng)窗口模板解決。我筆記里的做法就是刷完一類(lèi)題之后立刻總結(jié)一版通用解法模板配合兩三道典型例題之后遇到同類(lèi)型的題目直接套模板改參數(shù)效率比每次從頭推導(dǎo)高太多。2.3 筆記結(jié)構(gòu)的演進(jìn)從流水賬到反查手冊(cè)最早我的筆記就是流水賬——今天刷了什么題、AC還是WA、用了什么方法寫(xiě)到后面發(fā)現(xiàn)根本沒(méi)法查。后來(lái)我重構(gòu)了一次按專(zhuān)題分類(lèi)組織每條筆記包含五個(gè)要素問(wèn)題模型、核心思路、代碼模板、復(fù)雜度分析、易錯(cuò)點(diǎn)?，F(xiàn)在做題遇到卡殼我能快速定位到相關(guān)筆記比搜索引擎還好用。這個(gè)結(jié)構(gòu)這里也分享給你后面每個(gè)專(zhuān)題我都是按這五個(gè)要素來(lái)寫(xiě)的。3. 核心知識(shí)點(diǎn)拆解STL容器到底該怎么用3.1 vector的底層機(jī)制與性能取舍vector是C里用得最多的容器但很多人只是當(dāng)可變長(zhǎng)數(shù)組用對(duì)它的底層機(jī)制和性能特性了解不夠。vector的本質(zhì)是動(dòng)態(tài)數(shù)組底層維護(hù)三個(gè)指針起始位置、當(dāng)前使用末尾、容量末尾。當(dāng)元素?cái)?shù)量超過(guò)當(dāng)前容量時(shí)vector會(huì)重新分配一塊更大的內(nèi)存通常翻倍把舊元素逐個(gè)拷貝過(guò)去然后釋放舊內(nèi)存。這一步非常貴——如果你在循環(huán)里不斷push_back觸發(fā)了擴(kuò)容時(shí)間復(fù)雜度就是O(n)的拷貝開(kāi)銷(xiāo)。實(shí)操中我的建議如果能預(yù)估元素?cái)?shù)量上限直接調(diào)用reserve預(yù)留空間。舉個(gè)例子你要讀取一個(gè)有N個(gè)整數(shù)的數(shù)組int n; cin n; vectorint nums; nums.reserve(n); // 推薦避免多次擴(kuò)容拷貝 for (int i 0; i n; i) { int x; cin x; nums.push_back(x); }順便說(shuō)一個(gè)刷題時(shí)經(jīng)常踩的坑vector的size()返回的是size_t類(lèi)型無(wú)符號(hào)整數(shù)如果直接拿0去減它得到的是一個(gè)巨大的正數(shù)導(dǎo)致循環(huán)永遠(yuǎn)不結(jié)束或者越界。正確寫(xiě)法是先轉(zhuǎn)成int再減或者用nums.size()參與比較時(shí)保持兩邊同為無(wú)符號(hào)類(lèi)型。3.2 map、set與unordered系列的選擇邏輯很多新手糾結(jié)什么時(shí)候用map、什么時(shí)候用unordered_map這里有個(gè)簡(jiǎn)單的判斷標(biāo)準(zhǔn)需要有序遍歷鍵值對(duì)用map底層紅黑樹(shù)O(log n)操作只需要快速查找不需要順序用unordered_map底層哈希表平均O(1)操作需要判斷元素是否存在且不關(guān)心順序用unordered_set需要去重且保持順序用set實(shí)際刷題時(shí)九成以上的題目用unordered_map就夠了因?yàn)楣２檎业某?shù)極小性能遠(yuǎn)好于紅黑樹(shù)的log n。只有在考到按順序輸出或者找第k小元素這類(lèi)需要區(qū)間操作時(shí)才輪到map和set出場(chǎng)。有個(gè)細(xì)節(jié)要注意unordered_map的遍歷順序是不確定的如果你的結(jié)果對(duì)順序有要求必須先排序再處理。3.3 priority_queue與自定義比較器優(yōu)先隊(duì)列堆是很多算法題的利器特別是涉及每次取最大/最小的場(chǎng)景。默認(rèn)的priority_queue是大頂堆取的是最大元素。如果要取最小元素一般兩種寫(xiě)法// 寫(xiě)法一用 greater 指定小頂堆 priority_queueint, vectorint, greaterint minHeap; // 寫(xiě)法二存入負(fù)值 priority_queueint maxHeap; maxHeap.push(-x); // 取出來(lái)的時(shí)候記得取負(fù)對(duì)于自定義結(jié)構(gòu)體需要重載比較運(yùn)算符。這里是重災(zāi)區(qū)很多人搞不清比較方向和堆的大小的關(guān)系。我的記憶技巧是返回true表示第一個(gè)參數(shù)排在第二個(gè)參數(shù)后面也就是優(yōu)先級(jí)更低。struct Node { int dist; int id; }; // 自定義小頂堆dist小的優(yōu)先 struct Cmp { bool operator()(const Node a, const Node b) { return a.dist b.dist; // 注意小頂堆用的是大于號(hào) } }; priority_queueNode, vectorNode, Cmp pq;提示Dijkstra算法、合并K個(gè)有序鏈表、滑動(dòng)窗口最大值這些經(jīng)典問(wèn)題底層全依賴(lài)優(yōu)先隊(duì)列這個(gè)容器值得花一小時(shí)專(zhuān)門(mén)練透。3.4 string的常用操作與坑字符串在算法題里繞不開(kāi)尤其是處理子串、回文串、字符統(tǒng)計(jì)。C的string有不少方便的函數(shù)但有幾個(gè)坑值得注意substr的參數(shù)是起始位置長(zhǎng)度不是起始位置結(jié)束位置。很多從Python轉(zhuǎn)過(guò)來(lái)的人容易在這上面翻車(chē)。getline配合cin處理含空格的整行輸入如果你前面用過(guò)cin 緩沖區(qū)會(huì)留下?lián)Q行符直接用getline會(huì)讀到空行。解決辦法是先cin.ignore()。字符統(tǒng)計(jì)用數(shù)組代替map如果范圍是26個(gè)小寫(xiě)字母直接用vectorint cnt(26, 0)性能遠(yuǎn)好于unordered_map。這是一個(gè)經(jīng)常被忽視的優(yōu)化點(diǎn)。對(duì)string做大量拼接操作時(shí)注意比str str ch高效得多前者是原地操作后者會(huì)創(chuàng)建新對(duì)象。4. 經(jīng)典算法模板與場(chǎng)景拆解4.1 二分查找不是找到就完了而是邊界二分查找算得上最簡(jiǎn)單也最容易寫(xiě)錯(cuò)的算法。說(shuō)它簡(jiǎn)單是因?yàn)樗悸肪鸵痪湓?huà)——每次砍掉一半說(shuō)它容易寫(xiě)錯(cuò)是因?yàn)檫吔鐥l件稍微調(diào)錯(cuò)就是死循環(huán)或者漏解。我推薦的寫(xiě)法是左閉右開(kāi)區(qū)間配合searchFirst等價(jià)變體統(tǒng)一處理這樣記起來(lái)只有一個(gè)模板// 在有序數(shù)組中查找第一個(gè) target 的元素位置不存在返回 nums.size() int lower_bound(vectorint nums, int target) { int left 0, right nums.size(); // 左閉右開(kāi) while (left right) { int mid left (right - left) / 2; // 防溢出寫(xiě)法 if (nums[mid] target) { left mid 1; } else { right mid; } } return left; }注意我用了left (right - left) / 2而不是(left right) / 2。當(dāng)left和right都接近2^31時(shí)直接相加可能溢出。雖然在普通題目里不容易觸發(fā)但這是個(gè)好習(xí)慣競(jìng)賽時(shí)能救你一命。這套模板的核心思想始終保持答案可能在[left, right)區(qū)間內(nèi)最終left和right會(huì)收斂到同一個(gè)位置這個(gè)位置就是答案。想找最后一個(gè)小于target的元素就得在判斷條件上做文章但區(qū)間框架不變。4.2 滑動(dòng)窗口最長(zhǎng)與最短的套路差異滑動(dòng)窗口是雙指針?biāo)枷氲倪M(jìn)階版專(zhuān)門(mén)用于處理子數(shù)組/子串問(wèn)題。核心維護(hù)一個(gè)窗口[left, right]通過(guò)擴(kuò)展和收縮遍歷所有可能的狀態(tài)。最長(zhǎng)類(lèi)問(wèn)題如無(wú)重復(fù)最長(zhǎng)子串的模板int maxWindow(vectorint nums) { int left 0, ans 0; unordered_mapint, int window; // 記錄窗口內(nèi)元素狀態(tài) for (int right 0; right nums.size(); right) { window[nums[right]]; while (窗口條件不滿(mǎn)足) { // 收縮左邊界 window[nums[left]]--; if (window[nums[left]] 0) window.erase(nums[left]); left; } ans max(ans, right - left 1); } return ans; }最短類(lèi)問(wèn)題如最短覆蓋子串則是完全相反的形態(tài)——先不斷擴(kuò)展直到滿(mǎn)足條件再?lài)L試收縮找最短。這兩者的核心區(qū)別在于最長(zhǎng)類(lèi)窗口是不滿(mǎn)足才收縮最短類(lèi)窗口是滿(mǎn)足就收縮。我一開(kāi)始把這兩套邏輯混在一起每次寫(xiě)都要推半天后來(lái)把模板分開(kāi)記錄之后基本秒套。有一個(gè)高頻考點(diǎn)是窗口內(nèi)的統(tǒng)計(jì)方式。如果只涉及字符且字符范圍有限比如只有字母建議用數(shù)組計(jì)數(shù)而不是map代碼如下vectorint cnt(128, 0); // ASCII碼范圍 int needCnt 0; // 記錄滿(mǎn)足條件的字符種類(lèi)數(shù)4.3 DFS與BFS搜迷宮和求最短路的兩種武器搜索是算法題的分水嶺。DFS深度優(yōu)先搜索適合求所有解的場(chǎng)景全排列、組合、島嶼數(shù)量、回溯剪枝BFS廣度優(yōu)先搜索適合求最短路徑的場(chǎng)景走迷宮、最小步數(shù)、單詞接龍。DFS的經(jīng)典框架以島嶼數(shù)量為例void dfs(vectorvectorchar grid, int i, int j) { if (i 0 || i grid.size() || j 0 || j grid[0].size()) return; if (grid[i][j] 0) return; // 已訪(fǎng)問(wèn)或非陸地 grid[i][j] 0; // 標(biāo)記已訪(fǎng)問(wèn)原地修改 dfs(grid, i 1, j); dfs(grid, i - 1, j); dfs(grid, i, j 1); dfs(grid, i, j - 1); }這里有個(gè)非常關(guān)鍵的點(diǎn)visited標(biāo)記一定要在遞歸進(jìn)入之前完成。如果放在遞歸開(kāi)始之后可能會(huì)造成重復(fù)訪(fǎng)問(wèn)和死循環(huán)。我一開(kāi)始習(xí)慣性在進(jìn)入下一層之前不加標(biāo)記超時(shí)之后排查半天才發(fā)現(xiàn)問(wèn)題。BFS框架則依賴(lài)隊(duì)列int bfs(vectorvectorint grid, int startX, int startY) { int n grid.size(), m grid[0].size(); vectorvectorint dist(n, vectorint(m, -1)); queuepairint, int q; q.push({startX, startY}); dist[startX][startY] 0; int dirs[4][2] {{1,0},{-1,0},{0,1},{0,-1}}; while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (auto d : dirs) { int nx x d[0], ny y d[1]; if (nx 0 || nx n || ny 0 || ny m) continue; if (dist[nx][ny] ! -1) continue; dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } return dist[目標(biāo)x][目標(biāo)y]; }用dist數(shù)組同時(shí)承擔(dān)是否訪(fǎng)問(wèn)過(guò)和距離為多少兩個(gè)職責(zé)這是BFS中最常用的優(yōu)化寫(xiě)法能省一個(gè)額外的visited數(shù)組。4.4 動(dòng)態(tài)規(guī)劃入門(mén)最難啃但回報(bào)最大的一章動(dòng)態(tài)規(guī)劃是很多人的噩夢(mèng)我一開(kāi)始也被嚇到后來(lái)發(fā)現(xiàn)其實(shí)是方法論問(wèn)題。比起背狀態(tài)轉(zhuǎn)移方程更重要的是按固定步驟思考定義狀態(tài)dp[i]表示什么大多數(shù)題目里dp[i]代表以第i個(gè)元素結(jié)尾的最優(yōu)解或者前i個(gè)元素的最優(yōu)解。寫(xiě)出轉(zhuǎn)移方程dp[i]怎么由更小的狀態(tài)推出來(lái)確定初始條件dp[0]或dp[1]等于什么確認(rèn)遍歷順序從前往后還是從后往前一維還是二維以最經(jīng)典的最長(zhǎng)遞增子序列LIS為例int lengthOfLIS(vectorint nums) { int n nums.size(); if (n 0) return 0; vectorint dp(n, 1); // 初始值每個(gè)元素自身構(gòu)成長(zhǎng)度為1的序列 int ans 1; for (int i 1; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } return ans; }這個(gè)O(n2)的寫(xiě)法是最容易理解的版本。如果想優(yōu)化到O(n log n)需要用貪心二分維護(hù)一個(gè)遞增序列的尾部最小值數(shù)組這個(gè)進(jìn)階版本我放在筆記后面作為拓展題不建議新手一上來(lái)就啃。DP的題感培養(yǎng)需要大量題量支撐。我個(gè)人經(jīng)驗(yàn)是先保證能把背包問(wèn)題、最長(zhǎng)公共子序列、最長(zhǎng)遞增子序列、編輯距離這四個(gè)最經(jīng)典模型吃透之后再看其他DP題就不會(huì)覺(jué)得是完全陌生的了。5. 精度、溢出與性能調(diào)優(yōu)算法題里最隱蔽的坑5.1 整數(shù)溢出的常見(jiàn)場(chǎng)景C刷題最常見(jiàn)的問(wèn)題之一就是溢出。比如計(jì)算中間值時(shí)兩個(gè)10^9的數(shù)相乘直接得到10^18已經(jīng)超過(guò)int上限約2.1×10^9。很多人題目思路全對(duì)提交卻WA一查才發(fā)現(xiàn)是溢出。我的檢查清單運(yùn)算過(guò)程中涉及乘法且數(shù)值可能超過(guò)10^4先把變量類(lèi)型設(shè)成long long求平均值取(left right) / 2時(shí)用left (right - left) / 2防溢出狀態(tài)轉(zhuǎn)移方程里出現(xiàn)加法比如二維DP中dp[i][j] dp[i][j-1]如果答案可能超過(guò)int上限dp數(shù)組直接定義成vectorvectorlong long5.2 浮點(diǎn)數(shù)比較永遠(yuǎn)不要用如果你做過(guò)涉及浮點(diǎn)數(shù)的題比如二分答案求平方根一定會(huì)遇到精度問(wèn)題。浮點(diǎn)數(shù)在內(nèi)存中是近似表示的所以sqrt(2) * sqrt(2) 2在C里很可能得到false。正確的做法是定義一個(gè)極小值epsilon用絕對(duì)值差是否小于epsilon來(lái)判斷。const double EPS 1e-8; if (fabs(a - b) EPS) { // 視為相等 }5.3 時(shí)間復(fù)雜度的估算方法很多新手問(wèn)我題目提交超時(shí)是不是算法不夠好。實(shí)際上超時(shí)有兩個(gè)原因要么復(fù)雜度太高要么常數(shù)太大。前者靠換算法后者靠?jī)?yōu)化編碼細(xì)節(jié)。估算方法很簡(jiǎn)單假設(shè)你的程序每秒能執(zhí)行大約10^8次基本運(yùn)算這個(gè)值對(duì)OJ環(huán)境大致適用。那么數(shù)據(jù)規(guī)模n 10^5O(n2)算法 10^10次必超時(shí)數(shù)據(jù)規(guī)模n 10^5O(n log n)算法 ≈ 1.7×10^6次很安全數(shù)據(jù)規(guī)模n 10^6O(n)算法 10^6次沒(méi)問(wèn)題拿到題目第一件事不是寫(xiě)代碼而是先看數(shù)據(jù)范圍確定允許的復(fù)雜度級(jí)別。這個(gè)習(xí)慣能幫你排除掉一半的錯(cuò)誤思路。比如看到n ≤ 10^5就應(yīng)該立刻排除需要兩層循環(huán)的O(n2)解法。5.4 輸入輸出優(yōu)化cin和cout沒(méi)你想的那么慢刷題時(shí)經(jīng)常聽(tīng)到用scanf別用cin的說(shuō)法。這個(gè)說(shuō)法有歷史背景早期C的cin為了兼容C的stdio默認(rèn)開(kāi)啟了同步導(dǎo)致性能偏低。但在現(xiàn)代OJ上你只要在main開(kāi)頭加上一行ios::sync_with_stdio(false); cin.tie(nullptr);cin和cout的速度就能逼近scanf/printf完全夠用。我個(gè)人是能用cin就用cin省去格式串的調(diào)試時(shí)間只有需要格式化輸出特定寬度時(shí)才用printf。這行的原理是關(guān)閉C和C兩套IO的同步緩沖區(qū)cin和cout不再等待stdio的刷新自然就快了。注意關(guān)閉同步后不要混用cin和scanf會(huì)亂序這點(diǎn)寫(xiě)在筆記的第一頁(yè)。6. 常見(jiàn)問(wèn)題與排查技巧實(shí)錄6.1 編譯錯(cuò)誤篇大多數(shù)人卡住的不是算法我能說(shuō)一半以上新手提交不通過(guò)卡在編譯錯(cuò)誤階段嗎常見(jiàn)的編譯錯(cuò)誤有這幾種忘了引入頭文件用vector不加vector用sqrt不加cmath。解決辦法是養(yǎng)成寫(xiě)完代碼先自查include的習(xí)慣。結(jié)構(gòu)體比較沒(méi)重載運(yùn)算符用了sort對(duì)自定義結(jié)構(gòu)體排序卻忘了定義比較函數(shù)編譯直接報(bào)錯(cuò)。函數(shù)聲明和定義不匹配特別是模板函數(shù)聲明時(shí)用了T定義時(shí)用了int類(lèi)型對(duì)不上。注意C11起的特性差異auto、unordered_map、make_pair這些都是C11的如果平臺(tái)用的是C98標(biāo)準(zhǔn)全部報(bào)錯(cuò)。刷題前先確認(rèn)標(biāo)準(zhǔn)版本。一個(gè)非常實(shí)用的排錯(cuò)技巧從報(bào)錯(cuò)信息的最后一行倒著看。編譯器的報(bào)錯(cuò)經(jīng)常是級(jí)聯(lián)的——第一個(gè)錯(cuò)誤引發(fā)后面幾十個(gè)錯(cuò)誤但真正的源頭往往在最后那一行。6.2 運(yùn)行時(shí)錯(cuò)誤段錯(cuò)誤和棧溢出的區(qū)別提交后報(bào)Runtime Error大多數(shù)情況是段錯(cuò)誤訪(fǎng)問(wèn)了非法內(nèi)存。常見(jiàn)的觸發(fā)點(diǎn)數(shù)組越界vectorint nums(10); nums[10] 1;下標(biāo)最大只能是9空指針/野指針用了一個(gè)未初始化的指針解引用end迭代器*nums.end()是未定義行為遞歸深度過(guò)大DFS遞歸穿過(guò)1萬(wàn)層以上可能爆棧如果是遞歸爆棧有兩個(gè)解決辦法一是把遞歸改成顯式的棧模擬比如用stack保存狀態(tài)二是把DFS改成BFS。設(shè)計(jì)算法時(shí)就考慮遞歸深度比出了問(wèn)題再改要省事得多。6.3 邏輯錯(cuò)誤AC代碼為什么總差一點(diǎn)點(diǎn)最氣人的是本地運(yùn)行沒(méi)問(wèn)題提交就WA。這類(lèi)問(wèn)題絕大多數(shù)是邊界條件沒(méi)處理好空數(shù)組、只含一個(gè)元素的數(shù)組已經(jīng)有序的數(shù)組全是相同元素的數(shù)組最大值的邊界情況比如k大于數(shù)組長(zhǎng)度我的建議是寫(xiě)完代碼后走一遍自己寫(xiě)的樣例還不夠要手動(dòng)構(gòu)造3-4個(gè)極端用例。比如排序算法測(cè)一下[]和[5]二分查找測(cè)一下target小于所有元素和target大于所有元素的情況。五毛錢(qián)的功夫能省去半天調(diào)試時(shí)間。6.4 死循環(huán)的排查套路如果你發(fā)現(xiàn)程序卡住不輸出多半是循環(huán)沒(méi)退出。排查順序二分查找的left和right更新是否正確left mid 1和right mid這是正確節(jié)奏如果把left mid就會(huì)陷入兩個(gè)相鄰位置的死循環(huán)滑動(dòng)窗口的left是否在某個(gè)條件下永不右移鏈表的快慢指針有沒(méi)有在同一節(jié)點(diǎn)打轉(zhuǎn)DFS/BFS的狀態(tài)標(biāo)記是否漏了某個(gè)分支有一個(gè)調(diào)試技巧很實(shí)用——在循環(huán)體的開(kāi)頭加一行cout debug: left right endl;觀察變量變化死循環(huán)的位置立刻暴露。用完記得刪掉。7. 環(huán)境配置與刷題工作流7.1 本地調(diào)試環(huán)境搭建要點(diǎn)雖然OJ上提交不看本地環(huán)境但本地調(diào)試能極大提升刷題效率。我的開(kāi)發(fā)環(huán)境是三件套VSCode GCC 一個(gè)簡(jiǎn)單的測(cè)試腳本。寫(xiě)算法題時(shí)我從來(lái)不在一個(gè)main函數(shù)里堆代碼——而是寫(xiě)一個(gè)包含全部測(cè)試用例的單文件測(cè)試用命令行編譯運(yùn)行g(shù) -stdc17 -Wall -Wextra -g -o main main.cpp-Wall -Wextra能提示絕大多數(shù)未定義行為和類(lèi)型轉(zhuǎn)換問(wèn)題-g生成調(diào)試信息配合gdb使用。這些編譯選項(xiàng)在OJ上是不會(huì)啟用的所以在本地編譯干凈通過(guò)能提前過(guò)濾掉一大半問(wèn)題。7.2 刷題前5分鐘的準(zhǔn)備動(dòng)作我每次開(kāi)始刷題前會(huì)先花五分鐘默一遍基礎(chǔ)模板快排的partition、二分查找的兩個(gè)變體、DFS和BFS的骨架、滑動(dòng)窗口的左右指針移動(dòng)邏輯。這就像熱身能讓手和大腦快速進(jìn)入狀態(tài)。如果你還沒(méi)有自己整理過(guò)模板我的建議是現(xiàn)在就打開(kāi)一個(gè)空白文檔手敲一遍上面列的核心模板。手敲和復(fù)制粘貼的差別很大——敲的過(guò)程中你才會(huì)注意到那些邊界條件的細(xì)節(jié)。7.3 筆記更新的迭代方式這份筆記寫(xiě)了小半年更新方式從一開(kāi)始的刷到哪記到哪變成了現(xiàn)在的版本管理方式每個(gè)專(zhuān)題單獨(dú)一個(gè)文件每次刷題后如果有新感悟或者新坑追加在對(duì)應(yīng)專(zhuān)題的補(bǔ)充記錄區(qū)域。我現(xiàn)在習(xí)慣在每道題提交通過(guò)之后順手更新筆記——哪怕只是加一條這題可以用上一題模板直接套。這樣積累足夠多之后筆記就是一本完全個(gè)人化的算法手冊(cè)。8. 最后的實(shí)操建議8.1 做題順序怎么定先廣度后深度如果你剛開(kāi)始刷題我強(qiáng)烈建議按這個(gè)順序掃一遍知識(shí)點(diǎn)線(xiàn)性表數(shù)組、鏈表、棧、隊(duì)列→ 哈希表 → 排序與自定義排序 → 二分查找 → 雙指針/滑動(dòng)窗口 → 樹(shù)的基礎(chǔ)遍歷 → DFS/BFS → 回溯 → 貪心 → 動(dòng)態(tài)規(guī)劃。前段是性?xún)r(jià)比最高的內(nèi)容投入三四周就能有明顯感覺(jué)。動(dòng)態(tài)規(guī)劃放到最后不是因?yàn)椴恢匾且驗(yàn)樗枰C合運(yùn)用前面的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)太早接觸容易打擊信心。8.2 一道題刷到什么程度算會(huì)了我自己的標(biāo)準(zhǔn)有三層能獨(dú)立AC、能講清楚思路和復(fù)雜度、能說(shuō)出這題的變種以及模板還有哪些其他用途。只滿(mǎn)足第一層算做過(guò)了三層都滿(mǎn)足才算掌握了。后者關(guān)系到你碰到新題時(shí)能不能快速聯(lián)想到舊套路。每道題AC之后建議順手做兩件事一是看一眼題解區(qū)是否有比你的方法更優(yōu)的解法記錄下來(lái)二是想一想如果題目稍微改一下條件比如數(shù)組變成無(wú)序、最大值改為最小值、m次改為k次你的解法還成立嗎。這兩個(gè)習(xí)慣對(duì)培養(yǎng)算法思維特別有效。8.3 分享我的一個(gè)習(xí)慣錯(cuò)題本比題單更值錢(qián)我做題最寶貴的資產(chǎn)不是AC過(guò)的題而是那些多次提交才過(guò)、或者看了題解才恍然大悟的題。遇到這種題我除了正常筆記外專(zhuān)門(mén)在文檔末尾加了一個(gè)弱題清單記錄當(dāng)時(shí)的卡殼點(diǎn)。每周回頭重做清單里的題直到一次AC再移出清單。這比每天刷新題有效得多——你真正需要訓(xùn)練的是你的薄弱點(diǎn)而不是你已經(jīng)會(huì)的東西。這份筆記還在持續(xù)更新接下來(lái)我會(huì)補(bǔ)充的內(nèi)容包括圖論進(jìn)階拓?fù)渑判颉⒉⒉榧?、最短路、字符串算法KMP、Trie樹(shù)、更多動(dòng)態(tài)規(guī)劃的經(jīng)典模型以及一些競(jìng)賽向的技巧。如果你是按這篇筆記的框架來(lái)學(xué)習(xí)的建議每學(xué)完一個(gè)專(zhuān)題寫(xiě)自己的三條總結(jié)把你遇到的坑和心得也記進(jìn)去——自己的筆記永遠(yuǎn)是最好用的筆記。