企业官网建设流程全解析

简介：面向北京理工大学大二数据结构课程乐学平台的编程题汇编，收录了约瑟夫问题、验证表、循环小数、多项式运算、括号匹配、二叉树、排序查找、图的遍历等典型题目解答，适合正在学习数据结构的高校学生对照练习与考前复习。压缩包共29个文件，全部为cpp源程序，整体大小约25KB，每个题目独立成文件，文件名对应题号与题目简称，便于按章节检索。内容覆盖线性表、栈与队列、树、图、查找与排序等核心模块，既有基础验证类代码，也包括表达式求值、哈夫曼树、平衡二叉树、快速排序、关键路径、迷宫问题等进阶算法实现。已有2968人浏览学习，代码结构清晰、命名规范，可作为理解算法流程和调试思路的参考资料。通过研读这些实现，读者能快速掌握复杂数据结构的操作逻辑，获得常用算法模板。 大二上学期那阵子，北理工的乐学平台上堆了一串数据结构编程题，别的题还好说，偏偏约瑟夫问题、验证表、循环小数这几个名字看起来八竿子打不着，却一个比一个折腾人。最离谱的是那道"综教楼后的坑"，当时整个宿舍都在猜这题到底想让我们干嘛。后来把这几道题彻底吃透我才反应过来，它们表面上是四个独立题目，骨子里全在考同一件事：怎么用合适的数据结构，把现实问题翻译成计算机能算的模型。

这篇文章我不打算直接贴完整答案，那对学习没什么帮助。我会把每道题的完整思考链路、核心代码片段、以及我在乐学平台上反复提交失败后总结出的边界条件，全部拆开讲清楚。不管你是正在被这几道题折磨的学弟学妹，还是单纯想巩固数据结构基础的朋友，这篇都能给你点实在的东西。

1. 约瑟夫问题：从"老实模拟"到"小学数学"的进化

1.1 三种解法的复杂度对比

约瑟夫问题描述起来很简单：n个人围成一圈，从第k个人开始报数，报到m的人出列，然后从下一个人重新报数，直到所有人都出列。但"简单"和"高效"之间隔着一条鸿沟。

我第一次做这题，脑子里的第一反应就是直接照着题意模拟，写了个循环链表，每次数到m就删节点。这么做最符合直觉，人围成圈对应循环链表，出列对应删除节点，代码写起来也顺手。问题是当n和m都很大的时候，比如n=100000、m=99999，每删除一个人就要遍历m个节点，总复杂度是O(n*m)，跑起来慢得让人绝望。

第二种思路是用数组模拟，核心是用取模运算实现"循环"效果：

int idx = 0; // 假设从0开始报数 for (int i = n; i >= 1; i--) { idx = (idx + m - 1) % i; printf("%d ", arr[idx]); // 将arr[idx]之后的元素整体前移，覆盖掉出列者 for (int j = idx; j < i - 1; j++) { arr[j] = arr[j + 1]; } }

数组方案在删除元素时需要O(n)的搬移，整体复杂度还是偏高。但如果题目要求输出完整的出列序列，那数组模拟反而是最稳的选择，因为数学优化方案只能算出最后幸存者，算不出中间过程。

1.2 递推公式的推导与实现

如果题目只问"最后剩下的是几号"，那这题就从一个链表模拟题变成了一个纯数学题。核心思路是反推：假设我知道了n-1个人的约瑟夫问题中幸存者的编号，我能不能算出n个人的情况？

关键在编号映射。n个人报数时，第一个出列的人是第m%n个（从0开始编号就是(m-1)%n）。这个人出列后，剩下的人重新组成一个n-1规模的约瑟夫环，但所有人的编号都相对于原来偏移了m位。所以反推公式就是：

f[1] = 0 f[i] = (f[i-1] + m) % i

这个递推式里的f[i]表示"i个人报数，最后幸存者在这i个人中的编号（从0开始）"。最终答案如果是要求1-based编号，输出f[n]+1就行。

为什么这么算是对的？你可以这样理解：每次有一个人出列后，圈子的起点发生了变化，但"相对位置"的规律是不变的。"幸存者在n-1人圈里的位置"加上m个人之后的位置偏移，再对n取模，就得到了他在n人圈里的实际位置。这个思路很像数学里的数学归纳法，知道了小规模问题的解，就能一步步推大规模问题的解，时间复杂度只有O(n)。

