拼多多2019秋招编程题全解析：从动态规划到贪心策略

拼多多2019秋招编程题合集，这套题在当年出来之后，网上讨论度一直挺高。最近又陆续有人翻出来问，说想拿它当秋招练手的材料，我趁着整理旧资料的机会，把这套题重新过了一遍，顺手把每道题的核心解法和踩过的坑写下来。文章会按照题目类型拆开讲，不只给答案，也会说清楚每一道题背后的“出题逻辑”，这样你刷题的时候就不会只记住孤立题解，而是能理解拼多多这类大厂笔试到底在考什么。

无论你现在刷题是为了准备秋招笔试，还是单纯想提升算法能力，这套题都值得认真做一遍。它覆盖面比较均衡，代码量不大，但对思路的考察很扎实，属于那种“看起来不难，写起来容易卡壳”的典型题目。我在下面整理的就是当时刷题时做的拆解和复盘，有些点可能比标准题解更啰嗦，但都是实打实踩过坑之后得出的经验。

1. 拼多多2019秋招编程题的整体画像：题量、难度与知识点分布

先说我对这套题的整体感觉。拼多多笔试的编程题一般是四道左右，考试时间在100分钟左右，题面会故意包装成业务场景，比如“多多果园”“多多买菜”之类，但你扒开外壳往里看，基本都是经典算法题换了套皮肤。这个特点在2019年秋招这轮就很明显了。

从题量看，四道题覆盖的知识点大概是：第一道排序加位运算，第二道动态规划，第三道图的遍历，第四道贪心加堆。没有特别偏门的算法，也没有需要十几行大模板的题目，整体难度梯度做得比较合理。第一题基本是送分题，用来稳住心态；中间两道题是主力，能给大多数人造成一点压力；最后一道压轴题则负责拉开分数差距。

这里有一个容易被忽略的点：拼多多笔试的输入输出格式比较折腾。很多题不是给你一个数组然后返回排序结果，而是需要你从标准输入里读取多行数据，处理完了再用指定格式打印出来。不少人在牛客网刷习惯了核心代码模式，到了笔试现场遇到ACM模式就慌了，光是读输入输出就浪费了十五分钟。这个问题在你练这套题的时候就要刻意克服，建议全部用sys.stdin.read()或者带缓冲的读取方式处理，一次性把数据读完，别用input()一行行读，在数据量大的时候会明显拖慢速度。

再一个是时间复杂度的隐性要求。题目数据范围通常不会直接写在题面最显眼的位置，有时候藏在输入格式里，有时候干脆放在备注里，但它是决定你算法选择的唯一标准。我从这套题里看到，O(n^2)的解法在第二题和第四题是过不了全量数据的，必须往 O(n log n) 甚至 O(n) 去优化。

下面用一张表把这套题的主要特征汇总一下，方便你对整体有个把握。

代码量都不算大，这也是大厂笔试的共同特点——他们考的不是大工程能力，而是你能不能在小规模代码量里把思路想清楚，把边界条件处理干净。

再说说这套题里最容易翻车的地方。第一是读题不仔细，题目里“附加条件”特别多，很容易漏看，比如第二题的连续采摘，题目描述里会反复强调“最多连续采m棵”，当你写代码写嗨了，这些细节最容易被抛到脑后，然后整个转移方程就裂开了。第二个容易翻车的地方是变量类型，某些题目数据范围到了10^9级别，int会溢出，要用long。这些看似基础的问题，在笔试的高压环境下反而是失分重灾区。

所以我的建议是，刷这套题时别急着追求AC，第一遍先自己写，第二遍刻意检查你的代码在边界数据上会不会挂，第三遍再对照题解复盘，看别人的写法哪里比你的简洁，哪里提升了复杂度。这样一套题下来，收获比盲刷十道题要大得多。

2. 四道代表性的卡人题：从读题到AC的完整拆解

这套题里最值得细说的就是中间两道和最后一道，它们代表了笔试中三种最常见的卡人方式：状态不知道怎么设计、图论代码不够熟练、贪心证明想不清楚。下面逐题拆开讲。

2.1 第一道热身题：按二进制中“1”的个数排序

