排了几天队终于把C初级算法课第四课的课后习题全部刷完了。这堂课的主题是数组统计和模拟算法说实话刚拿到题目的时候我还觉得有点简单——数组统计不就是遍历一遍数个数吗模拟算法不就是照着题目描述写代码吗真正动手做下来才发现这两块内容远没有看上去那么人畜无害。数组统计的核心不在会不会数数而在用什么方式数得快、数得准模拟算法的核心也不在看不看得懂题目而在怎么把一段文字规则翻译成无歧义的代码状态机。这篇就把我刷完第四课全部习题后的完整思路、参考代码和踩坑记录整理出来给同样在学C算法基础的朋友一份可以直接参考的作业级攻略。不管你是刚学完循环和数组的新手还是刷题偶尔卡壳的进阶者这篇都值得认真过一遍。1. 课后题不是凑数数组统计与模拟算法各考什么先说个我自己的体会很多人把这两类题当成简单题觉得只要按部就班写就能过。但实际上这两类题是算法能力的两块重要地基——一个是数据组织能力一个是流程抽象能力。1.1 数组统计从暴力遍历到空间换时间数组统计类题目表面上是让你求频次、最大值、最小值、众数、去重数量这些指标。但背后的核心考点是你能不能根据数据范围选择合适的统计手段。拿统计频次来说最原始的做法是对每个元素遍历一遍数组数它出现了几次。这在元素个数很少时没问题一旦数组长度上百上千时间复杂度就变成了O(n^2)明显浪费。初级算法课在这个阶段想教你的其实是计数数组的思路如果元素的值域是已知且有限的小范围比如0到100、0到1000那么我可以直接开一个长度等于值域的数组用下标代表元素值、数组内容代表出现次数的方式一趟遍历完成统计。这种做法的本质是空间换时间。很多新手不理解为什么这样就是更优其实就是把原本需要反复遍历才能得到的信息提前用一块内存固定下来访问时变成O(1)查表。理解了这个点后面学哈希表、桶排序都是同一个套路的延伸。1.2 模拟算法把剧本翻译成代码模拟算法更直接——题目给你一段规则或者一个剧本你只需要按步骤执行通常在最后输出某个状态即可。听起来像翻译工作但真正写出不犯错、不超时、不越界的模拟代码需要具备三个能力状态定义能力清楚程序运行中哪些变量需要维护位置、计数、方向、存活状态等。规则翻译能力把如果碰到墙就反弹这类自然语言改写成if (nx 0 || nx n) 就调整方向这类逻辑表达式。终止条件判断能力很多模拟题不是跑固定步数而是跑直到某个条件成立这个条件写不好就是死循环。在课后题里这两类知识经常组合出现要么在模拟过程中需要统计某些数据的频率要么在统计完之后需要按照规则输出结果。所以第四课把它们编在同一个章节里其实是有教学逻辑的——统计是读数据模拟是演过程两个视角合起来才是完整的算法思维。2. 数组统计真题拆解频次、众数与奇偶重排这一节我们直接进入题目。2.1 统计每个数字的频次计数数组的经典用法题目描述给定一个长度为N1 ≤ N ≤ 10000的整数数组数组元素的值在0到100之间。请统计每个值出现的次数并按值从小到大输出值:次数只输出出现过的值。这道题就是典型的计数数组教学题。值域只有0到100完全不用排序也不用搞什么复杂结构。#include iostream using namespace std; int main() { int n; cin n; int cnt[101] {0}; // 下标0~100初始清零 for (int i 0; i n; i) { int x; cin x; cnt[x]; // 出现一次就加一 } for (int i 0; i 100; i) { if (cnt[i] 0) { cout i : cnt[i] endl; } } return 0; }这段代码有两个细节值得注意。第一int cnt[101] {0}这种写法可以把整个数组初始化为0如果不写 {0}局部数组的值是不确定的后面加出来的结果就是错的。第二遍历输出的时候只输出cnt[i] 0的避免输出一堆0:0干扰结果。时间复杂度是O(N 101)其中O(N)是输入统计的时间O(101)是扫计数数组的时间。这比O(N^2)朴素做法快得多而且代码同样简单。2.2 找众数多版本实现与选择题目描述给定一个长度为N1 ≤ N ≤ 1000的整数数组元素在0到10000之间。输出出现次数最多的数如果多个数出现次数相同输出其中最小的那个。这道题值域变成了0到10000直接开10001个int的数组依然没问题。关键在于多个众数时输出最小这个条件。#include iostream using namespace std; int cnt[10001]; // 全局数组默认全0 int main() { int n; cin n; int maxCnt 0, ans 0; for (int i 0; i n; i) { int x; cin x; cnt[x]; if (cnt[x] maxCnt) { maxCnt cnt[x]; ans x; } else if (cnt[x] maxCnt x ans) { ans x; } } cout ans maxCnt endl; return 0; }这里有个小技巧由于我们按输入顺序实时更新答案所以当出现次数追平当前最大值时不能直接替换答案只有在当前元素的值比已有答案更小的情况下才替换。这样最后得到的ans就是满足条件的答案。如果值域再大一些比如元素可以到10^9计数数组就不好开了。这时候有两个替代方案一是先排序再扫一遍相同的数会聚在一起统计相邻连续段长度二是用std::map或std::unordered_map做哈希统计。在初级课阶段我建议先把计数数组练熟因为哈希表的实现细节更多等后面学了哈希再回过头来优化也不迟。2.3 奇偶重排一趟扫描与稳定性的取舍题目描述给定一个长度为N的整数数组把所有的奇数移到前半部分偶数移到后半部分。要求不用额外数组且时间复杂度尽量低。这道题常见解法是双指针左指针找偶数右指针找奇数找到就交换。但这会导致一个问题——交换后奇数和偶数的相对顺序会被打乱。题目没有明确要求稳定所以可以用。#include iostream #include vector using namespace std; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; int left 0, right n - 1; while (left right) { while (left right a[left] % 2 ! 0) left; // 左指针停在偶数 while (left right a[right] % 2 0) right--; // 右指针停在奇数 if (left right) { swap(a[left], a[right]); } } for (int i 0; i n; i) cout a[i] ; return 0; }如果题目要求保持原来的相对顺序稳定双指针就不行了。这时候可以借助std::stable_partition不过我更推荐手写一个零入数组的思路用一个额外vector存结果第一趟放奇数第二趟放偶数。初级阶段的题目一般不强求稳定但你要能一眼判断出哪种方案满足哪种约束。3. 只用四步模拟题也可以拆得干干净净模拟算法题看起来五花八门但我刷了这课的题目后总结出一个通用框架屡试不爽。3.1 四步法拆题、定状态、演规则、查边界第一步拆题。把题目描述里的每个动作用横线列出来比如初始有n个物体→每一轮做某个操作→操作后更新某些数值→当满足某条件时停止。这一步是为了避免看漏规则。第二步定状态。明确程序里要维护哪些变量。比如模拟一个棋子在棋盘上移动至少需要当前横坐标、当前纵坐标、已走步数、棋盘边长、障碍物集合。第三步演规则。把每个动作翻译成代码。动作1可能对应一个for循环动作2可能对应一个if-else分支规则里的同时直到往往对应不同的控制结构。第四步查边界。模拟题60%的错误发生在边界上数组越界、步数没走完、初始状态漏处理。3.2 案例实战开关灯问题题目描述有n盏灯编号1到n初始全部熄灭。第1轮按下编号为1的倍数的灯的开关第2轮按下编号为2的倍数的灯的开关……第n轮按下编号为n的倍数的灯的开关。问最后亮着的是哪几盏灯。教科书标准做法是开一个布尔数组模拟每轮操作#include iostream #include vector using namespace std; int main() { int n; cin n; vectorbool on(n 1, false); // 下标1~n初始全灭 for (int round 1; round n; round) { for (int j round; j n; j round) { on[j] !on[j]; // 切换开关 } } for (int i 1; i n; i) { if (on[i]) cout i ; } return 0; }这个做法的复杂度是O(n log n)因为内层循环的次数总和是n/1 n/2 ... n/n调和级数约等于n ln n。对于n100000来说完全可以接受。但刷完这题我再想了一下其实开关灯问题有一个数论解法一盏灯最后是亮是灭取决于它的因子个数。因子个数为奇数说明被按了奇数次亮着因子个数为偶数灭着。而完全平方数的因子个数是奇数——所以答案就是1到n之间的所有完全平方数。这个从模拟到数学规律的思维恰恰是刷模拟题最有价值的收获先确认模拟能跑出正确结果再反推有没有更优雅的模型。4. 两道经典综合模拟题的完整推演刷完基础题之后还有两道稍微综合的题目让我卡了一段时间这里完整复盘一下。4.1 约瑟夫问题用模拟建立直觉题目描述n个人围成一圈从第1个人开始报数报到m的人出列然后从下一个人重新开始报数问最后剩下的人的编号。这是模拟算法的入门必做题图论里叫约瑟夫环。第一直觉是用链表做但初级课我们还没学链表所以常用的方法是vector模拟圆圈出列的人标记为-1报数时跳过-1。#include iostream #include vector using namespace std; int main() { int n, m; cin n m; vectorint people(n); for (int i 0; i n; i) people[i] i 1; int idx 0; // 当前报数起点 int remaining n; while (remaining 1) { int step (m - 1) % remaining; // 从当前点走m-1步到达出列位置 idx (idx step) % remaining; people.erase(people.begin() idx); // 删除出列者 remaining--; // idx已经指向删除后下一个人的位置 } cout people[0] endl; return 0; }这里一个关键点是step (m - 1) % remaining。因为当前idx处已经算一个人报数报到m的人实际上是从idx再走m-1步。取模% remaining是防止m大于当前存活人数时多绕圈。代码很简洁但在线删除vector元素是O(n)的所以整体复杂度O(n^2)对于n10000都吃力。n如果到了10^5就需要用树状数组或者推导数学公式著名的约瑟夫递推式f(1)0f(i)(f(i-1)m)%i。我建议初学者先把模拟版写对再考虑数学优化不然很容易优化了个寂寞。4.2 小游戏角色移动模拟把规则写成代码题目描述给定一个n行m列的网格有些格子是障碍物。一个角色从(1,1)出发按照一串指令移动指令由字符U、D、L、R组成分别表示上、下、左、右移动一格。每次移动前先判断目标位置是否越界或是障碍物如果是则停留在原地否则移动。请输出执行完所有指令后的坐标。这道题和热门搜索里那些C小游戏代码如何用C做小游戏的需求关系密切——角色移动是所有小游戏最基础的逻辑。#include iostream #include string #include vector using namespace std; int main() { int n, m; string cmds; vectorvectorint grid; // 0空地 1障碍 // 输入省略假设grid已经读入 int x 1, y 1; // 当前坐标1-based int dx[4] {-1, 1, 0, 0}; // U D int dy[4] {0, 0, -1, 1}; // 对应L R 需要映射 for (char c : cmds) { int nx x, ny y; if (c U) { nx x - 1; } else if (c D) { nx x 1; } else if (c L) { ny y - 1; } else if (c R) { ny y 1; } // 边界检查 障碍物检查 if (nx 1 nx n ny 1 ny m grid[nx][ny] 0) { x nx; y ny; } } cout x y endl; return 0; }我比较建议用方向数组dx/dy而不是一堆if嵌套因为一旦指令种类从4个变成8个加上斜向移动方向数组的优势就很明显。这也是后面写BFS迷宫搜索时的基础。实际写完这道题后我又顺手把障碍物改成了可破坏的类型加了生命值和背包数组整个就变成了一个简化版小游戏的逻辑框架。所以这套课后题对于想做C小游戏的同学来说其实是很好的起步练习。5. 交题被拒的现场还原边界条件排查实录刷题最花时间的往往不是写代码而是调试。我自己交这课作业时就被三个错误反复折磨一个个排查过来给大家当反面教材。5.1 数组越界1/-1的魔咒有一道数组统计题要求比较相邻元素我写出了这样的循环for (int i 0; i n; i) { if (a[i] a[i 1]) cnt; }当i n-1时a[i1]越界访问。有些编译器不报错但读出来的是随机值导致结果时而对时而错。排查方法很简单当你怀疑越界把i1这类表达式的取值范围在纸上列出来——i最大是n-1那么i1最大是n数组下标不能等于n。我的习惯是只要涉及i1循环条件就写成i n - 1涉及i-1循环条件就写成i 0。这个习惯帮我避免了一大半越界错误。5.2 计数数组未初始化局部数组 vs 全局数组有一道题我第一次交上去答案错误排查半天发现是计数数组定义在main函数内部int main() { int cnt[1000]; // 局部数组未初始化 ... }局部数组如果不显式初始化里面的值是随机的历史栈内存数据可能是0也可能不是0。这样直接cnt[x]结果当然是错的。解决办法有两个。一种是把数组定义到全局区全局数组默认初始化为0int cnt[1000]; // 全局自动全0 int main() { ... }另一种是在局部定义时显式初始化int cnt[1000] {0}; // 显式清零如果你用的是vector那更简单vectorint cnt(1000, 0)。我个人的经验是竞赛和做题时尽量用全局数组少踩初始化的坑也方便调试。5.3 模拟死循环缺少步数或状态上限还有一道模拟题要求一直移动直到回到起点我在while循环里写的是while (x ! startX || y ! startY) { // 更新位置 }乍一看没问题但有一种情况会导致死循环角色移动方式存在陷阱可能永远回不到起点。原因在于我没有给循环设置步数上限。模拟题的通用防御性写法是int maxSteps n * m * 4 10; // 根据状态空间估计 int step 0; while ( (x ! startX || y ! startY) step maxSteps) { // 更新位置 step; } if (step maxSteps) { // 此时可以判定循环不可能终止或者需要输出不可能 }这里的maxSteps根据题目的状态空间估一个上限就好。比如角色在nm网格里状态最多也就nm种再乘以可能的剩余指令变化。加这一步之后即使题目里的规则有问题也不会让程序卡死。5.4 完整排查链路从错误答案到定位根因最后分享一个完整的排查过程。有一道频次统计题我的输出总是漏掉最后一个值。我没有直接改代码而是按这个步骤走先打印关键变量在统计循环结束后打印n确认输入正确。打印cnt数组前10个值发现cnt[0]不对偏小1。怀疑输入没读全检查发现循环条件是i n导致多读了一个无效值后面处理错位。修正为i n后输出恢复正常。很多新手遇到答案错误就上网搜答案其实这是效率最低的方式。最有效的办法是先打印中间结果看看数据在哪个环节发生变化。在代码里临时加cout ...不需要担心污染代码调完再删就行。这是排查一切算法题的通用基本功。6. 从课后题看下一站这些能力可以往哪用课刷完了作业交完了但这两类能力的扩展方向还是值得说清楚。6.1 数组统计的场景升级计数数组的缺陷很明显值域一大就爆内存。所以当数据范围从0到100变成0到10^9时下一步就要学unordered_map做哈希统计。另外如果题目要求的是连续区间内的统计比如滑动窗口最大值、窗口内不同元素个数那么计数数组配合窗口移动加左边减右边就是非常高效的做法这也是后面滑动窗口题目的雏形。6.2 模拟算法的场景升级模拟算法本身看似笨拙但几乎所有复杂算法都包含模拟的思维。搜索算法DFS/BFS本质上就是在模拟一个状态空间的遍历过程动态规划是在模拟所有决策路径并选最优。现在刷的这几道模拟题其实是在训练你把自然语言描述的状态迁移翻译成代码的能力这个能力在以后做复杂项目时一样管用。比如想写一个最简单的扫雷游戏需要模拟每一步翻开格子后的状态更新想写一个回合制战斗小游戏需要模拟角色血量和技能冷却时间的逐帧变化。这些和今天做的开关灯问题、角色移动问题本质是一样的——只不过把数组换成了结构体把简单规则换成了复杂规则。我自己学这课最大的感受是不要把课后题当成任务而是当成一块块积木。这课练的数组统计是各种数据结构的基础操作模拟算法是逻辑抽象的基础功两者叠加起来已经足够支撑你写一个不大不小的小游戏或小型工具了。如果你也是刚学C不久建议把这课所有题目都亲手敲一遍代码不要直接抄答案敲完后再想一想每个循环的边界条件是怎么推出来的——想通了这课就真正过关了。