第79天说实话能坚持到这个数字我自己都有点意外。今天的课后习题训练量不算大但内容很杂从最基础的冒泡排序优化到不太常碰的卢卡斯定理从指针和引用的区别到vscode突然罢工的跳转问题中间还穿插了字符串数组初始化和结构体链表的复查。如果你也在用vscode刷C或者正在算法题和语法细节之间来回切换那这份记录里应该有不少能对上号的东西。我尽量把今天实际写的代码、踩进去又爬出来的坑、以及事后复盘才想明白的“为什么”原原本本留在下面。1. 第79天训练的整体规划不是题海是查漏补缺1.1 今天为什么选这些题目坚持到第79天我发现自己遇到的最大障碍不是题目难而是“东一榔头西一棒子”。如果今天看到什么热词就刷什么第二天很容易忘得一干二净。所以大概两周前我给自己定了个规矩每次训练只围绕三个模块展开——算法基本功、语言细节、工程环境。今天的算法部分选了冒泡排序、前缀和、单调栈、快速幂外加一道要求用卢卡斯定理的模板题。语言细节部分复习了引用、指针、STL容器初始化、字符串转数组还有结构体链表。工程环境部分则花了不少时间处理vscode的C/C跳转失效和fopen报C4996安全警告。这套配比看起来很散但其实每一块都对应着我这几天暴露出的弱点比如取模运算总是写错顺序比如字符数组的结尾到底要不要动。选完之后我还在本子上写了一句提示“如果写完代码讲不出为什么那就不算真正掌握。”所以下面的内容基本也是按这个句式来整理的——先讲是什么再讲为什么。1.2 训练节奏先写框架再调细节以前我刷题喜欢立刻打开编辑器边写边想结果经常写着写着发现思路错了又从头来。今天换了个节奏先在纸上把函数签名、关键循环、边界条件列出来再动手敲。比如冒泡排序这道题我在纸上写的是外层循环 n-1 趟 内层循环 n-1-i 次 如果相邻逆序就交换 记录是否发生过交换提前退出等把这几行写清楚代码基本不费脑子就能填出来。这个习惯对今天的广度优先搜索模板也有帮助——虽然今天没有完整实现BFS但我在复习广搜模板时同样先把队列、visited数组、方向数组四个要素列出来再对照之前的代码补注释。2. 今日算法题的代码复盘四个考点四个坑2.1 冒泡排序加一个标志位最坏情况变最好情况冒泡排序确实是入门算法但写对的人没想象中多。我今天的第一个版本就漏了提前退出跑起来虽然能过样例但用一个几乎有序的数组去测发现没有任何优化白白扫描了很多趟。正确写法是在内层循环结束后判断如果一整趟都没有发生交换说明已经有序直接break。#include vector #include algorithm void bubbleSort(std::vectorint arr) { int n static_castint(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]) { std::swap(arr[j], arr[j 1]); swapped true; } } if (!swapped) break; } }如果不加这个标志位最好情况和最坏情况都是O(n²)加了之后最好情况变成O(n)。这道题给我的提醒是即使是“入门算法”也要问自己一句“最坏情况、最好情况分别是什么”。很多人用内层循环每轮都扫到 n-1-i但其实一旦提前有序后面全是无效比较。2.2 前缀和一维和二维的边界问题必须用下标从1开始前缀和是那种“学会了就很爽”的技巧。今天复习一维前缀和时我盯着代码检查了半天发现如果数组下标从0开始查询区间[0, r]会需要特判r等于0的情况。后来我统一把所有练习代码改成下标从1开始也就是把原始数据读进a[1]到a[n]前缀和数组pre[i]表示前i个元素的和std::vectorlong long a(n 1), pre(n 1, 0); for (int i 1; i n; i) { std::cin a[i]; pre[i] pre[i - 1] a[i]; } // 查询 [l, r] // answer pre[r] - pre[l - 1]二维前缀和也是同样的道理。递推式是// sum[i][j] sum[i-1][j] sum[i][j-1] - sum[i-1][j-1] a[i][j] // 查询子矩阵(x1, y1)到(x2, y2) // sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] sum[x1-1][y1-1]这里最隐蔽的坑是“容斥原理”的符号加两个相邻前缀和之后重叠部分被加了两遍所以要减去一个。如果直接用这个式子跑一组随机数能对上就记住对不上多半是减号多写了一个。我今天的做法是写了一个暴力二维循环去对拍随机数据这种方法在初学阶段非常管用。2.3 单调栈从“每日温度”看栈的单调性今天的单调栈题目是经典的“每日温度”给一个数组要求找出每个元素右边第一个比它大的元素距离它多远。如果两层循环O(n²)也能做但数据量一大就超时。单调栈的思路是维护一个从栈底到栈顶“递减”的序列当前元素如果比栈顶大说明栈顶元素找到了右边第一个更大的值。#include vector #include stack std::vectorint dailyTemperatures(const std::vectorint temperatures) { int n static_castint(temperatures.size()); std::vectorint ans(n, 0); std::stackint st; for (int i 0; i n; i) { while (!st.empty() temperatures[i] temperatures[st.top()]) { int idx st.top(); st.pop(); ans[idx] i - idx; } st.push(i); } return ans; }我刚开始不理解为什么要在栈里存下标而不是值。后来想明白了栈里存下标才能算“距离”如果只存值右边第一个更大元素的下标差就算不出来。这个细节和“单调栈存什么”直接相关建议新手在纸上模拟几遍比背模板有用得多。2.4 快速幂、质数判断与卢卡斯定理的取模细节今天的重头戏是快速幂和卢卡斯定理。快速幂我虽然写了不知道多少遍今天还是因为忘记取模导致溢出。代码本身不复杂long long quickPow(long long a, long long b, long long mod) { long long res 1 % mod; while (b 0) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; }注意两个细节一是res的初始值当mod为1时必须写成res 1 % mod否则结果永远是1但实际应该是0二是在循环里务必将a和res每次都取模因为a在平方过程中可能迅速超过long long的范围。质数判断优化我今天顺便写了一遍“6k±1”的试除法。大于2和3的质数必然是6的倍数两侧的数字所以循环可以每次增加6从而减少取模次数。bool isPrime(long long n) { if (n 1) return false; if (n 3) return true; if (n % 2 0 || n % 3 0) return false; for (long long i 5; i * i n; i 6) { if (n % i 0 || n % (i 2) 0) return false; } return true; }卢卡斯定理解决的是大组合数取模问题在模数为质数、n和m很大时特别实用。今天为了理解它的C写法我先写了一个基于费马小定理求逆元的组合数函数再套上递归。核心代码是这样的const int MOD 100000; long long fact[MOD], invFact[MOD]; long long modPow(long long a, long long b, long long mod) { long long res 1; while (b 0) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; } void initFact(int p) { fact[0] 1; for (int i 1; i p; i) fact[i] fact[i - 1] * i % p; invFact[p - 1] modPow(fact[p - 1], p - 2, p); for (int i p - 2; i 0; --i) invFact[i] invFact[i 1] * (i 1) % p; } long long combSmall(long long n, long long m, long long p) { if (m n) return 0; return fact[n] * invFact[m] % p * invFact[n - m] % p; } long long lucas(long long n, long long m, long long p) { if (m 0) return 1; return combSmall(n % p, m % p, p) * lucas(n / p, m / p, p) % p; }我今天在这里踩了一个很蠢的坑忘记初始化fact[0] 1导致组合数对所有m0的情况全算成0。排查了十分钟才发现是初始化顺序的问题。这提醒我凡是涉及阶乘的主题先写一个小的主函数测试C(0,0)、C(1,1)这些边界用例。3. 语言细节复盘这些“基础”藏了不少坑3.1 引用、指针和值传递我建议你画一张内存图这个知识点几乎每次面试都会被问学C的人绕不开。今天把三个传递方式写成代码对比一眼就能看出区别void swapByValue(int a, int b) { int temp a; a b; b temp; } void swapByPointer(int* a, int* b) { int temp *a; *a *b; *b temp; } void swapByReference(int a, int b) { int temp a; a b; b temp; }用值传递时函数拿到的是实参的副本怎么改都不会影响调用方指针传递时函数拿到的是实参地址的副本但通过这个地址可以间接修改实参引用传递则是给实参起了一个别名函数内操作的就是实参本身。从安全性看引用比指针更直观不会出现空指针问题从灵活性看指针可以做指针运算也能指向空代价是必须自己检查合法性。我建议画一张简单的内存图三个格子代表a、b原始值三个小框代表函数参数。值传递会新开两块内存指针传递也新开两块内存但存的是地址引用传递不开新内存。画完就明白“为什么C里推荐优先用引用”。3.2 字符串数组初始化与字符串转数组今天在C字符串数组初始化上花了不少时间。题目本身是让我把字符串转换成字符数组再逐位处理结果我纠结起“char数组到底要不要手动加\0”这件事。char str1[] hello; // 自动加\0占6字节 char str2[6] hello; // 合法最后一个位置放\0 char str3[5] hello; // 不安全没有位置放\0可能越界用std::string转换时常用的方法是std::string s hello; const char* p s.c_str(); // 只读访问 std::vectorchar buf(s.begin(), s.end()); buf.push_back(\0); // 如果需要以\0结尾另外要注意sizeof和strlen的区别。对字符数组来说sizeof返回数组占用的总字节数strlen只统计到\0之前的字符数。今天我用strcpy_s的时候目标数组长度如果比字符串长度小会直接报错。如果不是练习用的玩具代码我建议在真实项目里优先用std::string和std::vectorchar避免手工管理字符数组的结尾。3.3 STL容器与排序比较器dict和map的使用建议std::vector、std::stack、std::set这些容器今天都用到了。STL的坑往往不在“会不会用”而在“用的时候有没有想清楚底层行为”。比如vector的reserve和resize很多人混着用。reserve只预留容量不改变sizeresize改变size新元素默认初始化。如果我要写一个固定大小的数组常用后面这个如果要实现动态插入才用reserve配合push_back。std::sort是今天的一个隐藏考点。它的比较器必须满足“严格弱序”意思是如果a b为true那么b a必须为false。如果比较器写成一个或可能导致未定义行为轻则排序结果诡异重则程序崩溃。我见过同学写成std::sort(v.begin(), v.end(), [](int a, int b) { return a b; });这绝对是不行的。正确写法是只返回a b。STL的很多实现依靠严格弱序来避免访问越界写会把相等的元素当成“需要交换”结果不可预测。3.4 结构体链表基本语法别把next写在结构体内部的值类型上今天复习结构体链表时发现自己以前在定义链表节点时写错过一个关键地方在结构体内部直接写Node next;而不是Node* next;。这里的问题在于结构体里如果包含非指针的自身类型就会造成无限递归连字节数都算不出来。struct Node { int data; Node* next; // 必须是指针不能是 Node next; Node(int value) : data(value), next(nullptr) {} };今天练的是头插法代码比较简洁#include iostream struct Node { int data; Node* next; Node(int value) : data(value), next(nullptr) {} }; Node* insertHead(Node* head, int value) { Node* newNode new Node(value); newNode-next head; return newNode; } void printList(Node* head) { while (head) { std::cout head-data ; head head-next; } std::cout \n; }这里必须说清楚用new分配出来的节点是放在堆上的函数返回后不会自动销毁。如果学完链表后没有delete内存会一直泄漏。我现在做小题时会专门写一个clearList遍历链表释放所有节点再把头指针置空。很多刷题教程不关心这一点但工程上这是基本功。4. 今天额外处理的两个环境问题vscode跳转失效与C49964.1 vscode里函数和变量全部无法跳转从现象到解决晚上准备复现代码时vscode突然出现了诡异现象所有C函数、变量都无法跳转鼠标悬停也不显示类型信息。我第一反应是插件崩了重启vscode之后依然无效。后来排查发现这个问题多半出在C/C插件的浏览数据库配置上。简单说IntelliSense需要知道三个信息编译器路径、头文件路径、C标准。当这三个信息对不上很多符号就会变成“未知”跳转自然失效。我的修复办法分三步第一步打开命令面板搜索C/C: Reset IntelliSense Database重置插件缓存。很多时候能直接救回来。如果不行进入第二步检查.vscode/c_cpp_properties.json是否存在以及内容是否正确{ configurations: [ { name: Win64, includePath: [ ${workspaceFolder}/**, C:/msys64/ucrt64/include ], defines: [], compilerPath: C:/msys64/ucrt64/bin/g.exe, cStandard: c17, cppStandard: c17, intelliSenseMode: windows-gcc-x64 } ], version: 4 }这个文件里最关键的是compilerPath和includePath。如果我用的是MinGW-w64编译器路径就必须指向真正的g.exe如果Path环境变量里没有IntelliSense完全找不到标准头文件。第三步是确认当前文件的语言模式如果右下角显示的不是“C”也会无法正常跳转。处理完这三个点函数和变量跳转都恢复了。说实话这类问题在vscode配置C/C环境里非常常见尤其是刚装完插件、还没有创建工作区文件夹的朋友。建议每次新建项目时都复制一份基础的c_cpp_properties.json到.vscode目录省得以后反复踩坑。4.2 fopen报C4996三种处理方式分别用在哪里今天用freopen重定向标准输入vscode的终端直接给我刷了一排警告大意是提示fopen系列函数不安全建议用fopen_s替代。这个C4996警告在Windows下特别多。我试过三种解法它们的适用场景不太一样。第一种最推荐在工程代码里使用用std::ifstream和std::ofstream代替C标准库的fopen。C流对象不需要手动管理空字符结尾而且类型安全更好。#include fstream #include iostream int main() { std::ifstream fin(input.txt); if (!fin) { std::cerr open failed\n; return 1; } int x; while (fin x) { std::cout x ; } return 0; }第二种在刷题环境里如果你确实想用freopen也可以直接关闭这条安全警告。最省事的是在源文件顶部写一行宏定义#define _CRT_SECURE_NO_WARNINGS注意这个宏必须在所有头文件之前否则无效。第三种如果必须调用C接口就用微软提供的新版本fopen_sFILE* fp nullptr; errno_t err fopen_s(fp, input.txt, r); if (err ! 0) { /* 处理错误 */ }fopen_s更安全因为它强制接收一个错误码并且不允许空指针。但我个人还是更倾向于用std::ifstream因为它不用记FILE*的生命周期也更符合C的编程习惯。4.3 Visual C Redistributable与C/C构建的关系聊到运行库今天在群里看到有人问“我用vscode写C为什么在别人电脑上跑不起来”最后发现是缺少Visual C Redistributable。这里面的逻辑是vscode本身不编译你的代码它只是调用编译器如果你用的是MSVC或者项目里动态链接了MSVC运行时那么在未安装对应版本运行库的机器上启动程序时会提示缺少VCRUNTIME140.dll之类的东西。解决办法很简单装一个对应架构和版本的运行时或者让编译器把运行时静态链接进可执行文件。如果你用的是g且想彻底避免运行时依赖可以在链接时加上-static把libstdc和libgcc也静态包含进来。今天我在vscode里配置了构建任务用g -stdc17 -Wall -Wextra main.cpp -o main并没有刻意处理这个问题但理解了这个机制后至少不会再对着“找不到运行库”的弹窗发懵。5. 课后延伸把今天学到的东西用到实际场景里5.1 回调函数函数指针和std::function怎么选训练中提到的“C回调函数例子”虽然不在题单里但我今天顺带复习了一下。回调的核心是把一个函数当作参数传给另一个函数由后者在合适时机调用。最简单的写法是函数指针#include iostream void onFinish() { std::cout task finished\n; } void runTask(void (*callback)()) { // 模拟任务执行 std::cout running...\n; callback(); } int main() { runTask(onFinish); return 0; }如果回调需要捕获上下文状态普通函数指针就不够了。此时可以用std::function加lambda表达式#include functional #include iostream void runTask(const std::functionvoid() callback) { std::cout running...\n; callback(); } int main() { int value 42; runTask([value]() { std::cout value value \n; }); return 0; }从工程角度看std::function的灵活性更高但它比裸函数指针多一点开销。在性能敏感的循环里用函数指针可能更高效在业务逻辑层优先用std::function封装回调代码更清晰。5.2 用TDengine的taos_stmt_prepare做参数化写入今天热搜里有TDengine的C绑定写入我正好也想聊聊这个方向。TDengine是一个时序数据库它的C/C接口支持预编译语句写入。简单来说taos_stmt_prepare和MySQL的prepare很像先写一条带占位符的SQL再通过绑定参数填充具体值减少重复解析SQL的开销。按照常见实践流程大致是先taos_stmt_init获得语句句柄再用taos_stmt_prepare准备插入语句然后逐个绑定参数最后调用taos_stmt_execute执行。如果你正在做设备数据采集那么这套接口比拼SQL字符串更安全也能避免数值转字符串带来的格式问题。不过我今天在本地没有连接TDengine实例只能做个思路记录等真正跑通后再单独写篇更详细的。5.3 C小游戏和魔方还原算法不是白学的很多人刷完题会问这些算法除了应付考试还能干嘛其实冒泡排序和快速排序可以用于小游戏的排行榜BFS可以用于格子类游戏的寻路结构体链表天然适合音乐播放器的播放列表。至于魔方还原那更是一个综合项目至少会用到深度搜索、状态压缩和双向广搜这些技巧。我今天的课后延伸内容里有一项是“C小游戏”我打算从命令行版的打砖块开始先把碰撞检测用到的二维数组和运算符重载搞明白再考虑图形库。这才是“把训练写进项目”的正循环。今天训练到这里我最大的体会是C的核心不是背语法而是理解每个特性为什么存在。冒泡排序的提前退出、前缀和的下标偏移、引用的别名语义、vscode的配置路径这些单独看都很零碎但拼在一起才组成一个能独立解决问题的程序员。明天我计划把广搜模板改成带路径输出的版本再复盘一遍单调栈在“矩形最大面积”里的变体。训练记录的意义就是让每一次努力都留下可追踪的轨迹。
