美团校招笔试真题精讲：DP、字符串解析与贪心堆

美团2023校招笔试第10场编程题我是在秋招群里看到大家讨论时才真正去扒的。美团的技术笔试一向不跟你玩虚的题目表面套着外卖、骑手、商家这些业务壳子内核全是算法和数据结构的基本功。第10场这场题网上没有特别完整的官方题解我结合考生回忆和常见题型做了复原把三道题从读题、建模、代码到调试全过程都拆开讲一遍。不管你是正在准备校招的应届生还是想拿大厂真题练手的技术人这篇内容都值得认真看完里面的代码都是可以直接跑的。1. 美团第10场笔试的出题风格与备战思路1.1 美团编程题到底在筛选什么样的人美团笔试的编程题和牛客上那些纯八股算法题有一个明显区别题目场景基本都来自真实业务比如配送、订单、商家、套餐、骑手调度。但剥掉场景外壳之后考的依然是最经典的算法模型。这其实是在筛选两类能力第一能不能从业务描述里抽象出数学模型第二能不能在一个半小时内写出边界处理干净、复杂度过关的代码。很多人以为大厂笔试考的是“难题偏题”我刷完第10场的感觉恰恰相反。三道题没有一道是那种需要“灵光一闪”的脑筋急转弯都是你只要练过经典题型就能做的中等偏上难度题。但它的坑点在于题目描述很长数据范围藏得深边界条件多稍不注意就会在极端例子上翻车。说白了它考的是“稳定输出”的能力不是“灵光一闪”的运气。1.2 第10场三题的整体画像DP、字符串解析、贪心堆我把第10场考到的题型归纳为三类第一道是带权区间调度本质是动态规划配合二分查找考的是经典的“选与不选”决策模型第二道是套餐表达式解析本质是字符串处理加括号展开考的是递归下降或者栈的运用第三道是订单调度优化本质是贪心加优先队列考的是“局部最优能否推出全局最优”的直觉和证明能力。这三道题正好对应了大厂笔试最常考的三大板块DP、字符串、贪心。特别是第二道字符串解析很多人都觉得“这有什么好考的”实际上它特别能拉开差距。因为字符串题不是会不会某个算法的问题而是能不能把边界条件写对的问题。括号嵌套、多位数、乘法优先级这几个点任何一个没处理好都可能导致样例过了、提交却全是WA。1.3 上考场前需要练熟的核心算法如果你离笔试还有两三周我建议围绕这几个方向做针对性训练动态规划里的区间调度类、背包类、最长上升子序列类每个都要能手写状态转移方程字符串解析类重点关注括号匹配、表达式求值、逆波兰式这些是大厂高频考点贪心算法里优先队列优化是重中之重尤其是像“任务调度”“会议室安排”这类模型一定要练到看到题目就能条件反射地想到堆。数据结构方面线段树和树状数组可以暂时放一放笔试更高频的是数组、哈希表、栈、堆、二分查找。第10场这三题没有任何一题需要高级数据结构但如果你连堆的API都写不熟练第三题现场调起来会非常痛苦。我的建议是优先把常用数据结构的各种操作练到“闭眼能写”的程度再去做套题。2. 真题还原与精讲三道编程题从读题到AC2.1 第1题外卖订单区间选择带权区间调度DP题目描述大致是这样平台会放出n个众包配送订单每个订单i有一个配送时间段[l_i, r_i]骑手如果接单就必须在这个时间段内占用自己来完成配送不能中途接别的单。每个订单的配送费是v_i。问骑手最多能赚多少配送费数据范围n不超过10^5l_i和r_i都是10^9以内的大整数v_i可能达到10^9。这个题就是标准的带权区间调度。给大家一个生活化类比你有一间自习室很多同学来预约使用每个预约有开始时间、结束时间和愿意付的钱你只能接待时间不冲突的预约怎么才能赚最多模型一模一样。思路是这样先把所有订单按右端点r从小到大排序。设dp[i]表示“从前i个订单中能获得的最大配送费”。对于第i个订单只有两种决策不接它那么收益是dp[i-1]接它那么前一个订单的右端点必须小于等于当前订单的左端点也就是要在前i-1个订单里找一个最靠后的、r_j l_i的订单j然后收益就是dp[j] v_i。因为r已经排好序了找这个j可以直接用二分。状态转移方程dp[i] max(dp[i-1], v_i dp[j])其中j 满足 r_j l_i 的最大下标可以用 bisect_right 在 r 数组中查找。完整代码from bisect import bisect_right n int(input()) orders [] for _ in range(n): l, r, v map(int, input().split()) orders.append((r, l, v)) orders.sort() # 按右端点排序 r_list [x[0] for x in orders] dp [0] * (n 1) for i in range(1, n 1): r, l, v orders[i - 1] # 在前 i-1 个订单里找 r_j l_i j bisect_right(r_list, l, 0, i) # 注意 hii 是为了不把当前订单自己算进去 dp[i] max(dp[i - 1], dp[j] v) print(dp[n])这个代码时间复杂度是O(n log n)主要开销在排序和二分。空间复杂度O(n)也够用。这里有一个特别容易写错的点二分查找的hi参数。我第一次写的时候写成了bisect_right(r_list, l)没有限制hii结果当前订单自己也可能被算进去因为它的右端点r_i大概率大于l_i所以在大部分情况下没事但一旦出现l_i大于等于r_i的异常数据就会算出错误结果。虽然题目一般保证l_i r_i但笔试里养成“能写严谨就写严谨”的习惯能少踩很多坑。如果你用C写注意v_i和dp数组都要开long long不然10^9级别的价值累加起来直接溢出。这是大厂笔试特别爱藏的坑Python用户由于有高精度反而不会遇到但C用户一定要记得。2.2 第2题套餐表达式解析递归下降法处理括号题目描述可以复刻成这样给一个套餐表达式里面包含菜品名、数量、加号和括号。比如“(牛肉面2卤蛋3)2米饭4”意思是一个套餐里包含2份牛肉面和3份卤蛋这个套餐来2份再加4份米饭。给定每道菜的单价格要求输出每种菜的总份数以及总价格。表达式保证语法合法括号可以嵌套菜品名由中文或英文字母组成不含数字、加号、括号。这个题第一反应是“用正则表达式啊”但真去写正则就会发现括号嵌套和乘法优先级非常难处理。正则适合做“文本模式匹配”不适合做“带嵌套结构的语法解析”。这种嵌套结构正统做法是递归下降解析或者用栈手写。我推荐递归下降因为代码结构清晰面试时也更好解释。我们要定义两个函数parse_expr解析一整个由加号连接的表达式parse_factor解析一个“因子”。因子有两种形态要么是“菜品名数字”要么是“(表达式)数字”。数字可以省略省略时按1份处理。直接上代码class Parser: def __init__(self, s): self.s s self.i 0 self.n len(s) def parse_expr(self): # expr : factor ( factor)* res {} while self.i self.n and self.s[self.i] ! ): sub self.parse_factor() for k, v in sub.items(): res[k] res.get(k, 0) v if self.i self.n and self.s[self.i] : self.i 1 return res def parse_factor(self): # factor : item num? | ( expr ) num? if self.s[self.i] (: self.i 1 sub self.parse_expr() if self.i self.n and self.s[self.i] ): self.i 1 num self.parse_num() if num 1: for k in sub: sub[k] * num return sub else: name self.parse_name() num self.parse_num() return {name: max(1, num)} def parse_name(self): start self.i while (self.i self.n and self.s[self.i] ! ( and self.s[self.i] ! ) and self.s[self.i] ! and not self.s[self.i].isdigit()): self.i 1 return self.s[start:self.i] def parse_num(self): num 0 while self.i self.n and self.s[self.i].isdigit(): num num * 10 int(self.s[self.i]) self.i 1 return num expr (牛肉面2卤蛋3)2米饭4 menu {牛肉面: 12, 卤蛋: 2, 米饭: 3} cnt Parser(expr).parse_expr() total sum(cnt.get(name, 0) * price for name, price in menu.items()) print(cnt) print(total)输出结果{牛肉面: 4, 卤蛋: 6, 米饭: 4} 72验证一下套餐里2份牛肉面3份卤蛋来2份就是4份牛肉面和6份卤蛋再加4份米饭总价412624*348121272。正确。这个题有几个关键细节。第一parse_num返回0时表示“没有数字”需要靠max(1, num)兜底否则“牛肉面卤蛋”这种不带数字的写法会被算成0份。第二括号后的乘法一定要在累加之前做否则会把括号内的内容算到外面再乘导致重复计数。第三菜品名的扫描循环必须在遇到数字、括号、加号时停下否则“牛肉面2”会被解析成菜名“牛肉面2”。有读者可能会问为什么不用Python自带的eval因为eval只能处理数学表达式不能处理“菜品名当变量名”这种业务语义。而且笔试环境不一定允许这么偷懒还是用解析器稳。2.3 第3题最多按时完成订单贪心最大堆第三题题目描述骑手手上有n个订单每个订单需要耗时t_i并且有一个截止时间d_i。骑手一次只能处理一个订单订单可以按任意顺序做。如果某个订单在截止时间d_i之前完成就算按时完成否则就是超时订单没有收益。问最多能按时完成多少个订单这个场景很像期末考试周的复习安排每门功课要花不同的时间每门都有截止日期你希望尽可能多的科目能按时搞定。经典解法是“截止时间排序 最大堆贪心”。为什么按截止时间排序因为如果若干订单在某个可行方案中都能按时完成那么按照截止时间从小到大的顺序执行它们也一定都能按时完成。这个性质叫“交换论证”和单机调度里最常见的排序原则一样。所以我们可以按d_i递增依次“尝试”每个订单。实现思路用一个最大堆维护“当前已选择的订单耗时”。每来一个新订单先假设把它选上把总耗时cur加上t_i然后检查cur是否超出当前截止时间d_i。如果没超出说明这个订单可以按时完成保留。如果超出了说明在已选订单里至少有一个不能按时完成那我们就从堆里弹出一个耗时最大的订单把它的耗时从cur里减掉。这样做的结果是完成的订单数量没变加了一个又删了一个但总耗时cur变得最小为后续订单腾出了更多空间。这个“删最大耗时”的贪心为什么是对的因为每个订单对答案数量贡献相同都只算1个为了“数量”最大化在必须放弃一个时应该放弃耗时最长的那个这样剩余订单总耗时最小能继续容纳更多订单。证明一句话删除耗时最大的订单一定不会比删除其他订单更差。完整代码import heapq n int(input()) orders [] for _ in range(n): t, d map(int, input().split()) if t d: # 单订单耗时超过截止时间的直接不可能完成 orders.append((d, t)) orders.sort() # 按截止时间升序 heap [] # 最大堆存负数 cur 0 for d, t in orders: cur t heapq.heappush(heap, -t) if cur d: cur heapq.heappop(heap) # 弹出耗时最大的订单 print(len(heap))比如输入3 1 3 2 2 1 1按截止时间排序后是(1,1)、(2,2)、(1,3)。依次处理处理(1,1)cur11堆里有1个。处理(2,2)cur32弹出耗时最大的2堆里有1个。处理(1,3)cur23堆里有2个。 输出2。实际上最优方案确实是做两个要么做(1,1)和(2,2)但第二个完成时间是32不行正确组合是做(1,1)和(1,3)完成时间分别是1和2都按时。答案是2。这里要特别注意代码里先过滤了td的订单。如果不做这一步下面这种极端情况订单(100, 1)它比截止时间还长无论怎么排都不可能按时完成。如果不过滤把它push进堆后cur1001然后弹掉它自己堆里确实没它看起来好像也没事。但更危险的情况是后面有别的订单这个超长订单会把一个本来合理的订单顶掉导致结果偏大。所以过滤掉td的订单既是为了正确性也是为了让贪心语义更清晰。第三题的复杂度是O(n log n)空间O(n)。笔试数据量一般到10^5级别这个复杂度完全没压力。3. 笔试现场实操复盘我推荐的做题流程3.1 拿到题目不要急着敲代码先做四件事很多同学上来就盯着输入样例开始写代码这是笔试里最致命的节奏问题。我自己的习惯是拿到一道题先做四件事第一圈出数据范围判断能不能用O(n^2)暴力还是必须上O(n log n)第二剥掉业务外壳把题目归纳成经典的算法模型第三在草稿纸上写状态转移方程或者贪心策略并想清楚“为什么这样是对的”第四确认输入输出的格式陷阱比如是否是多组测试数据、是否涉及大整数、是否需要保留小数。拿第10场这三道题举例。第一题一看n是10^5立刻决定用带权区间调度DP第二题一看括号嵌套马上确定用递归下降不用正则硬刚第三题一看“最多”“截止时间”立刻想到排序加堆。如果你上来就写大概率会在写到一半时发现算法选错然后重新推翻时间全浪费了。3.2 三题的时间分配与放弃策略一场笔试通常在一个半小时左右三到四道编程题。我的建议分配是每道题读题和建模10分钟写代码20分钟调试15分钟。这是理想情况现实中肯定会遇到卡住的题。这里我分享一个很重要的策略不要按题目顺序死磕。先把所有题目快速扫一遍找到最有把握的一题先做。为什么因为笔试是按通过率计分的你做出两道完整题远比在三道题上各拿一半分要划算。如果某道题想了15分钟还没有完整思路立刻标记跳过去做下一道。等所有题都过一遍再回来啃硬骨头。第10场这三题的难度梯度其实不算大但这不代表你可以掉以轻心。第二题字符串解析看起来最“简单”但它最容易在细节上翻车所以我个人会把它放到第二位做先把DP题拿下稳定军心。3.3 自测用例怎么设计才能不翻车笔试最怕的就是“样例过了提交0分”。样例只能覆盖最正常的路径真正的坑都在边界。我通常给每道题设计四类测试数据第一类最小边界比如n1、n0、空字符串第二类因为题目保证n为正整数所以第一题不用测n0但要测n1确保二分不越界第三类极端数据比如所有区间都重叠、所有区间都不重叠、订单截止时间相同、订单耗时相同第四类最大复杂度数据n10^5时确认代码能在时间内跑完。另外字符串题的用例要格外注意嵌套和连续数字。比如“(牛肉面2)3米饭4”和“牛肉面2卤蛋3”这种没有括号的简单表达式都要跑一遍。正则表达式很难处理“连续括号”的情况递归下降法也要反复验证parse_factor和parse_expr之间会不会死循环。4. 实际笔试中容易踩的坑与排查技巧4.1 常见问题速查表我整理了第10场这三类题型里我自己以及身边同学踩过的高频问题直接做成表格方便大家自查。问题现象可能原因解决方案第一题输出值偏小区间按左端点排序了导致dp转移找不到正确的前驱一定要按右端点排序二分查找才有意义第一题二分越界或结果错误bisect的hi参数没有限制把当前区间也查进去了写bisect_right(r_list, l, 0, i)而不是只传两个参数第一题C结果溢出v和dp用了int10^9级价值累加溢出全部用long long第二题括号内菜品计数翻倍括号后的倍数在累加后才乘或者在循环里重复乘了先乘再累加且在parse_factor内部完成乘法第二题没有数字时统计成0parse_num返回0没有处理默认数量1用max(1, num)兜底第二题表达式解析死循环加号或括号处理后没有正确移动i指针在parse_expr里检查每次循环是否都消耗了字符第三题结果偏大没有过滤td的订单超长订单顶掉了正常订单加入订单前判断if t d第三题结果偏小堆用错了存正数导致每次弹出的是耗时最小的订单用最大堆Python里存负数C里用priority_queue默认大顶堆4.2 一次真实排错实录bisect 的下标边界这里说一个我真实遇到过的问题。第一题我写完第一版代码时二分写的是j bisect_right(r_list, l)样例通过我心想稳了。结果随手写了一个自测用例只有一个区间(1, 5, 100)l1, r5。用错误的写法bisect_right(r_list, 1)会返回1因为r_list[5]中第一个大于1的索引就是1然后dp[1] max(dp[0], dp[1] 100)这会导致把还没算出来的dp[1]拿来做转移结果直接出错或者更隐蔽地算出一个偏大的值。我当时发现输出不对后第一反应是“是不是排序出了问题”排查了很久才发现是二分的hi参数没有限制。后来我凡是遇到“在自身数组里查位置”的场景都会强制写清楚hi参数并且加一行注释搜索范围必须排除当前元素。这个习惯在笔试里救了我很多次。4.3 限时环境下我常用的几个调试技巧笔试环境没有IDE那么完善的断点调试所以我常用的方法有三个。第一print大法要“有策略地打印”。不要满屏print而是在关键分支打印一个标记变量比如dp数组的变化过程、堆的当前状态、解析器的当前字符索引。这样能看到算法走到哪一步开始歪。第二先写一个O(n^2)的暴力解法再和优化后的答案对拍。笔试时间紧但对拍小数据是值得的。n20以内的随机数据暴力最优各跑一遍输出不一致就说明优化算法有逻辑错误然后缩小数据规模定位。第三如果某道题调试超过15分钟还找不到问题果断放弃去做下一道。很多时候你纠结的那个bug其实是题意理解错了比如题目要求的是“最多完成订单数”你却一直纠结“怎样排序让总耗时最小”。换一个角度重新读题往往比死磕代码更有效。另外说一个和代码无关但很重要的点笔试前一定要熟悉你选择的编程语言的标准库。比如Python里heapq是堆bisect是二分collection.Counter可以当哈希表用C里priority_queue默认是大顶堆vector的lower_bound和upper_bound的返回语义要分清。这些工具如果在现场还要查文档时间就来不及了。我个人对第10场这场笔试最深的感受是它不考偏题怪题但每一道都精准踩在“你以为你会、实则很容易写错”的地方。第一题考二分边界第二题考解析细节第三题考贪心的正确性理解。如果你能把这三道题从头到尾手写一遍并且讲清楚每一步为什么这么做那么美团这类场景化算法题对你来说就不再是障碍。最后再分享一个小技巧平时刷题时故意在写完代码后不看测试样例自己先手推一遍输出再和程序结果对比。这个习惯能帮你大幅提升笔试现场的一次通过率。