1.3 我在乐学平台上踩过的边界条件坑

这题代码量不大，但能让你白白WA好几次的细节多得离谱。我自己就栽在三个地方：

第一个坑是编号起点。题目如果告诉你"第1个人开始报数"，你在递推时要把所有编号减1处理，因为递推公式是基于0编号的。算完f[n]之后记得加1还原。

第二个坑是m比n大的情况。比如n=5、m=8，很多人写模拟时会纠结"还没数完一圈人就没了怎么办"。其实无论是模拟还是递推，取模运算已经天然处理了这个问题，(m-1)%n就是第一个出列的人，重复报数再多轮也是一样的效果。

第三个坑最隐蔽：递推公式的第一项f[1]到底是0还是1。如果你从0开始编号，f[1] = 0，因为一个人的时候他自己就是幸存者。如果你顺手从1开始编号，想当然地设f[1] = 1，那后面每一步算出来都是错的，而且错得很均匀——每个f[i]都差1，导致最终答案恰好差1。检查半天才看出来。

提示：最好在做题前就统一好编号约定，代码里注释注明"本函数内所有编号均为0-based，输出时+1"，能省掉大量调试时间。

2. 验证表：用栈给数据"验明正身"

2.1 我理解的"验证表"在考什么

"验证表"这个名字看起来有点抽象，我当时在乐学平台上看到题目的第一反应是"验证什么表？"后来仔细一想，这题本质上考的是栈的应用——给定一个序列或者一组操作，让你验证它是否满足某种结构约束。数据结构课里"栈"这一章最重要的应用场景，恰恰就是这类"结构合法性验证"。

在这类题目中，"表"可以是一个括号序列，可以是一个出栈序列，甚至可以是某种表达式的符号表。题目会给你一段输入，让你判断它是否合法。之所以这类题必考栈，是因为栈天然具有"后进先出"的约束，而很多结构规则恰好也是这种嵌套式的约束。用栈来处理，每一步操作都对应着"压入"或"弹出"，逻辑清晰，代码也不会太复杂。

2.2 括号匹配：最常见的验证场景

如果题目给你一串由()[]{}组成的括号序列，让你判断是否匹配，那标准做法大家应该都熟：左括号入栈，右括号与栈顶比对，能匹配就弹出，不能匹配直接判错。