这道题的原题大意是：输入n个正整数，请你按每个数字的二进制表示中1的个数从多到少排序，如果1的个数相同，数字大的排在前面。这道题说实话没有太多算法难度，但它很能检验基本功。

我当时的写法是这样的：

def count_bits(num): cnt = 0 while num: num &= num - 1 cnt += 1 return cnt

很多人会直接用bin(num).count('1')，这个写法当然也能过，但num & (num - 1)这个技巧还是值得练一下的。它每次循环消掉最低位的1，循环次数等于二进制中1的个数，而不是整数的位数。严格来说，两种方法在笔试这个量级下都能跑，但如果你追求代码效率和面试官的好感度，位运算写法是更好的习惯。

这道题的另一个考点是自定义排序的稳定性。题目要求按1的个数和数字大小两个维度排序，最稳妥的写法是构造元组或者字典再排序：

ans = sorted(nums, key=lambda x: (count_bits(x), x), reverse=True)

这里用元组的好处是Python会先比较第一个元素，相等时再比较第二个元素，正好符合题目要求，不容易出错。如果你写成先按数字排序再按1的个数用稳定排序来倒腾，也能得到正确答案，但代码会复杂很多，笔试里没必要。

2.2 中间的黄金选手：连续采摘问题的DP状态设计

这道题的情景是果园里有n棵果树排成一列，每棵树上有一定数量的果实。你从第一棵树开始往右走，可以选择摘或者不摘某一棵树上的果实，但是不能连续采摘超过m棵树，问最后最多能摘到多少果实。

我第一次看到这题的时候，第一反应是“这不就是个简单DP吗”，然后很快被打脸。如果没有任何限制条件，这题确实只是普通的一维DP。但加上“连续采摘不能超过m棵”这个限制之后，状态里必须记录当前已经连续摘了多少棵树，否则你无法判断下一次采摘是否合法。

这里就是典型的“状态设计”问题。很多人在笔试时卡住，不是因为不会DP，而是不知道DP状态除了下标之外还要记录什么。我的递推设计是这样：

dp[i][j]表示走到第i棵树时，最后一共连续采摘了j棵树的最大果实数。其中j的范围是0到m，j=0表示当前这棵树没有摘。

转移分两种情况。第一种情况是第i棵树不摘，那么连续采摘的计数就会清零，dp[i][0] = max(dp[i-1][0], dp[i-1][1], ..., dp[i-1][m])。第二种情况是第i棵树采摘，那么它前面必须已经连续摘了j-1棵树，dp[i][j] = dp[i-1][j-1] + fruits[i]。

参考代码可以这样写：

def max_fruits(fruits, m): n = len(fruits) dp = [[-10**18] * (m + 1) for _ in range(n + 1)] dp[0][0] = 0 for i in range(1, n + 1): val = fruits[i - 1] # 当前不摘，连续计数清零 dp[i][0] = max(dp[i - 1]) # 当前摘，枚举连续摘了 j 棵 for j in range(1, m + 1): dp[i][j] = dp[i - 1][j - 1] + val return max(dp[n])

这个代码的时间复杂度是 O(nm)。我当时交上去之后发现只能过一半测试点，剩下的超时了。后来看数据范围才知道n和m都可能到10^5级别，O(nm)根本跑不动，必须优化。

优化的思路是把dp[i][0] = max(dp[i-1])这一步用单调队列优化掉。因为我们只看上一行的连续j个状态里的最大值，而随着i增加，这个窗口是滑动着往前走的，它其实是一个经典滑动窗口最大值问题。用单调队列可以把计算max这一操作的复杂度从O(m)降到O(1)，整体复杂度就变成了O(n)。如果你对单调队列还不熟，建议专门去练几道“滑动窗口最大值”类型的题目，笔试里DP和单调队列结合的情况非常多，值得投入时间。

这道题给我们的核心启发是：拿到DP题目之后，不要急着写转移方程，先想清楚“题目里的附加限制，需要我在状态里额外记住什么信息”，这一步想明白，代码就成功了一大半。

2.3 压轴级图论题：岛屿寻宝的连通块统计

这道题的包装是多多的寻宝游戏给了一个二维网格，1表示有宝藏的陆地，0表示水，上下左右相连的陆地算同一个岛屿。问的是一共有多少个岛屿，以及最大的岛屿面积有多大。

