美团校招编程笔试复盘：核心算法模板与边界细节实战

2023年春天我参加了美团校招技术岗的编程笔试第2场那套题给我留下的印象特别深。和很多大厂笔试一样美团这场不是纯刷难度而是同时考察基本功、读题能力和代码实现速度。当时我做完之后专门复盘了一遍把每道题的思路、边界、优化路径都整理成了笔记今天这篇就把这套题的拆解过程和实战经验完整放出来适合正在准备暑期实习、秋招或者想拿大厂笔试练手的同学参考。先给大家一个整体判断美团2023校招第2场编程题的题量适中难度分布呈阶梯状前一两道属于送分题中间有一道需要动脑子的最后一道压轴题会拉开差距。如果你是第一次参加这类笔试最大的挑战往往不是算法本身而是“读题速度”和“对边界条件的敏感度”。下面我按整体风格、典型题目详解、实现细节、常见坑点四个部分来讲最后再补一段我自己的复盘心得。1. 美团校招编程题的整体风格与第2场定位1.1 美团笔试到底在考什么先说说美团校招技术岗笔试的通用套路。大部分大厂笔试都是ACM赛制或者核心代码模式美团一般用牛客网平台核心技术岗通常采用核心代码模式也就是你只需要实现一个函数体输入输出由平台处理少数场次会出现ACM模式需要自己处理标准输入输出。从考核重点来看美团编程题有几个非常明显的倾向。第一是数据结构基础数组、字符串、链表、栈、队列、哈希表、二叉树、并查集这些高频考点反复出现。第二是经典算法模板二分答案、双指针、滑动窗口、贪心、动态规划、前缀和与差分、拓扑排序只要把这几类模板练熟基本能覆盖八成题目。第三是工程化代码能力也就是你写的代码是否足够健壮有没有处理越界、空值、大数溢出甚至变量命名是否清晰这些都会影响最终评分。美团还有一个特色题目喜欢包装业务场景。比如“外卖配送时间估算”“商家评分排序”“路径规划”之类的背景但剥掉外壳之后核心还是那些经典模型。所以读题的时候一定要学会“去壳”把业务词汇翻译成数据结构这一步往往决定了你能不能快速解题。1.2 第2场编程题的难度分布与考察倾向2023校招技术第2场从结构上讲整体题量和美团的常规风格一致大概在4道题左右时间是相对紧张的。难度大致呈阶梯分布第1题属于签到题基本是入门级的字符串或简单模拟给考生建立信心第2、3题属于中等偏上涉及数组、贪心或者动态规划第4题是压轴题往往需要结合多种算法或者比较巧妙的数学推导。从考察倾向上看这场明显更侧重基础算法的熟练度。没有特别偏门的题目也没有复杂的数学建模只要把经典模板练到“肌肉记忆”级别前几题都能比较顺利拿下。压轴题则更像是对综合能力的测试你是不是真的理解算法背后的原理能不能应对题目中的各种限制条件能不能在时间复杂度和空间复杂度之间做取舍。我个人的感受是这套题的区分度很在线。基础扎实的同学能在40分钟内解决前3题压轴题可能还需要15到25分钟但如果基础不够牢第二道题就开始卡壳后面心态容易崩。下面我结合具体题目来讲。1.3 赛前准备需要练到哪种程度针对这套题的风格我给大家一个准备标准的参考。不需要盲目刷难题但需要保证几类基本功达到“不假思索”的程度字符串的常见操作要闭眼能写包括统计字符频率、子串判断、翻转等数组的遍历、排序、去重、前缀和这些操作要形成条件反射动态规划至少要熟练掌握线性DP和背包模型明白状态定义和状态转移是怎么推出来的二分和贪心必须要能够手写模板理解边界条件。还有一个常被忽略的点核心代码模式下的函数签名理解。很多同学在力扣上刷题习惯了到了牛客笔试平台发现题目输入输出格式不一样反而慌神。建议正式笔试前至少用牛客的模拟考试功能练两三次熟悉它的题目排版、编译器版本和判题方式。2. 第2场编程题复盘三道典型题目详解由于美团笔试题目并不会公开完整题面下面这3道是根据我参加第2场以及和同场同学交流后还原出来的相似题型考察点和赛题高度一致完全可以作为复盘的依据。我按难度递进来讲字符串签到题、数组贪心/DP题、区间处理压轴题。2.1 签到题字符串重排能否构成回文串先来说第1道题。题目大致是这样的给定一个字符串你可以任意重新排列其中的字符问是否能够构成一个回文串。比如输入“carrace”可以重排成“racecar”所以输出true输入“abc”无论如何重排都无法构成回文串输出false。思路非常直接回文串的充要条件是字符串中所有字符的出现次数中最多只有一个字符出现奇数次其余字符都必须是偶数次。原因也很简单回文串是对称结构对称位置上的字符成对出现所以大多数字符都必须出现偶数次只有中间位置如果字符串长度是奇数可以放一个单独的字符对应一个奇数次字符。所以题目就变成了统计字符串中每个字符出现的频率数一数有多少个字符出现了奇数次如果奇数次字符的个数小于等于1就能构成回文串。#include string using namespace std; class Solution { public: bool canPermutePalindrome(string s) { int cnt[128] {0}; for (char c : s) { cnt[c]; } int oddCount 0; for (int i 0; i 128; i) { if (cnt[i] % 2 1) { oddCount; } } return oddCount 1; } };时间复杂度为O(n)n是字符串长度我们需要遍历一次字符串完成统计再遍历一次128个可能字符检查奇偶性所以总复杂度为O(n)且常数极小。空间复杂度为O(1)因为字符集大小固定我这里直接开了128大小的数组。这道题有一个容易踩的坑字符集范围。题目如果只说“字符串”并没有说明只包含小写字母那我建议直接按ASCII 128来开数组。如果你贪图省事只考虑小写字母遇到空格、数字、大写字母就会数组越界或者统计错误。这道题虽然简单但恰恰是这种细节决定了一次AC还是白白罚时。2.2 核心题环形数组的最大子数组和第2道题是典型的数组题但加了一个环形限制做起来比普通的“最大子数组和”要复杂一些。题目大意是给定一个整数数组nums代表一个环形数组即首尾相接请找出一个连续子数组使得它的元素和最大返回这个最大和。注意子数组至少包含一个元素并且同一个位置不能被选择两次。先说常规的“最大子数组和”这是Kadane算法的经典应用从左往右遍历维护当前子数组的最大和cur以及全局最大和maxSum。每到一个新元素要么把它加到之前的子数组上要么从这个位置重新开始转移式就是cur max(num, cur num)。但环形数组多了一种情况最大子数组可能跨过数组的边界也就是从数组尾部开始、绕一圈到数组头部结束。处理环形数组的常用思路是“正难则反”跨边界的最长子数组等价于数组总和减去数组中间某段“最小子数组和”。所以可以把问题拆成两步先用Kadane算法求出普通情况下的最大子数组和maxSum再用类似方法求出最小子数组和minSum最后答案是max(maxSum, totalSum - minSum)。这个思路能成立是因为环形数组中所有可能的选择要么不跨边界要么跨边界而跨边界的部分去掉中间那一段最小负贡献后剩下的和就是totalSum减去最小子数组和。不过这里有个坑如果数组中所有元素都是负数totalSum - minSum会等于0此时maxSum本来就是负数中的最大值直接取maxSum即可。所以最后要加一个判断如果maxSum小于0直接返回maxSum否则再返回max(maxSum, totalSum - minSum)。我见过很多同学在这个边界上翻车输出0而不是负数的最大值原因就是没有处理“不允许选择空子数组”这个限制。#include vector #include algorithm using namespace std; class Solution { public: int maxSubarraySumCircular(vectorint nums) { int curMax 0, maxSum nums[0]; int curMin 0, minSum nums[0]; int total 0; for (int num : nums) { curMax max(num, curMax num); maxSum max(maxSum, curMax); curMin min(num, curMin num); minSum min(minSum, curMin); total num; } // 如果所有元素都是负数maxSum就是最大的那个负数直接返回 if (maxSum 0) return maxSum; return max(maxSum, total - minSum); } };时间复杂度O(n)空间复杂度O(1)。这道题考察的知识点其实很集中第一是Kadane算法的变体第二是环形数组的转化思路。如果你能准确写出求最大和最小的两套Kadane逻辑这道题基本就能做对了。我自己复盘时觉得这道题的得分率可能不算高因为它需要两步转化。很多人知道最大子数组和的模板但面对“环形”就不知道怎么扩展。其实环形类问题在算法题里很常见比如环形链表、环形房屋打劫套路都差不多要么分类讨论要么把数组复制一份变成长为2n的普通数组。但复制数组也有风险可能超出时间限制或空间限制所以更推荐用“正难则反”的思路。2.3 压轴题区间合并与最大重叠数优化第3道题是一道区间题背景可能被包装成“多个任务请求在时间轴上的调度”核心模型是区间操作。题目大意是给定若干个区间每个区间用左端点和右端点表示如果两个区间有交集就可以合并成一个更大的区间请输出合并后的所有区间。有些变体还会要求你求出“在任意时刻最多有几个区间同时重叠”。先讲基础版的区间合并思路非常简单先把区间按照左端点从小到大排序然后遍历所有区间维护当前合并区间的左边界L和右边界R。如果下一个区间的左端点小于等于当前右边界说明两个区间有交集就把当前右边界更新为二者右端点的较大值否则就说明当前区间已经合并完毕保存结果并把当前区间切换到新的区间。排序的时间复杂度为O(nlogn)遍历一次O(n)总体复杂度O(nlogn)。#include vector #include algorithm using namespace std; class Solution { public: vectorvectorint merge(vectorvectorint intervals) { if (intervals.empty()) return {}; sort(intervals.begin(), intervals.end()); vectorvectorint res; int L intervals[0][0], R intervals[0][1]; for (int i 1; i intervals.size(); i) { if (intervals[i][0] R) { R max(R, intervals[i][1]); } else { res.push_back({L, R}); L intervals[i][0]; R intervals[i][1]; } } res.push_back({L, R}); return res; } };如果题目要求的是“最大重叠数”做法就变成差分数组了。把每个区间的左端点处加1、右端点后一位处减1然后从头到尾累加累加过程中的最大值就是最大重叠区间数。这个思路的精髓在于它把所有区间在时间轴上的增减变化压缩成了一个差分序列一次线性扫描就能得到结果避免了n个区间两两判断交集带来的O(n^2)复杂度。美团这道压轴题据我同学反馈还可能要求“返回最多重叠的位置”那就要在累加过程中记录最大值第一次出现的位置。这个变体其实比单纯求最大重叠数要稍微多写几行代码但核心套路不变。这道题综合了排序算法、贪心思想和差分技巧如果读题不仔细很容易只写出区间合并那一版然后漏掉第二问。3. 实现细节与笔试环境实战3.1 核心代码模式与ACM模式的输入输出差异美团笔试在牛客平台上通常采用核心代码模式也就是平台自动处理输入输出你只需要实现指定的函数。但为了防止某场突然改成ACM模式大家最好还是掌握标准输入输出的写法毕竟两种模式的边界处理习惯不一样。核心代码模式下你拿到的函数签名已经严格规定好了参数类型和返回值类型。比如上面第二道题的签名是int maxSubarraySumCircular(vectorint nums)你需要按这个签名来实现不要自己定义main函数也不要修改函数名。一个很常见的错误是很多同学在力扣上习惯了public:后的类方法到了牛客的C环境可能要求用普通函数或者不同的类名所以考试前一定先看一下题目给出的代码模板不要直接粘贴旧的代码。ACM模式下你需要自己写int main()并且处理多组输入。这种模式最容易翻车的点是题目可能包含多组测试用例需要循环读取直到EOF。你要判断是while (cin n)还是先输入一个T表示测试用例组数。美团这种牛客平台的笔试大多数是单组测试用例但偶尔会有多组。我的建议是拿到题目先快速扫一眼输入输出描述确定是单组还是多组不要凭经验猜。3.2 边界条件和数据范围要提前判断笔试的判题系统会同时用多个测试用例来验证你代码的正确性包括非常刁钻的边界数据。数据范围决定的不只是变量类型还会影响算法选择。比如第二道题的数组长度如果n的范围达到10^5那O(n^2)的暴力解法肯定会超时必须用O(n)的Kadane算法。如果n的范围只有10^3暴力循环也许能过但笔试现场我不会赌这种运气直接按最优解写因为最优解往往也是代码最简洁的版本。再比如区间题的数值范围如果区间端点达到10^9就不能用数组模拟差分必须用哈希表或者排序后的扫描线来做。如果区间端点比较小比如只有10^5那开一个10^510的数组做差分是完全可以的。所以我建议养成一个习惯做题前先看数据范围然后确定“这个范围要求什么复杂度”再倒推算法。边界值这块我通常会在写完代码之后专门检查几类情况数组为空、数组只有一个元素、所有元素相等、所有元素为负数、最大值出现在数组尾部、区间刚好没有交集、区间包含关系等。把这些边界值在草稿纸上跑一遍能过滤掉80%的隐蔽bug。3.3 笔试现场的时间分配与调试技巧编程笔试是时间有限、题目有梯度所以时间分配很重要。我的个人策略是先花2到3分钟把所有题目扫一遍按难度打分先做签到题再做熟悉的题目把压轴题放到最后。最忌讳的是在第二题的某个细节上死磕40分钟导致后面的题目没有时间看哪怕能做出来的题也浪费了。调试方面核心代码模式没法像本地IDE那样打日志但你可以用中间变量辅助判断。比如在写Kadane算法时如果你不确定这个转移方程对不对可以自己在草稿纸上用小数组模拟一遍。例如数组[-2,1,-3,4,-1,2,1,-5,4]里跑一遍Kadane算法初始化cur0、maxSum-2遇到-2时cur-2maxSum-2遇到1时cur1maxSum1遇到-3时cur-2maxSum1遇到4时cur4maxSum4。这样一轮下来你就能确认整个算法没有逻辑漏洞。另外建议本地练题时就用牛客或者类似的比赛平台来写代码让自己适应没有自动补全、没有报错提示的原始编辑器环境。我见过不少同学在IDE里写出完整代码一上在线编辑器就各种编译报错其实就是不熟悉环境导致的紧张。4. 常见问题与排查技巧实录4.1 运行错误、超时和答案错误的典型原因第一类问题是运行错误。出现这种情况通常有两种原因一是数组越界比如你在差分数组里把右端点加1之后直接拿来当索引但右端点本身就是数组长度这时候就溢出了二是访问了空容器比如没有提前判断intervals是否为空直接访问intervals[0]。解决方法是写代码时就在入口处加异常保护例如if(intervals.empty()) return {};。第二类问题是超时。超时意味着你的算法复杂度太高。当题目数据范围达到10^5以上但你还是用了两重循环时基本必超时。还有一种情况是排序的时候把比较函数写得非常慢也容易导致常数过大。排查思路很简单看题目给定的数据范围估算如果按你的算法最高会执行多少次基本操作如果超过10^8就要考虑优化算法了。第三类问题是答案错误。这种问题通常不是编译错而是逻辑在某个边界场景上不成立。比如环形数组求和那道题如果没有处理全负数数组的情况答案就会错区间合并那道题如果没有处理新区间恰好与当前区间相接的情况也可能丢数据。这种问题只能靠平时的边界数据训练来预防临时在笔试现场去猜是比较被动的。4.2 现场避坑清单结合我的实操经验这里整理一份笔试现场可以直接对照的避坑清单读懂输出格式是输出一行结果还是多行结果行尾有没有空格要求这直接决定你代码里要不要做格式处理。数据范围有没有可能超出int范围如果会用long long不要用int硬扛。排序前想清楚排序规则是通过lambda还是自定义比较函数注意相等元素之间要保持稳定或者不影响结果。使用二分时一定要确认区间是左闭右开还是左闭右闭两种写法对应的退出条件、mid取法都不同建议固定一种模板练熟。使用哈希表时注意重复元素覆盖与累加的关系我见过很多答案错误是在“应该累加却用赋值”的地方出的。题目要求返回索引还是返回值很多题目差之毫厘谬以千里比如要求返回子数组下标你返回了最大值平台就报错。核心代码模式下不要额外输出任何调试语句cout的输出都会被判题系统当成答案的一部分导致格式错误。4.3 复盘后的下一步准备路线如果这套题你做得还不错说明基础算法模板基本过关下一步可以主攻中等偏上难度的综合题尤其是结合哈希表排序、滑动窗口单调队列、动态规划状态压缩这些组合题。如果做得不理想也不要气馁大厂笔试本身就不是一锤子买卖春招、秋招、实习、提前批会有多次机会关键是每次笔试后都要复盘错题对应的知识点然后去补刷同类型20道左右直到形成肌肉记忆。具体建议是建立一个自己的题库分类按“数组技巧”“字符串处理”“图与树”“动态规划”“贪心和二分”分门别类每类下面留下做过且写对过的模板代码。到什么程度算过关看到一个题你能在10秒内说出它的题型标签、复杂度目标、可能踩的边界条件基本就稳了。美团的笔试风格比较稳定只要练到位通过率会明显提高。我个人实际操作中还有一个习惯就是每次笔试完当天趁记忆还热着把每道题的核心思路和代码立即整理成一篇复盘笔记。不追求写得多漂亮重点是记录当时的思考路径和踩过的坑过两周再回头看收获比单纯刷十道新题还要大。最后再分享一个小技巧针对美团这类业务背景包装的题目读题时可以把所有业务名词圈出来然后强制翻译成数据结构术语。比如“外卖配送时间”就是区间“商家评分排序”就是数组排序“用户分组”就是哈希表。一旦你完成了这层翻译题目难度会瞬间下降一档。这套题本身难度不算离谱真正拉开差距的往往是临场的心态和细节处理的熟练度。希望这篇复盘对你有用下一次笔试加油。