今天是我C课后习题训练记录的第82篇。说实话能坚持到这个天数靠的已经不是刚开始那股冲劲了而是一套能稳定跑通的日常流程每天固定花四五十分钟先翻一翻前几天的旧题防止手生再做一两道新题保持手感最后把当天踩过的坑老老实实记下来。今天这篇记录主要围绕三个核心训练点展开单调栈求解“下一个更大元素”、快速幂和质数判断的优化组合、字符串拆分与结构体链表的混合练习。如果你也在用刷题的方式学C或者正准备算法笔试、机试这篇文章里的代码可以直接拿去用后面“踩坑记录”那一节也值得重点看——很多问题不是题目本身难而是语言细节和环境配置在拖后腿。1. 今日训练编排算法、语言细节、工程习惯三线并进1.1 为什么Day82要这样安排刷题刷到第82天最容易出现的问题是“偏科”。有的同学前五十天猛刷算法题结果遇上复杂一点的字符串处理就手忙脚乱有的同学天天研究语法糖和STL源码一上机写题连暴力解都憋不出来。我的体会是过了基础阶段之后每天的练习必须同时照顾三个维度算法思维、语言细节、工程习惯。今天选的三块内容就是按这个思路搭的。单调栈属于高频考点是典型的“暴力解谁都会、优化靠思维”的题目快速幂和质数判断是数学类算法的基本功面试笔试里出现频率极高字符串拆分和结构体链表则是把语言细节拉出来单练——这两块恰恰是很多人写C时最容易翻车的地方。有人可能会问都第82天了为什么还要练字符串和链表这种基础内容因为基础内容和基础内容不一样。数组遍历、条件判断这种确实不用天天练但字符串初始化、指针操作、内存布局这些细节隔一阵不碰就会生疏而且生疏的代价特别大——线上笔试没有编译器提示一个越界写就可能全盘皆输。1.2 我每天的固定训练节奏先说说我这82天跑下来的流程大家可以根据自己的时间裁剪。我一般是晚上九点开始总时长控制在50分钟左右前10分钟复习一道三到五天前做过的旧题不看答案直接重写重点检查边界条件是否还记得。中间30分钟做今天的新题一题为主如果状态好就加一道同类型的小题。最后10分钟整理笔记记录今天新接触的语法点、报错信息、复杂度分析思路。这个节奏的关键在于“旧题重写”。我之前吃过亏连续两周只做新题结果面试时让写一个插入排序居然在循环边界上卡了半分钟。从那以后旧题复习就没断过。今天复习的是插入排序正好和后面的链表练习呼应。2. 核心练习一单调栈求解“下一个更大元素”2.1 题目描述与暴力解法今天第一题是经典的“下一个更大元素”给定一个数组返回一个新的数组每个位置存的是原数组中该位置右边第一个比它大的元素如果右边没有更大的元素就存-1。比如输入[2, 1, 4, 3]输出就是[4, 4, -1, -1]。拿到题先想暴力解对每个元素从它右边开始线性扫描找到第一个比它大的就停下。时间复杂度O(n²)数组小的时候没问题但数据量到十万级别就必然超时。这道题的题眼在于“右边第一个比它大”这个描述它天然暗示着一种顺序关系后面的元素会“淘汰”前面的元素。2.2 单调栈的推演过程单调栈的思路可以这么理解我维护一个栈栈里的元素从底到顶保持单调递减。每来一个新元素就把栈顶那些比它小的元素全部“处理掉”——因为这些栈顶元素的“下一个更大元素”就是当前这个新元素处理完把它们弹出再把新元素的下标压进去。为了直观我习惯用“排队看身高”来类比一排人从左到右站好每个人向右看找第一个比自己高的人。你站在这排人后面前面那些比你矮的人马上就能看到你所以他们的问题当场解决而比你高的人看不到你得继续等后面更高的人出现。这里有一个关键点栈里存的是下标不是元素值。原因很简单我们最后要按下标位置填充结果数组如果存值还得额外记录位置白白增加复杂度。这个“存下标”的习惯我在前几天的“每日温度”那道题里就养成了今天再用一次非常顺手。2.3 完整代码与易错点#include iostream #include vector #include stack using namespace std; vectorint nextGreaterElement(vectorint nums) { int n (int)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; }写这个循环时有三个易错点今天全踩了一遍第一个是while条件里到底用还是。这取决于题目要求的是“第一个大于”还是“第一个不小于”。本题要求严格大于所以用等于的时候不弹出这样才能保证结果是“下一个更大”而不是“下一个大于等于”。第二个是在弹出时取res[st.top()] nums[i]千万别写成res[st.top()] i一旦写错结果数组里面全是下标而不是值。第三个是最后栈里剩下的元素。循环结束后栈里还有元素的话说明它们右边没有更大的值因为结果数组初始化为-1所以这部分不需要额外处理。这是单调栈题目里一个很巧的设计初始值就是兜底答案。3. 核心练习二快速幂与质数判断的优化组合3.1 快速幂原理指数二进制展开第二题是计算a的b次方对mod取模的结果典型的快速幂模板题。很多人第一次接触快速幂时会被它的名字吓到其实原理特别朴素任何一个正整数指数都能写成二进制形式比如10 1010₂所以a^10 a^8 × a^2。我们只需要把指数不断右移同时让底数不断自乘遇到二进制位是1的时候把当前的幂乘进结果里就行。long long fastPow(long long base, long long exp, long long mod) { long long res 1 % mod; base % mod; while (exp 0) { if (exp 1) { res res * base % mod; } base base * base % mod; exp 1; } return res; }这里面两个细节值得展开说。第一个是res 1 % mod。如果mod可能是1初始化为1就有问题因为任何数对1取模都是0。写成1 % mod既安全又不会多花任何成本属于模板里值得保留的好习惯。第二个是每一步都取模。幂运算的结果增长极快a^b很快就会溢出long long所以必须边乘边模。模运算对乘法是相容的(a * b) % mod等于(a % mod) * (b % mod) % mod这是快速幂能正确工作的数学基础。3.2 工程场景大数取模与哈希快速幂不只是竞赛题里的套路工程上也有实际意义。比如哈希函数里经常要计算base^k mod prime字符串哈希的滚动计算本质就是快速幂的变体再比如一些加密算法里的模幂运算虽然实际实现更复杂但基本框架就是这个模板的延伸。我今天练这道题的另一个目的是把它和质数判断串起来——很多题目里“找一个比数据范围大的质数作为模数”是一个常见操作如果对质数分布不敏感容易随手填一个非质数导致哈希碰撞率飙升。3.3 质数判断的6k±1优化判断质数也是高频考点。最粗暴的写法是从2试到sqrt(n)时间复杂度O(√n)大多数场景够用。但今天练习的是优化版所有大于3的质数都满足6k±1的形式。原理是自然数按模6分类能被2整除的、能被3整除的都已经排除了剩下的只能是6k1或6k5也就是6k-1。bool isPrime(int n) { if (n 3) return n 1; if (n % 2 0 || n % 3 0) return false; for (int i 5; i * i n; i 6) { if (n % i 0 || n % (i 2) 0) return false; } return true; }这个优化的实质是把试除范围压缩了近三分之二。循环步长是6每次检查i和i2两个候选值正好覆盖6k-1和6k1。注意两个边界n 3时直接返回n 1这样2和3能正确判为质数1和负数判为合数循环条件是i * i n用乘法而不是sqrt(n)既避免了浮点运算误差又比每次调用sqrt函数快。3.4 实测对比结果我在本地用十万以内的数字做了一轮对比测试简单记录一下数据普通试除法大约需要运行80多毫秒6k±1优化版大约30毫秒出头差距在2.5倍左右。数字越大、测试范围越广这个差距越明显。刷题时不差这几十毫秒但养成“能优化就优化”的习惯到了复杂度敏感的大数据场景就受益了。4. 核心练习三字符串拆分与数组初始化陷阱4.1 字符串数组初始化的几种写法今天第三道练习题是给定一个逗号分隔的字符串比如apple,banana,cherry,date把它拆成一个字符串数组并按原顺序输出。题目本身不难但我在复习时专门把“字符串数组初始化”这个点做了一次横向对比因为这里面的写法太多了而且一不小心就踩坑。// 写法一C风格字符数组 char fruits1[][10] {apple, banana, cherry}; // 写法二string数组 string fruits2[] {apple, banana, cherry}; // 写法三vectorstring vectorstring fruits3 {apple, banana, cherry};第一种写法的坑在于第二维长度。char fruits1[][10]意味着每个字符串最多存9个字符加一个结束符如果初始化的字符串长度超过10编译期不报错但写入时就越界了。这种“编译期不报错、运行时才炸”的行为最恶心。第二种写法没有长度限制是C里最自然的写法。第三种写法更灵活适合不知道元素个数的场景。4.2 把string拆成数组的三种方案回到拆分问题本身主流解法有三种getlinestringstream、findsubstr、以及C语言风格的strtok。我用得最顺手的是stringstream方案#include sstream vectorstring split(const string s, char delim) { vectorstring tokens; stringstream ss(s); string token; while (getline(ss, token, delim)) { if (!token.empty()) tokens.push_back(token); } return tokens; }getline的第三个参数允许指定分隔符这是很多人忽略的用法。默认情况下getline读一整行但加上分隔符参数后它每次读到一个分隔符就返回一段内容。这个方案的优势是代码量小、可读性好缺点是性能一般如果要在超长字符串上高频拆分建议用findsubstr手写循环。另一个值得注意的坑是空字符串。如果输入是apple,,bananagetline会把中间那个空串也读出来所以循环里必须加if (!token.empty())过滤。这个细节我上次没加结果输出结果多了一个空行调试了半天才发现。4.3 字符串字面量修改的坑复习字符串时我还顺手试了一个经典陷阱直接修改字符串字面量。char* p hello; p[0] H; // 未定义行为在C里字符串字面量的类型是const char[]老旧的写法char* p hello是历史遗留虽然部分编译器还接受但运行期修改它属于未定义行为可能直接崩溃。正确写法是把字面量复制到可修改的数组里char p[] hello; p[0] H; // 合法说到底现代C里优先用std::string只有在对接C接口时才需要退回到字符数组。我这个习惯也是最近才彻底改过来的以前总觉得字符数组更“底层、更酷”实际上用std::string不但安全性能在现代编译器优化下也不会差。5. 核心练习四结构体链表与插入排序复习5.1 结构体节点的基本语法今天顺手复习了结构体链表的基础语法。很多教程把链表讲得神乎其神但说到底就是一个结构体加一个指向自己类型的指针struct Node { int val; Node* next; Node(int v) : val(v), next(nullptr) {} };这里有一个新手容易犯的错误定义结构体时用Node* next但结构体类型本身还没定义完为什么可以这样写因为指针本身只占固定大小编译器不需要完整类型定义就能确定指针的布局。这个“不完整类型可以声明指针”的规则同样适用于类的向前声明。链表的操作核心是“改指向”。插入一个节点本质是先把新节点的next指到后一个节点再把前一个节点的next改指向新节点。顺序反了就会丢链这是我在前几天的练习里真正摔过的跤。5.2 手写链表还有没有必要有同学会问STL里明明有list为什么还要手写链表我的观点很直接为了应付笔试必须会手写为了工程开发优先用STL。笔试环境里经常让你“实现一个链表反转”或“在链表中删除指定节点”这时候考官想看的是你对指针操作的理解而不是你会不会调用std::list。但真实项目里手写链表维护成本太高现代C首选还是STL容器。今天复习链表我刻意把插入排序的数组版本改成了链表版本。链表不支持随机访问所以排序时不能用下标直接取值必须通过指针遍历。这个过程让我重新理解了“算法依赖数据结构”这个抽象概念。5.3 插入排序复习边界条件是生命线顺带把插入排序的数组版本也重写了一遍void insertionSort(vectorint arr) { for (int i 1; i (int)arr.size(); i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; --j; } arr[j 1] key; } }这个算法的逻辑一句话就能说清把当前元素插入到前面有序序列的正确位置。真正容易出错的不是思路而是两个边界j 0防止数组越界访问内层循环结束后arr[j 1] key这个赋值位置一定要在循环外面。我见过好几个同学把这个赋值写进循环里结果整个数组被覆盖得一塌糊涂。6. 工欲善其事VSCode配置与运行库那些事6.1 VSCode C/C环境配置要点训练记录写到第82天环境问题遇到的可不少。先说VSCode配置C/C环境这是新手最容易卡住的地方。我的建议是装三个东西C/C扩展插件、Code Runner插件以及一个编译器。编译器在Windows上一般装MinGW-w64直接下载离线包解压把bin目录加进系统PATH就行。VSCode要完成编译运行核心是配置好tasks.json{ version: 2.0.0, tasks: [ { label: build, type: cppbuild, command: g, args: [ -g, ${file}, -o, ${fileDirname}/${fileBasenameNoExtension}.exe ], group: { kind: build, isDefault: true } } ] }这里的-g选项一定要加它表示生成调试信息后面才能用断点调试功能。很多人配置完发现点调试没反应多半就是漏了这一步。6.2 Visual C Redistributable到底解决什么问题这几天训练里有个话题反复出现Visual C Redistributable下载安装。不少新手很迷惑为什么有的软件装上后提示缺少运行库去装这个“Redistributable”就好了把话说白你用C写的Windows程序可能会依赖微软提供的CRTC运行时库和STL实现。这些运行库文件不是随便放的微软把它们打包成了“Visual C Redistributable”分发给用户。你写的程序发布出去目标机器不一定装了这些运行库最简单的解决办法就是让用户先装对应的Redistributable。所以这不是什么“系统垃圾”而是C程序在Windows上的“运行环境”。我今天也遇到一次运行报错弹窗提示VCRUNTIME140.dll找不到装上对应的x64版本运行库后问题立刻解决。这个经验记下来以后发布C工具给别人用时能省很多沟通成本。6.3 fopen安全错误和其他编译警告今天写文件操作代码时g报了一个C4996警告内容是关于fopen的“安全问题”。这是微软系编译器特有的提示它希望开发者用fopen_s这类安全增强版本替代传统函数。在Windows上如果坚持用标准C函数最简单的处理是在源文件头部加上#define _CRT_SECURE_NO_WARNINGS或者对g来说可以忽略这个提示因为它本质上是MSVC的警告g默认不会报。真正要留意的不是这个警告本身而是它背后的逻辑老函数不检查缓冲区边界容易出安全问题。刷题时怎么方便怎么来但写生产代码时还是应该用安全版本或者直接上std::ifstream。7. 今日踩坑记录与排查心得7.1 今天印象最深的三个bug第一个bug出现在单调栈里我把结果数组初始长度写成了n - 1刚好少了一个元素运行时直接越界。排查过程挺蠢的——我一度以为是取模导致数据出错其实是数组越界这种最基础的问题。这提醒我遇到诡异结果先检查数组长度和下标再考虑算法逻辑。第二个bug在字符串拆分输入字符串末尾多了一个逗号getline读到最后一个空串并加入了结果数组导致输出多了一项。这就是我前面说的if (!token.empty())过滤问题加一行判断就解决了。第三个bug是快速幂模板里的一个经典失误exp 1写成了exp 1逻辑瞬间变成死循环。这类低级错误在疲劳状态下特别容易犯我的对策是写完代码后逐行读一遍尤其是位运算和赋值语句。7.2 排查方法论从“打印大法”到断点调试排查这些问题时我用了两套手段。第一套是“打印大法”在关键位置输出中间变量比如单调栈的栈顶元素、拆分过程中的每一个token。这套方法简单粗暴适合快速定位方向。第二套是VSCode断点调试配合launch.json配置好之后可以逐步观察变量变化特别适合排查循环边界问题。我的习惯是先用打印大法判断“哪个阶段出错了”再用断点定位“哪一行出错了”。两套手段配合绝大多数bug都能在十分钟内解决。7.3 给刷题新手的几点建议最后分享几条我自己坚持了82天总结出来的经验。第一不要只追求“AC”而跳过总结每道题做完至少写三句话的笔记考点是什么、我卡在哪一步、下次怎么避免。第二旧题重写比疯狂刷新题重要得多。第三代码风格从第一天就要认真对待——变量命名清晰、缩进统一、注释写“为什么”而不是“是什么”这些习惯到后面会回报你。最后再说一句我个人的体会是刷题这件事最难的不是某道题而是持续不断的自我复盘。第82天训练下来真正留在脑子里的往往不是AC的那一瞬间而是那些报错信息、那些边界条件、那些“原来如此”的顿悟时刻。今天这份记录如果对你有一点用那我这一晚上就没白熬。下次有空的话我准备把“回调函数和函数指针”这块内容好好整理一下那是最近觉得最该补的一块短板。