如果你刷过LeetCode的“岛屿数量”和“岛屿最大面积”，看到这道题会觉得很亲切。它就是这两道题的合并版，不涉及复杂的图算法，BFS或者DFS都能解。我推荐用BFS来做，因为递归DFS在网格比较大的时候有可能爆栈，虽然不是一定会爆，但在笔试环境里没必要冒这个险。

参考代码如下，用队列处理遍历逻辑：

from collections import deque def solve(grid): if not grid or not grid[0]: return 0, 0 n, m = len(grid), len(grid[0]) visited = [[False] * m for _ in range(n)] dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)] islands = [] for i in range(n): for j in range(m): if grid[i][j] == 1 and not visited[i][j]: queue = deque() queue.append((i, j)) visited[i][j] = True area = 0 while queue: x, y = queue.popleft() area += 1 for dx, dy in dirs: nx, ny = x + dx, y + dy if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 1 and not visited[nx][ny]: visited[nx][ny] = True queue.append((nx, ny)) islands.append(area) if not islands: return 0, 0 return len(islands), max(islands)

这道题最坑的地方其实在题目描述里，它给出的网格不一定是规则的正方形，可能是矩形，所以行数n和列数m要分开读，方向数组写4个方向而不是8个方向。还有输入里可能存在换行符或者多余空格，用split之后忘记转int就会导致类型错误。

另外有一个小细节：这道题里网格如果用字符'1'和'0'表示，比较的时候要用grid[i][j] == '1'，不要写== 1。我当时就是看了一眼数据是整数就直接写了==1，结果本地跑得好好的，线上全部WA，最后发现样例输入是用字符串形式给的。这种低级错误在笔试里是最可惜的。

2.4 最考验思路的调度题：多多排班的贪心证明

这道题的整体描述是有一批任务，每个任务有一个最晚完成时间和完成所需天数，同一时间只能做一个任务，任务一旦开始就不能中断，问你最多能完成多少个任务。

把场景包装去掉以后，它其实就是“课程表III”的原题。解法是贪心加优先队列，具体思路是：先把任务按截止时间从小到大排序，然后用一个小顶堆维护当前已经选择的任务所需时间。按顺序遍历任务时，先假定选择当前任务，把它的耗时塞进堆里，当前总耗时也加上这个耗时。如果当前总耗时超过了当前任务的截止时间，就从堆里拿出耗时最大的那个任务扔掉，让它变成未选择状态。

这个贪心策略的核心直觉是：在所有已选任务中，抛弃耗时最长的那个，可以最大程度地腾出时间给后面的任务，从而让总选择数量最大化。

import heapq def max_tasks(deadlines, needs): tasks = sorted(zip(deadlines, needs)) cur_time = 0 heap = [] for deadline, need in tasks: cur_time += need heapq.heappush(heap, -need) if cur_time > deadline: cur_time += heapq.heappop(heap) return len(heap)

这里我用了负号构造大顶堆，因为Python的heapq默认是小顶堆。如果你直接往堆里塞正的need，pop出来的就是最小的那个，那可就完全反了。这是这道题最经典的坑，没有之一。

很多人在考场上一看到这道题就想着用DP或者回溯暴力求解，看到n的范围是10^5才意识到必须用贪心。但这里有一个前提：这类“带截止时间的任务调度”问题不是什么时候都能贪心的，它之所以能用上面的贪心解法，是因为每个任务耗时相同权重，我们只求数量最大化，而不是带权重的最大收益。如果题目改成每个任务有不同的收益，要求最大收益，那这道贪心解法就失效了，得换状态压缩DP。所以刷题的时候一定要看清题目问的是“数量最多”还是“收益最大”，这两个问法对应的解法完全不同。

3. 从“果园”和“寻宝”看穿包装：题目背后的能力筛选逻辑

拼多多这套笔试让我印象最深的，反而不是题目本身，而是它给每一道算法题都套了一层业务场景的外壳。很多人刷惯了LeetCode的裸题题面，一到笔试这种“场景题”就发懵，觉得题目读起来很长很吓人，理解题意就要花掉一半时间。但其实这种题目剥掉外壳之后，内核还是那几类经典算法。

