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