前言里先给个定位这是一篇面向正在准备校招笔试的同学的复盘文章。我会按照我的记忆尽量还原考试中的三道题结合实际作答过程把每道题的思考链路、推导过程、代码实现和踩坑点完整写出来。题目细节如果和原卷有出入以原卷为准但题型和考察点是真实的。1. 猿辅导2020校招笔试三的整体印象题量与时间分配的实战策略在正式开始讲题之前先说点实在的猿辅导这场校招笔试安排在一个在线OJ平台上我当时考的是技术岗卷面一共三道编程题时长限制是120分钟。从难度梯度来看第一题属于“中等偏下”的经典动态规划第二题是贪心加优先队列第三题是单调栈的变体。整体上不考偏题怪题每一道都能在剑指Offer和LeetCode热门题里找到影子但每道题又都比原题多绕了一个弯。这种“不直接考原题而是把原题换场景再加条件”的出题方式其实非常考验平时刷题是不是真的理解了算法本质。如果只是背题看到第一题“翻转子数组求最大子段和”可能就会懵因为大多数人只刷过“最大子段和”没刷过加翻转操作的版本。我在考场上坐下来之后没有急着读题而是先把三个题目的信息量扫了一遍大致分配了一下时间第一题30分钟第二题35分钟第三题40分钟剩下15分钟用来处理编译错误和边界情况。这个时间分配最终帮助我全部AC时间刚好卡线。我还想给一个关于编程语言的建议我笔试用的是Java因为平时刷题最熟的就是JavaHashMap、PriorityQueue这些容器API不用查文档就能写完。如果你更习惯C或Python完全没问题但前提是你的熟练度要足够支撑你在不看文档的情况下写出完整解法。笔试不是炫技现场最稳的语言就是最好的语言。这里有一个很多应届生容易忽略的点笔试平台的输入输出方式。猿辅导这套笔试是标准ACM风格需要自己处理多组输入、拆字符串、转整数和我们平时在LeetCode上只需要写函数完全不同。我考前专门花了两个晚上在牛客网上练习IO模板把常见几种“第一行给n第二行给n个数”“多行不确定数量”的读法全部敲熟。这个准备工作帮我省下不少时间因为考试时不需要为Scanner和BufferedReader的用法浪费脑容量。2. 第一题翻转一次子数组后的最大连续子段和题目大意是这样的给定一个长度为n的整数数组nums可以选择一个非空连续子数组进行翻转翻转操作只能做一次问最后能够得到的最大连续子数组和是多少。n的范围在10^5量级nums里的元素可以是负数。2.1 从基础版到进阶版翻转操作到底改变了什么如果去掉翻转这个操作这题就是最经典的“最大连续子段和”用Kadane算法一遍扫过去O(n)解决。所以关键问题是翻转一次子数组究竟对答案产生了什么影响我们可以把数组想象成三段前面没有被翻转的部分A中间被翻转的部分B后面没有被翻的部分C。翻转B段本质上就是把B段内部的元素顺序倒过来。然后我们要求的还是“连续子数组的最大和”这个连续子数组在翻转后的数组里可能完全落在A、B、C其中一段也可能横跨两段。看到这里很多人的第一反应是“枚举翻转区间里面再跑Kadane”这显然不现实因为枚举翻转区间就是O(n^2)。我当时推导出的关键结论是翻转一次子数组后原来的一段连续区间会变成“原数组中的一个前缀加上一个后缀”的组合。什么意思呢比如要选一个从位置i开始到位置j结束的连续子数组翻转操作相当于把这段子数组内部顺序变了但子数组覆盖的整体范围不变。为了把问题简化很多解法会把目标子数组分成三段在某位置x左边我们选原数组的一个后缀因为翻转后这部分顺序不变在x位置我们选被翻转的那段在x右边我们选原数组的一个前缀。最终等价于枚举翻转中心维护左侧最优后缀和和右侧最优前缀和两者加起来取最大值。2.2 状态定义与代码实现我最终采用的解法分两步先预处理每个位置左侧的最大后缀和以及右侧的最大前缀和然后再枚举分隔点做合并。这里稍微展开一下预处理思路。对任意位置i“左侧最大后缀和”表示的是在原数组的[0, i]范围内必须包含位置i且往左延伸的连续一段的最大和。这个递推关系是leftBest[i] max(nums[i], leftBest[i - 1] nums[i])。右侧最大前缀和同理从右往左扫rightBest[i] max(nums[i], rightBest[i 1] nums[i])。然后枚举翻转的影响范围。把所有情况归并后可以用一个非常简洁的DP完成我们只需要知道“到当前位置为止已经翻转过子数组的右侧衔接点取到什么位置最优”。下面给出我当时的Java实现加了一些注释帮助理解。public class FlipMaxSubarray { public int maxSumAfterFlip(int[] nums) { int n nums.length; int[] right new int[n 1]; right[n] Integer.MIN_VALUE; int cur Integer.MIN_VALUE; // right[i]表示从i位置开始往右的最大前缀和 for (int i n - 1; i 0; i--) { cur Math.max(nums[i], cur nums[i]); right[i] cur; } // leftSum记录扫描过程中以当前位置为右侧端点时左侧能贡献的最大后缀和 int leftSum Integer.MIN_VALUE; int totalMax Integer.MIN_VALUE; int suffix Integer.MIN_VALUE; for (int i 0; i n; i) { // 更新当前作为左边部分时的后缀状态 suffix Math.max(nums[i], suffix nums[i]); leftSum Math.max(leftSum, suffix); // 翻转区间的右边界在i那么右侧从i之后取前缀区间内可以翻转或保持原序 int candidate leftSum (i 1 n ? Math.max(0, right[i 1]) : 0); totalMax Math.max(totalMax, candidate); } return totalMax; } }乍一看这段代码只扫了一遍数组其实右边预处理好之后后续的合并是O(n)。不过注意上面这个版本处理的是“选择一段区间翻转后最大连续子数组要么包含该区间要么避开该区间”如果翻转区间完全避开答案子数组其实就退化成了原始Kadane的结果所以我还用Kadane又求了一次原数组最大子段和最后和翻转情况取max双重保险。2.3 这题最容易栽的边界情况第一个坑数组全负数。如果整个数组都是负数最大连续子数组只能是一个单独元素此时翻转操作没有任何意义因为翻转不能把负的变成正的。我的代码如果只写“左侧加右侧”的合并可能会翻车因为当right[i 1]为负数时我加了Math.max(0, right[i 1])这会把右侧负数贡献直接丢弃实际上是允许子数组不延伸到右侧的。这个处理是正确的但你必须意识到它把负数贡献舍弃了最终max还能在扫描过程中覆盖到纯单元素的情况。第二个坑翻转区间可以为空吗题目明确说“非空连续子数组”所以翻转至少翻一个元素。但一个元素的翻转等于没翻因此结果至少等于原数组的最大子段和。很多解法没有专门处理这个点导致少了一种情况。最稳妥的策略就是我先用Kadane求一遍原数组答案再和翻转后的候选值取max不会漏。回过头来看这道题如果只对“翻转区间”进行两两枚举O(n^2)在10^5数据量下妥妥超时。我一开始也在考场上有过是不是要写线段树或者分治的念头后来发现只需要把问题拆成“左边后缀右边前缀”的组合问题就非常清晰了。这个思路值得单独拎出来讲任何一次翻转子数组的操作本质上只是把一段区间的顺序反转它对“最大连续子数组和”的影响完全可以映射为前后缀的重新拼接。3. 第二题最少教室预订数量贪心加优先队列的经典套路这道题的出现其实挺贴合猿辅导的业务场景考的就是在线教育里非常常见的排课问题。题目大意是有n门课程每门课给一个开始时间start[i]和结束时间end[i]每间教室同一时刻只能承担一门课程。问至少需要多少间教室才能让所有课程正常进行。n最大到10^5时间范围是int内的毫秒级时间戳也可能缩放到小时数。3.1 为什么第一思路是对的按开始时间排序这道题的核心数据结构是优先队列。最经典的解法是先按开始时间排序然后维护一个小顶堆堆顶存的是当前已分配教室中最早下课的时间。每来一门新课如果它的开始时间不早于堆顶的结束时间说明可以把这间刚空出来的教室复用它先从堆里弹出旧课程再把新课压入如果它的开始时间早于堆顶结束时间说明当前所有教室都满了只能新开一间教室。为什么按开始时间排序是关键因为只有当课程按开始时间递增处理时我们才能保证每当处理一门课程时所有可能已经结束的课程都已经在堆里暴露出来。如果乱序处理会出现“后面已经开始、前面还没被处理”的错乱状态导致优先队列无法正确判断教室是否空闲。我考场上的代码大致是这样的import java.util.*; public class MinClassrooms { public int minClassrooms(int[][] courses) { if (courses null || courses.length 0) return 0; Arrays.sort(courses, (a, b) - a[0] - b[0]); PriorityQueueInteger pq new PriorityQueue(); pq.offer(courses[0][1]); for (int i 1; i courses.length; i) { if (courses[i][0] pq.peek()) { pq.poll(); } pq.offer(courses[i][1]); } return pq.size(); } }如果你看过LeetCode 253会议室II会发现这个解法几乎一模一样。区别在于这道题里时间点可能非常密集而且题目要求输出的是“需要一个整数”不是“哪些课程共用教室”所以无需回溯过程优先队列的大小就是答案。3.2 另一种思路差分扫描什么情况用更划算除了贪心加优先队列还可以用差分数组扫描把所有开始时间记1结束时间记-1然后对所有时间点排序扫一遍累加过程中出现的最大值就是答案。这个思路更接近“同时段最大重叠数”的几何理解代码量也更少。但要注意差分扫描适合“时间点比较稀疏但课程数很多”的场景因为需要把所有开始结束时间点合并成一个2n长度的数组来排序。如果时间戳范围非常小比如在0到1000之间直接用桶数组做差分不排序也可以。可如果时间范围很大且课程数多排序复杂度是O(n log n)和优先队列一样实际耗时却没有明显优势。我当时在考场上之所以选优先队列版本是因为它的O(n log n)非常稳定而且不需要把结束时间单独拆出来排序。但如果时间戳比较集中、想控制在O(t n)的复杂度差分法是另一个好选择。两个方案没有绝对优劣关键是要在短时间内判断出数据范围更适合哪种。3.3 等号与边界为什么start等于end时会出问题这里我要专门提醒一个容易翻车的细节题目里结束时间end是开区间还是闭区间通常课程安排里“课程A的结束时间”和“课程B的开始时间”如果相等A结束后B立即开始是可以共用一间教室的。所以判断条件应该是courses[i][0] pq.peek()时才能复用而不能是大于。很多人在LeetCode刷过会议室II知道用大于等于但到了笔试现场因为是自定义的输入输出容易紧张写成大于。还有一个边界是课程数组可能为空或者某个课程的开始时间大于结束时间后者虽然不会出现在正常数据里但我在写防御性代码时还是会留一个校验。考场上的经验是笔试平台的测试数据通常不会给非法数据但数组为空的情况非常常见一定要特判否则优先队列对空peek会直接抛异常。从题目难度分配来看第二题其实比第一题更基础一些考的是“你知不知道这个经典模型”。我猜出题人把它放在中间就是为了让能通过第一题的同学稳定拿分。这类题目没有太多思维陷阱唯一需要修炼的就是看到“最少教室”“最多重叠”这类词组时能条件反射地想到排序加优先队列。4. 第三题删除K位数字使结果最大单调栈的现实变形第三题是压轴题也是最绕的一道。题目大意是输入一个由数字组成的字符串num和一个整数k允许从这个字符串中删除恰好k个数字问剩下的字符串能构成的最大数字是什么。num的长度可以达到10^6级别k小于num长度。这里要注意剩下的数字可以包含前导零吗题目一般会说清楚如果没有特殊说明前导零是可以保留的但最后拼接后的字符串就是数字的字面形式某些平台要求输出时去掉前导零。4.1 为什么“最大”不能用贪心直接删最小数字如果要求的是删除k个数字后剩下的数字最小LeetCode 402有个非常经典的单调栈解法。但猿辅导这里考的是最大其实本质一样只需要把“删除拐点大的数字”改为“删除拐点小的数字”。很多人没有想清楚单调栈为什么能处理这种问题只背了“删k个数字变最小用单调递减栈”这类口诀一旦方向反转就乱了。我的思考方式是从左到右扫描数字维护一个当前构造中的答案序列。只要发现当前数字比答案序列末尾的数字大并且仍然有删除额度就应该把末尾那个更小的数字删掉因为用更大的数字占据更靠前的位置会让整体数值更大。这个过程不断重复直到当前数字不比答案序列末尾大或者删除次数用完。这就是单调栈的决策模型只是比较方向和“删除最小值”版本刚好相反。4.2 代码实现与复杂度分析由于n可以到10^6直接对字符串做insert和delete操作不可行StringBuilder的deleteCharAt在末尾操作是O(1)但如果在中间频繁删除会产生大量元素移动最坏是O(n^2)。正确做法是用数组模拟栈或直接用StringBuilder做末尾追加和末尾回退。下面的Java实现是考场版本public class RemoveKDigitsToMax { public String removeKdigitsToMax(String num, int k) { if (num null || num.length() 0) return 0; int n num.length(); if (k n) return 0; StringBuilder stack new StringBuilder(); int[] digits new int[n]; for (int i 0; i n; i) { digits[i] num.charAt(i) - 0; } int remain k; for (int i 0; i n; i) { int cur digits[i]; while (remain 0 stack.length() 0) { int top stack.charAt(stack.length() - 1) - 0; if (cur top) { stack.deleteCharAt(stack.length() - 1); remain--; } else { break; } } stack.append(num.charAt(i)); } // 如果删完k次之前就扫描完直接截断末尾 while (remain 0 stack.length() 0) { stack.deleteCharAt(stack.length() - 1); remain--; } // 去掉前导零 int start 0; while (start stack.length() - 1 stack.charAt(start) 0) start; return stack.substring(start).length() 0 ? 0 : stack.substring(start); } }整体复杂度是O(n)因为每个字符最多被压入栈一次、弹出一次。空间复杂度O(n)。可能有人会问如果把“变大”的目标反一下改成删除k个数字后得到最小数不就是在cur top的时候出栈吗没错本质是一样的。我在考场上写完后为了确认方向没反特意拿“1432219”手动测试了一下删除3个数字得到最大数应该是“43219”而不是“1432”如果写成升序保留会得到错误结果。这种用小样例自测的习惯非常关键笔试的时候没有即时反馈平台逻辑错了自己是能靠例子验出来的一定不能省。4.3 这道题真正麻烦的不是算法而是输出格式前导零问题在“最大数”场景下其实不那么容易出现因为只要高位不是零整体数字就不会有大问题。但如果你删除的k非常接近字符串长度剩余数字可能全是零。比如num100200k4正确的最大剩余数字是“20”还是“0020”不同平台对此要求不一样。我当时的做法是输出前先去掉前导零如果最终结果为空就输出“0”。这个处理对多数测试点是安全的。另外题目要求“删除恰好k位”而不是“最多k位”。所以如果遍历完字符串后删除次数还没用完必须从栈尾部继续删。这是因为如果数字本身呈单调不增序列比如“98765”中间不会有触发删除的“拐点”但题目又要求必须删k个那只能删末尾那几个因为删除高位会让数字急剧变小删除末尾对最高位的影响最小。这个细节我见过很多人在笔试里漏掉导致样例过、大数据挂。5. 考后复盘这次笔试直接暴露出的准备短板三场考下来我对猿辅导这套笔试题的出题风格有了一些自己的判断。猿辅导是教育公司所以业务场景题喜欢用排课、教室、学生这类词汇包装但底层算法并不会脱离主流面试题范围。这次第三场整体难度在线虽然每道题都能找到经典原型但都需要临场做一次场景抽象和条件变形如果只是靠题库模板遇到第一题和第三题时很容易卡住。我复盘时给自己总结了三个短板也是我想重点提醒后面同学的。第一个短板是“对常见算法模型的复杂度边界不够敏感”。第一题我一开始在纸上试图枚举翻转起点和终点写了两行就意识到是O(n^2)赶紧停住。这个顿悟不是天生的而是因为平时刷题时养成了先看数据范围的习惯。n是10^5O(n^2)一定是超时的于是逼自己找O(n)或O(n log n)的做法。如果你平时刷题从来不管数据范围只求LeetCode能过那笔试现场就会非常被动。第二个短板是“用Java写ACM风格的输入输出不够熟练”。虽然我考前专门练过但第二题自定义排序那一段我竟然在Comparator的lambda表达式上犹豫了十几秒担心sort的稳定性会不会影响优先队列的答案。事后看这种担心是多余的因为排序顺序只影响处理先后不会影响最终需要的教室数量。但考试时那十几秒的犹豫足以说明平时还是太依赖IDE的提示了。第三个短板是“多角度验证做得不够”。第三题我在写完单调栈后只测了题目给的样例和一个随机小样例就急着提交了。其实应该再补一个“删除次数用不完”的用例比如数字单调递减、k小于长度的情况来验证处理尾部删除的代码是否执行。在笔试平台一道题提交次数往往有限一旦超过罚时会很影响心态。后来我养成了一个习惯每一次提交前至少在心里跑三个边界用例——空输入、全同元素、极值边界。这三个用例覆盖了大多数逻辑错误也算是我这次笔试最大的收获。另外给后来者一个非常具体的建议猿辅导这类校招笔试时间两个小时看起来很长实际上每道题分到的时间并不多。我强烈建议一进考场先花5分钟把所有题目都读一遍把每道题的数据范围标出来再决定从哪道题先开始。我的习惯是先做自己最有把握的题把确定的分先拿到而不是按题目顺序死磕。这种策略在这次考试里帮了我大忙因为第三题我虽然想到了单调栈但实现和验证花费了比预期多的时间如果不是第一题提前完成最后很可能交不完整。6. 从校招笔试到正式面试这套题背后想筛选什么能力很多人以为笔试只是刷人的工具实际上它透露了面试的考察方向。猿辅导的面试大概率会围绕你在笔试里的解法继续深挖比如问你第一题能不能优化、第二题如果把“教室数量最少”改成“打印出每个时间段使用教室的课程编号”该怎么办、第三题如果删除k的数值特别大该怎么处理。这些追问的出现都在笔试题目里埋了伏笔。我后来在面试环节确实被问到了第一题的变种如果翻转区间可以翻转多次还能不能用类似的前后缀合并来解。我的第一反应是“不能”因为多次翻转会让区间之间的关系变得复杂。面试官点头后又追问“只能翻转一次”这个限制在题目里是不是多余的如果去掉翻转次数限制最大连续子段和会不会有变化。这个问题其实是在考你对翻转操作的语义理解任意多次翻转等价于可以任意排列某些区间问题就变得完全不同了。能从DP推导出“翻转一次不改变子数组覆盖范围”并讲清楚这个边界比把AC代码背下来重要得多。所以如果你打算投猿辅导这类在线教育大厂请不要把校招笔试当成一次性考试来准备。三道题里出现的每一个“为什么能这样贪心”“为什么时间复杂度可达标”都有可能变成面试桌上的发问点。认真复盘一道题比盲目刷十道新题更有价值。这是我三场笔试加面试下来最深的感受。最后说一个已经被我验证过很多次的小技巧任何一次校招笔试结束之后趁热把每道题的题面、自己当时写的代码、提交后卡住的边界样例整理成一个文本文件存到自己的题库里。这个动作我坚持了几个月到了秋招后期翻看这些复盘记录时能非常明显地看到自己思维漏洞的迭代过程。复习旧题不是浪费时间它是在给自己建立一套“可复用的解题判断标准”。希望这篇复盘对大家有帮助也祝各位准备校招的同学笔试顺利。
前言里先给个定位这是一篇面向正在准备校招笔试的同学的复盘文章。我会按照我的记忆尽量还原考试中的三道题结合实际作答过程把每道题的思考链路、推导过程、代码实现和踩坑点完整写出来。题目细节如果和原卷有出入以原卷为准但题型和考察点是真实的。1. 猿辅导2020校招笔试三的整体印象题量与时间分配的实战策略在正式开始讲题之前先说点实在的猿辅导这场校招笔试安排在一个在线OJ平台上我当时考的是技术岗卷面一共三道编程题时长限制是120分钟。从难度梯度来看第一题属于“中等偏下”的经典动态规划第二题是贪心加优先队列第三题是单调栈的变体。整体上不考偏题怪题每一道都能在剑指Offer和LeetCode热门题里找到影子但每道题又都比原题多绕了一个弯。这种“不直接考原题而是把原题换场景再加条件”的出题方式其实非常考验平时刷题是不是真的理解了算法本质。如果只是背题看到第一题“翻转子数组求最大子段和”可能就会懵因为大多数人只刷过“最大子段和”没刷过加翻转操作的版本。我在考场上坐下来之后没有急着读题而是先把三个题目的信息量扫了一遍大致分配了一下时间第一题30分钟第二题35分钟第三题40分钟剩下15分钟用来处理编译错误和边界情况。这个时间分配最终帮助我全部AC时间刚好卡线。我还想给一个关于编程语言的建议我笔试用的是Java因为平时刷题最熟的就是JavaHashMap、PriorityQueue这些容器API不用查文档就能写完。如果你更习惯C或Python完全没问题但前提是你的熟练度要足够支撑你在不看文档的情况下写出完整解法。笔试不是炫技现场最稳的语言就是最好的语言。这里有一个很多应届生容易忽略的点笔试平台的输入输出方式。猿辅导这套笔试是标准ACM风格需要自己处理多组输入、拆字符串、转整数和我们平时在LeetCode上只需要写函数完全不同。我考前专门花了两个晚上在牛客网上练习IO模板把常见几种“第一行给n第二行给n个数”“多行不确定数量”的读法全部敲熟。这个准备工作帮我省下不少时间因为考试时不需要为Scanner和BufferedReader的用法浪费脑容量。2. 第一题翻转一次子数组后的最大连续子段和题目大意是这样的给定一个长度为n的整数数组nums可以选择一个非空连续子数组进行翻转翻转操作只能做一次问最后能够得到的最大连续子数组和是多少。n的范围在10^5量级nums里的元素可以是负数。2.1 从基础版到进阶版翻转操作到底改变了什么如果去掉翻转这个操作这题就是最经典的“最大连续子段和”用Kadane算法一遍扫过去O(n)解决。所以关键问题是翻转一次子数组究竟对答案产生了什么影响我们可以把数组想象成三段前面没有被翻转的部分A中间被翻转的部分B后面没有被翻的部分C。翻转B段本质上就是把B段内部的元素顺序倒过来。然后我们要求的还是“连续子数组的最大和”这个连续子数组在翻转后的数组里可能完全落在A、B、C其中一段也可能横跨两段。看到这里很多人的第一反应是“枚举翻转区间里面再跑Kadane”这显然不现实因为枚举翻转区间就是O(n^2)。我当时推导出的关键结论是翻转一次子数组后原来的一段连续区间会变成“原数组中的一个前缀加上一个后缀”的组合。什么意思呢比如要选一个从位置i开始到位置j结束的连续子数组翻转操作相当于把这段子数组内部顺序变了但子数组覆盖的整体范围不变。为了把问题简化很多解法会把目标子数组分成三段在某位置x左边我们选原数组的一个后缀因为翻转后这部分顺序不变在x位置我们选被翻转的那段在x右边我们选原数组的一个前缀。最终等价于枚举翻转中心维护左侧最优后缀和和右侧最优前缀和两者加起来取最大值。2.2 状态定义与代码实现我最终采用的解法分两步先预处理每个位置左侧的最大后缀和以及右侧的最大前缀和然后再枚举分隔点做合并。这里稍微展开一下预处理思路。对任意位置i“左侧最大后缀和”表示的是在原数组的[0, i]范围内必须包含位置i且往左延伸的连续一段的最大和。这个递推关系是leftBest[i] max(nums[i], leftBest[i - 1] nums[i])。右侧最大前缀和同理从右往左扫rightBest[i] max(nums[i], rightBest[i 1] nums[i])。然后枚举翻转的影响范围。把所有情况归并后可以用一个非常简洁的DP完成我们只需要知道“到当前位置为止已经翻转过子数组的右侧衔接点取到什么位置最优”。下面给出我当时的Java实现加了一些注释帮助理解。public class FlipMaxSubarray { public int maxSumAfterFlip(int[] nums) { int n nums.length; int[] right new int[n 1]; right[n] Integer.MIN_VALUE; int cur Integer.MIN_VALUE; // right[i]表示从i位置开始往右的最大前缀和 for (int i n - 1; i 0; i--) { cur Math.max(nums[i], cur nums[i]); right[i] cur; } // leftSum记录扫描过程中以当前位置为右侧端点时左侧能贡献的最大后缀和 int leftSum Integer.MIN_VALUE; int totalMax Integer.MIN_VALUE; int suffix Integer.MIN_VALUE; for (int i 0; i n; i) { // 更新当前作为左边部分时的后缀状态 suffix Math.max(nums[i], suffix nums[i]); leftSum Math.max(leftSum, suffix); // 翻转区间的右边界在i那么右侧从i之后取前缀区间内可以翻转或保持原序 int candidate leftSum (i 1 n ? Math.max(0, right[i 1]) : 0); totalMax Math.max(totalMax, candidate); } return totalMax; } }乍一看这段代码只扫了一遍数组其实右边预处理好之后后续的合并是O(n)。不过注意上面这个版本处理的是“选择一段区间翻转后最大连续子数组要么包含该区间要么避开该区间”如果翻转区间完全避开答案子数组其实就退化成了原始Kadane的结果所以我还用Kadane又求了一次原数组最大子段和最后和翻转情况取max双重保险。2.3 这题最容易栽的边界情况第一个坑数组全负数。如果整个数组都是负数最大连续子数组只能是一个单独元素此时翻转操作没有任何意义因为翻转不能把负的变成正的。我的代码如果只写“左侧加右侧”的合并可能会翻车因为当right[i 1]为负数时我加了Math.max(0, right[i 1])这会把右侧负数贡献直接丢弃实际上是允许子数组不延伸到右侧的。这个处理是正确的但你必须意识到它把负数贡献舍弃了最终max还能在扫描过程中覆盖到纯单元素的情况。第二个坑翻转区间可以为空吗题目明确说“非空连续子数组”所以翻转至少翻一个元素。但一个元素的翻转等于没翻因此结果至少等于原数组的最大子段和。很多解法没有专门处理这个点导致少了一种情况。最稳妥的策略就是我先用Kadane求一遍原数组答案再和翻转后的候选值取max不会漏。回过头来看这道题如果只对“翻转区间”进行两两枚举O(n^2)在10^5数据量下妥妥超时。我一开始也在考场上有过是不是要写线段树或者分治的念头后来发现只需要把问题拆成“左边后缀右边前缀”的组合问题就非常清晰了。这个思路值得单独拎出来讲任何一次翻转子数组的操作本质上只是把一段区间的顺序反转它对“最大连续子数组和”的影响完全可以映射为前后缀的重新拼接。3. 第二题最少教室预订数量贪心加优先队列的经典套路这道题的出现其实挺贴合猿辅导的业务场景考的就是在线教育里非常常见的排课问题。题目大意是有n门课程每门课给一个开始时间start[i]和结束时间end[i]每间教室同一时刻只能承担一门课程。问至少需要多少间教室才能让所有课程正常进行。n最大到10^5时间范围是int内的毫秒级时间戳也可能缩放到小时数。3.1 为什么第一思路是对的按开始时间排序这道题的核心数据结构是优先队列。最经典的解法是先按开始时间排序然后维护一个小顶堆堆顶存的是当前已分配教室中最早下课的时间。每来一门新课如果它的开始时间不早于堆顶的结束时间说明可以把这间刚空出来的教室复用它先从堆里弹出旧课程再把新课压入如果它的开始时间早于堆顶结束时间说明当前所有教室都满了只能新开一间教室。为什么按开始时间排序是关键因为只有当课程按开始时间递增处理时我们才能保证每当处理一门课程时所有可能已经结束的课程都已经在堆里暴露出来。如果乱序处理会出现“后面已经开始、前面还没被处理”的错乱状态导致优先队列无法正确判断教室是否空闲。我考场上的代码大致是这样的import java.util.*; public class MinClassrooms { public int minClassrooms(int[][] courses) { if (courses null || courses.length 0) return 0; Arrays.sort(courses, (a, b) - a[0] - b[0]); PriorityQueueInteger pq new PriorityQueue(); pq.offer(courses[0][1]); for (int i 1; i courses.length; i) { if (courses[i][0] pq.peek()) { pq.poll(); } pq.offer(courses[i][1]); } return pq.size(); } }如果你看过LeetCode 253会议室II会发现这个解法几乎一模一样。区别在于这道题里时间点可能非常密集而且题目要求输出的是“需要一个整数”不是“哪些课程共用教室”所以无需回溯过程优先队列的大小就是答案。3.2 另一种思路差分扫描什么情况用更划算除了贪心加优先队列还可以用差分数组扫描把所有开始时间记1结束时间记-1然后对所有时间点排序扫一遍累加过程中出现的最大值就是答案。这个思路更接近“同时段最大重叠数”的几何理解代码量也更少。但要注意差分扫描适合“时间点比较稀疏但课程数很多”的场景因为需要把所有开始结束时间点合并成一个2n长度的数组来排序。如果时间戳范围非常小比如在0到1000之间直接用桶数组做差分不排序也可以。可如果时间范围很大且课程数多排序复杂度是O(n log n)和优先队列一样实际耗时却没有明显优势。我当时在考场上之所以选优先队列版本是因为它的O(n log n)非常稳定而且不需要把结束时间单独拆出来排序。但如果时间戳比较集中、想控制在O(t n)的复杂度差分法是另一个好选择。两个方案没有绝对优劣关键是要在短时间内判断出数据范围更适合哪种。3.3 等号与边界为什么start等于end时会出问题这里我要专门提醒一个容易翻车的细节题目里结束时间end是开区间还是闭区间通常课程安排里“课程A的结束时间”和“课程B的开始时间”如果相等A结束后B立即开始是可以共用一间教室的。所以判断条件应该是courses[i][0] pq.peek()时才能复用而不能是大于。很多人在LeetCode刷过会议室II知道用大于等于但到了笔试现场因为是自定义的输入输出容易紧张写成大于。还有一个边界是课程数组可能为空或者某个课程的开始时间大于结束时间后者虽然不会出现在正常数据里但我在写防御性代码时还是会留一个校验。考场上的经验是笔试平台的测试数据通常不会给非法数据但数组为空的情况非常常见一定要特判否则优先队列对空peek会直接抛异常。从题目难度分配来看第二题其实比第一题更基础一些考的是“你知不知道这个经典模型”。我猜出题人把它放在中间就是为了让能通过第一题的同学稳定拿分。这类题目没有太多思维陷阱唯一需要修炼的就是看到“最少教室”“最多重叠”这类词组时能条件反射地想到排序加优先队列。4. 第三题删除K位数字使结果最大单调栈的现实变形第三题是压轴题也是最绕的一道。题目大意是输入一个由数字组成的字符串num和一个整数k允许从这个字符串中删除恰好k个数字问剩下的字符串能构成的最大数字是什么。num的长度可以达到10^6级别k小于num长度。这里要注意剩下的数字可以包含前导零吗题目一般会说清楚如果没有特殊说明前导零是可以保留的但最后拼接后的字符串就是数字的字面形式某些平台要求输出时去掉前导零。4.1 为什么“最大”不能用贪心直接删最小数字如果要求的是删除k个数字后剩下的数字最小LeetCode 402有个非常经典的单调栈解法。但猿辅导这里考的是最大其实本质一样只需要把“删除拐点大的数字”改为“删除拐点小的数字”。很多人没有想清楚单调栈为什么能处理这种问题只背了“删k个数字变最小用单调递减栈”这类口诀一旦方向反转就乱了。我的思考方式是从左到右扫描数字维护一个当前构造中的答案序列。只要发现当前数字比答案序列末尾的数字大并且仍然有删除额度就应该把末尾那个更小的数字删掉因为用更大的数字占据更靠前的位置会让整体数值更大。这个过程不断重复直到当前数字不比答案序列末尾大或者删除次数用完。这就是单调栈的决策模型只是比较方向和“删除最小值”版本刚好相反。4.2 代码实现与复杂度分析由于n可以到10^6直接对字符串做insert和delete操作不可行StringBuilder的deleteCharAt在末尾操作是O(1)但如果在中间频繁删除会产生大量元素移动最坏是O(n^2)。正确做法是用数组模拟栈或直接用StringBuilder做末尾追加和末尾回退。下面的Java实现是考场版本public class RemoveKDigitsToMax { public String removeKdigitsToMax(String num, int k) { if (num null || num.length() 0) return 0; int n num.length(); if (k n) return 0; StringBuilder stack new StringBuilder(); int[] digits new int[n]; for (int i 0; i n; i) { digits[i] num.charAt(i) - 0; } int remain k; for (int i 0; i n; i) { int cur digits[i]; while (remain 0 stack.length() 0) { int top stack.charAt(stack.length() - 1) - 0; if (cur top) { stack.deleteCharAt(stack.length() - 1); remain--; } else { break; } } stack.append(num.charAt(i)); } // 如果删完k次之前就扫描完直接截断末尾 while (remain 0 stack.length() 0) { stack.deleteCharAt(stack.length() - 1); remain--; } // 去掉前导零 int start 0; while (start stack.length() - 1 stack.charAt(start) 0) start; return stack.substring(start).length() 0 ? 0 : stack.substring(start); } }整体复杂度是O(n)因为每个字符最多被压入栈一次、弹出一次。空间复杂度O(n)。可能有人会问如果把“变大”的目标反一下改成删除k个数字后得到最小数不就是在cur top的时候出栈吗没错本质是一样的。我在考场上写完后为了确认方向没反特意拿“1432219”手动测试了一下删除3个数字得到最大数应该是“43219”而不是“1432”如果写成升序保留会得到错误结果。这种用小样例自测的习惯非常关键笔试的时候没有即时反馈平台逻辑错了自己是能靠例子验出来的一定不能省。4.3 这道题真正麻烦的不是算法而是输出格式前导零问题在“最大数”场景下其实不那么容易出现因为只要高位不是零整体数字就不会有大问题。但如果你删除的k非常接近字符串长度剩余数字可能全是零。比如num100200k4正确的最大剩余数字是“20”还是“0020”不同平台对此要求不一样。我当时的做法是输出前先去掉前导零如果最终结果为空就输出“0”。这个处理对多数测试点是安全的。另外题目要求“删除恰好k位”而不是“最多k位”。所以如果遍历完字符串后删除次数还没用完必须从栈尾部继续删。这是因为如果数字本身呈单调不增序列比如“98765”中间不会有触发删除的“拐点”但题目又要求必须删k个那只能删末尾那几个因为删除高位会让数字急剧变小删除末尾对最高位的影响最小。这个细节我见过很多人在笔试里漏掉导致样例过、大数据挂。5. 考后复盘这次笔试直接暴露出的准备短板三场考下来我对猿辅导这套笔试题的出题风格有了一些自己的判断。猿辅导是教育公司所以业务场景题喜欢用排课、教室、学生这类词汇包装但底层算法并不会脱离主流面试题范围。这次第三场整体难度在线虽然每道题都能找到经典原型但都需要临场做一次场景抽象和条件变形如果只是靠题库模板遇到第一题和第三题时很容易卡住。我复盘时给自己总结了三个短板也是我想重点提醒后面同学的。第一个短板是“对常见算法模型的复杂度边界不够敏感”。第一题我一开始在纸上试图枚举翻转起点和终点写了两行就意识到是O(n^2)赶紧停住。这个顿悟不是天生的而是因为平时刷题时养成了先看数据范围的习惯。n是10^5O(n^2)一定是超时的于是逼自己找O(n)或O(n log n)的做法。如果你平时刷题从来不管数据范围只求LeetCode能过那笔试现场就会非常被动。第二个短板是“用Java写ACM风格的输入输出不够熟练”。虽然我考前专门练过但第二题自定义排序那一段我竟然在Comparator的lambda表达式上犹豫了十几秒担心sort的稳定性会不会影响优先队列的答案。事后看这种担心是多余的因为排序顺序只影响处理先后不会影响最终需要的教室数量。但考试时那十几秒的犹豫足以说明平时还是太依赖IDE的提示了。第三个短板是“多角度验证做得不够”。第三题我在写完单调栈后只测了题目给的样例和一个随机小样例就急着提交了。其实应该再补一个“删除次数用不完”的用例比如数字单调递减、k小于长度的情况来验证处理尾部删除的代码是否执行。在笔试平台一道题提交次数往往有限一旦超过罚时会很影响心态。后来我养成了一个习惯每一次提交前至少在心里跑三个边界用例——空输入、全同元素、极值边界。这三个用例覆盖了大多数逻辑错误也算是我这次笔试最大的收获。另外给后来者一个非常具体的建议猿辅导这类校招笔试时间两个小时看起来很长实际上每道题分到的时间并不多。我强烈建议一进考场先花5分钟把所有题目都读一遍把每道题的数据范围标出来再决定从哪道题先开始。我的习惯是先做自己最有把握的题把确定的分先拿到而不是按题目顺序死磕。这种策略在这次考试里帮了我大忙因为第三题我虽然想到了单调栈但实现和验证花费了比预期多的时间如果不是第一题提前完成最后很可能交不完整。6. 从校招笔试到正式面试这套题背后想筛选什么能力很多人以为笔试只是刷人的工具实际上它透露了面试的考察方向。猿辅导的面试大概率会围绕你在笔试里的解法继续深挖比如问你第一题能不能优化、第二题如果把“教室数量最少”改成“打印出每个时间段使用教室的课程编号”该怎么办、第三题如果删除k的数值特别大该怎么处理。这些追问的出现都在笔试题目里埋了伏笔。我后来在面试环节确实被问到了第一题的变种如果翻转区间可以翻转多次还能不能用类似的前后缀合并来解。我的第一反应是“不能”因为多次翻转会让区间之间的关系变得复杂。面试官点头后又追问“只能翻转一次”这个限制在题目里是不是多余的如果去掉翻转次数限制最大连续子段和会不会有变化。这个问题其实是在考你对翻转操作的语义理解任意多次翻转等价于可以任意排列某些区间问题就变得完全不同了。能从DP推导出“翻转一次不改变子数组覆盖范围”并讲清楚这个边界比把AC代码背下来重要得多。所以如果你打算投猿辅导这类在线教育大厂请不要把校招笔试当成一次性考试来准备。三道题里出现的每一个“为什么能这样贪心”“为什么时间复杂度可达标”都有可能变成面试桌上的发问点。认真复盘一道题比盲目刷十道新题更有价值。这是我三场笔试加面试下来最深的感受。最后说一个已经被我验证过很多次的小技巧任何一次校招笔试结束之后趁热把每道题的题面、自己当时写的代码、提交后卡住的边界样例整理成一个文本文件存到自己的题库里。这个动作我坚持了几个月到了秋招后期翻看这些复盘记录时能非常明显地看到自己思维漏洞的迭代过程。复习旧题不是浪费时间它是在给自己建立一套“可复用的解题判断标准”。希望这篇复盘对大家有帮助也祝各位准备校招的同学笔试顺利。
)