为什么大厂要这样出题？我的理解是，他们想考察的不仅仅是你会不会某个算法模板，而是你能不能快速把一个模糊的实际场景抽象成一个清晰的算法问题。这种能力在日常工作和代码评审里非常重要，因为真实业务里没人会给你写清楚“这里用动态规划”，你拿到手的需求永远是“用户连续浇了七天水之后积分如何计算”这种描述，你需要自己从中识别出状态、转移和边界条件。

具体来说，这道题的包装风格呈现出三个核心筛选维度：

第一个维度是读题和信息提取能力。场景题的题面普遍偏长，有些关键约束条件藏在某个转折句里，比如“注意不能连续采摘”，有些人扫一眼就顺手划过，漏了，后面写出来的代码自然是错的。我当时在整理这套题的时候对比过一些朋友的反馈，那些笔试成绩高的人，读题时普遍有一个好习惯：先用笔在草稿纸上把题面里出现的数字全都圈出来，明确哪些是输入，哪些是条件，哪些是要输出的东西，然后才开始动手写代码。

第二个维度是快速匹配题目原型的能力。题目包装成寻宝、果园、排班，但核心都是常见算法题。刷题量足够大的人看到“连续采摘m棵”就会自动联想到DP状态设计，看到“岛屿”就会想到BFS，看到“截止时间+最大任务数”就会想到贪心加堆。这种“模式识别”能力是刷题刷出来的，没有捷径，但可以用“一题多刷”的方式来加速。我建议拿到一道场景题后，先自己写一版，然后去查一下它对应的裸题原型是哪一道LeetCode题，把它俩放在一起对比着看，这个动作会让你的模式识别网络变得非常敏锐。

第三个维度是边界情况和代码鲁棒性。笔试的测试点里一定有最大数据范围、空输入、重复元素、类型溢出这些边界用例。我遇到过不少同学，解题思路完全正确，代码也没写错，但就是没有处理空数组的情况，直接报错。拼多多这套题里，边界处理几乎是每道题都会踩的雷区。我的习惯是写完代码之后，立刻构造三个测试用例：一个是最小输入，比如n=1；一个是最大规模，想象一下数据量拉满会发生什么；还有一个是特殊形状的测试用例，比如所有元素都相等，或者布局图形不对称。三个用例都跑通，再提交，通过率会高很多。

我整理了一个小的对照表格，把场景题和裸题原型对应起来，帮助大家建立快速识别模式：

这套对应能力，说穿了其实就是把一个长题目压缩成几个关键词的能力。我每次刷题都会刻意练习这个压缩动作，把一段二百字的场景描述浓缩成三个词放进笔记里，时间久了，看到新题的时候脑子里的“模板库”就能快速响应。

再一个让我感触很深的点是拼多多笔试对“工程细节”的考察。这四道题本身不考什么黑科技，但如果你是第一次写ACM模式的核心代码，你会发现自己连while True配try-except读入多组数据的写法都不太熟练，更别提处理输入里的逗号分隔符和额外换行符了。很多人在LeetCode上刷得风生水起，一到真实笔试就挂，很大程度上不是算法不行，而是对标准输入输出的处理太生疏。这个只能用模拟环境来解决，我建议从今天开始就用牛客网或者自己搭一个sys.stdin的读取模板来刷题，多练几次就不再发怵了。

4. 应对这套题及类似大厂笔试的备战策略

前面拆题拆了不少，现在说说更实际的问题：如果你现在开始为秋招做准备，应该怎么刷这类大厂笔试编程题，才不会被突然出现的“场景外套”和“ACM模式”打乱阵脚。

先说刷题优先级。拼多多这套题覆盖的知识点给你提供了一个很清晰的复习路径：排序、DP、BFS/DFS、贪心、堆。这些是互联网公司笔试的高频考点，优先级应该是第一梯队。我建议按下面这个清单去安排你的刷题内容和顺序：

