我当年准备秋招的时候刷过不少大厂的笔试真题拼多多2019秋招这套编程题合集给我留下的印象特别深。它不像有些公司那样上来就甩一道动态规划压轴题而是把贪心、字符串处理、排序、模拟这些基础考点翻来覆去地揉进题目里难度梯度拉得很开既有让大部分人能拿分的“签到题”也有需要冷静推导才能啃下来的“拉分题”。这篇文章我就按自己记忆里的版本把这份合集里三道很有代表性的题目拆开揉碎讲一遍不管你是正在准备秋招的应届生还是想练手基础算法的工程师都能从里面捞到点东西。先说明一点题目描述是我按当年看到的版本整理归纳的细节可能和原题有出入但核心考点和做题思路是完全一致的。我尽量把“为什么这么想”讲透而不是只贴一段代码让你背。1. 拼多多2019秋招编程题的核心考点拆解1.1 为什么这套题偏爱“贪心字符串”看完整份合集你会发现一个很明显的倾向题目非常喜欢把贪心策略藏在字符串或者数组操作里面。表面上是让你处理一串数字、一堆数实际上考的是你能不能找到一个“局部最优能推出全局最优”的结论。这其实很符合笔试的筛选逻辑——在两个小时左右的时间里面试官没指望你能写出多么精巧的复杂算法他更想看到你面对一个不熟悉的业务场景时能不能快速抽象出问题本质然后用最常见的枚举、排序、滑动窗口、堆这些工具把它解决掉。贪心之所以被偏爱是因为它的思维门槛和代码量都比较适合笔试场景。一个贪心策略想清楚了代码往往二十行就写完想不清楚你可能会写一个DFS或者动态规划一样能做但调试时间成倍上涨。生活里也有类似的经验餐厅高峰时段出餐考的不是厨师会不会做满汉全席而是能不能在菜品固定、资源有限的情况下快速判断先做哪桌、后做哪桌让翻台率最高。笔试里的贪心题考的就是这种“快速判断先后顺序”的能力。1.2 难度分层与答题顺序这套题目的难度大致可以分为三档。第一档是简单模拟题基本不需要什么算法思想照着规则写循环就能过这种题的目标是“必须全对”不能因为粗心丢分。第二档是中等贪心题需要你先发现一个规律比如“局部最优能推出全局最优”再结合排序或者滑动窗口去实现这类题决定了你笔试能不能过线。第三档是相对综合的题可能要用到堆、优先队列或者更复杂的枚举优化这类题是用来区分高分的能写出暴力解拿到部分分也是好的。我自己的做题顺序是先把所有题目都读一遍按照“模拟题 贪心题 综合题”的顺序做。模拟题最快拿分先把心态稳住贪心题需要一点灵感和推导放到中间综合题如果十分钟内没有思路先写一个暴力版本保住部分分绝不要在一道题上死磕到时间用完。这个策略在拼多多这套题里特别适用因为它的题目之间并没有互相依赖每一道都是独立的得分点。2. 经典题目一靓号方案的最少修改次数2.1 题意还原把号码改成连续m个相同数字这道题是典型的生活化包装。题目说手机号码里出现连续相同数字比如“888”“666”会被当成靓号。现在你有一个长度为n的数字串目标是让这个串中某一段连续m个位置的数字变得完全相同问你最少需要修改其中的多少位。每次修改可以把任意一位数字改成0到9之间的任意数字修改一位计一次操作。举个例子假设数字串是“12893”m3。你会发现原串里没有任何连续3个相同的数字。如果目标数字是8我们可以把第1位1改成8得到“82893”这里“88”只有2个连续不满足再把第2位2改成8得到“88893”连续3个8修改了2位这就是一个可行方案。但有没有可能只改1位就凑出连续3个相同数字你看“12893”里位置2、3、4分别是2、8、9没有相同位置1、2、3分别是1、2、8也没有相同位置3、4、5分别是8、9、3还是没有相同。所以这个例子最少需要修改2位。这种题如果直接上手去模拟“改哪几位”很容易绕晕。正确的打开方式是反过来想先锁定连续m个位最终要变成哪个数字再看哪些位本来就是这个数字剩下的就是必须改的位。2.2 解题思路枚举目标数字滑动窗口因为数字只有0到9十种可能所以连续相同数字的目标数字一定是这十个数字之一。我们可以依次假设目标数字是c然后遍历所有长度为m的连续窗口看每个窗口里有多少个位置的数字不等于c这些位置就是需要修改的位置。窗口内不等于c的位置数量越少说明修改次数越少。为了快速求出每个窗口里不等于c的个数可以用前缀和数组。定义一个数组prepre[i]表示字符串前i个字符中不等于c的字符个数。那么从位置l开始、长度为m的窗口也就是区间[l, lm-1]里面不等于c的个数就是pre[lm] - pre[l]。我们只需要枚举所有合法的起始位置l取这个差的最小值然后对十个c都做一遍同样的操作全局最小值就是答案。这个思路的时间复杂度是O(10 * n)也就是O(n)对于笔试的数据范围来说非常稳。空间上用一个前缀和数组就够如果要求更省内存也可以直接维护一个滑动窗口的计数器在移动窗口的时候更新把空间降到O(1)。不过笔试里O(n)空间完全可以接受我建议先用最清晰的前缀和写法保证正确性优先。2.3 完整代码实现C下面这段代码是按上面的思路实现的可以直接在在线评测系统里编译运行。#include bits/stdc.h using namespace std; int main() { int n, m; string s; cin n m s; int ans n; for (char c 0; c 9; c) { vectorint pre(n 1, 0); for (int i 0; i n; i) { pre[i 1] pre[i] (s[i] ! c ? 1 : 0); } for (int i 0; i m n; i) { int need pre[i m] - pre[i]; ans min(ans, need); } } cout ans endl; return 0; }代码本身不长但有几个细节值得展开说。第一个细节是外层循环遍历的是字符‘0’到‘9’不是数字0到9写的时候要注意字符字面量的引号。第二个细节是前缀和数组pre的长度是n1pre[0]始终为0这样处理区间和的时候不需要额外判空。第三个细节是初始ans直接设成n因为最坏情况下整个串全改一遍最多也就n次这个初值一定不会让答案漏掉。2.4 这道题最容易踩的三个坑第一个坑是“目标数字”想当然地认为一定是原串里出现过的数字。这是最容易犯的错误。原串里没有‘0’但把某一段全改成‘0’的修改次数可能比改成任意一个出现过数字都少。所以枚举目标数字时十个数字都要遍历不能偷懒。第二个坑是忽略了窗口可以不是原串中已经存在相同数字的起始位置。有些同学为了少改几步只去看原串中“已经有两个连续相同数字”的地方然后试图在这个基础上扩展。这在笔试里会漏掉很多情况因为最佳窗口可能恰好落在原串里完全没有任何重复数字的位置。滑动窗口枚举所有起始位置才能保证不漏解。第三个坑是边界条件。如果m大于n理论上不可能存在长度为m的字串但题目一般会保证mn。如果遇到不保证的情况我建议在开头加一个判断直接输出-1或者按题目要求处理。另外如果原串本身就满足条件ans会被更新成0这是正确的结果不要觉得答案必须是正数。3. 经典题目二最大拼接数3.1 题意还原n个数拼成最大值这道题在拼多多这套题里算比较“友好”的但也是很多人在排序比较器上栽跟头的一道题。题目大意是给定n个非负整数你可以改变它们的排列顺序要求把它们全部拼接成一个数输出这个数能得到的最大值。比如给出[3, 30, 34, 5, 9]最大的拼接结果是“9534330”如果只是按数字大小降序排列得到“5343309”显然不是最优。为什么不能直接按数字大小排序因为数字大小和拼接后的字符串长度、前缀都有关系。比如3和303比30小但拼接时“330”比“303”大所以3应该排在30前面。这说明决定顺序的关键不是数值大小而是“谁放在前面能让拼接结果更大”。这种题的标准解法是自定义排序比较器比较两个数a和b时把a和b都转成字符串然后比较ab和ba的字典序如果ab更大就让a排在b前面。这个比较器看着简单但它背后的直觉很重要——两个数拼接的结果只有两种可能要么a在前要么b在前二选一里取字典序更大的那个就能保证整体的最终结果最优。3.2 排序比较器的选择为什么不能直接按数字大小很多第一次做这道题的同学会问为什么贪心策略是成立的两个数之间选更优的拼接方式局部最优真的能推出全局最优吗答案是能但这个结论并不显然。严格证明需要说明这个比较器满足传递性也就是说如果a应该排在b前面b应该排在c前面那么a也应该排在c前面。这个性质可以通过字符串拼接的数学性质来证明笔试的时候不需要写证明但心里要明白这不是“碰巧管用”。我个人建议在用Python刷题时用functools.cmp_to_key来传入自定义比较器如果用C就在sort的第三个参数里写一个lambda表达式。无论哪种语言都要关注比较的逻辑返回-1表示a应该排在b前面返回1表示b应该排在a前面这和Java里Comparator的compare方法语义一致。最容易出错的地方是直接把比较器写成a b这种数字大小比较那就完全背离了题意。3.3 完整代码实现PythonPython写这道题非常顺手因为字符串拼接和排序都是内置能力。完整代码如下import sys from functools import cmp_to_key def solve(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) nums data[1:1 n] if all(num 0 for num in nums): print(0) return def cmp(a, b): if a b b a: return -1 elif a b b a: return 1 else: return 0 nums.sort(keycmp_to_key(cmp)) print(.join(nums)) if __name__ __main__: solve()这里有个小细节我一开始就把输入转成了字符串列表而不是整数列表这样后面排序和拼接都不需要反复做类型转换。cmp函数里ab和ba都是字符串拼接所以比较的是字典序恰好和数字大小一致。排序完成后用join方法把所有字符串拼起来输出就是最终答案。3.4 边界情况全零输入这道题最经典的边界情况就是全零输入。如果输入是[0, 0, 0]排序后拼接出来的字符串是“000”但数字形式的答案应该是0。如果不做特殊处理程序就会输出“000”在OJ上直接判错。处理方式就是在排序前先判断一下如果所有数都是0直接输出单个“0”。也可以拼完之后判断结果字符串是否全是0再决定输出“000”还是“0”。我更喜欢前者因为更早返回逻辑更清晰。另外还有一种小坑是输入里可能有前导零的字符串形式比如“007”虽然题目一般不会出但万一遇到按字符串处理仍然能正确拼接因为拼接时“007”和“7”的字典序是符合数字直觉的。4. 经典题目三收银台排队模拟4.1 题意还原多个窗口的最短排队拼多多这套题里还有一类很实际的场景题我印象里是模拟超市收银台或者食堂打饭窗口。题目大意有m个收银台n个顾客按顺序到达每个顾客的服务时间是t[i]。顾客到达后会选择当前排队人数最少或者说最先空闲的收银台去排队问你所有顾客服务完成的总时间是多少。这类题考察的其实不是算法而是你能否把一个真实的排队过程用数据结构准确建模。最直观的模拟方式是开一个数组记录每个收银台当前排队的总耗时来一个顾客就把他加到耗时最少的窗口后面。但如果每次都用循环去找耗时最少的窗口复杂度是O(n*m)。当n和m都到十万级别时这个复杂度就撑不住了。正确的做法是用优先队列也就是小顶堆来维护每个收银台当前完成所有已分配顾客的时间戳。我们可以想象一下真实的排队场景收银台不是“窗口数组”而是一个个正在运行的线程谁先处理完手头的顾客谁就有空接收下一个人。所以我们需要快速找到“当前最早空闲”的那个收银台优先队列天生就是干这个的。4.2 用堆模拟的完整流程算法的流程可以拆成几步。第一步准备一个小顶堆堆里放的是每个收银台“完成当前所有已分配顾客后的时间”。初始时堆是空的。第二步依次遍历每个顾客如果当前堆的大小还不到m说明还有完全空闲的收银台直接把这个顾客分配到任意一台空闲台并把它变成该台的结束时间t[i]也就是把这个t[i]压入堆。第三步如果堆的大小已经等于m说明所有收银台都在忙我们取出堆顶元素cur它表示最早空闲的收银台的完成时间把当前顾客安排给它那么该收银台新的完成时间就是cur t[i]再把这个新时间压回堆里。这个过程不断重复最后堆里保存的是每个收银台最终完成所有顾客的时间。答案就是堆中的最大值。为什么不是最小值因为总时间取决于最晚完成的那台收银台而不是最早的。这里又有不少人会搞混。4.3 完整代码实现C我一般用C写这类模拟题因为priority_queue用起来很方便。完整代码如下#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorint t(n); for (int i 0; i n; i) { cin t[i]; } priority_queueint, vectorint, greaterint pq; for (int i 0; i n; i) { if ((int)pq.size() m) { pq.push(t[i]); } else { int cur pq.top(); pq.pop(); pq.push(cur t[i]); } } long long ans 0; while (!pq.empty()) { ans max(ans, (long long)pq.top()); pq.pop(); } cout ans endl; return 0; }注意priority_queue默认是大顶堆这里必须用greater 把它变成小顶堆否则取出的就是最晚完成的收银台整个逻辑就错了。另外当m大于等于n时每个顾客都有独立收银台答案就是所有t[i]的最大值代码里的if分支天然会处理这种情况不需要额外判断。4.4 模拟题的通用套路这种排队模拟题在笔试题里出现频率非常高而且变种很多。有的题目会让顾客按不同时间点到达这时候你不能简单按输入顺序处理而是要维护一个“当前时间”和“顾客到达时间”的双指针先处理已经到达的顾客再模拟时间推进。有的题目会让你输出每个收银台的排队人数分布这时候除了存完成时间还要额外维护人数。还有的题目会把服务时间改成随机的概率事件那就是另一套高级玩法了。遇到这类题我的经验是先画一条时间轴把“什么时候有人到达”“什么时候有人离开”标清楚再决定用优先队列还是普通队列。千万不要一上来就写代码模拟题的逻辑一旦理错后面全是白搭。优先队列能解决“每次找最早结束”的问题普通队列能解决“先来先服务”的问题两者结合几乎能覆盖所有的排队场景题。5. 笔试实战编程题答题的几条经验5.1 合理分配做题时间回到这份拼多多2019秋招部分编程题合集本身我认为它最有价值的不是某一道题的答案而是整份卷子的节奏感。拿到题目后我建议先花三到五分钟快速浏览所有题把每道题按“读懂了”“有点思路”“完全没思路”分三类。第一类立刻做第二类先写下核心思路再动手第三类放到最后。在单题上设置一个硬性的时间上限比如二十分钟超过这个时间还没调通果断写一个暴力版本或者直接跳到下一题。笔试不要求满分过线靠的是拿到所有该拿的分。5.2 输入输出与边界细节很多同学在本地IDE里跑得好好的一上在线评测系统就编译错误或者答案错误大部分问题出在输入输出处理上。比如题目说“多组测试数据”就需要while(cinn)循环处理如果字符串里可能包含空格就不要用cin s改用getline如果结果可能超过2的31次方记得用long long。这些都不是算法问题但每一条都可能导致整题零分。我在写的时候会先把数据范围圈出来凡是有加法、乘法的地方都用long long规避风险哪怕题目给的范围看起来不大。这点投入在笔试里非常划算。5.3 常见问题速查表下面这个表是我在刷题和实际笔试中总结出来的高频问题每一条都真实踩过坑你可以直接当成检查单来用。现象常见原因解决建议本地运行正常OJ显示编译错误用了C11特性但编译器版本低尽量不使用太新的语法或者确认平台支持的版本答案和样例不一致输入格式看错比如漏读了换行用断言或临时打印检查读入大量数据时超时用了O(n^2)暴力循环换成前缀和、滑动窗口或优先队列优化字符串排序结果不对比较器写成了数字比较用ab和ba做字典序比较输出“000”而不是“0”全零数字没有特判排序前或输出前判断是否全零整数溢出导致答案诡异int范围不够统一用long long存储中间结果优先队列取出的不是最早结束默认大顶堆使用greater 或存入负值这个表没有覆盖所有场景但覆盖了这份合集中三道题最容易出现的问题。你在做题时遇到奇怪的现象优先往输入输出格式和数据类型上排查大概率能找到原因。5.4 写在最后的一点个人体会刷完这套题我最大的体会是大厂笔试并不追求知识点的数量而是追求每个基础工具使用的熟练度。滑动窗口、前缀和、优先队列、自定义排序这几个东西翻来覆去地考但每次包装的业务场景都不一样。你需要的不是背题而是建立一种“读到问题就能联想到对应工具”的条件反射。我在实际准备中会刻意把常见工具分类整理成模板比如“求连续区间最优解优先想滑动窗口”“每次找最值并更新优先想堆”“两个元素按规则比较排序优先想自定义比较器”。拼多多这套题正好是检验这些模板的最好素材有时间的话不妨反复做两遍第一遍看重解法第二遍刻意不看答案自己限时重写效果会明显不一样。
拼多多2019秋招编程题解析：贪心、滑动窗口与堆的实战应用
我当年准备秋招的时候刷过不少大厂的笔试真题拼多多2019秋招这套编程题合集给我留下的印象特别深。它不像有些公司那样上来就甩一道动态规划压轴题而是把贪心、字符串处理、排序、模拟这些基础考点翻来覆去地揉进题目里难度梯度拉得很开既有让大部分人能拿分的“签到题”也有需要冷静推导才能啃下来的“拉分题”。这篇文章我就按自己记忆里的版本把这份合集里三道很有代表性的题目拆开揉碎讲一遍不管你是正在准备秋招的应届生还是想练手基础算法的工程师都能从里面捞到点东西。先说明一点题目描述是我按当年看到的版本整理归纳的细节可能和原题有出入但核心考点和做题思路是完全一致的。我尽量把“为什么这么想”讲透而不是只贴一段代码让你背。1. 拼多多2019秋招编程题的核心考点拆解1.1 为什么这套题偏爱“贪心字符串”看完整份合集你会发现一个很明显的倾向题目非常喜欢把贪心策略藏在字符串或者数组操作里面。表面上是让你处理一串数字、一堆数实际上考的是你能不能找到一个“局部最优能推出全局最优”的结论。这其实很符合笔试的筛选逻辑——在两个小时左右的时间里面试官没指望你能写出多么精巧的复杂算法他更想看到你面对一个不熟悉的业务场景时能不能快速抽象出问题本质然后用最常见的枚举、排序、滑动窗口、堆这些工具把它解决掉。贪心之所以被偏爱是因为它的思维门槛和代码量都比较适合笔试场景。一个贪心策略想清楚了代码往往二十行就写完想不清楚你可能会写一个DFS或者动态规划一样能做但调试时间成倍上涨。生活里也有类似的经验餐厅高峰时段出餐考的不是厨师会不会做满汉全席而是能不能在菜品固定、资源有限的情况下快速判断先做哪桌、后做哪桌让翻台率最高。笔试里的贪心题考的就是这种“快速判断先后顺序”的能力。1.2 难度分层与答题顺序这套题目的难度大致可以分为三档。第一档是简单模拟题基本不需要什么算法思想照着规则写循环就能过这种题的目标是“必须全对”不能因为粗心丢分。第二档是中等贪心题需要你先发现一个规律比如“局部最优能推出全局最优”再结合排序或者滑动窗口去实现这类题决定了你笔试能不能过线。第三档是相对综合的题可能要用到堆、优先队列或者更复杂的枚举优化这类题是用来区分高分的能写出暴力解拿到部分分也是好的。我自己的做题顺序是先把所有题目都读一遍按照“模拟题 贪心题 综合题”的顺序做。模拟题最快拿分先把心态稳住贪心题需要一点灵感和推导放到中间综合题如果十分钟内没有思路先写一个暴力版本保住部分分绝不要在一道题上死磕到时间用完。这个策略在拼多多这套题里特别适用因为它的题目之间并没有互相依赖每一道都是独立的得分点。2. 经典题目一靓号方案的最少修改次数2.1 题意还原把号码改成连续m个相同数字这道题是典型的生活化包装。题目说手机号码里出现连续相同数字比如“888”“666”会被当成靓号。现在你有一个长度为n的数字串目标是让这个串中某一段连续m个位置的数字变得完全相同问你最少需要修改其中的多少位。每次修改可以把任意一位数字改成0到9之间的任意数字修改一位计一次操作。举个例子假设数字串是“12893”m3。你会发现原串里没有任何连续3个相同的数字。如果目标数字是8我们可以把第1位1改成8得到“82893”这里“88”只有2个连续不满足再把第2位2改成8得到“88893”连续3个8修改了2位这就是一个可行方案。但有没有可能只改1位就凑出连续3个相同数字你看“12893”里位置2、3、4分别是2、8、9没有相同位置1、2、3分别是1、2、8也没有相同位置3、4、5分别是8、9、3还是没有相同。所以这个例子最少需要修改2位。这种题如果直接上手去模拟“改哪几位”很容易绕晕。正确的打开方式是反过来想先锁定连续m个位最终要变成哪个数字再看哪些位本来就是这个数字剩下的就是必须改的位。2.2 解题思路枚举目标数字滑动窗口因为数字只有0到9十种可能所以连续相同数字的目标数字一定是这十个数字之一。我们可以依次假设目标数字是c然后遍历所有长度为m的连续窗口看每个窗口里有多少个位置的数字不等于c这些位置就是需要修改的位置。窗口内不等于c的位置数量越少说明修改次数越少。为了快速求出每个窗口里不等于c的个数可以用前缀和数组。定义一个数组prepre[i]表示字符串前i个字符中不等于c的字符个数。那么从位置l开始、长度为m的窗口也就是区间[l, lm-1]里面不等于c的个数就是pre[lm] - pre[l]。我们只需要枚举所有合法的起始位置l取这个差的最小值然后对十个c都做一遍同样的操作全局最小值就是答案。这个思路的时间复杂度是O(10 * n)也就是O(n)对于笔试的数据范围来说非常稳。空间上用一个前缀和数组就够如果要求更省内存也可以直接维护一个滑动窗口的计数器在移动窗口的时候更新把空间降到O(1)。不过笔试里O(n)空间完全可以接受我建议先用最清晰的前缀和写法保证正确性优先。2.3 完整代码实现C下面这段代码是按上面的思路实现的可以直接在在线评测系统里编译运行。#include bits/stdc.h using namespace std; int main() { int n, m; string s; cin n m s; int ans n; for (char c 0; c 9; c) { vectorint pre(n 1, 0); for (int i 0; i n; i) { pre[i 1] pre[i] (s[i] ! c ? 1 : 0); } for (int i 0; i m n; i) { int need pre[i m] - pre[i]; ans min(ans, need); } } cout ans endl; return 0; }代码本身不长但有几个细节值得展开说。第一个细节是外层循环遍历的是字符‘0’到‘9’不是数字0到9写的时候要注意字符字面量的引号。第二个细节是前缀和数组pre的长度是n1pre[0]始终为0这样处理区间和的时候不需要额外判空。第三个细节是初始ans直接设成n因为最坏情况下整个串全改一遍最多也就n次这个初值一定不会让答案漏掉。2.4 这道题最容易踩的三个坑第一个坑是“目标数字”想当然地认为一定是原串里出现过的数字。这是最容易犯的错误。原串里没有‘0’但把某一段全改成‘0’的修改次数可能比改成任意一个出现过数字都少。所以枚举目标数字时十个数字都要遍历不能偷懒。第二个坑是忽略了窗口可以不是原串中已经存在相同数字的起始位置。有些同学为了少改几步只去看原串中“已经有两个连续相同数字”的地方然后试图在这个基础上扩展。这在笔试里会漏掉很多情况因为最佳窗口可能恰好落在原串里完全没有任何重复数字的位置。滑动窗口枚举所有起始位置才能保证不漏解。第三个坑是边界条件。如果m大于n理论上不可能存在长度为m的字串但题目一般会保证mn。如果遇到不保证的情况我建议在开头加一个判断直接输出-1或者按题目要求处理。另外如果原串本身就满足条件ans会被更新成0这是正确的结果不要觉得答案必须是正数。3. 经典题目二最大拼接数3.1 题意还原n个数拼成最大值这道题在拼多多这套题里算比较“友好”的但也是很多人在排序比较器上栽跟头的一道题。题目大意是给定n个非负整数你可以改变它们的排列顺序要求把它们全部拼接成一个数输出这个数能得到的最大值。比如给出[3, 30, 34, 5, 9]最大的拼接结果是“9534330”如果只是按数字大小降序排列得到“5343309”显然不是最优。为什么不能直接按数字大小排序因为数字大小和拼接后的字符串长度、前缀都有关系。比如3和303比30小但拼接时“330”比“303”大所以3应该排在30前面。这说明决定顺序的关键不是数值大小而是“谁放在前面能让拼接结果更大”。这种题的标准解法是自定义排序比较器比较两个数a和b时把a和b都转成字符串然后比较ab和ba的字典序如果ab更大就让a排在b前面。这个比较器看着简单但它背后的直觉很重要——两个数拼接的结果只有两种可能要么a在前要么b在前二选一里取字典序更大的那个就能保证整体的最终结果最优。3.2 排序比较器的选择为什么不能直接按数字大小很多第一次做这道题的同学会问为什么贪心策略是成立的两个数之间选更优的拼接方式局部最优真的能推出全局最优吗答案是能但这个结论并不显然。严格证明需要说明这个比较器满足传递性也就是说如果a应该排在b前面b应该排在c前面那么a也应该排在c前面。这个性质可以通过字符串拼接的数学性质来证明笔试的时候不需要写证明但心里要明白这不是“碰巧管用”。我个人建议在用Python刷题时用functools.cmp_to_key来传入自定义比较器如果用C就在sort的第三个参数里写一个lambda表达式。无论哪种语言都要关注比较的逻辑返回-1表示a应该排在b前面返回1表示b应该排在a前面这和Java里Comparator的compare方法语义一致。最容易出错的地方是直接把比较器写成a b这种数字大小比较那就完全背离了题意。3.3 完整代码实现PythonPython写这道题非常顺手因为字符串拼接和排序都是内置能力。完整代码如下import sys from functools import cmp_to_key def solve(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) nums data[1:1 n] if all(num 0 for num in nums): print(0) return def cmp(a, b): if a b b a: return -1 elif a b b a: return 1 else: return 0 nums.sort(keycmp_to_key(cmp)) print(.join(nums)) if __name__ __main__: solve()这里有个小细节我一开始就把输入转成了字符串列表而不是整数列表这样后面排序和拼接都不需要反复做类型转换。cmp函数里ab和ba都是字符串拼接所以比较的是字典序恰好和数字大小一致。排序完成后用join方法把所有字符串拼起来输出就是最终答案。3.4 边界情况全零输入这道题最经典的边界情况就是全零输入。如果输入是[0, 0, 0]排序后拼接出来的字符串是“000”但数字形式的答案应该是0。如果不做特殊处理程序就会输出“000”在OJ上直接判错。处理方式就是在排序前先判断一下如果所有数都是0直接输出单个“0”。也可以拼完之后判断结果字符串是否全是0再决定输出“000”还是“0”。我更喜欢前者因为更早返回逻辑更清晰。另外还有一种小坑是输入里可能有前导零的字符串形式比如“007”虽然题目一般不会出但万一遇到按字符串处理仍然能正确拼接因为拼接时“007”和“7”的字典序是符合数字直觉的。4. 经典题目三收银台排队模拟4.1 题意还原多个窗口的最短排队拼多多这套题里还有一类很实际的场景题我印象里是模拟超市收银台或者食堂打饭窗口。题目大意有m个收银台n个顾客按顺序到达每个顾客的服务时间是t[i]。顾客到达后会选择当前排队人数最少或者说最先空闲的收银台去排队问你所有顾客服务完成的总时间是多少。这类题考察的其实不是算法而是你能否把一个真实的排队过程用数据结构准确建模。最直观的模拟方式是开一个数组记录每个收银台当前排队的总耗时来一个顾客就把他加到耗时最少的窗口后面。但如果每次都用循环去找耗时最少的窗口复杂度是O(n*m)。当n和m都到十万级别时这个复杂度就撑不住了。正确的做法是用优先队列也就是小顶堆来维护每个收银台当前完成所有已分配顾客的时间戳。我们可以想象一下真实的排队场景收银台不是“窗口数组”而是一个个正在运行的线程谁先处理完手头的顾客谁就有空接收下一个人。所以我们需要快速找到“当前最早空闲”的那个收银台优先队列天生就是干这个的。4.2 用堆模拟的完整流程算法的流程可以拆成几步。第一步准备一个小顶堆堆里放的是每个收银台“完成当前所有已分配顾客后的时间”。初始时堆是空的。第二步依次遍历每个顾客如果当前堆的大小还不到m说明还有完全空闲的收银台直接把这个顾客分配到任意一台空闲台并把它变成该台的结束时间t[i]也就是把这个t[i]压入堆。第三步如果堆的大小已经等于m说明所有收银台都在忙我们取出堆顶元素cur它表示最早空闲的收银台的完成时间把当前顾客安排给它那么该收银台新的完成时间就是cur t[i]再把这个新时间压回堆里。这个过程不断重复最后堆里保存的是每个收银台最终完成所有顾客的时间。答案就是堆中的最大值。为什么不是最小值因为总时间取决于最晚完成的那台收银台而不是最早的。这里又有不少人会搞混。4.3 完整代码实现C我一般用C写这类模拟题因为priority_queue用起来很方便。完整代码如下#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorint t(n); for (int i 0; i n; i) { cin t[i]; } priority_queueint, vectorint, greaterint pq; for (int i 0; i n; i) { if ((int)pq.size() m) { pq.push(t[i]); } else { int cur pq.top(); pq.pop(); pq.push(cur t[i]); } } long long ans 0; while (!pq.empty()) { ans max(ans, (long long)pq.top()); pq.pop(); } cout ans endl; return 0; }注意priority_queue默认是大顶堆这里必须用greater 把它变成小顶堆否则取出的就是最晚完成的收银台整个逻辑就错了。另外当m大于等于n时每个顾客都有独立收银台答案就是所有t[i]的最大值代码里的if分支天然会处理这种情况不需要额外判断。4.4 模拟题的通用套路这种排队模拟题在笔试题里出现频率非常高而且变种很多。有的题目会让顾客按不同时间点到达这时候你不能简单按输入顺序处理而是要维护一个“当前时间”和“顾客到达时间”的双指针先处理已经到达的顾客再模拟时间推进。有的题目会让你输出每个收银台的排队人数分布这时候除了存完成时间还要额外维护人数。还有的题目会把服务时间改成随机的概率事件那就是另一套高级玩法了。遇到这类题我的经验是先画一条时间轴把“什么时候有人到达”“什么时候有人离开”标清楚再决定用优先队列还是普通队列。千万不要一上来就写代码模拟题的逻辑一旦理错后面全是白搭。优先队列能解决“每次找最早结束”的问题普通队列能解决“先来先服务”的问题两者结合几乎能覆盖所有的排队场景题。5. 笔试实战编程题答题的几条经验5.1 合理分配做题时间回到这份拼多多2019秋招部分编程题合集本身我认为它最有价值的不是某一道题的答案而是整份卷子的节奏感。拿到题目后我建议先花三到五分钟快速浏览所有题把每道题按“读懂了”“有点思路”“完全没思路”分三类。第一类立刻做第二类先写下核心思路再动手第三类放到最后。在单题上设置一个硬性的时间上限比如二十分钟超过这个时间还没调通果断写一个暴力版本或者直接跳到下一题。笔试不要求满分过线靠的是拿到所有该拿的分。5.2 输入输出与边界细节很多同学在本地IDE里跑得好好的一上在线评测系统就编译错误或者答案错误大部分问题出在输入输出处理上。比如题目说“多组测试数据”就需要while(cinn)循环处理如果字符串里可能包含空格就不要用cin s改用getline如果结果可能超过2的31次方记得用long long。这些都不是算法问题但每一条都可能导致整题零分。我在写的时候会先把数据范围圈出来凡是有加法、乘法的地方都用long long规避风险哪怕题目给的范围看起来不大。这点投入在笔试里非常划算。5.3 常见问题速查表下面这个表是我在刷题和实际笔试中总结出来的高频问题每一条都真实踩过坑你可以直接当成检查单来用。现象常见原因解决建议本地运行正常OJ显示编译错误用了C11特性但编译器版本低尽量不使用太新的语法或者确认平台支持的版本答案和样例不一致输入格式看错比如漏读了换行用断言或临时打印检查读入大量数据时超时用了O(n^2)暴力循环换成前缀和、滑动窗口或优先队列优化字符串排序结果不对比较器写成了数字比较用ab和ba做字典序比较输出“000”而不是“0”全零数字没有特判排序前或输出前判断是否全零整数溢出导致答案诡异int范围不够统一用long long存储中间结果优先队列取出的不是最早结束默认大顶堆使用greater 或存入负值这个表没有覆盖所有场景但覆盖了这份合集中三道题最容易出现的问题。你在做题时遇到奇怪的现象优先往输入输出格式和数据类型上排查大概率能找到原因。5.4 写在最后的一点个人体会刷完这套题我最大的体会是大厂笔试并不追求知识点的数量而是追求每个基础工具使用的熟练度。滑动窗口、前缀和、优先队列、自定义排序这几个东西翻来覆去地考但每次包装的业务场景都不一样。你需要的不是背题而是建立一种“读到问题就能联想到对应工具”的条件反射。我在实际准备中会刻意把常见工具分类整理成模板比如“求连续区间最优解优先想滑动窗口”“每次找最值并更新优先想堆”“两个元素按规则比较排序优先想自定义比较器”。拼多多这套题正好是检验这些模板的最好素材有时间的话不妨反复做两遍第一遍看重解法第二遍刻意不看答案自己限时重写效果会明显不一样。