美团2023秋招编程岗笔试复盘：四道真题与备赛策略

8月的一个周六下午我打开笔试链接屏幕上是倒计时和四道编程题。美团2023秋招编程岗第一批笔试算是每年校招里关注度最高的一场投递人数多、题目风格典型、难度梯度明显后面几批次的题目也经常和它相似。这篇文章我想把这次笔试的完整复盘写出来包括四道题的解题思路、考场上的时间分配、容易踩的坑以及从题目反推出来的备赛方向。无论你是准备投美团的技术岗还是想拿大厂笔试练手这份复盘应该都能给你一些实处的东西。先交代一下背景美团笔试用的是牛客/赛码这类在线评测平台编程题部分大概四道时间比较紧总分按通过用例比例给分。也就是说不是只有AC全部用例才得分部分通过也有分。这个机制很关键后面我会专门讲怎么利用它。1. 笔试整体体验与题目结构分析1.1 美团笔试的节奏与风格美团笔试给我最直接的感受是题面不长但每一道都裹着一层业务场景。比如“小美有一些任务”“小明去游玩”之类的包装本质还是算法题。这种风格对校招同学其实挺友好因为读题压力不大关键是把场景抽象成算法模型。时间分配上四道题大概给了100分钟左右。听起来很宽裕但实际进入状态后你会发现如果第三题卡住第四题基本就没时间碰了。美团笔试的难度曲线通常有点“前缓后陡”第一题是签到题第二题是经典贪心或模拟第三题开始上强度第四题往往是动态规划或者状态压缩这类硬骨头。第一批的题目也是这样。还有一个特点美团的题对复杂度要求很明确。数据范围放在那里基本告诉你该用什么算法。n在10^5级别就是O(n log n)或O(n)n在20以下就要考虑状压或者爆搜。很多人笔试翻车不是因为不会做而是因为选错了算法复杂度估错跑大用例直接超时。1.2 第一批四道题的考点分布这里先给个总览表格后面逐题细说题号核心考点难度预估值得注意的点第一题字符串处理、贪心简单边界条件多容易想复杂第二题区间调度、贪心排序中等偏易排序规则要想清楚第三题前缀和、哈希表中等数值范围大不能用滑动窗口硬搞第四题状态压缩DP、图论困难转移顺序和初始化是难点从考点分布能看出来美团不考太偏门的东西就是基础算法里的高频题型贪心、前缀和、动态规划。但注意基础不代表简单它会在边界条件和数据范围上给你挖坑。比如第三题如果没注意到数组里可能有负数很容易写出“看似正确”的滑动窗口然后被特殊用例卡住。2. 四道真题的逐题拆解2.1 第一题字符串贪心开局送分题这题我印象里是这样一个模型给定一个只包含小写字母的字符串s每次操作可以把任意一个字符改成任意小写字母求最少操作多少次能让修改后的字符串中任意相邻两个字符都不相同。这种题只要想明白一个点就很简单当你从左往右扫描时如果发现s[i] s[i-1]你只需要修改s[i]不需要回头修改s[i-1]。因为前一个位置已经和前前一个位置确认过不相同了你改了它反而可能破坏前面的状态。修改s[i]之后它和s[i-1]肯定不同接下来只需要担心它和s[i1]撞车所以直接把扫描位置跳过s[i1]就行。C参考写法#include bits/stdc.h using namespace std; int main() { string s; cin s; int n s.size(); int ans 0; for (int i 1; i n; i) { if (s[i] s[i - 1]) { ans; // 当前字符被修改后和左右都不相同跳过下一个字符 i; } } cout ans endl; return 0; }这个解法的时间复杂度是O(n)空间O(1)。实测样例和手推都没问题。给大家提个醒这题最容易犯的错不是不会做而是把简单问题复杂化。我见过有人去枚举改成哪个字母甚至写DFS回溯完全没必要。你只需要计数不需要真的构造出修改后的字符串。另一个容易忽略的点是循环里跳指针的边界比如字符串是aaa第一次发现s[1]s[0]后i变成2循环结束答案1正确。如果是aaaa第一次i变成2此时s[2]s[1]因为没真改答案2也对。所以这个跳过写法是安全的。2.2 第二题区间调度经典贪心的变种第二题讲的是“小明一天最多能完整看多少个节目”。抽象成区间模型每个节目有开始时间l和结束时间r小明可以选择任意节目但不能同时看两个问最多能看几个。这个就是经典的最大不相交区间数量。贪心策略按结束时间从小到大排序然后依次选择“开始时间大于等于当前已经选中的最后一个区间结束时间”的区间。为什么要按结束时间排而不是按开始时间或者区间长度排因为结束时间越早留给后面的时间越多。按区间长度排是很多新手容易犯的错误比如一个短区间横跨两个长区间中间选它反而会挡住后面两个得不偿失。核心代码#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorpairint, int seg(n); for (int i 0; i n; i) { cin seg[i].second seg[i].first; // first存结束时间方便排序 } sort(seg.begin(), seg.end()); int ans 0, last_end -1; for (auto p : seg) { if (p.second last_end) { ans; last_end p.first; } } cout ans endl; return 0; }时间复杂度O(n log n)排序是瓶颈。这道题在美团笔试里算中规中矩但要小心输入数据里会不会有l r的情况以及区间是否允许“端点相接”。一般完整看节目如果上一个节目在t结束下一个节目从t开始是可以无缝衔接的所以判断条件是而不是。2.3 第三题前缀和加哈希一道容易踩坑的中等题第三题是“给定一个数组问有多少个连续子数组的元素和等于k”。题面可能包装成小美挑选连续几天的营业额但模型就是这个。看到连续子数组和等于k第一反应是滑动窗口。但这里有个隐藏信息数组元素可能有负数。一旦有负数滑动窗口的单调性就不成立了窗口左边界不能简单地收缩。所以这道题的正确姿势是前缀和加哈希表。核心思想是前缀和pre[i]表示前i个元素之和。子数组[j1, i]的和等于pre[i] - pre[j]。如果pre[i] - pre[j] k那么pre[j] pre[i] - k。所以我们遍历i的时候只需要查一下之前出现过多少个前缀和等于pre[i] - k然后累加进答案再把当前的pre[i]计数加一。C参考代码#include bits/stdc.h using namespace std; int main() { int n; long long k; cin n k; vectorlong long a(n); for (int i 0; i n; i) cin a[i]; unordered_maplong long, long long cnt; cnt[0] 1; long long pre 0, ans 0; for (int i 0; i n; i) { pre a[i]; ans cnt[pre - k]; cnt[pre]; } cout ans endl; return 0; }注意两个地方第一pre和cnt的value必须用long long因为n最大可以到10^5数组元素也可能到10^9前缀和很容易超过int范围。第二cnt[0]1这个初始化一定要有否则漏掉从第一个元素开始的子数组。这是很多人丢分的地方。这题想考察的其实是“能不能识别数据范围对算法选择的影响”。如果只看题目不看数据范围很容易写出滑动窗口的假算法样例能过但一跑大数据就超时或者报错。笔试里这种坑特别多读题时务必把数据范围圈出来看一遍。2.4 第四题状态压缩DP压轴硬骨头第四题是典型的压轴题模型是旅行商问题TSP的变种给定n个城市的坐标或距离矩阵从0号城市出发每个城市恰好访问一次最后回到0号城市求最短总路程。n大概是18左右。n等于18这个数据范围是一个很强的提示如果暴力枚举排列18!根本没戏所以必然要往状态压缩DP上想。状态压缩的核心是把“哪些城市已经访问过”这个集合用一个二进制数mask表示mask的第i位为1表示第i个城市已经访问过。定义dp[mask][i]表示当前已经访问过的城市集合为mask最后到达的城市是i时的最短距离。转移时枚举下一个未访问的城市j更新dp[mask | (1 j)][j]。最终答案是min(dp[(1n)-1][i] dist[i][0])也就是访问完所有城市后最后停在某个城市i再回到0号城市。参考代码#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorvectorlong long dist(n, vectorlong long(n)); for (int i 0; i n; i) for (int j 0; j n; j) cin dist[i][j]; int total 1 n; vectorvectorlong long dp(total, vectorlong long(n, LLONG_MAX / 4)); dp[1][0] 0; for (int mask 1; mask total; mask) { for (int i 0; i n; i) { if (!(mask (1 i)) || dp[mask][i] LLONG_MAX / 4) continue; for (int j 0; j n; j) { if (mask (1 j)) continue; int next_mask mask | (1 j); dp[next_mask][j] min(dp[next_mask][j], dp[mask][i] dist[i][j]); } } } long long ans LLONG_MAX / 4; int full total - 1; for (int i 1; i n; i) { ans min(ans, dp[full][i] dist[i][0]); } cout ans endl; return 0; }复杂度是O(2^n * n^2)n18时大概是6千万次量级C完全能跑。需要注意初始化dp[1][0]0因为初始在0号城市mask只有第0位是1。其他dp值先设成一个很大的数然后用min去更新。LLONG_MAX / 4防止后续加法溢出这个小细节建议养成习惯。状压DP在笔试里属于“会者不难难者不会”的类型。如果之前没见过现场很难推出来。我的建议是考前至少把经典的TSP、棋盘覆盖、子集枚举题目练一遍对这种“n很小但别的做法都过不了”的题就会形成条件反射。3. 考场实战策略与避坑记录3.1 时间分配先保底再攻坚四道题100分钟我的策略是前20分钟把第一题和第二题解决掉这两题属于“必须拿满”的部分大概占40分。第三题留30分钟争取拿满或者拿大部分分。最后30分钟给第四题如果做不出完整正解就写暴力或部分分能过多少算多少。这不是放弃而是利用“按通过用例给分”的规则最大化分数。很多人习惯从第一题做到第四题在一道题上死磕到AC才肯走。这种习惯在大厂笔试里会吃大亏。美团笔试的时间设计本身就没打算让你四道全AC拉开差距的往往是“谁能在有限时间里拿到更多部分的分数”。第四题写一个O(n!)的暴力DFSn10以内的用例能过也能拿到不错的分数。别觉得暴力丢人笔试里拿到分才是硬道理。3.2 现场容易忽略的五个细节第一多组输入和EOF问题。美团笔试题有时候不告诉你有几组测试数据用while(cin n)这种写法更安全。第二long long。只要数据范围超过10^9求和、距离、前缀和这些一律用long long。第三输出格式。有的题要求空格分隔有的要求换行有的要求不能有多余空格样例输出一定要看仔细。第四本地调试和提交的差异。本地过了样例不代表能AC要考虑极端输入比如空字符串、n1、最大值边界。第五不要在代码里输出调试信息。我就见过有人本地调试完忘了删cerr提交后输出一堆乱七八糟的东西直接判错。另一个值得说的是“看清楚题目给的变量名”。美团笔试喜欢把数组元素叫score、cost、price之类的业务词看代码时容易和标准算法里的变量搞混。我习惯在草稿纸上先画出题目模型再动手写代码这个习惯能省很多反复读题的时间。4. 从笔试反推美团技术偏好与备赛路线4.1 美团笔试题背后的用人逻辑美团技术岗的招聘量一直不小笔试作为第一道筛选关卡本质上不是为了考倒你而是为了筛掉“基本功不扎实”的人。你看四道题的考点字符串、贪心、前缀和、动态规划全是大学数据结构和算法课里的内容没有一道考偏题怪题。这说明美团看重的是基础算法的掌握程度和代码实现的熟练度而不是你会不会某个冷门技巧。还有一点美团笔试的场景包装都在往业务上靠比如节目安排、营业额统计、城市旅行。这传递出来的信号是他们希望你具备“把业务问题抽象成算法模型”的能力。后端开发日常写业务代码很多时候不是算法多难而是能不能从一堆需求里找到核心逻辑。笔试其实就是在提前测试这个能力。另外美团后端的技术栈以Java为主但笔试完全不限制语言C、Java、Python都可以。所以选语言的原则很简单哪个熟练用哪个。别在考场上为了“试试新语言”而换语言能用C随手写出高复杂度代码就用C。4.2 我的刷题建议与常见误区如果目标是美团这类大厂的编程岗刷题方向可以参考一个比例高频算法专题占七成包括贪心、二分、前缀和、链表、二叉树、动态规划暴力回溯和状态压缩占两成冷门数据结构占一成。LeetCode热题100加剑指offer的题量覆盖美团笔试大部分考点是够用的。很多同学刷题有个误区一道题想了五分钟没思路就去看题解看完觉得自己会了过两天又忘。正确的做法是给自己限时简单题15分钟中等题30分钟难题40分钟。没思路可以看题解但看完必须自己重新写一遍并且记录这道题的考点和解法关键词。我用这个方法刷了一个多月笔试时最大的感受是“看到题面就能联想到它属于哪一类题”后面顺着套路走就行。现在AI编程工具确实很火很多人拿它帮忙刷题、做题。但笔试现场只能靠你自己所以基本功还是要一次次手敲代码练出来。你可以用AI辅助理解思路但不要让它替代你思考。等到面试环节手撕代码的时候更是这样平时的积累骗不了人。最后再说一个容易忽略的准备工作提前半小时把电脑、网络、输入法都检查好把常用语言的输入输出模板准备好。别小看这些琐事我见过有人因为输入法没切换写代码时中英文标点混用编译卡了好几分钟。大厂笔试一年比一年卷任何细节都可能影响最后的结果。希望这份复盘对你有帮助祝笔试顺利。