又是一年秋招季最近好几个学弟学妹跑来问我说想看去年的笔试题练练手尤其是教育科技这一块的公司。我翻了一下网盘正好还留着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) { stackint numStack; stackstring 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 是3prev 是空字符串所以结果是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^5O(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(vectorint 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) { vectorint 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(vectorMeeting 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) { vectorMeeting 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年的题目到现在我偶尔还会翻出来给身边人练手因为它考的知识点不过时题的风格也足够典型。希望这篇复盘能帮你把每一道题背后的思路吃透而不只是记住答案。
又是一年秋招季最近好几个学弟学妹跑来问我说想看去年的笔试题练练手尤其是教育科技这一块的公司。我翻了一下网盘正好还留着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) { stackint numStack; stackstring 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 是3prev 是空字符串所以结果是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^5O(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(vectorint 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) { vectorint 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(vectorMeeting 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) { vectorMeeting 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年的题目到现在我偶尔还会翻出来给身边人练手因为它考的知识点不过时题的风格也足够典型。希望这篇复盘能帮你把每一道题背后的思路吃透而不只是记住答案。
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
