又是一年秋招季，最近好几个学弟学妹跑来问我，说想看去年的笔试题练练手，尤其是教育科技这一块的公司。我翻了一下网盘，正好还留着2017年好未来秋招技术岗的笔试题目记录，这套题放在今天看依然很能打，考点覆盖了字符串处理、动态规划、贪心和二叉树，全是笔试高频中的高频。我把这套题做了一次完整复盘，把每道题的题意、思路、代码和踩坑点都整理了出来，不管你是准备校招还是想检验一下自己的算法功底，都可以直接拿来当模拟卷做一遍。
这套题整体难度中等偏上，没有特别偏难怪的题目，但每道题都有一定的区分度。换句话说，代码写得出来的人很多，能一次写对、把边界条件处理干净的人不多。面试官想看的其实不是你背了多少模板，而是你在有限时间内能不能把思路理清楚，把代码写得稳。下面我从试卷结构开始，逐题拆解。
1. 试卷结构与考察范围复盘
1.1 笔试形式与整体题型分布
2017年那会儿好未来的笔试用的是第三方在线评测系统，牛客网和赛码网都有用过，技术岗一般是两道选择题加四道编程题，总分100分，编程题占大头。考试时间是90分钟，前半个小时一般用来写选择题，真正留给编程题的时间差不多60分钟。四道题要在60分钟内全部AC，说实话压力不小，所以做题顺序和取舍策略很重要。
从考点分布来看，这套题对应的是经典的数据结构与算法四大块：字符串与栈、动态规划、贪心、二叉树。这些内容在《剑指Offer》和LeetCode前200题里都有大量对应题目，属于校招必刷范围。没有考复杂的图论、线段树这类进阶内容，也没有考偏门的位运算技巧，整体风格偏向考察基础功和代码实现能力。
1.2 题目难度梯队与时间分配建议
我按当年的做题体验给四道题排了个难度梯队：
| 题号 | 考点 | 难度 | 建议用时 | 核心难点 |
|---|---|---|---|---|
| 第一题 | 字符串解码、栈 | 中等 | 12分钟 | 嵌套处理与状态恢复 |
| 第二题 | 环形数组最大子段和 | 中等偏难 | 15分钟 | 环形情况的思维转换 |
| 第三题 | 区间调度、贪心 | 简单 | 8分钟 | 贪心策略证明与排序规则 |
| 第四题 | 判断二叉搜索树 | 中等 | 15分钟 | 边界条件与递归参数设计 |
我当时的策略是先把第三题这种一眼能看穿思路的题做掉，稳定拿分，再回来啃第一题和第二题。第四题虽然代码不长，但容易在细节上翻车，所以我放在最后写。这个顺序不一定适合所有人，但基本原则是：先做有把握的，再做需要思考的，千万别在前两道题上耗太久导致后面会做的题没时间写。
2. 第一题：字符串解码——栈的经典应用场景
2.1 题目描述与输入输出格式
这道题的题面大概是这样的：给定一个经过压缩编码的字符串，编码规则是k[encoded_string]，表示方括号内部的字符串重复 k 次。注意 k 保证是正整数，并且编码字符串可以嵌套，比如3[a2[c]]表示a2[c]重复3次，而2[c]表示c重复2次，所以最终结果是accaccacc。
输入一个压缩后的字符串，长度不超过200，包含数字、方括号和大小写字母。输出展开后的完整字符串。题目保证输入合法，不需要处理括号不匹配的情况，但需要自己处理多位数的情况，比如10[a]要正确展开成aaaaaaaaaa。
这个题在LeetCode上对应的是394题，但在2017年那会儿还算是比较新颖的考法。它考察的核心点很明确：能不能用栈维护嵌套的上下文状态。如果你想着用递归去解析，也能写，但代码量会大不少，而且在OJ上容易因为递归深度出问题。
2.2 解题思路与状态设计
我当时拿到题第一反应是字符串里套括号，这不就是表达式求值的简化版吗，用栈来处理嵌套是最自然的选择。但这里的难点在于，你不仅要处理括号的嵌套，还要处理数字和字符串两种上下文的同时嵌套。
用一个数字栈和一个字符串栈，分别保存当前层重复次数和之前已经拼好的字符串。具体来说，从左到右扫描字符，遇到数字就累加成 num，遇到左括号就把当前的 num 和 cur 分别压入两个栈，然后重置 num 和 cur，开始处理内层内容；遇到右括号就弹栈，把栈顶字符串加上当前 cur 重复 cnt 次的结果。
这里最关键的一点是：重复拼接的时候，要拼到之前记录的前缀后面，而不是直接重置当前字符串。我见过不少新手在这里写错，把strStack.top() + cur * cnt写成了cur * cnt，导致外层的内容丢失。
2.3 代码实现与复杂度分析
#include <iostream> #include <string> #include <stack> #include <cctype> using namespace std; string decodeString(string s) { stack<int> numStack; stack<string> strStack; string cur = ""; int num = 0; for (char c : s) { if (isdigit(c)) { num = num * 10 + (c - '0'); } else if (c == '[') { numStack.push(num); strStack.push(cur); num = 0; cur = ""; } else if (c == ']') { int cnt = numStack.top(); numStack.pop(); string prev = strStack.top(); strStack.pop(); for (int i = 0; i < cnt; i++) { prev += cur; } cur = prev; } else { cur += c; } } return cur; } int main() { string s; while (cin >> s) { cout << decodeString(s) << endl; } return 0; }时间复杂度是 O(n)，这里 n 指展开后字符串的长度，因为每个字符最终都要被拼接一次。空间复杂度是 O(n)，主要花在栈和结果字符串上。这个复杂度在大厂笔试里属于标准答案级别，不会因为效率问题被扣分。
2.4 这道题容易踩的坑
第一个坑是数字累加。很多人在处理isdigit(c)时忘记 num 可能不止一位，直接num = c - '0'，遇到10[a]就变成0[a]了。正确写法是num = num * 10 + (c - '0')，这一点在遇到多位数时特别重要。
第二个坑是字母的大小写问题。题目里可能同时出现大写和小写字母，直接拼接即可，不需要做转换，但要注意isalpha()判断别把方括号也算进去。用else分支处理字母是最稳妥的。
第三个坑是连续嵌套的恢复顺序。处理3[a2[c]]时，读到内层2[c]的]后，cur 变成cc，然后马上遇到外层]，此时 cnt 是3，prev 是空字符串，所以结果是cc重复3次，也就是cccccc，但正确结果应该是accaccacc。原因在于处理内层右括号时，cur 被更新成了cc，而这个cc应该作为整体重复内容再拼到外层前缀里。如果你在代码里没有把cur = prev这一步做好，结果就会错。
注意：这里的核心思想是，栈里保存的字符串是"当前层已经拼好的前缀"，cur 是"正在处理的内层内容"。每次遇到
]时，把 cur 重复后拼回前缀，然后把这个新字符串作为新的 cur 交给更外层的栈去处理。
3. 第二题：环形数组最大子段和——动态规划的思维升级
3.1 题目背景与变化点
这道题在经典的最大子段和问题上加了一个环形条件：给定一个整数数组，首尾相接成一个环，求环形数组中最大的连续子段和。比如数组[1, -2, 3, 4, -1, 2]，如果是普通数组，最大子段和是8，对应3 + 4 + (-1) + 2；但头尾相接后，还可以取[2, 1, -2, 3, 4]这样的跨界子段，和是8。这个条件下，普通的一维Kadane算法直接套上去就不够了。
2017年那会儿做这道题，很多人的第一反应是暴力枚举起点，把数组复制一倍，然后对每个起点做一次Kadane，复杂度 O(n^2)，小数据能过，但题目数组范围是10^5，O(n^2) 必挂。你需要想到线性做法。
3.2 核心思路：两种情况取最大值
环形数组的最大子段和只有两种可能：要么不跨过首尾边界，就是普通数组的最大子段和；要么跨过首尾边界，这时候如果取跨界的部分，那么没取到的部分恰好是数组中的一个最小子段和，所以跨界最大子段和等于数组总和减去最小子段和。
为什么等于总和减最小子段和？举个例子，数组[1, -2, 3, 4, -1, 2]，总和是7。如果我想取跨界的[2, 1, -2, 3, 4]，这等价于取整个数组但去掉中间没选的那一段[-1]，也就是最小子段和 -1。7 减去 (-1) 等于8，正好是跨界子段和。更一般地，在一个环上，你选一段连续区域，剩下没选的那部分也是连续区域，所以跨界最大子段和 = 总和 - 不选区域的最小和。
但这里有一个特殊边界情况需要小心：如果数组里全是负数，比如[-3, -2, -1]，普通最大子段和是 -1，总和减最小子段和等于 -6 - (-6) = 0，显然不对，因为题目要求至少选一个数，你不能选空集。所以最终答案要做一个判断：如果普通最大子段和还是负数，说明整个数组都是负数，直接返回普通最大子段和即可。
3.3 线性代码实现与解释
#include <iostream> #include <vector> #include <algorithm> #include <climits> using namespace std; int maxSubarraySumCircular(vector<int>& nums) { int curMax = 0, curMin = 0; int maxSum = INT_MIN, minSum = INT_MAX; int total = 0; for (int x : nums) { curMax = max(curMax + x, x); maxSum = max(maxSum, curMax); curMin = min(curMin + x, x); minSum = min(minSum, curMin); total += x; } if (maxSum < 0) { return maxSum; } return max(maxSum, total - minSum); } int main() { int n; while (cin >> n) { vector<int> nums(n); for (int i = 0; i < n; i++) { cin >> nums[i]; } cout << maxSubarraySumCircular(nums) << endl; } return 0; }这个代码同时在一次遍历里算出了普通最大子段和、普通最小子段和和总和，非常紧凑。curMax 和 curMin 的更新逻辑是对称的，理解了一个就理解了另一个。核心思想是Kadane算法，也就是动态规划：以当前位置结尾的最大子段和，要么是前一个位置结尾的最大子段和加上当前数，要么从当前数重新开始。
时间复杂度 O(n)，空间复杂度 O(1)。
3.4 容易忽略的边界细节
这道题最容易丢分的地方就是全负数数组。如果你没有做maxSum < 0的判断，直接用max(maxSum, total - minSum)，在全负数的情况下会输出0而不是最大负数，直接错一半测试用例。这个坑我在复盘的时候反复提醒自己，后来刷LeetCode 918题时发现官方题解也是这个套路，说明这类边界判断不是刁难，而是考察你思考问题是否全面。
另外要注意的是，题目可能会在数据范围里给出 int 溢出的情况。如果数组长度10^5，每个数绝对值10^9，总和是会超过 int 范围的。笔试环境里 C++ 的 int 一般是32位，最大约21亿，两个10^9相加就崩了。稳妥起见，涉及累加的地方直接开long long，不要为了省那点内存去赌数据不会超。
4. 第三题：会议安排——贪心策略的选择与证明
4.1 题目描述与朴素思路
这道题是区间调度问题的一个经典变体。题目描述很贴近实际：你是一个会议室管理员，一天内有很多团队预约了会议室，每个预约用一个区间[start, end)表示起止时间，你需要从这些预约中选出尽量多的预约，让它们之间互不重叠，问最多能选几个。注意这里区间是左闭右开还是左闭右闭会影响边界判断，一般来说笔试题里约定[start, end]且两个会议首尾相接不算冲突，比如一个会议到10点结束，另一个10点开始，可以连续安排。
朴素的做法是搜索加回溯，枚举所有预约的子集，检查是否冲突，取最大值。这种方式在 n 很小的时候可行，但 n 到10^5就完全不可能了。这道题的正确解法是贪心。
4.2 为什么"按结束时间最早"是最优策略
区间调度问题的经典贪心策略是：按结束时间从小到大排序，然后从前往后扫描，能选就选。这个策略的直观理解是：结束时间越早的会议，给后面留下的时间越多，所以优先安排它一定不亏。
但要说服自己这个策略是对的，光靠直觉不够。可以用交换论证：假设最优解的第一个会议是 A，而按结束时间排序后第一个会议是 B，那么 B 的结束时间不晚于 A 的结束时间。把最优解中的 A 换成 B，后面的会议依然不会和 B 冲突，因为它们在时间上排在 A 之后，而 B 结束得更早。这样替换后解的大小不变，就可以一步步把所有会议都换成贪心选择的会议，所以贪心解是最优解。
顺便说一下为什么另外两个常见策略是错的。按开始时间最早排序，可能出现一个开始很早但结束很晚的会议，占用后面大量时间；按持续时间最短排序，可能出现一个跨在两个较短会议中间的会议，导致两个都无法安排。这两种策略在面试时如果被问到，能现场举出反例是很加分的。
4.3 C++实现与排序规则细节
#include <iostream> #include <vector> #include <algorithm> using namespace std; struct Meeting { int start; int end; }; int maxMeetings(vector<Meeting>& meetings) { sort(meetings.begin(), meetings.end(), [](const Meeting& a, const Meeting& b) { if (a.end != b.end) { return a.end < b.end; } return a.start < b.start; }); int count = 0; int lastEnd = -1; for (const auto& m : meetings) { if (m.start >= lastEnd) { count++; lastEnd = m.end; } } return count; } int main() { int n; while (cin >> n) { vector<Meeting> meetings(n); for (int i = 0; i < n; i++) { cin >> meetings[i].start >> meetings[i].end; } cout << maxMeetings(meetings) << endl; } return 0; }排序比较器里先按结束时间升序，如果结束时间相同再按开始时间升序，这样排序结果是稳定的，避免因为顺序不稳定导致多算或少算。lastEnd初始值设为 -1，保证第一个会议一定能被选上，因为所有会议开始时间都大于等于0。
时间复杂度 O(n log n)，空间复杂度 O(1)。
4.4 这道题想考察什么
区间调度问题本身不难，但它在实际业务中对应的是资源分配、任务排期、广告投放时段优化等场景，对做教育科技产品的人来说尤其有代入感。你要给不同年级的学生安排直播课，每个课程有固定的时间段，如何排课能让教室利用率最高，本质上就是这个题。
我在复盘时单独把这道题拿出来说，是因为它属于典型的"看起来简单但能拉开差距"的题。思路对的人三分钟写完，思路偏的人可能在排序规则上纠结半天，或者纠结 start 相等、end 相等这种特殊数据。多写几个测试组试一下自己写的代码，比背诵题解有用得多。
5. 第四题：判断二叉搜索树——递归参数与遍历两种思路
5.1 题目描述与直觉陷阱
题目要求判断一棵二叉树是否是二叉搜索树（BST）。BST的定义是：左子树中的所有节点值都小于根节点值，右子树中的所有节点值都大于根节点值，并且左右子树本身也是BST。这里的关键词是"所有节点"，不是"左子节点"和"右子节点"。
很多人第一次看到这个题，会写一个递归：判断左子节点是否小于根、右子节点是否大于根，然后递归判断左右子树。这个写法在大多数情况下能通过，但遇到这种情况会出错：根节点是10，右子节点是15，右子节点的左子节点是8。按上面的写法，15大于10没问题，8小于15也没问题，递归判断右子树时只比较了8和15，没有拿8和根节点10比较，于是判定为BST，实际上8在根节点10的右子树里却小于10，不是BST。
这个错误的本质是：你只约束了相邻层级之间的大小关系，没有把祖先节点的约束传递到整个子树。正确的判断需要给每棵子树传递一个合法取值范围（上下界）。
5.2 递归上下界法的完整实现
#include <iostream> #include <limits.h> using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; bool helper(TreeNode* node, long long lower, long long upper) { if (node == NULL) { return true; } if (node->val <= lower || node->val >= upper) { return false; } return helper(node->left, lower, node->val) && helper(node->right, node->val, upper); } bool isValidBST(TreeNode* root) { return helper(root, LLONG_MIN, LLONG_MAX); }理论上每层递归中，左子树的合法范围是(lower, 当前节点值)，右子树的合法范围是(当前节点值, upper)。如果当前节点值不在这个开区间内，直接返回 false。这里用long long而不是int是因为节点值可以是 INT_MIN 或 INT_MAX，如果上下界直接取 INT_MIN 和 INT_MAX，比较时会出现相等导致误判。
时间复杂度 O(n)，每个节点只访问一次，空间复杂度 O(h)，h 是树高。
5.3 中序遍历法：另一种等价思路
BST有一个重要性质：中序遍历结果是严格递增的。所以判断BST的另一个方法是做一次中序遍历，检查遍历序列是否严格递增。这个思路在代码上更直观，也不需要传上下界参数。
class Solution { private: long long prev = LLONG_MIN; bool flag = true; public: void inorder(TreeNode* node) { if (node == NULL) return; inorder(node->left); if (node->val <= prev) { flag = false; return; } prev = node->val; inorder(node->right); } bool isValidBST(TreeNode* root) { inorder(root); return flag; } };这里要注意的是prev初始值。如果用INT_MIN作为初始值，遇到第一个节点值恰好也是 INT_MIN 时，node->val <= prev成立，会误判。所以同样用LLONG_MIN起步。另外，如果某个节点不满足递增条件，可以提前return，不需要继续遍历，但递归写法中要注意别把后面的节点漏了导致状态不对。
5.4 笔试评分会怎么看你这道题
判断BST这道题，OJ不会看你写了哪种方法，只看结果对不对。但如果你在面试现场写这道题，面试官可能会追问：两种方法有什么区别？你更推荐哪种？这里有一个很好的加分点：中序遍历法虽然没有显式传上下界，但它利用的是BST的全局性质，代码更简洁；递归上下界法更容易理解为什么是对的，也更适合扩展到泛型数据结构。
我当时在笔试里选的是上下界法，因为写起来不容易出现边界错误。中序遍历法需要一个额外的成员变量保存上一个值，如果笔试环境要求代码不能有全局变量，需要把prev放在类成员里，也还算方便。两种写法都建议练熟，现场写任何一个都能过，但能讲清楚两者之间的联系会更好。
6. 笔试实战经验与避坑清单
6.1 在线评测系统的输入输出细节
当年好未来的笔试是用在线OJ跑的，输入输出格式卡得很死。很多人题目本身写对了，但栽在输入输出的处理上，非常可惜。循环读入多组测试数据时，最稳妥的写法是while (cin >> n)，不要用for (int i = 0; i < n; i++)假设只有一组数据。输出每一行结果后要换行，最后一个结果也要换行，不然OJ会判格式错误。
关于效率，cin和cout默认会同步C标准库，导致读写变慢，在数据量大的时候可能超时。笔试时建议在 main 函数开头加两行：ios::sync_with_stdio(false); cin.tie(NULL);，这样cin的速度能接近scanf。但要注意，加了这两行后就不要混用cin和scanf了，容易出问题。
6.2 常见错误与排查方法速查表
| 症状 | 可能原因 | 排查方式 |
|---|---|---|
| 样例通过但提交0分 | 多组输入没写循环 | 检查是否用while (cin >> n) |
| 运行超时 | 使用了 O(n^2) 算法 | 看数据范围，换线性或 O(n log n) 思路 |
| 答案错误但小数据正常 | int 溢出或边界条件漏判 | 累加变量改成long long，检查全负数等边界 |
| 递归栈溢出 | 树退化成长链 | 试试中序的非递归写法或按数据范围评估递归深度 |
| 编译错误 | 数组越界或头文件缺失 | 确认vector、stack、algorithm等头文件是否引入 |
排查时最忌讳的是盯着代码看，不动手。遇到过不去的用例，先在本地构造几组小数据，把中间变量打出来，跟手算结果对比，很快就能定位问题。
6.3 做题顺序和时间的分配心得
我个人的经验是：笔试开始后先把四道题都快速过一遍，花2分钟判断每道题的考点和大致难度，然后从最简单的开始写。这样能保证会做的题都拿到分，不会出现在一道难题上耗40分钟、最后两道题白卷的情况。
这套真题里我建议的做题顺序是：第三题（区间调度）→ 第一题（字符串解码）→ 第二题（环形子段和）→ 第四题（判断BST）。第三题代码量最小，思路最明显，是保分题；第一题需要仔细处理栈的逻辑，但难度不算高；第二题和第四题都有思维陷阱，放在后面集中精力攻。
7. 从一套真题谈备考方法
7.1 专项突破比盲目刷题有效
每次有人问我秋招怎么刷题，我都会建议按专题来，而不是按题号从前往后刷。这套真题其实已经帮你划好了重点：字符串栈处理、动态规划、贪心、二叉树，这四个专题在校招笔试里出现的频率极高。你可以分别花一周时间主攻一个专题，把LeetCode上对应的经典题做一遍。比如栈专题做394题字符串解码和150题逆波兰表达式；DP专题做53题最大子段和、918题环形子段和；贪心做435题无重叠区间；树做98题验证BST。把这些题吃透，再回来做这套真题，你会发现思路顺畅很多。
专题刷题的过程中，不要只看题解，动手写代码是一方面，更重要的是把自己卡住的地方记录下来。我备考的时候会建一个文档，每道题记三行：题目链接、卡住的点、突破口是什么。第二轮复习直接看这个文档，效率比自己重新做一遍高得多。
7.2 限时模拟和复盘的价值
笔试和平时刷题最大的区别是时间压力。平时你可以想半小时再动手，笔试不行。建议在牛客网或者LeetCode的模拟环境里，给自己限时90分钟做一套题，全程像考试一样。一开始可能做不完，这很正常，多做几次就会找到节奏。考完复盘时，重点看两道题：一道是你花了太多时间的题，想想哪里浪费了时间；一道是你完全没思路的题，想想是哪个知识点薄弱。
复盘还有一个容易被忽略的环节：看正确代码的写法，特别是别人怎么处理边界的。比如字符串解码里num = num * 10 + (c - '0')，这个一行代码的处理方式，比你写得长串if else要省时省力得多。学习好的代码风格，下次笔试时能减少很多低级错误。
7.3 数据结构基础永远不能丢
这套真题里四道题全都能用数组、栈、递归解决，没有用到高级数据结构。越是这样的题，越考验你对基础数据结构的理解深度。栈在字符串解码里的作用是什么？其实是在保存不同层的上下文。递归在判断BST里的作用是什么？是在给每棵子树传递限制条件。如果能把这些底层逻辑想清楚，刷题时就不容易背了套路忘了本质。
我也见过不少同学上来就刷难题、专攻竞赛题，结果校招笔试反而挂了，因为基础题写得太慢、边界老是错。基础不牢，地动山摇，这句话放到算法笔试里格外真实。
最后再分享一个我自己的习惯：每次做完一套真题，我会隔一个月再做一遍。第二遍做的时候，如果还能做到不看题解写出来并一次通过，这道题才算真正掌握了。好未来这套2017年的题目，到现在我偶尔还会翻出来给身边人练手，因为它考的知识点不过时，题的风格也足够典型。希望这篇复盘能帮你把每一道题背后的思路吃透，而不只是记住答案。