但多类型括号嵌套时有个经典大坑：交叉匹配。比如输入[(])，如果你只检查"左右括号成对出现"，这串会通过检查，但它实际上是不合法的，因为[还没闭合，(就出现了。正确做法是遇到右括号时，必须严格检查栈顶元素是否是对应的左括号。

bool isValid(char* s) { int len = strlen(s); char stack[len]; int top = -1; for (int i = 0; i < len; i++) { if (s[i] == '(' || s[i] == '[' || s[i] == '{') { stack[++top] = s[i]; } else { // 右括号出现时栈为空，说明右括号多了 if (top == -1) return false; char left = stack[top--]; if ((s[i] == ')' && left != '(') || (s[i] == ']' && left != '[') || (s[i] == '}' && left != '{')) { return false; } } } // 循环结束后栈必须为空，否则说明左括号多了 return top == -1; }

代码里要注意的是最后一行判断，我之前就漏掉过：如果输入是((()，前半段全是左括号，循环正常走完，但栈里还剩着三个左括号，这时候应该判非法。很多人一开始只会想着"有没有匹配不上的右括号"，忽略了"有没有匹配不上的左括号"。

2.3 验证出栈序列合法性的另类考法

"验证表"还有一种常见变化：给定一个入栈序列1 2 3 4 5，再给一个出栈序列比如4 5 3 2 1，问这个出栈序列是不是合法的。这类题思路和括号匹配异曲同工，只是把栈的元素从括号换成了数字。

核心做法是：用一个栈模拟入栈和出栈过程。遍历出栈序列里的每个数，如果栈顶不是当前要出栈的数，就一直从入栈序列里取数压栈；如果入栈序列都取完了栈顶还不对，那这个出栈序列就非法。

bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize) { int stack[pushedSize]; int top = -1; int pushIdx = 0; for (int i = 0; i < poppedSize; i++) { // 栈顶不是目标，就持续入栈 while (top == -1 || stack[top] != popped[i]) { if (pushIdx >= pushedSize) return false; stack[++top] = pushed[pushIdx++]; } // 栈顶匹配，弹出 top--; } return true; }

这类"用栈验证性质"的题，核心思想都是模拟。你要站在计算机的角度，严格按照规则执行每一步操作，凡是规则执行不下去的地方，就是非法输入出现的地方。

3. 循环小数：哈希表与鸽巢原理的天作之合

3.1 从竖式除法说起

循环小数这道题，描述很简单：给你两个整数，一个是分子，一个是分母，输出它们相除的小数表示。如果是循环小数，用括号标出循环节。比如1/3输出0.(3)，1/6输出0.1(6)。

我第一次拿到这题完全没思路，后来一想，这不就是小学学的竖式除法吗？在纸上算1/3的时候，你会发现余数永远是1，除不尽，于是小数位永远在重复3。要判断循环节，关键就是看余数——一旦某个余数在之前出现过，那么从它上次出现到这次出现之间的商序列，就是循环节。

那到底用什么来"记住"某个余数之前出现的次数？数组可以，但分母可能很大，开一个足够大的数组理论上可行（余数的范围是0到分母-1），但更好的做法是用哈希表，直接把"余数值"映射到"它出现时的小数位下标"，查找是O(1)的。

3.2 核心实现

char* fractionToDecimal(int numerator, int denominator) { // 先处理整数部分，再模拟小数部分 long long n = numerator, d = denominator; // 提前判断符号（题目通常给正整数，但防御性处理总是好的） bool negative = false; if (n < 0 && d > 0 || n > 0 && d < 0) negative = true; n = llabs(n); d = llabs(d); // 整数部分 long long intPart = n / d; n = n % d; if (n == 0) return format(negative, intPart); // 整除，直接输出 // 模拟小数部分 int idx = 0; int hash[10000]; // 用数组代替哈希表，余数范围有限 memset(hash, -1, sizeof(hash)); char frac[10000]; while (n != 0) { // 余数之前出现过了，说明找到了循环节 if (hash[n] != -1) { int loopStart = hash[n]; // 在loopStart处插入左括号，在末尾插入右括号 break; } hash[n] = idx; n *= 10; frac[idx++] = n / d + '0'; n = n % d; } // 组装最终结果 }

这里的核心代码逻辑是：每次把当前余数乘以10，再除以分母得到一位商，然后更新余数。哈希表记录"每个余数第一次出现的位置"，一旦发现重复，就说明从那个位置开始进入循环节。

3.3 为什么一定会循环

有同学可能会问：万一这个分数根本不会循环怎么办？这就是个数学问题了——任何有理数的十进制表示，要么有限，要么无限循环。原因是除法运算中，每一步的余数取值范围是0到分母-1，总共只有分母种可能性。一旦余数重复出现，后续的计算过程就会完全重复，循环是必然的。

这个结论就是鸽巢原理的典型应用：分母是d时，余数最多d种，如果小数部分至少产生了d+1位，那必然有两个余数相同，循环从那里开始。这也是算法复杂度有上界的原因，最多O(d)步就能找到循环节，不用担心死循环。

我在乐学平台上提交这题时，WA了几次，问题都出在细节上：

• 负数的处理：虽然题目说输入是正整数，但我养成了防御性处理的习惯。如果不处理负数，-1 / 2会输出0.-5这种莫名其妙的结果。
• 输出格式：循环节要用一对圆括号括起来，且必须放在正确的位置上，不能把所有小数位都放进括号里。
• 记忆化数组的初始化：余数0和余数k的区别要分清楚，如果忘记初始化，哈希表里残留上一次运行的脏数据，会导致判断紊乱。

3.4 为什么用哈希表而不是顺序查找

这道题技术上不难，但很多同学会下意识地用一个数组把所有的余数都记下来，然后每次新余数出现时，从头到尾扫一遍看有没有重复。这样做在分母很小的时候没问题，分母一旦变成几万的量级，每一轮的查找都是O(d)，整体退化到O(d^2)，在乐学平台的超时边界上很容易被卡。用哈希表把查找降到O(1)，整个算法就是O(d)，一劳永逸。

4. 综教楼后的坑：场景题背后的单调栈

4.1 建模：从地形剖面到接雨水

"综教楼后的坑"这道题，我一开始完全摸不着头脑。后来才明白，这题是在描述综教楼后面有一排高低不平的地面，下了雨之后积水会留在低洼处，让你计算一共能存多少水。

这不就是经典的"接雨水"（Trapping Rain Water）问题吗？给一个数组height，每个元素表示某个位置的地面高度，下雨后低洼处会积水，求总积水量。我之前在力扣上刷到过这题，但没想到它会以"综教楼后的坑"这种极富校园特色的名字出现在数据结构作业里。

这个问题之所以放在数据结构课上讲，是因为它有一种非常漂亮的解法——单调栈。所谓单调栈，就是栈内元素保持单调递增或单调递减。在这道题里，我们维护一个高度递减的栈，或者说，栈里存的是下标，但下标对应的高度从栈底到栈顶是递减的。

4.2 单调栈解法拆解

核心思路是：从左到右遍历每个位置的高度。如果当前高度小于等于栈顶高度，就入栈。如果当前高度大于栈顶高度，说明在栈顶位置可能形成了一个"坑"，因为左边有比它高或等高的边界（栈里的前一个元素），右边有当前这个更高的位置。

int trap(int* height, int n) { int stack[n]; int top = -1; int ans = 0; for (int i = 0; i < n; i++) { while (top != -1 && height[i] > height[stack[top]]) { // 栈顶是要计算的坑底位置 int bottom = stack[top--]; if (top == -1) break; // 左边没有更高的墙了，存不住水 int left = stack[top]; int width = i - left - 1; int h = (height[left] < height[i] ? height[left] : height[i]) - height[bottom]; ans += h * width; } stack[++top] = i; } return ans; }

这个解法的时间复杂度是O(n)，每个元素最多入栈一次、出栈一次，空间复杂度O(n)。它的巧妙之处在于，水是一层一层算的，每次找到左右两边最近的比坑底高的边界，用"短板效应"算这一层能存多少水。

用双指针也能做，但单调栈的思路更贴合这学期数据结构课的主题——栈不只是用来做括号匹配的，它在很多数组处理问题里都能发挥奇效。

4.3 我在做这题时犯过的方向性错误

我第一次做这题时，完全没往单调栈上想，而是试图用一个"左右指针"模拟水面的上升过程，结果代码写得又长又乱，边界条件多到爆炸，最终在某次提交时被一个高度差很大的边缘用例击穿，心态差点崩了。

后来冷静下来才意识到，这类场景题最重要的不是马上写代码，而是先把问题抽象成数学模型。我在地图上画了一个地形剖面图，把每个高度都标出来，然后手动模拟了一遍雨水填坑的过程，这才猛然发现——每次能存水的区域，都是由"左边界、坑底、右边界"三段组成的，而单调栈天然地维护了这种"三段结构"。

所以我的建议是：拿到场景题，第一步用笔在纸上画图，把抽象的描述变成可视化的结构；第二步想一想这节课学了什么——如果作业出现在"栈和队列"那一章，多半能用栈解决；第三步才是动手写代码。大部分同学卡住，不是因为代码能力不行，而是因为第一步就跳过了。

注意：单调栈解法里有个常见的理解误区——不是每次出栈都一定能算水量。当栈里只剩一个元素时，说明左边没有墙了，这时候就算右边再高也存不住水，必须跳过。

最后分享一点我的体会

做完这四道题，我的感觉是乐学平台的题目虽然名字花哨，但考察的点都很扎实：约瑟夫问题考的是"有没有能力把O(n*m)优化成O(n)"，验证表考的是"知不知道栈是结构验证的天然工具"，循环小数考的是"能不能想到用哈希表做余数记忆"，综教楼后的坑考的是"能不能把场景题抽象成数据结构模型"。这些能力恰恰是数据结构这门课真正想培养的——不是让背代码，而是让建立一个"遇到问题先想数据结构"的思维习惯。

如果你现在正在被这几道题折磨，给你一个实际操作层面的小建议：每道题写完，在代码注释里写下"这道题用的核心数据结构是什么，为什么选它"，写不出来的说明还没完全想明白。我当时就是靠这个办法逼自己想清楚了约瑟夫问题为什么递推公式里要取模、循环小数为什么一定要用哈希表。数据结构学到后来你会发现，编程语言和语法都是表面的东西，真正值钱的就是这个"选型"的决策能力。

本文还有配套的精品资源，点击获取