我把之前的内容重新写一遍这次确保它是完整发布的正文——直接铺开符合博文本身的阅读体验。在竞赛圈和面试圈混久了你会发现不管你是准备蓝桥杯、打ACM还是日常刷LeetCode最后大家手里都会攒一堆“C算法模板”。所谓模板不是让你背个答案去套题而是把那些思路固定、边界容易踩坑的算法提前写成一套自己能默写、能改、能信任的代码。这玩意儿就像你工具箱里的活动扳手平时不觉得真到现场调Bug调到头大的时候有个趁手的模板能省半小时不止。这篇东西就是我从自己常用模板库里挑出来的一部分以C为主覆盖了从环境配置、排序查找、质数判断、图论最短路到单调栈、字符串处理这些高频考点。准备蓝桥杯的同学可以重点看Dijkstra和单调栈那两章刷LeetCode的可以重点看二分和字符串转换那部分至于刚开始学C的建议从第一章环境配置看起把VSCode这套跑通了再往后走。1. 上机前先把环境调明白VSCode跑通C/C先说一个很现实的问题很多人不是算法不会是环境先把他劝退了。我看过太多群里的小伙伴下了个VSCode装了C/C插件然后写个helloworld编译报一堆错最后默默回到Dev-C或者别的IDE去了。其实VSCode配C/C环境没那么玄乎捋清楚几个环节就行。1.1 为什么我建议VSCode配MinGW-w64我个人的建议是用VSCode加MinGW-w64这套组合而不是一上来就装Visual Studio。原因挺简单竞赛和笔试环境基本都基于GCC你用MinGW-w64意味着本地编译行为比如-O2优化、long long的IO表现、__int128这种扩展类型跟评测机更接近。Visual Studio的MSVC编译器在标准库实现和某些未定义行为的处理上有差异容易出现“本地能过、交上去崩了”的情况。安装的时候有几个注意点。MinGW-w64建议选自带POSIX线程的版本因为C标准库里的std::thread需要线程模型支持win32线程模型在某些场景下会有问题。装完把g.exe所在目录一般是...\mingw64\bin加到系统Path环境变量里这一步不做后面VSCode里怎么折腾都白搭。VSCode这边装三个东西就够C/C扩展就是微软那个、Code Runner可选图省事、以及一个你顺手的主题。C/C扩展负责语法高亮和智能感知Code Runner负责一键编译运行。1.2 配置tasks.json和launch.json的思路很多人一看到tasks.json和launch.json就头大其实它们做的事情特别简单tasks.json告诉VSCode“怎么编译”launch.json告诉VSCode“编译完之后怎么运行和调试”。tasks.json里核心就一个command和args。我常用的配置长这样{ version: 2.0.0, tasks: [ { type: cppbuild, label: C Build, command: g, args: [ -stdc17, -O2, -Wall, ${file}, -o, ${fileDirname}/${fileBasenameNoExtension}.exe ], problemMatcher: [$gcc], group: build } ] }注意我在args里写了-stdc17和-O2。C17现在基本是主流竞赛和大部分面试环境默认支持的标准网上很多模板代码用了结构化绑定、std::optional这种新特性标准太低会编译不过。-O2是为了和评测环境对齐同时也会暴露一些因为未定义行为导致的诡异问题早点发现比比赛时发现好。launch.json配置调试器的路径指向MinGW-w64里的gdb.exe就行。等这套文件配置好你按F5能跑、能断点、能看变量环境这关就算过了。1.3 编译期报错和运行期异常处理思路完全不同配置好环境之后接下来遇到的就是报错。我把常见报错分成两类处理逻辑完全不同。第一类是编译期报错比如“找不到头文件”“未定义的引用”。前者多半是Path没配好或者头文件路径没指对后者常见于你声明了函数但没写实现或者链接时少写了某个源文件。这类报错的好处是它会在编译阶段拦住你不会让程序跑起来所以排错相对安全。第二类是运行期异常热搜词里有个很典型的“捕获到标准C异常。有关详细信息请参见系统日志文件”。这种一看就是程序跑起来之后抛了异常多半是数组越界、访问了被释放的内存、或者STL容器使用姿势不对。遇到这种问题我的习惯是先把-Wall开起来重新编译一次看看有没有警告。很多未定义行为在警告里已经能看出端倪比如有符号和无符号比较、变量未初始化这些在-Wall下会原形毕露。再教大家一个小技巧在VSCode里调试遇到诡异问题先别急着看launch.json里的各种复杂配置直接在项目目录下开个终端手动敲一遍g -stdc17 -O2 -Wall -g main.cpp -o main ./main如果命令行里能跑通说明是VSCode配置的问题如果命令行里就崩了说明是你代码的问题。这一下就把问题范围砍掉一半排查效率高很多。2. 排序查找与质数竞赛和面试最先用的模板环境跑通之后我们进入正题。排序、查找、质数判断这三类几乎是你开始刷题一周内就会撞上的东西。说它们简单是因为原理好懂说它们复杂是因为边界条件一多起来代码写得丑就特别容易出Bug。我的做法是每个类别只留一套自己最顺手的模板用熟了再谈优化。2.1 冒泡排序练手可以比赛慎用冒泡排序教学价值大于实用价值。它的核心思想是每一轮把相邻元素中较大或较小的那个往后“冒”一轮下来最大值就位。模板非常简单void bubbleSort(vectorint arr) { int n arr.size(); for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { swap(arr[j], arr[j 1]); swapped true; } } if (!swapped) break; // 已经有序提前结束 } }这个swapped标记是个经典优化如果一趟遍历下来没有任何交换说明数组已经有序直接退出。最坏情况是O(n²)最好情况接近O(n)配合提前退出。我平时基本不用它处理正经的排序任务但写面试题的时候可能会用它应急因为代码足够短不容易写错。2.2 手写快排了解原理模板别背太死真正上场的是快速排序。手写快排的模板有很多版本有单边扫描的、有双边扫描的有先处理基准再递归的有先递归再处理的。千万要注意的是网上流传的一些“背下来就行”的快排模板在遇到大量重复元素时会退化到O(n²)。最典型的就是那种每次选arr[left]作为基准、然后简单分区的写法在[1, 1, 1, 1, ..., 1]这种数组上会跑得特别慢。我偏好的写法是“三路快排”的思路把数组分成小于、等于、大于三个区域。虽然代码长一点但至少面对重复元素时不会退化而且稍作修改就能用来解决“第K大”或者“荷兰国旗”这类问题。template typename T void quickSort3Way(vectorT arr, int l, int r) { if (l r) return; T pivot arr[l (rand() % (r - l 1))]; // 随机选基准 int lt l, gt r, i l 1; while (i gt) { if (arr[i] pivot) { swap(arr[i], arr[lt]); } else if (arr[i] pivot) { swap(arr[i], arr[gt--]); } else { i; } } quickSort3Way(arr, l, lt - 1); quickSort3Way(arr, gt 1, r); }随机选基准很重要它能保证在面对有序数组时不会每次选中极端值导致递归深度变成O(n)从而把最坏时间复杂度拉回到期望O(n log n)。面试时如果被问到“快排最坏情况是什么”你答完最好接一句“所以我会随机化基准”这句话会显得你真正理解快排而不只是背了个模板。2.3 判断质数试除法到埃氏筛的优化套路判断质数这个点热词里专门有“判断质数c优化”说明大家在这上面卡过不少次。最简单的试除法模板是判断到sqrt(n)bool isPrime(long long n) { if (n 2) return false; if (n % 2 0) return n 2; for (long long i 3; i n / i; i 2) { if (n % i 0) return false; } return true; }这里有个细节i n / i等价于i * i n但写成i * i会有隐患——如果n接近2^31-1i*i在int范围内可能溢出。写成n / i就完全避免了乘法溢出问题。这种细节在单次判断质数时无所谓但如果写进竞赛代码面对long long级别的输入就会变成真正的坑。如果题目要求一次性判断一批数谁是质数单次试除就不够了得用埃氏筛。埃氏筛模板也比较短vectorint sieve(int n) { vectorint primes; vectorbool isPrime(n 1, true); isPrime[0] isPrime[1] false; for (int i 2; i n; i) { if (isPrime[i]) { primes.push_back(i); if ((long long)i * i n) for (long long j (long long)i * i; j n; j i) isPrime[j] false; } } return primes; }注意内层循环从i * i开始而不是从2*i开始因为小于i*i且含有因子i的数已经被更小的质因子筛过了。这个优化可以让埃氏筛的复杂度从O(n log n)降到接近O(n log log n)在筛10^7范围内的质数时体感差距很大。2.4 二分查找边界不谈清楚早晚踩坑排序之后必然要谈查找而二分查找是刷题绕不过去的坎。我几乎可以断言十个写二分的人有八个在边界条件上栽过跟头。到底写left right还是left rightmid更新是left mid还是left mid 1这些问题不统一每次写出来都心虚。我的做法是记住一套固定的“查找左边界”模板别的变体都从它上面推int binarySearchLeft(vectorint nums, int target) { int l 0, r (int)nums.size() - 1; while (l r) { int mid l (r - l) / 2; if (nums[mid] target) r mid - 1; else l mid 1; } return l; // 第一个 target 的位置 }这里的关键是循环不变量r始终指向满足nums[r] target的位置l始终指向满足nums[l] target的位置。循环结束时l就是第一个大于等于target的下标。如果需要“第一个大于target”的位置只要把换成即可。很多二分变体本质都是改这个比较符号其余代码都不用动。mid l (r - l) / 2这个写法也是为了防溢出。(l r) / 2在l和r都很大的时候可能超过int范围虽然题目里多半不会出现这种极端值但这是个良好的习惯。3. 最短路Dijkstra的朴素版和堆优化版都放这图论这块最短路是必考中的必考。而最短路算法里Dijkstra又是绝对的主角。蓝桥杯也好、面试手撕也好Dijkstra出现的频率高到我愿意花一整章来整理它的两种写法。注意Dijkstra处理不了负权边这个前提条件一定要记住遇到负权边得换SPFA或者Bellman-Ford不然结果是错的。3.1 朴素版Dijkstra适合稠密图和点数较少的场景朴素版Dijkstra的时间复杂度是O(V²)适合顶点数在几千以内、并且图比较稠密的情况。它的思路是维护一个dist数组每次从未确定的点里选一个距离最小的点再用它去松弛其它点。这个“每次找最小”的过程用暴力扫描完成所以复杂度里有个V²。const int INF 0x3f3f3f3f; vectorint dijkstra(int n, int s, vectorvectorpairint,int graph) { vectorint dist(n 1, INF); vectorbool visited(n 1, false); dist[s] 0; for (int i 1; i n; i) { int u -1; for (int j 1; j n; j) { if (!visited[j] (u -1 || dist[j] dist[u])) { u j; } } if (u -1 || dist[u] INF) break; visited[u] true; for (auto [v, w] : graph[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; } } } return dist; }注意我使用了0x3f3f3f3f而不是INT_MAX作为无穷大。原因是dist[u] w在dist[u]已经是INT_MAX时可能溢出变成负数导致松弛判断出错。0x3f3f3f3f大约是10^9加上一个边权也远达不到int上限安全得多。这个细节在竞赛里非常重要平时练习时一旦发现“答案变成负数了”先查一下是不是无穷大的问题。3.2 堆优化版Dijkstra稀疏图和大图的必选项当图的顶点数到了10^5这个级别O(V²)就完全没法用了。这时候要用堆优化版——用优先队列最小堆来维护“当前距离最小的点”每次弹出时如果发现这个点已经处理过就跳过直到队列为空。时间复杂度降到O(E log V)E是边数。vectorlong long dijkstra(int n, int s, vectorvectorpairint,long long graph) { const long long INF 0x3f3f3f3f3f3f3f3fLL; vectorlong long dist(n 1, INF); priority_queuepairlong long,int, vectorpairlong long,int, greater pq; dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; // 过期节点跳过 for (auto [v, w] : graph[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } return dist; }这段代码里特别要强调if (d ! dist[u]) continue这里的“过期节点”处理。因为我们不修改优先队列里已有元素的值而是直接插入一个新的、更小的距离所以同一个点可能出现在队列里好几次。弹出时如果发现这个距离已经不是当前记录的最小距离说明它是旧数据直接跳过。很多人一开始不理解为什么要加这一行结果发现同一个点被重复松弛很多次效率反而降了。greater这个空模板参数是C17之后允许的写法它会自动推导出比较类型比写greaterpairlong long,int要清爽一点。如果你们的编译器比较老写完整版本也行。3.3 两种版本怎么选我给自己定的判断规则我的选型规则很简单顶点数在1000以内直接朴素版顶点数多、或者边稀疏用堆优化版。举个具体场景蓝桥杯很多图的题顶点数在几百到一两千之间朴素版完全够用而且代码短不容易错而LeetCode上一些最短路题图可能到几万个节点那就是堆优化的天下。有向图和无向图的处理差别只在建图这一步。无向图需要在addEdge时同时加正反两条边有向图只加一条。这个细节经常有人漏一漏就是WAWrong Answer而且因为代码逻辑看起来没毛病特别难排查。我习惯把建图单独封装成一个函数并且每次都强制自己写一段注释说明“这里是双向边”减少低级失误。4. 单调栈一个模板吃透一类题单调栈是我个人非常偏爱的一个数据结构因为它的代码量特别少但能解决的问题类型相当多。热搜词里有“单调栈算法c”那我把它的通用模板和几个识别特征都整理出来。4.1 单调栈的固定套路单调栈的核心思想是维护一个栈让栈内元素保持单调递增或递减遍历数组时利用这个单调性快速找到“某个元素左侧/右侧第一个比它大/小的元素”。以“找每个元素右边第一个比它大的元素”为例经典模板vectorint nextGreaterElement(vectorint nums) { int n nums.size(); vectorint res(n, -1); stackint st; for (int i 0; i n; i) { while (!st.empty() nums[st.top()] nums[i]) { res[st.top()] nums[i]; st.pop(); } st.push(i); } return res; }这里的栈存的是下标不是值。为什么存下标因为存下标既可以通过nums[st.top()]拿到值又能知道这个元素的位置方便后续操作。这是单调栈的最重要细节之一。思路推演一下遍历到i时栈顶那些比nums[i]小的元素它们的“右边第一个比它大的元素”就是当前nums[i]所以出栈并记录答案。等到nums[i]自己也入栈后栈内依然保持从栈底到栈顶递减的顺序。整个流程走完还在栈里的元素就是右边没有更大值的初始化的-1保留即可。4.2 单调栈能解决的问题信号单调栈能解决的题目都有个共同特征题目里出现“找到左边/右边第一个比自己大/小的元素”这类描述。比如经典的两道题每日温度给定一个温度序列求每一天要等几天才能等到更高温度。这其实就是找右边第一个比它大的元素的距离。接雨水求柱子之间能存多少水。这需要找每个位置左右两侧更高的边界也可以用单调栈做。看到这类题第一反应就可以是单调栈。模板本身很固定真正决定你ACAccepted与否的是能不能把题目翻译成“下一个更大/更小元素”的模型。我建议刚开始练的时候每题先把这个翻译写在注释里写多了自然就形成条件反射了。单调栈的时间复杂度是O(n)因为每个元素最多入栈一次、出栈一次比暴力解法的O(n²)好看太多。5. 字符串数组与位运算全是隐藏分可能有人觉得字符串和位运算不算算法但我觉得这类题恰恰是“五分拉满分”的关键。很多人看不上这些细节觉得背背模板就完了结果工作时写C代码一写一个Bug。这里挑几个高频的坑展开讲。5.1 字符串数组初始化的三种写法“c字符串数组初始化”是热搜词里被怼出来的问题。字符串数组的初始化看似简单但C里有好几种写法各有各的使用场景// 写法一C风格字符串数组用双引号批量初始化 const char* arr1[] {hello, world}; // 写法二std::string 数组最常用 string arr2[] {apple, banana, cherry}; // 写法三动态分配的 vectorstring vectorstring arr3 {one, two, three};写法一是C风格字符串是const char*常量指针不能修改但兼容老接口。写法二是C风格std::string管内存不怕越界应该作为主力。写法三最常见于竞赛因为它可以动态添加元素还能用size()拿长度。有一个隐藏坑C风格字符串按行初始化、然后试图用cin读入一整行带空格的文本时需要用到cin.getline或者getline否则空格会被截断。用std::string加getline则没这些烦恼。5.2 字符串转数字别自己造轮子“c字符串转数组”这个需求也很常见尤其是写那种“给一串逗号分隔的数字”的题目。我的建议是能使用标准库函数就别自己手写解析器stoi、stol、stoll以及stringstream都是现成的。string s 12345; int num stoi(s); // 12345 // 带分隔符的拆分 string data 1,2,3,4,5; stringstream ss(data); string token; vectorint nums; while (getline(ss, token, ,)) { nums.push_back(stoi(token)); }getline(ss, token, ,)可以指定分隔符来逐段读取这是处理CSV类输入最好的方式。stoi在C11引入遇到不在数字范围内的字符串会抛异常所以如果你输入的字符串可能包含非数字字符最好先做判断或包一层try-catch。这个点平时练习注意不到笔试时会给你来一记教训。5.3 位运算按位与与运算符优先级位运算这块C的运算符优先级是一个非常隐蔽的大坑。热词里有“c按位与”和“c运算符优先级顺序表”这俩其实经常一起出现。原因是的优先级比低比很多新手预期的要低得多。int x 5; if (x 1 1) { // 会不会出问题 // ... }这段代码的坑在于的优先级高于所以表达式实际被解析为x (1 1)也就是x 1然后拿这个值作为if条件。虽然在这个具体例子里碰巧逻辑差不多对但你一旦写出x 3 1这种稍微复杂点的表达式结果就会完全偏离预期。我的建议是位运算表达式统一套括号比如(x 1) 1。不要考验你记优先级的能力直接靠括号把事情说清楚别人review你的代码时也轻松。类似地和的优先级也低于算术运算符x 2 1会被解析成x (2 1)同样要加括号。6. 模板背完之后还差一步如果你一路看到这里手里应该已经有了一套能用的C算法模板环境配好了排序、质数、二分、最短路、单调栈、字符串处理都有现成代码。但我想说句实话模板本身救不了你真正救你的是把模板内化成肌肉记忆的过程。6.1 用真题把模板“养”成自己的能力我的做法是每学一个新模板当天就找3道包含这个知识点的真题来练不是背完模板去做题而是做的时候强迫自己不翻模板写完再翻模板对照。你会发现凡是自己默写不出来的部分就是没真正理解的部分。比如Dijkstra的堆优化如果你能闭着眼睛写出“过期节点跳过”那行而且知道为什么要有那行才算真正过关。针对蓝桥杯这类有固定比赛时间的场景我还会给自己加一个限制手速题比如排序、质数判断、字符串转换要在10分钟内写完并跑通样例稍难一点的模板题比如Dijkstra、单调栈控制在20到30分钟内。这个时间压力的训练和算法知识本身同等重要因为考场上你大多数时候不是不会写而是来不及写。6.2 关于背诵的建议“c算法模板”本身没有太大意义真正有意义的是你的模板库经过实战检验、被你自己修改过、知道它每个分支在干什么。所以如果让我给一个建议那就是从今天开始建一个属于自己的模板文件夹每个模板都配上注释和一道例题链接然后每周回头review一次。这样持续一个月你会发现自己写代码的速度和自信都会上一个台阶。我个人在实际操作中最深的体会是与其记住十个花哨的模板不如把一个基础模板写对一百遍。因为所有复杂算法的高效写法本质上都是从这个基础版本一点点“长”出来的。等你对基础模板足够熟你就自然开始琢磨怎么把Dijkstra换成A*、怎么把单调栈改成单调队列、怎么把快排改造成第K大元素的快速选择。到那时候这个模板库才是真正属于你的工具而不是网上复制粘贴来的胶囊。最后分享一个小技巧把这些模板里的每个核心算法都配上“为什么这个写法是对的”的注释而不是只写“这段代码干了什么”。前者能帮你在考试紧张时快速回顾思路后者只会在关键时刻增加你的记忆负担。我自己的模板文件里注释基本都是在讲思路和边界条件代码本身反而不是第一重点了。这就是我这些年用C打比赛、刷题、面试下来最想和你们分享的东西。工具准备好了剩下的就是动起来。