• 排序和自定义排序：必刷，重点掌握key=lambda和元组排序，以及稳定排序的特性。
• 二分查找：笔试出现频率极高，重点练“最后一个小于等于target”和“第一个大于等于target”这类变体，边界条件一定要自己推一遍。
• 双指针和滑动窗口：跟数据结构结合紧密，练到看见“连续子数组”就能条件反射想到。
• 动态规划：不要只刷线性DP，背包、区间DP、状态DP都要照顾到，特别是“带限制条件”的状态设计，这是最容易卡人的点。
• 图论：BFS和DFS是最基础的要求，并查集也要会，岛屿问题、连通分量、最短路径这几个方向至少要各练三道题。
• 贪心加堆：先理解贪心为什么成立，再动手写代码，不然很容易写出看起来对、实际不成立的解法。

然后是笔试现场的时间分配。我的习惯是拿到卷子第一件事不是写代码，而是花五分钟把四道题全部扫一遍。每道题快速判断三件事：题目场景对应什么算法原型、数据范围大概能接受什么复杂度、自己有没有把握在半小时内AC。然后把题目按难度分成两个梯队，先做有把握的题保证手感，最后留大约四十分钟来啃最难的那道压轴题。

为什么一定要先扫一遍题目？因为笔试不是要求你把所有题都AC，而是让你在有限时间内拿到尽可能多的分数。如果你死磕第一道难题半小时，其他三道原本能拿分的题就没时间做了。先易后难是整个笔试策略的核心。

再一个容易被忽略的坑是：一定要提前准备好自己的代码模板。我指的模板不是让你去背那些几百行的板子，而是把高频的操作片段提前写好，放进你熟悉的代码风格里。举几个实际例子：

import sys def solve(): data = sys.stdin.read().split() if not data: return n = int(data[0]) # 按需处理

这个读取模板能兼容绝大多数字符串型输入，比一行行input()要稳得多。再比如：

# 并查集模板 def find(a): if parent[a] != a: parent[a] = find(parent[a]) return parent[a] def union(a, b): pa, pb = find(a), find(b) if pa != pb: parent[pa] = pb

这些模板花不了多少时间准备，但到了笔试现场，你不需要重新考虑细节，直接套用，节省下来的时间都是实打实的分数。

还有一个建议，如果你发现自己的知识储备已经比较全面，但总是因为“思路想不出来”而卡住，那问题可能在于你刷题的方式太被动了。很多人刷题是看一道题，没有思路，立刻翻题解，看懂了然后提交，最后感叹一句“原来这么简单”。但这样刷十道题，下一次遇到新题还是不会。正确的方法是：拿到题目后，先给自己定一个十五分钟的思考闹钟，在这十五分钟内，不管想不想得出来，都要把思路写在纸上，哪怕写“我想到的暴力解法是……”也好。时间到了再翻答案。这个强迫自己输出思考的过程，是提升解题能力最有效的方式。

关于要不要刷历年真题这件事，我的看法是：真题值得刷，但不要只刷真题。秋招笔试是一个抽样测试，考什么知识点、难度梯度如何，确实能从历年真题里看出趋势。但你不能指望靠刷原题押中考点，因为大厂的题库更新速度非常快，今天刷到的题明天大概率不会原样出现。真题的正确用途是帮你熟悉题型结构和场景包装的方式，算法能力本身还是需要靠系统刷基础题来打底。这个主次关系千万不能搞反。

最后再说说拼多多这套题里透出来的一个趋势：业务场景和算法题的结合越来越紧密。从热词里的地址核验、API、滑块验证这些方向能够看出，拼多多技术侧已经大量渗透到电商基础设施、反作弊和物流系统里。相应地，笔试题目也会更倾向于考察“快速理解业务语义并抽象成算法模型”的能力。这套题虽然来自2019年，但它的场景包装风格和出题思路，放到今天依然很有参考价值，甚至可以说，现在各家大厂的笔试都在朝着“更贴近真实业务场景”的方向演进。

我在实际带人刷题的时候发现，一道题反复做三遍的效果远好于做三道新题。第一遍不看题解自己AC，第二遍把代码优化到尽量简洁，第三遍在白纸上把思路完整写出来，相当于模拟面试时的口述过程。这三遍做完，这道题才算真正消化成自己的东西。刷题数量可以不多，但每一步都要走扎实，笔试考场上你才会发现，那些平时反复练过的思路会像条件反射一样自然冒出来。