1. 这份笔记从哪来适合谁看把标题拆开看就一句话这是一个C入门选手写给自己的算法刷题笔记。不是什么系统教材也不是什么大神心得就是我自己边学边记录、边踩坑边修正的东西顺手整理出来分享给同样在摸索的人。先说说我自己的情况方便你判断内容适不适合你。我写C写过一阵子业务代码但算法这块一直是短板做题基本靠直觉碰上稍复杂的就抓瞎。今年决定系统地补一补把力扣、洛谷、牛客上的题按专题刷边刷边把套路记下来。这份笔记就是那时候开始攒的到现在已经积累了小两百条还在持续更新。笔记主要解决三个问题。第一是知识碎片化——今天学个链表、明天碰个DP过两周全忘了必须有个地方把套路固定下来。第二是代码模板化——很多算法本质上就是几套固定写法的变种把模板记熟能省掉大量重复推导时间。第三是排错经验化——算法题里最耗时间的其实是各种隐蔽错误比如数组越界、死循环、边界条件这些坑光靠看书学不到必须自己踩一遍才能记住。所以这份笔记的核心价值不在于系统全面而在于**实战可复现**——每条笔记都对应一个真实题目或真实场景写的时候就能直接用。笔记默认你有基本语法功底知道指针、引用、STL容器是什么但不需要你有算法竞赛背景零基础刷题的人跟着这个框架走完全没问题。我用的编译器是GCC 9.4配合VS Code环境刷题平台是力扣和洛谷。后面所有代码都基于C11标准个别地方用了C17的特性我会单独标注。2. 整体设计思路为什么我选择专题刷题模板沉淀的方式2.1 入门算法的核心矛盾知识量大与时间精力有限的冲突算法题涉及的知识点非常多数组、链表、栈、队列、树、图、排序、搜索、动态规划、贪心、回溯、字符串匹配……如果按教材一章一章啃啃到树就已经想放弃了。但反过来看真正笔试面试常考的并没那么玄乎核心其实就是那几个固定专题的排列组合。我统计过自己刷的一百多道题出题频率最高的就这几类双指针和滑动窗口大概占20%二分查找和二分答案差不多15%数据结构设计题15%DFS和BFS搜索15%动态规划15%剩下是贪心、回溯和杂题。这个比例说明一件事你把六七个专题的套路吃透就能覆盖八成以上的题目。这就是我选择专题刷题而不是按页翻书的原因。2.2 模板沉淀一篇笔记解决一类题一个很深的体会是一道题你会做不代表你掌握了这一类题。很多题看起来不一样底层解法是同一套东西。比如最长无重复子串、最小覆盖子串、长度最小的子数组表面上三题完全无关但全部可以用滑动窗口模板解决。我笔记里的做法就是刷完一类题之后立刻总结一版通用解法模板配合两三道典型例题之后遇到同类型的题目直接套模板改参数效率比每次从头推导高太多。2.3 笔记结构的演进从流水账到反查手册最早我的笔记就是流水账——今天刷了什么题、AC还是WA、用了什么方法写到后面发现根本没法查。后来我重构了一次按专题分类组织每条笔记包含五个要素问题模型、核心思路、代码模板、复杂度分析、易错点。现在做题遇到卡壳我能快速定位到相关笔记比搜索引擎还好用。这个结构这里也分享给你后面每个专题我都是按这五个要素来写的。3. 核心知识点拆解STL容器到底该怎么用3.1 vector的底层机制与性能取舍vector是C里用得最多的容器但很多人只是当可变长数组用对它的底层机制和性能特性了解不够。vector的本质是动态数组底层维护三个指针起始位置、当前使用末尾、容量末尾。当元素数量超过当前容量时vector会重新分配一块更大的内存通常翻倍把旧元素逐个拷贝过去然后释放旧内存。这一步非常贵——如果你在循环里不断push_back触发了扩容时间复杂度就是O(n)的拷贝开销。实操中我的建议如果能预估元素数量上限直接调用reserve预留空间。举个例子你要读取一个有N个整数的数组int n; cin n; vectorint nums; nums.reserve(n); // 推荐避免多次扩容拷贝 for (int i 0; i n; i) { int x; cin x; nums.push_back(x); }顺便说一个刷题时经常踩的坑vector的size()返回的是size_t类型无符号整数如果直接拿0去减它得到的是一个巨大的正数导致循环永远不结束或者越界。正确写法是先转成int再减或者用nums.size()参与比较时保持两边同为无符号类型。3.2 map、set与unordered系列的选择逻辑很多新手纠结什么时候用map、什么时候用unordered_map这里有个简单的判断标准需要有序遍历键值对用map底层红黑树O(log n)操作只需要快速查找不需要顺序用unordered_map底层哈希表平均O(1)操作需要判断元素是否存在且不关心顺序用unordered_set需要去重且保持顺序用set实际刷题时九成以上的题目用unordered_map就够了因为哈希查找的常数极小性能远好于红黑树的log n。只有在考到按顺序输出或者找第k小元素这类需要区间操作时才轮到map和set出场。有个细节要注意unordered_map的遍历顺序是不确定的如果你的结果对顺序有要求必须先排序再处理。3.3 priority_queue与自定义比较器优先队列堆是很多算法题的利器特别是涉及每次取最大/最小的场景。默认的priority_queue是大顶堆取的是最大元素。如果要取最小元素一般两种写法// 写法一用 greater 指定小顶堆 priority_queueint, vectorint, greaterint minHeap; // 写法二存入负值 priority_queueint maxHeap; maxHeap.push(-x); // 取出来的时候记得取负对于自定义结构体需要重载比较运算符。这里是重灾区很多人搞不清比较方向和堆的大小的关系。我的记忆技巧是返回true表示第一个参数排在第二个参数后面也就是优先级更低。struct Node { int dist; int id; }; // 自定义小顶堆dist小的优先 struct Cmp { bool operator()(const Node a, const Node b) { return a.dist b.dist; // 注意小顶堆用的是大于号 } }; priority_queueNode, vectorNode, Cmp pq;提示Dijkstra算法、合并K个有序链表、滑动窗口最大值这些经典问题底层全依赖优先队列这个容器值得花一小时专门练透。3.4 string的常用操作与坑字符串在算法题里绕不开尤其是处理子串、回文串、字符统计。C的string有不少方便的函数但有几个坑值得注意substr的参数是起始位置长度不是起始位置结束位置。很多从Python转过来的人容易在这上面翻车。getline配合cin处理含空格的整行输入如果你前面用过cin 缓冲区会留下换行符直接用getline会读到空行。解决办法是先cin.ignore()。字符统计用数组代替map如果范围是26个小写字母直接用vectorint cnt(26, 0)性能远好于unordered_map。这是一个经常被忽视的优化点。对string做大量拼接操作时注意比str str ch高效得多前者是原地操作后者会创建新对象。4. 经典算法模板与场景拆解4.1 二分查找不是找到就完了而是边界二分查找算得上最简单也最容易写错的算法。说它简单是因为思路就一句话——每次砍掉一半说它容易写错是因为边界条件稍微调错就是死循环或者漏解。我推荐的写法是左闭右开区间配合searchFirst等价变体统一处理这样记起来只有一个模板// 在有序数组中查找第一个 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时直接相加可能溢出。虽然在普通题目里不容易触发但这是个好习惯竞赛时能救你一命。这套模板的核心思想始终保持答案可能在[left, right)区间内最终left和right会收敛到同一个位置这个位置就是答案。想找最后一个小于target的元素就得在判断条件上做文章但区间框架不变。4.2 滑动窗口最长与最短的套路差异滑动窗口是双指针思想的进阶版专门用于处理子数组/子串问题。核心维护一个窗口[left, right]通过扩展和收缩遍历所有可能的状态。最长类问题如无重复最长子串的模板int maxWindow(vectorint nums) { int left 0, ans 0; unordered_mapint, int window; // 记录窗口内元素状态 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; }最短类问题如最短覆盖子串则是完全相反的形态——先不断扩展直到满足条件再尝试收缩找最短。这两者的核心区别在于最长类窗口是不满足才收缩最短类窗口是满足就收缩。我一开始把这两套逻辑混在一起每次写都要推半天后来把模板分开记录之后基本秒套。有一个高频考点是窗口内的统计方式。如果只涉及字符且字符范围有限比如只有字母建议用数组计数而不是map代码如下vectorint cnt(128, 0); // ASCII码范围 int needCnt 0; // 记录满足条件的字符种类数4.3 DFS与BFS搜迷宫和求最短路的两种武器搜索是算法题的分水岭。DFS深度优先搜索适合求所有解的场景全排列、组合、岛屿数量、回溯剪枝BFS广度优先搜索适合求最短路径的场景走迷宫、最小步数、单词接龙。DFS的经典框架以岛屿数量为例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标记一定要在递归进入之前完成。如果放在递归开始之后可能会造成重复访问和死循环。我一开始习惯性在进入下一层之前不加标记超时之后排查半天才发现问题。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数组同时承担是否访问过和距离为多少两个职责这是BFS中最常用的优化写法能省一个额外的visited数组。4.4 动态规划入门最难啃但回报最大的一章动态规划是很多人的噩梦我一开始也被吓到后来发现其实是方法论问题。比起背状态转移方程更重要的是按固定步骤思考定义状态dp[i]表示什么大多数题目里dp[i]代表以第i个元素结尾的最优解或者前i个元素的最优解。写出转移方程dp[i]怎么由更小的状态推出来确定初始条件dp[0]或dp[1]等于什么确认遍历顺序从前往后还是从后往前一维还是二维以最经典的最长递增子序列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(n²)的写法是最容易理解的版本。如果想优化到O(n log n)需要用贪心二分维护一个递增序列的尾部最小值数组这个进阶版本我放在笔记后面作为拓展题不建议新手一上来就啃。DP的题感培养需要大量题量支撑。我个人经验是先保证能把背包问题、最长公共子序列、最长递增子序列、编辑距离这四个最经典模型吃透之后再看其他DP题就不会觉得是完全陌生的了。5. 精度、溢出与性能调优算法题里最隐蔽的坑5.1 整数溢出的常见场景C刷题最常见的问题之一就是溢出。比如计算中间值时两个10^9的数相乘直接得到10^18已经超过int上限约2.1×10^9。很多人题目思路全对提交却WA一查才发现是溢出。我的检查清单运算过程中涉及乘法且数值可能超过10^4先把变量类型设成long long求平均值取(left right) / 2时用left (right - left) / 2防溢出状态转移方程里出现加法比如二维DP中dp[i][j] dp[i][j-1]如果答案可能超过int上限dp数组直接定义成vectorvectorlong long5.2 浮点数比较永远不要用如果你做过涉及浮点数的题比如二分答案求平方根一定会遇到精度问题。浮点数在内存中是近似表示的所以sqrt(2) * sqrt(2) 2在C里很可能得到false。正确的做法是定义一个极小值epsilon用绝对值差是否小于epsilon来判断。const double EPS 1e-8; if (fabs(a - b) EPS) { // 视为相等 }5.3 时间复杂度的估算方法很多新手问我题目提交超时是不是算法不够好。实际上超时有两个原因要么复杂度太高要么常数太大。前者靠换算法后者靠优化编码细节。估算方法很简单假设你的程序每秒能执行大约10^8次基本运算这个值对OJ环境大致适用。那么数据规模n 10^5O(n²)算法 10^10次必超时数据规模n 10^5O(n log n)算法 ≈ 1.7×10^6次很安全数据规模n 10^6O(n)算法 10^6次没问题拿到题目第一件事不是写代码而是先看数据范围确定允许的复杂度级别。这个习惯能帮你排除掉一半的错误思路。比如看到n ≤ 10^5就应该立刻排除需要两层循环的O(n²)解法。5.4 输入输出优化cin和cout没你想的那么慢刷题时经常听到用scanf别用cin的说法。这个说法有历史背景早期C的cin为了兼容C的stdio默认开启了同步导致性能偏低。但在现代OJ上你只要在main开头加上一行ios::sync_with_stdio(false); cin.tie(nullptr);cin和cout的速度就能逼近scanf/printf完全够用。我个人是能用cin就用cin省去格式串的调试时间只有需要格式化输出特定宽度时才用printf。这行的原理是关闭C和C两套IO的同步缓冲区cin和cout不再等待stdio的刷新自然就快了。注意关闭同步后不要混用cin和scanf会乱序这点写在笔记的第一页。6. 常见问题与排查技巧实录6.1 编译错误篇大多数人卡住的不是算法我能说一半以上新手提交不通过卡在编译错误阶段吗常见的编译错误有这几种忘了引入头文件用vector不加vector用sqrt不加cmath。解决办法是养成写完代码先自查include的习惯。结构体比较没重载运算符用了sort对自定义结构体排序却忘了定义比较函数编译直接报错。函数声明和定义不匹配特别是模板函数声明时用了T定义时用了int类型对不上。注意C11起的特性差异auto、unordered_map、make_pair这些都是C11的如果平台用的是C98标准全部报错。刷题前先确认标准版本。一个非常实用的排错技巧从报错信息的最后一行倒着看。编译器的报错经常是级联的——第一个错误引发后面几十个错误但真正的源头往往在最后那一行。6.2 运行时错误段错误和栈溢出的区别提交后报Runtime Error大多数情况是段错误访问了非法内存。常见的触发点数组越界vectorint nums(10); nums[10] 1;下标最大只能是9空指针/野指针用了一个未初始化的指针解引用end迭代器*nums.end()是未定义行为递归深度过大DFS递归穿过1万层以上可能爆栈如果是递归爆栈有两个解决办法一是把递归改成显式的栈模拟比如用stack保存状态二是把DFS改成BFS。设计算法时就考虑递归深度比出了问题再改要省事得多。6.3 逻辑错误AC代码为什么总差一点点最气人的是本地运行没问题提交就WA。这类问题绝大多数是边界条件没处理好空数组、只含一个元素的数组已经有序的数组全是相同元素的数组最大值的边界情况比如k大于数组长度我的建议是写完代码后走一遍自己写的样例还不够要手动构造3-4个极端用例。比如排序算法测一下[]和[5]二分查找测一下target小于所有元素和target大于所有元素的情况。五毛钱的功夫能省去半天调试时间。6.4 死循环的排查套路如果你发现程序卡住不输出多半是循环没退出。排查顺序二分查找的left和right更新是否正确left mid 1和right mid这是正确节奏如果把left mid就会陷入两个相邻位置的死循环滑动窗口的left是否在某个条件下永不右移链表的快慢指针有没有在同一节点打转DFS/BFS的状态标记是否漏了某个分支有一个调试技巧很实用——在循环体的开头加一行cout debug: left right endl;观察变量变化死循环的位置立刻暴露。用完记得删掉。7. 环境配置与刷题工作流7.1 本地调试环境搭建要点虽然OJ上提交不看本地环境但本地调试能极大提升刷题效率。我的开发环境是三件套VSCode GCC 一个简单的测试脚本。写算法题时我从来不在一个main函数里堆代码——而是写一个包含全部测试用例的单文件测试用命令行编译运行g -stdc17 -Wall -Wextra -g -o main main.cpp-Wall -Wextra能提示绝大多数未定义行为和类型转换问题-g生成调试信息配合gdb使用。这些编译选项在OJ上是不会启用的所以在本地编译干净通过能提前过滤掉一大半问题。7.2 刷题前5分钟的准备动作我每次开始刷题前会先花五分钟默一遍基础模板快排的partition、二分查找的两个变体、DFS和BFS的骨架、滑动窗口的左右指针移动逻辑。这就像热身能让手和大脑快速进入状态。如果你还没有自己整理过模板我的建议是现在就打开一个空白文档手敲一遍上面列的核心模板。手敲和复制粘贴的差别很大——敲的过程中你才会注意到那些边界条件的细节。7.3 笔记更新的迭代方式这份笔记写了小半年更新方式从一开始的刷到哪记到哪变成了现在的版本管理方式每个专题单独一个文件每次刷题后如果有新感悟或者新坑追加在对应专题的补充记录区域。我现在习惯在每道题提交通过之后顺手更新笔记——哪怕只是加一条这题可以用上一题模板直接套。这样积累足够多之后笔记就是一本完全个人化的算法手册。8. 最后的实操建议8.1 做题顺序怎么定先广度后深度如果你刚开始刷题我强烈建议按这个顺序扫一遍知识点线性表数组、链表、栈、队列→ 哈希表 → 排序与自定义排序 → 二分查找 → 双指针/滑动窗口 → 树的基础遍历 → DFS/BFS → 回溯 → 贪心 → 动态规划。前段是性价比最高的内容投入三四周就能有明显感觉。动态规划放到最后不是因为不重要而是因为它需要综合运用前面的数据结构基础太早接触容易打击信心。8.2 一道题刷到什么程度算会了我自己的标准有三层能独立AC、能讲清楚思路和复杂度、能说出这题的变种以及模板还有哪些其他用途。只满足第一层算做过了三层都满足才算掌握了。后者关系到你碰到新题时能不能快速联想到旧套路。每道题AC之后建议顺手做两件事一是看一眼题解区是否有比你的方法更优的解法记录下来二是想一想如果题目稍微改一下条件比如数组变成无序、最大值改为最小值、m次改为k次你的解法还成立吗。这两个习惯对培养算法思维特别有效。8.3 分享我的一个习惯错题本比题单更值钱我做题最宝贵的资产不是AC过的题而是那些多次提交才过、或者看了题解才恍然大悟的题。遇到这种题我除了正常笔记外专门在文档末尾加了一个弱题清单记录当时的卡壳点。每周回头重做清单里的题直到一次AC再移出清单。这比每天刷新题有效得多——你真正需要训练的是你的薄弱点而不是你已经会的东西。这份笔记还在持续更新接下来我会补充的内容包括图论进阶拓扑排序、并查集、最短路、字符串算法KMP、Trie树、更多动态规划的经典模型以及一些竞赛向的技巧。如果你是按这篇笔记的框架来学习的建议每学完一个专题写自己的三条总结把你遇到的坑和心得也记进去——自己的笔记永远是最好用的笔记。 
长河君 · 2026/10/19 15:27:57 · 阅读 1.2k C++算法刷题笔记：STL容器与高频模板实战
1. 这份笔记从哪来适合谁看把标题拆开看就一句话这是一个C入门选手写给自己的算法刷题笔记。不是什么系统教材也不是什么大神心得就是我自己边学边记录、边踩坑边修正的东西顺手整理出来分享给同样在摸索的人。先说说我自己的情况方便你判断内容适不适合你。我写C写过一阵子业务代码但算法这块一直是短板做题基本靠直觉碰上稍复杂的就抓瞎。今年决定系统地补一补把力扣、洛谷、牛客上的题按专题刷边刷边把套路记下来。这份笔记就是那时候开始攒的到现在已经积累了小两百条还在持续更新。笔记主要解决三个问题。第一是知识碎片化——今天学个链表、明天碰个DP过两周全忘了必须有个地方把套路固定下来。第二是代码模板化——很多算法本质上就是几套固定写法的变种把模板记熟能省掉大量重复推导时间。第三是排错经验化——算法题里最耗时间的其实是各种隐蔽错误比如数组越界、死循环、边界条件这些坑光靠看书学不到必须自己踩一遍才能记住。所以这份笔记的核心价值不在于系统全面而在于**实战可复现**——每条笔记都对应一个真实题目或真实场景写的时候就能直接用。笔记默认你有基本语法功底知道指针、引用、STL容器是什么但不需要你有算法竞赛背景零基础刷题的人跟着这个框架走完全没问题。我用的编译器是GCC 9.4配合VS Code环境刷题平台是力扣和洛谷。后面所有代码都基于C11标准个别地方用了C17的特性我会单独标注。2. 整体设计思路为什么我选择专题刷题模板沉淀的方式2.1 入门算法的核心矛盾知识量大与时间精力有限的冲突算法题涉及的知识点非常多数组、链表、栈、队列、树、图、排序、搜索、动态规划、贪心、回溯、字符串匹配……如果按教材一章一章啃啃到树就已经想放弃了。但反过来看真正笔试面试常考的并没那么玄乎核心其实就是那几个固定专题的排列组合。我统计过自己刷的一百多道题出题频率最高的就这几类双指针和滑动窗口大概占20%二分查找和二分答案差不多15%数据结构设计题15%DFS和BFS搜索15%动态规划15%剩下是贪心、回溯和杂题。这个比例说明一件事你把六七个专题的套路吃透就能覆盖八成以上的题目。这就是我选择专题刷题而不是按页翻书的原因。2.2 模板沉淀一篇笔记解决一类题一个很深的体会是一道题你会做不代表你掌握了这一类题。很多题看起来不一样底层解法是同一套东西。比如最长无重复子串、最小覆盖子串、长度最小的子数组表面上三题完全无关但全部可以用滑动窗口模板解决。我笔记里的做法就是刷完一类题之后立刻总结一版通用解法模板配合两三道典型例题之后遇到同类型的题目直接套模板改参数效率比每次从头推导高太多。2.3 笔记结构的演进从流水账到反查手册最早我的笔记就是流水账——今天刷了什么题、AC还是WA、用了什么方法写到后面发现根本没法查。后来我重构了一次按专题分类组织每条笔记包含五个要素问题模型、核心思路、代码模板、复杂度分析、易错点。现在做题遇到卡壳我能快速定位到相关笔记比搜索引擎还好用。这个结构这里也分享给你后面每个专题我都是按这五个要素来写的。3. 核心知识点拆解STL容器到底该怎么用3.1 vector的底层机制与性能取舍vector是C里用得最多的容器但很多人只是当可变长数组用对它的底层机制和性能特性了解不够。vector的本质是动态数组底层维护三个指针起始位置、当前使用末尾、容量末尾。当元素数量超过当前容量时vector会重新分配一块更大的内存通常翻倍把旧元素逐个拷贝过去然后释放旧内存。这一步非常贵——如果你在循环里不断push_back触发了扩容时间复杂度就是O(n)的拷贝开销。实操中我的建议如果能预估元素数量上限直接调用reserve预留空间。举个例子你要读取一个有N个整数的数组int n; cin n; vectorint nums; nums.reserve(n); // 推荐避免多次扩容拷贝 for (int i 0; i n; i) { int x; cin x; nums.push_back(x); }顺便说一个刷题时经常踩的坑vector的size()返回的是size_t类型无符号整数如果直接拿0去减它得到的是一个巨大的正数导致循环永远不结束或者越界。正确写法是先转成int再减或者用nums.size()参与比较时保持两边同为无符号类型。3.2 map、set与unordered系列的选择逻辑很多新手纠结什么时候用map、什么时候用unordered_map这里有个简单的判断标准需要有序遍历键值对用map底层红黑树O(log n)操作只需要快速查找不需要顺序用unordered_map底层哈希表平均O(1)操作需要判断元素是否存在且不关心顺序用unordered_set需要去重且保持顺序用set实际刷题时九成以上的题目用unordered_map就够了因为哈希查找的常数极小性能远好于红黑树的log n。只有在考到按顺序输出或者找第k小元素这类需要区间操作时才轮到map和set出场。有个细节要注意unordered_map的遍历顺序是不确定的如果你的结果对顺序有要求必须先排序再处理。3.3 priority_queue与自定义比较器优先队列堆是很多算法题的利器特别是涉及每次取最大/最小的场景。默认的priority_queue是大顶堆取的是最大元素。如果要取最小元素一般两种写法// 写法一用 greater 指定小顶堆 priority_queueint, vectorint, greaterint minHeap; // 写法二存入负值 priority_queueint maxHeap; maxHeap.push(-x); // 取出来的时候记得取负对于自定义结构体需要重载比较运算符。这里是重灾区很多人搞不清比较方向和堆的大小的关系。我的记忆技巧是返回true表示第一个参数排在第二个参数后面也就是优先级更低。struct Node { int dist; int id; }; // 自定义小顶堆dist小的优先 struct Cmp { bool operator()(const Node a, const Node b) { return a.dist b.dist; // 注意小顶堆用的是大于号 } }; priority_queueNode, vectorNode, Cmp pq;提示Dijkstra算法、合并K个有序链表、滑动窗口最大值这些经典问题底层全依赖优先队列这个容器值得花一小时专门练透。3.4 string的常用操作与坑字符串在算法题里绕不开尤其是处理子串、回文串、字符统计。C的string有不少方便的函数但有几个坑值得注意substr的参数是起始位置长度不是起始位置结束位置。很多从Python转过来的人容易在这上面翻车。getline配合cin处理含空格的整行输入如果你前面用过cin 缓冲区会留下换行符直接用getline会读到空行。解决办法是先cin.ignore()。字符统计用数组代替map如果范围是26个小写字母直接用vectorint cnt(26, 0)性能远好于unordered_map。这是一个经常被忽视的优化点。对string做大量拼接操作时注意比str str ch高效得多前者是原地操作后者会创建新对象。4. 经典算法模板与场景拆解4.1 二分查找不是找到就完了而是边界二分查找算得上最简单也最容易写错的算法。说它简单是因为思路就一句话——每次砍掉一半说它容易写错是因为边界条件稍微调错就是死循环或者漏解。我推荐的写法是左闭右开区间配合searchFirst等价变体统一处理这样记起来只有一个模板// 在有序数组中查找第一个 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时直接相加可能溢出。虽然在普通题目里不容易触发但这是个好习惯竞赛时能救你一命。这套模板的核心思想始终保持答案可能在[left, right)区间内最终left和right会收敛到同一个位置这个位置就是答案。想找最后一个小于target的元素就得在判断条件上做文章但区间框架不变。4.2 滑动窗口最长与最短的套路差异滑动窗口是双指针思想的进阶版专门用于处理子数组/子串问题。核心维护一个窗口[left, right]通过扩展和收缩遍历所有可能的状态。最长类问题如无重复最长子串的模板int maxWindow(vectorint nums) { int left 0, ans 0; unordered_mapint, int window; // 记录窗口内元素状态 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; }最短类问题如最短覆盖子串则是完全相反的形态——先不断扩展直到满足条件再尝试收缩找最短。这两者的核心区别在于最长类窗口是不满足才收缩最短类窗口是满足就收缩。我一开始把这两套逻辑混在一起每次写都要推半天后来把模板分开记录之后基本秒套。有一个高频考点是窗口内的统计方式。如果只涉及字符且字符范围有限比如只有字母建议用数组计数而不是map代码如下vectorint cnt(128, 0); // ASCII码范围 int needCnt 0; // 记录满足条件的字符种类数4.3 DFS与BFS搜迷宫和求最短路的两种武器搜索是算法题的分水岭。DFS深度优先搜索适合求所有解的场景全排列、组合、岛屿数量、回溯剪枝BFS广度优先搜索适合求最短路径的场景走迷宫、最小步数、单词接龙。DFS的经典框架以岛屿数量为例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标记一定要在递归进入之前完成。如果放在递归开始之后可能会造成重复访问和死循环。我一开始习惯性在进入下一层之前不加标记超时之后排查半天才发现问题。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数组同时承担是否访问过和距离为多少两个职责这是BFS中最常用的优化写法能省一个额外的visited数组。4.4 动态规划入门最难啃但回报最大的一章动态规划是很多人的噩梦我一开始也被吓到后来发现其实是方法论问题。比起背状态转移方程更重要的是按固定步骤思考定义状态dp[i]表示什么大多数题目里dp[i]代表以第i个元素结尾的最优解或者前i个元素的最优解。写出转移方程dp[i]怎么由更小的状态推出来确定初始条件dp[0]或dp[1]等于什么确认遍历顺序从前往后还是从后往前一维还是二维以最经典的最长递增子序列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(n²)的写法是最容易理解的版本。如果想优化到O(n log n)需要用贪心二分维护一个递增序列的尾部最小值数组这个进阶版本我放在笔记后面作为拓展题不建议新手一上来就啃。DP的题感培养需要大量题量支撑。我个人经验是先保证能把背包问题、最长公共子序列、最长递增子序列、编辑距离这四个最经典模型吃透之后再看其他DP题就不会觉得是完全陌生的了。5. 精度、溢出与性能调优算法题里最隐蔽的坑5.1 整数溢出的常见场景C刷题最常见的问题之一就是溢出。比如计算中间值时两个10^9的数相乘直接得到10^18已经超过int上限约2.1×10^9。很多人题目思路全对提交却WA一查才发现是溢出。我的检查清单运算过程中涉及乘法且数值可能超过10^4先把变量类型设成long long求平均值取(left right) / 2时用left (right - left) / 2防溢出状态转移方程里出现加法比如二维DP中dp[i][j] dp[i][j-1]如果答案可能超过int上限dp数组直接定义成vectorvectorlong long5.2 浮点数比较永远不要用如果你做过涉及浮点数的题比如二分答案求平方根一定会遇到精度问题。浮点数在内存中是近似表示的所以sqrt(2) * sqrt(2) 2在C里很可能得到false。正确的做法是定义一个极小值epsilon用绝对值差是否小于epsilon来判断。const double EPS 1e-8; if (fabs(a - b) EPS) { // 视为相等 }5.3 时间复杂度的估算方法很多新手问我题目提交超时是不是算法不够好。实际上超时有两个原因要么复杂度太高要么常数太大。前者靠换算法后者靠优化编码细节。估算方法很简单假设你的程序每秒能执行大约10^8次基本运算这个值对OJ环境大致适用。那么数据规模n 10^5O(n²)算法 10^10次必超时数据规模n 10^5O(n log n)算法 ≈ 1.7×10^6次很安全数据规模n 10^6O(n)算法 10^6次没问题拿到题目第一件事不是写代码而是先看数据范围确定允许的复杂度级别。这个习惯能帮你排除掉一半的错误思路。比如看到n ≤ 10^5就应该立刻排除需要两层循环的O(n²)解法。5.4 输入输出优化cin和cout没你想的那么慢刷题时经常听到用scanf别用cin的说法。这个说法有历史背景早期C的cin为了兼容C的stdio默认开启了同步导致性能偏低。但在现代OJ上你只要在main开头加上一行ios::sync_with_stdio(false); cin.tie(nullptr);cin和cout的速度就能逼近scanf/printf完全够用。我个人是能用cin就用cin省去格式串的调试时间只有需要格式化输出特定宽度时才用printf。这行的原理是关闭C和C两套IO的同步缓冲区cin和cout不再等待stdio的刷新自然就快了。注意关闭同步后不要混用cin和scanf会乱序这点写在笔记的第一页。6. 常见问题与排查技巧实录6.1 编译错误篇大多数人卡住的不是算法我能说一半以上新手提交不通过卡在编译错误阶段吗常见的编译错误有这几种忘了引入头文件用vector不加vector用sqrt不加cmath。解决办法是养成写完代码先自查include的习惯。结构体比较没重载运算符用了sort对自定义结构体排序却忘了定义比较函数编译直接报错。函数声明和定义不匹配特别是模板函数声明时用了T定义时用了int类型对不上。注意C11起的特性差异auto、unordered_map、make_pair这些都是C11的如果平台用的是C98标准全部报错。刷题前先确认标准版本。一个非常实用的排错技巧从报错信息的最后一行倒着看。编译器的报错经常是级联的——第一个错误引发后面几十个错误但真正的源头往往在最后那一行。6.2 运行时错误段错误和栈溢出的区别提交后报Runtime Error大多数情况是段错误访问了非法内存。常见的触发点数组越界vectorint nums(10); nums[10] 1;下标最大只能是9空指针/野指针用了一个未初始化的指针解引用end迭代器*nums.end()是未定义行为递归深度过大DFS递归穿过1万层以上可能爆栈如果是递归爆栈有两个解决办法一是把递归改成显式的栈模拟比如用stack保存状态二是把DFS改成BFS。设计算法时就考虑递归深度比出了问题再改要省事得多。6.3 逻辑错误AC代码为什么总差一点点最气人的是本地运行没问题提交就WA。这类问题绝大多数是边界条件没处理好空数组、只含一个元素的数组已经有序的数组全是相同元素的数组最大值的边界情况比如k大于数组长度我的建议是写完代码后走一遍自己写的样例还不够要手动构造3-4个极端用例。比如排序算法测一下[]和[5]二分查找测一下target小于所有元素和target大于所有元素的情况。五毛钱的功夫能省去半天调试时间。6.4 死循环的排查套路如果你发现程序卡住不输出多半是循环没退出。排查顺序二分查找的left和right更新是否正确left mid 1和right mid这是正确节奏如果把left mid就会陷入两个相邻位置的死循环滑动窗口的left是否在某个条件下永不右移链表的快慢指针有没有在同一节点打转DFS/BFS的状态标记是否漏了某个分支有一个调试技巧很实用——在循环体的开头加一行cout debug: left right endl;观察变量变化死循环的位置立刻暴露。用完记得删掉。7. 环境配置与刷题工作流7.1 本地调试环境搭建要点虽然OJ上提交不看本地环境但本地调试能极大提升刷题效率。我的开发环境是三件套VSCode GCC 一个简单的测试脚本。写算法题时我从来不在一个main函数里堆代码——而是写一个包含全部测试用例的单文件测试用命令行编译运行g -stdc17 -Wall -Wextra -g -o main main.cpp-Wall -Wextra能提示绝大多数未定义行为和类型转换问题-g生成调试信息配合gdb使用。这些编译选项在OJ上是不会启用的所以在本地编译干净通过能提前过滤掉一大半问题。7.2 刷题前5分钟的准备动作我每次开始刷题前会先花五分钟默一遍基础模板快排的partition、二分查找的两个变体、DFS和BFS的骨架、滑动窗口的左右指针移动逻辑。这就像热身能让手和大脑快速进入状态。如果你还没有自己整理过模板我的建议是现在就打开一个空白文档手敲一遍上面列的核心模板。手敲和复制粘贴的差别很大——敲的过程中你才会注意到那些边界条件的细节。7.3 笔记更新的迭代方式这份笔记写了小半年更新方式从一开始的刷到哪记到哪变成了现在的版本管理方式每个专题单独一个文件每次刷题后如果有新感悟或者新坑追加在对应专题的补充记录区域。我现在习惯在每道题提交通过之后顺手更新笔记——哪怕只是加一条这题可以用上一题模板直接套。这样积累足够多之后笔记就是一本完全个人化的算法手册。8. 最后的实操建议8.1 做题顺序怎么定先广度后深度如果你刚开始刷题我强烈建议按这个顺序扫一遍知识点线性表数组、链表、栈、队列→ 哈希表 → 排序与自定义排序 → 二分查找 → 双指针/滑动窗口 → 树的基础遍历 → DFS/BFS → 回溯 → 贪心 → 动态规划。前段是性价比最高的内容投入三四周就能有明显感觉。动态规划放到最后不是因为不重要而是因为它需要综合运用前面的数据结构基础太早接触容易打击信心。8.2 一道题刷到什么程度算会了我自己的标准有三层能独立AC、能讲清楚思路和复杂度、能说出这题的变种以及模板还有哪些其他用途。只满足第一层算做过了三层都满足才算掌握了。后者关系到你碰到新题时能不能快速联想到旧套路。每道题AC之后建议顺手做两件事一是看一眼题解区是否有比你的方法更优的解法记录下来二是想一想如果题目稍微改一下条件比如数组变成无序、最大值改为最小值、m次改为k次你的解法还成立吗。这两个习惯对培养算法思维特别有效。8.3 分享我的一个习惯错题本比题单更值钱我做题最宝贵的资产不是AC过的题而是那些多次提交才过、或者看了题解才恍然大悟的题。遇到这种题我除了正常笔记外专门在文档末尾加了一个弱题清单记录当时的卡壳点。每周回头重做清单里的题直到一次AC再移出清单。这比每天刷新题有效得多——你真正需要训练的是你的薄弱点而不是你已经会的东西。这份笔记还在持续更新接下来我会补充的内容包括图论进阶拓扑排序、并查集、最短路、字符串算法KMP、Trie树、更多动态规划的经典模型以及一些竞赛向的技巧。如果你是按这篇笔记的框架来学习的建议每学完一个专题写自己的三条总结把你遇到的坑和心得也记进去——自己的笔记永远是最好用的笔记。