先说个题外话。每年秋招刷题阶段美团这套多轮笔试一直是被低估的“宝藏题库”。它不像某些厂动不动上偏难怪题而是紧扣业务场景把排序、贪心、动态规划、线段树这些基本功揉进外卖、配送、商家这些真实问题里。2023校招技术第9场编程题整体做下来给我最强烈的感受是题目看似温和实则每一题都在考你的建模能力——你能不能把一个业务描述快速翻译成算法原型。今天就把这套题的复盘整理出来包含题目还原、完整代码、复杂度分析和考场上的真实取舍给后面准备大厂笔试的朋友一个参考。需要提前说明的是下面四道题是我根据第9场笔试的整体风格与个人复盘做的典型性还原不保证和原题逐字一致但题型结构、考察点和难度梯度是高度接近的。你可以把它当成一套“同风格仿真题”来练效果差别不大。1. 先看清局面第9场考了什么出题人想筛什么1.1 考点分布与难度曲线美团笔试的编程题通常是四道时间90到120分钟语言不限。第9场这组题目的难度分布很典型一道纯模拟、一道贪心、一道动态规划、一道数据结构呈现明显的阶梯状。第一题和第四题之间大概隔了三个难度层级但中间没有断层每道题都给你留下“跳一跳够得着”的空间。考点覆盖上哈希表与排序是第一题的核心考察的是最基本的代码组织能力第二题是区间贪心属于经典原型的包装第三题是带权区间调度的动态规划这个比较关键它同时考察了DP状态设计和二分查找是整场笔试的分水岭第四题是线段树或树状数组的区间查询问题属于压轴的数据结构题。为什么说这套题出得好因为它没有靠“偏题”来卡人而是把每个基础算法都放在了一个需要你动脑建模的场景里。比如第二题表面是骑手排班实际上就是“选最多不重叠区间”的经典贪心第三题表面是接单收益最大化本质是带权区间调度。如果你只是背了模板但不懂原理在识别模型这一步就会卡住。1.2 什么样的水平能稳过结合我实际参加校招的经验和周围同学的反馈这类笔试的过线策略大概是这样第一题必须在10分钟内AC这是送分题AC不了基本说明代码基本功还不到位第二题是保底题20分钟内要拿下它决定了你能不能进入下一轮筛选第三题尽量拿满分或大部分分这是拉开差距的地方第四题如果时间不够写出暴力解法或者部分数据点的解法也能拿到一定分数。我见过不少同学在笔试前刷了大量高难度题结果一上考场栽在第三题的“二分边界”上或者第四题直接空着。这个现象说明一个道理校招笔试比的不是你做过多少难题而是你在有限时间内能不能稳定输出。你对模板的熟练度、对题目模型的敏感度、对边界条件的敏感度这三样东西缺一不可。2. 例题还原与逐题拆解2.1 第一题外卖订单统计哈希 排序题目描述还原小团负责统计外卖平台一天的订单数据。给定 n 个订单每个订单有一个订单号字符串。请统计每个订单号出现的次数并按出现次数从高到低输出次数相同的按订单号字典序升序输出。 输入第一行为 n接下来 n 行每行一个订单号。 输出若干行每行是订单号和出现次数用空格分隔。考察点分析哈希表做频次统计这是最基础的一步几乎没有难度。排序比较器的正确写法尤其注意“次数降序、字典序升序”的复合排序条件。输入输出处理能力n 的最大值没有给得特别大但如果数据量到十万级别字符串比较的排序仍然是主要开销。题解思路这题没有算法门槛唯一值得说的是排序那一步。用HashMap统计完所有频次之后把entrySet转成List然后写一个lambda比较器。比较器里有个小坑如果次数相等要按 key 的字典序升序注意是两个条件都要写进比较器不能只排次数。参考代码Javaimport java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); MapString, Integer cnt new HashMap(); for (int i 0; i n; i) { String s sc.next(); cnt.put(s, cnt.getOrDefault(s, 0) 1); } ListMap.EntryString, Integer list new ArrayList(cnt.entrySet()); list.sort((a, b) - { if (!a.getValue().equals(b.getValue())) { return b.getValue() - a.getValue(); // 次数降序 } return a.getKey().compareTo(b.getKey()); // 字典序升序 }); for (Map.EntryString, Integer e : list) { System.out.println(e.getKey() e.getValue()); } } }复杂度分析统计频次 O(n)排序 O(k log k)其中 k 是不同订单号的数量。空间 O(k)。数据量如果到十万也完全没问题。考场提示这道题唯一的丢分点在于粗心。比如getOrDefault用得不熟导致空指针或者比较器两个条件的顺序写反。还有一个常见问题是忘记在统计完再排序而是边读边排那样会多一个不必要的 O(n log n)。这题没难度它筛掉的是代码基本功不扎实的人。2.2 第二题骑手的时间规划区间贪心题目描述还原外卖骑手小黄在一天内有 n 个可选的配送任务每个任务有一个开始时间 l 和一个结束时间 r取整数骑手在同一时间只能做一个任务且一个任务结束的瞬间可以立刻开始下一个任务。请问小黄一天最多能完成多少个配送任务 输入第一行为 n接下来 n 行每行两个整数 l 和 r。 输出一个整数表示最多能完成的任务数。考察点分析经典“最大不相交区间数量”问题。贪心策略的选择按结束时间排序每次选择结束时间最早且与已选区间不冲突的区间。为什么按结束时间排序是对的而不是按开始时间或区间长度题解思路这道题和《算法竞赛入门经典》里的“区间调度问题”一模一样只是换了个外卖场景的外壳。贪心策略是把所有区间按右端点升序排序然后从左到右扫描维护一个 last 变量记录上一个选中任务的结束时间如果当前任务的开始时间不小于 last就选择它并更新 last 为当前任务的结束时间。为什么要按结束时间排序道理很简单在可选区间中结束时间越早给后面留下的时间就越多这个选择从贪心角度是最优的。如果按开始时间排序或者按区间长度排序很容易构造出反例。参考代码Javaimport java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[][] tasks new int[n][2]; for (int i 0; i n; i) { tasks[i][0] sc.nextInt(); tasks[i][1] sc.nextInt(); } // 按结束时间升序排序 Arrays.sort(tasks, (a, b) - a[1] - b[1]); int ans 0; int lastEnd 0; for (int[] t : tasks) { if (t[0] lastEnd) { ans; lastEnd t[1]; } } System.out.println(ans); } }复杂度分析排序 O(n log n)扫描 O(n)空间 O(1)。这个复杂度在笔试中是标准的“秒杀级”。考场提示这里有一个容易出错的细节“一个任务结束的瞬间可以立刻开始下一个任务”意味着边界条件是t[0] lastEnd而不是t[0] lastEnd。别小看这个等号丢了这个等号所有首尾相接的用例都会算错。另外输入如果是乱序的一定要记得先排序再扫描。2.3 第三题带权接单最大化收益动态规划 二分题目描述还原骑手小蓝一天内可以接多个配送任务每个任务 i 有三个属性开始时间 l_i、结束时间 r_i、完成后的收益 p_i。骑手在同一时间只能做一个任务每个任务只能选做或不做任务结束的瞬间可以立刻开始下一个任务。请问小蓝一天最多能赚到多少收益 输入第一行为 n接下来 n 行每行三个整数 l, r, p。 输出一个整数表示最大收益。考察点分析第二题的升级版从“区间数量最多”变成“带权收益最大”。核心是带权区间调度问题需要动态规划。第二个考察点是二分查找需要在排序后的结束时间数组中快速定位“当前任务开始时间之前最后一个结束的任务”。题解思路这题是整场笔试的分水岭。第一反应可能会想用贪心但带权区间调度用贪心是错的简单反例两个短任务收益各1一个长任务覆盖它们收益3贪心选两个短任务只赚2最优应该选长任务赚3。正确做法是动态规划。先把所有任务按结束时间升序排序设 dp[i] 表示前 i 个任务中能获得的最大收益。 转移方程是不选第 i 个任务dp[i] dp[i-1]选第 i 个任务需要找到“结束时间不超过 l_i 的最后一个任务”的下标 j则 dp[i] dp[j] p_i两者取较大值。dp[0] 应该初始化为0表示一个任务都不选时的收益。这里最需要小心的就是二分查找。我们要找的是“最后一个结束时间不大于当前任务开始时间的任务下标”如果用系统自带的 binarySearch 需要处理“找不到时返回负数插入点”的细节容易踩坑。我建议手写一个二分// 在 a[0..r] 中找最后一个 key 的下标 static int searchLastLE(int[] a, int r, int key) { int left 0, right r; int ans 0; // 如果不存在返回0此时 dp[0] 0 while (left right) { int mid (left right) 1; if (a[mid] key) { ans mid; left mid 1; // 继续往右找 } else { right mid - 1; } } return ans; }参考代码Javaimport java.util.*; public class Main { static class Job { int l, r, p; Job(int l, int r, int p) { this.l l; this.r r; this.p p; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); Job[] jobs new Job[n 1]; // 下标从1开始方便dp for (int i 1; i n; i) { int l sc.nextInt(); int r sc.nextInt(); int p sc.nextInt(); jobs[i] new Job(l, r, p); } // 按结束时间升序排序 Arrays.sort(jobs, 1, n 1, (a, b) - a.r - b.r); int[] end new int[n 1]; int[] dp new int[n 1]; for (int i 1; i n; i) { end[i] jobs[i].r; } for (int i 1; i n; i) { int j searchLastLE(end, i - 1, jobs[i].l); dp[i] Math.max(dp[i - 1], dp[j] jobs[i].p); } System.out.println(dp[n]); } static int searchLastLE(int[] a, int r, int key) { int left 0, right r; int ans 0; while (left right) { int mid (left right) 1; if (a[mid] key) { ans mid; left mid 1; } else { right mid - 1; } } return ans; } }复杂度分析排序 O(n log n)每个任务做一次二分 O(log n)总复杂度 O(n log n)空间 O(n)。如果数据范围到十万级别这个复杂度是完全可以过的。考场提示dp 数组和 jobs 下标最好从1开始这样 dp[0]0 天然表示“没有任务可选时收益为0”避免初始化麻烦。二分返回的 j 表示“结束时间小于等于当前任务开始时间的最新任务下标”也就是当前任务之前可以无冲突执行的所有任务中排序序号最大的那个。如果二分写不熟练有一段时间没手写过考场上建议先在草稿纸上画几个边界用例验证一下思路再动手写代码。2.4 第四题商圈热力区间查询线段树题目描述还原小团管理着一排 n 个商圈每个商圈有一个热力值 a_i。需要支持两种操作修改将第 x 个商圈的热力值修改为 y。查询查询区间 [l, r] 内所有商圈的热力值之和以及区间内的最大热力值。 输入第一行 n第二行 n 个整数第三行 m接下来 m 行每行第一个整数 opop1 表示修改后面跟 x 和 yop2 表示查询后面跟 l 和 r。 输出每次查询输出一行两个整数分别是区间和与区间最大值。考察点分析单点修改、区间查询这是线段树的经典应用场景。一个线段树节点需要同时维护两个信息区间和、区间最大值。也可以用树状数组维护前缀和但树状数组不太好维护区间最大值所以这题线段树是更自然的选择。题解思路这题放在第四题难度梯度一下子拉上来了。核心就是建一棵线段树每个节点存两个值sum 和 max。修改操作是单点更新需要从根递归到叶子改完叶子的值后再递归回溯更新父亲节点。查询操作是标准区间查询递归过程中判断当前节点覆盖的区间是否完全在查询区间内是就直接返回否则分别递归左右子树。线段树的实现细节很多数组要开 4 倍 n、递归边界是 lr、向上合并 pushUp 时要同时更新 sum 和 max。这些点每一处都是失分点但只要写过几遍模板整体不难。参考代码Javaimport java.util.*; public class Main { static int[] a, sum, max; static int n; public static void main(String[] args) { Scanner sc new Scanner(System.in); n sc.nextInt(); a new int[n 1]; sum new int[4 * n 5]; max new int[4 * n 5]; for (int i 1; i n; i) { a[i] sc.nextInt(); } build(1, 1, n); int m sc.nextInt(); while (m-- 0) { int op sc.nextInt(); int x sc.nextInt(); int y sc.nextInt(); if (op 1) { update(1, 1, n, x, y); } else { int[] res query(1, 1, n, x, y); // res[0] 是区间和res[1] 是区间最大值 System.out.println(res[0] res[1]); } } } static void build(int p, int l, int r) { if (l r) { sum[p] a[l]; max[p] a[l]; return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); pushUp(p); } static void update(int p, int l, int r, int pos, int val) { if (l r) { sum[p] val; max[p] val; return; } int mid (l r) 1; if (pos mid) { update(p 1, l, mid, pos, val); } else { update(p 1 | 1, mid 1, r, pos, val); } pushUp(p); } static int[] query(int p, int l, int r, int L, int R) { if (L l r R) { return new int[]{sum[p], max[p]}; } int mid (l r) 1; int s 0; int mx Integer.MIN_VALUE; if (L mid) { int[] left query(p 1, l, mid, L, R); s left[0]; mx Math.max(mx, left[1]); } if (R mid) { int[] right query(p 1 | 1, mid 1, r, L, R); s right[0]; mx Math.max(mx, right[1]); } return new int[]{s, mx}; } static void pushUp(int p) { sum[p] sum[p 1] sum[p 1 | 1]; max[p] Math.max(max[p 1], max[p 1 | 1]); } }复杂度分析建树 O(n)单次修改和查询都是 O(log n)总复杂度 O((n m) log n)空间 O(4n)。如果数据范围是十万甚至百万级别这个复杂度是必须的暴力算法一定会超时。考场提示数组开 4 倍空间是保守估计千万不要开成 2 倍 n那样在递归边界情况下必然越界。如果笔试环境允许这题可以考虑用树状数组维护前缀和配合一个稀疏表或另一棵线段树维护区间最大值但实现起来比单独一棵线段树复杂不建议在考场上临时换思路。Java 的 Scanner 在大数据量读取时性能一般如果遇到超时可以考虑用 BufferedReader 快读。美团笔试一般不限语言Java 上考场时这点要提前心里有数。3. 实战复盘从读题到AC的完整思路3.1 读题阶段的三个动作很多同学做笔试是“读完题就开始写代码”这是大忌。我通常拿到题目后先做三件事第一把题目里的业务名词翻译成算法术语比如“商圈热力值”就是数组元素“配送任务”就是区间第二把输入输出格式看死尤其是多个测试用例时到底读到哪一行结束第三判断数据范围这决定了我用 O(n^2) 还是必须上 O(n log n) 甚至 O(n)。以第9场这套题为例第一题读完我就知道是哈希排序第二题读完我就知道是区间贪心第三题读完发现“收益最大化”而不是“数量最多”立刻意识到是带权DP第四题看到“区间求和区间最值单点修改”三件套直接锁定线段树。整个过程大概只用30秒。这30秒的价值远高于多写30行代码因为我避免了一上来就写一个“差不多”但实际错得离谱的方案。3.2 时间分配的实操策略考试时我习惯先花3-5分钟把四道题全部扫一遍标注每道题的难度判断然后按“先易后难、先保底后冲高”的顺序做。第9场这套题我给第一题留了10分钟第二题留了20分钟第三题留了35分钟第四题留了30分钟最后留10分钟检查边界和交卷。这个时间分配不是固定的但原则是绝不在一道题上死磕超过40分钟。如果第三题40分钟还没想通转移方程我会果断写一个暴力或部分分版本把时间留给第四题。毕竟考的是总分不是某一道题的对错。3.3 从部分分到AC的路线我观察到一个很有用的考场策略即使是会做的题也先从暴力版本开始写然后逐步优化。比如第三题如果你一时想不起来二分怎么定位“最后一个结束时间不大于当前开始时间的任务”没关系可以先写一个 O(n^2) 的DPfor (int i 1; i n; i) { dp[i] dp[i - 1]; for (int j i - 1; j 0; j--) { if (jobs[j].r jobs[i].l) { dp[i] Math.max(dp[i], dp[j] jobs[i].p); break; // 从后往前第一个满足的就是最优的那个 j } } }这个 O(n^2) 版本在 n 比较小的时候能拿大部分分也帮我验证了DP方程的正确性。等暴力过了样例再改成二分查找AC就是水到渠成的事。这个“先过样例再调复杂度”的流程能大幅降低写代码时的心理压力。4. 高频失分点与问题排查实录4.1 最容易出事的五个细节我每年都会帮学弟学妹们看笔试代码第9场这套题暴露出来的问题特别集中。第一个是第二题的边界等号问题“结束瞬间可以立刻开始下一个任务”很多人在t[0] lastEnd里漏写等号导致所有首尾相接的用例全错。第二个是第三题二分边界写错返回的下标越界或者找不到时返回了错误位置这个单独调试起来极其痛苦。第三个是第四题线段树空间开小了常见错误是只开 2n 而不是 4n一旦数据量上来直接数组越界。第四个是 Java 的Arrays.sort对二维数组排序时写错比较器方向导致贪心顺序反了。第五个是输入输出格式输出多了逗号、少了换行这些在笔试中都会扣分。这些问题单独看都不难但组合在一起就是笔试从“会做”到“AC”之间巨大的鸿沟。我的经验是每道题写完代码后不要急着提交先用题目给的样例跑一遍再自己构造两个边界用例比如 n1、区间首尾相接、查询区间恰好是整个数组等这些用例成本低但能暴露绝大多数细节错误。4.2 本地对拍与边界测试技巧这里分享一个实用技巧。写完后在本地IDE里准备一个对拍脚本写一个暴力解和正解用随机数据反复跑比较两个代码的输出。这个方法在第三题和第四题上尤其好用。第三题的 O(n^2) 暴力DP可以作为对拍基准验证二分优化版的正确性第四题可以用暴力遍历区间的方法作为基准验证线段树的查询结果。随机生成小规模数据比如 n 从1到20随机生成 l、r、p跑1000组如果输出全部一致就能极大提高AC的信心。我试过很多次对拍找出来的bug通常是二分边界和线段树合并逻辑的问题这些靠肉眼很难看出来但随机数据一跑就原形毕露。这个方法在校招笔试准备阶段非常值得花时间掌握它比盲目刷题效率高得多。4.3 笔试环境下的排查顺序真到了笔试现场没有IDE对拍怎么办我的排查顺序是先看编译是否通过再看样例是否通过然后构造三组小边界用例手算验证最后一个一个打印中间变量。打印中间变量是考场上最笨但最有效的方法。比如第三题我会打印end数组和每次二分返回的j对照手算的结果判断二分对不对。第四题我会打印每次 build 后每个节点的 sum 和 max在纸上画出树结构来核对。很多人不敢用打印调试觉得浪费时间。但实际上笔试环境没有断点调试功能打印调试是最可靠的定位手段。我见过太多人盯着代码看十分钟找不到bug打印一行输出就立刻发现问题。记住代码不是写出来就完了调试能力同样是校招考察的隐形能力。5. 给备战校招的人几句实在话刷题方向要跟着目标公司的出题风格走。美团这套笔试题给我最大的启发是它不追求偏题怪题而是把经典算法放进业务场景里考所以你准备的时候不要一门心思钻难题要把哈希、排序、贪心、DP、线段树、并查集这些基础算法吃透尤其是能够快速识别“题目背后是哪个算法模型”。针对这套题的具体建议第一题和第二题必须是“肌肉记忆”级别的熟练度因为它们是保底分第三题这种“DP二分”的组合是美团笔试的高频套路建议专门练一练带权区间调度、最长上升子序列这类的二分优化DP第四题线段树属于中高级数据结构至少要能手写单点修改区间查询的模板不需要会复杂的懒标记但基本的 pushUp、build、query、update 四个函数要能闭着眼写出来。最后说个个人经验第9场这套题里第三题和第四题对“细节”的要求远远高于对“思路”的要求。很多人一看题就知道用什么算法但一写就错。这种“知道但写不对”的差距只能靠平时多写、多对拍、多总结边界条件来弥补。校招笔试不是比拼智力而是比拼在压力环境下稳定输出的能力——这也是我复盘这套题最大的体会。