滴滴出行2017秋招笔试真题：四道经典算法题全解析

前阵子整理电脑里的旧资料翻出一份当年秋招时打印的滴滴出行2017秋招笔试真题-编程题汇总纸上还留着当时演算的笔迹。四道题我反反复复做了好几遍最后笔试环节顺利通过后来带新人时也常常拿这几题做训练。它不是那种偏题怪题集而是把动态规划、DFS搜索、数学推导、背包方案数这些基础考点包装在很生活化的场景里读题时甚至能感受到“出行”“迷宫”这类画面感。无论是准备校招、社招面试还是单纯想扎实算法基础这份题汇总都值得静心做一遍。这四道题放到今天来看依然不过时因为大厂笔试真正想考察的从来不是“你背了多少模板”而是你在有限时间内能否把经典模型识别出来并写出没有边界问题的代码。下面我把每道题的完整思路、AC代码、易错点全部拆开讲一遍顺便分享一些我在笔试现场总结出来的调试习惯。1. 这份题单的含金量滴滴笔试到底在考什么1.1 从真题风格看考察点滴滴出行2017秋招的笔试题型和现在不少公司类似编程题占比高题目数量不多但每道题都有明确的算法标签。整套题汇总下来我发现出题人有几个比较明显的偏好。第一重视基础算法模型。连续最大和是线性动态规划最经典的入门题数字和为sum的方法数是01背包方案数的直接变体这两类题在面试手撕代码环节出现频率极高。第二喜欢给算法穿上一层“场景外衣”。比如地下迷宫题本质上就是带体力消耗的图上搜索但包装成小青蛙逃出迷宫的故事后读题成本变高了考察的不只是算法还有从题目描述中抽象出模型的能力。第三数学题不会考得太深但需要你发现规律。末尾0的个数如果真去模拟阶乘数据一大就完蛋本质上是在考数论里的因子分解。再从时间维度看这套题整体难度属于“中等偏基础”没有特别冷门的后缀数组、网络流之类的东西。但正因为题目不偏大家都会做最后拼的就是正确率和速度。当年我在牛客上看到很多人在讨论区说“题目都见过就是没AC”原因基本都出在边界条件和输出格式上而不是算法本身不会。1.2 考点分布与时间分配建议我整理了一份考点分布表方便你对照自己的薄弱环节题目核心考点难度建议耗时连续最大和线性DP、贪心扫描简单10分钟末尾0的个数数学推导、因子统计简单8分钟地下迷宫DFS回溯、状态搜索、字典序比较较难30分钟数字和为sum的方法数01背包方案数DP中等15分钟四道题加起来建议控制在1小时以内。如果按照笔试时90分钟的设定其实还留了不少检查时间。我个人的策略是先做连续最大和和末尾0的个数这两道送分题必须拿满再做数字和为sum的方法数这道题代码短但稍不留神就会正序更新变成完全背包最后啃地下迷宫因为搜索题的代码量和出错概率都更大留足时间调试比较稳妥。2. 真题逐题解析从读题到AC全流程2.1 连续最大和经典动态规划的地基先看题面。输入一个整数N表示数组长度第二行有N个整数要求输出这个数组的连续子数组最大和。举个例子输入6 1 -2 3 5 -1 2对应的连续子数组最大和是9也就是取[3, 5, -1, 2]这一整段。这题的核心思路是Kadane算法也叫“扫描法”。维护一个变量cur表示“以当前元素结尾的连续子数组最大和”遍历数组时每次面临一个选择是把当前元素接在前面的子数组后面还是从当前元素重新开始一段。状态转移方程就一句话cur max(x, cur x) ans max(ans, cur)为什么这么写因为如果cur x还不如x本身大说明前面那段子数组对整体是负贡献那不如舍弃掉从当前位置重新累积。这个过程一遍扫描就能完成时间复杂度O(n)空间复杂度O(1)。很多新手会犯一个典型错误把cur初始化为0把ans也初始化为0。当数组全是负数时比如[-3, -1, -2]正确答案应该是-1但初始化成0后整个答案就变成了0。正确做法是让cur和ans都初始化为数组第一个元素然后从第二个元素开始遍历。我一般写输入处理时直接使用sys.stdin.read().split()一次性读入避免多次调用input()带来的性能损耗和可能的读取问题。完整代码import sys def main(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) nums list(map(int, data[1:1 n])) cur nums[0] ans nums[0] for x in nums[1:]: cur max(x, cur x) if cur ans: ans cur print(ans) if __name__ __main__: main()这道题虽然简单但它是很多动态规划题目的“地基”。二维最大子矩阵问题本质上就是对每一行做前缀和压缩后转化为连续最大和环形数组的最大子段和问题则是先求最大子段和再求最小子段和最后用总和减掉。把最基础的线性DP吃透后面这些变形都是一层窗户纸。2.2 末尾0的个数别真的去算阶乘第二道题是个典型数学题。输入一个正整数n要求输出n!的十进制表示末尾有多少个连续的0。比如n5时5!120末尾有1个0n10时10!3628800末尾有2个0。刚看到这题时最容易想到的思路是直接计算阶乘然后循环取模统计0的个数。但如果n给到100甚至1000Python还能用大整数硬算但C的long long早就爆了而且笔试系统的内存和耗时也扛不住。再说这题考察的本意根本不是大数计算。换个角度想末尾的0是怎么来的10 2 × 5一个0就需要一个因子2和一个因子5配对。在1到n的所有整数里因子2的数量远远多于因子5的数量所以末尾0的个数实际上等于“1到n中所有数的因子5的总个数”。但这里有个容易踩的坑因子5不只出现在5的倍数里25含有两个因子5125含有三个因子5。所以不能只统计n // 5还要继续统计n // 25、n // 125直到商为0为止。def trailing_zeroes(n): cnt 0 while n: n // 5 cnt n return cnt这段代码的含义是第一次n // 5统计5的倍数贡献了一个5第二次n // 5统计25的倍数额外贡献了一个5第三次统计125的倍数额外贡献的第三个5以此类推。循环跑完cnt就是答案。举个具体例子n25时5的倍数有5、10、15、20、25共5个因子525本身还有一个额外的因子5所以总共6个0。用代码验证25//5525//251516。完全正确。我当年踩过的坑是直接用while i n: cnt n // i; i * 5这种写法在Python里问题不大但n特别大时可能效率稍低更严谨的做法是不断n // 5这样循环次数是log级别的几乎是常数时间。题目如果问的是其他进制比如二进制末尾0的个数那就是统计因子2的个数思路一模一样只需要把除数从5换成2。2.3 地下迷宫DFS回溯与“最优路径”陷阱这道题是整套题里最有含金量的一道当年在讨论区也是最热闹的。题面比较长我简化描述一下。小青蛙掉进一个N行M列的地下迷宫每个格子是0或10表示墙不能走1表示可以走。它从左上角(0,0)出发出口在(0,M-1)题目保证这两个格子是1。小青蛙有初始体力值P在迷宫内向四个方向移动会消耗不同体力向上移动消耗3向下移动消耗0向左移动消耗1向右移动消耗1。要求找到一条从起点到出口的路径使得到达出口时剩余体力尽量大如果有多条路径剩余体力相同输出坐标序列字典序最小的一条。如果体力耗尽前无法到达出口输出一行Can not escape!。这个题首先想到的当然是搜索。但要注意它不是单纯的最短路径问题因为每个方向的体力消耗不一样向下走反而完全不消耗体力所以最短路径不等于最优路径。也不能用贪心因为你不知道当前选择最省体力的方向是否会导致后续陷入死胡同。最稳妥的做法是DFS 回溯把所有能到达终点的路径都搜一遍然后按“剩余体力最大其次字典序最小”的比较规则更新答案。搜索方向我习惯按照上、右、左、下来定义对应坐标变化和体力消耗分别是(-1, 0, 3)、(0, 1, 1)、(0, -1, 1)、(1, 0, 0)。这里有几个关键细节必须处理到位。第一走过的格子不能重复走否则DFS会陷入无限循环所以需要visited数组进入递归前标记回溯后恢复。第二每次移动前要检查下一个格子是否在迷宫范围内、是否为1、是否已访问。第三体力判断要在移动完成后进行如果当前剩余体力小于0直接剪掉。关于体力等于0能否继续移动不同版本的笔试题描述存在细微差异。我按“体力不能为负等于0也可以站在出口”的版本来实现如果你拿到的题面要求“体力大于0才能移动”把if power 0改成if power 0即可。这是各种回忆版本里最常见的差异点建议实际做题时先根据样例确认。import sys sys.setrecursionlimit(10000) def main(): input_data sys.stdin.read().strip().split() idx 0 n int(input_data[idx]); idx 1 m int(input_data[idx]); idx 1 p int(input_data[idx]); idx 1 grid [] for _ in range(n): row [] for _ in range(m): row.append(int(input_data[idx])); idx 1 grid.append(row) visited [[False] * m for _ in range(n)] directions [(-1, 0, 3), (0, 1, 1), (0, -1, 1), (1, 0, 0)] best_path None best_power -1 def dfs(x, y, power, path): nonlocal best_path, best_power if power 0: return if x 0 and y m - 1: if power best_power: best_power power best_path path[:] elif power best_power: if best_path is None or path best_path: best_path path[:] return # 剪枝如果当前体力已经小于历史最优后续最多保持不变不可能反超 if power best_power: return for dx, dy, cost in directions: nx x dx ny y dy if 0 nx n and 0 ny m and grid[nx][ny] 1 and not visited[nx][ny]: visited[nx][ny] True path.append((nx, ny)) dfs(nx, ny, power - cost, path) path.pop() visited[nx][ny] False visited[0][0] True dfs(0, 0, p, [(0, 0)]) if best_path is None: print(Can not escape!) else: out [] for x, y in best_path: out.append(f({x},{y})) print( .join(out)) if __name__ __main__: main()代码里我加了一个剪枝if power best_power: return。为什么安全因为四个方向中向下移动消耗体力为0也就是说后续路径无论怎么走剩余体力最多只能保持不变不可能变得更大。如果当前剩余体力已经小于历史最优解那最终也不可能超过历史最优解所以可以直接剪掉。这个剪枝在数据范围大时能省不少时间而且不影响答案正确性。另外关于字典序比较Python的列表比较就是逐元素比较的路径里的每个元素都是坐标元组所以path best_path可以直接判断两条路径谁字典序更小。由于所有路径起点都是(0,0)这个比较天然等价于从第二个坐标开始比较。如果不想依赖Python的语法糖也可以把路径坐标转成字符串再比较效果一样。这道题实际考场上出错率很高主要原因有两个一是没有回溯visited状态导致一条路径搜索完后其他路径无法经过同样的格子二是只记录了第一条找到的路径没有做“剩余体力最大”和“字典序最小”的双重比较。我见过不少人的代码能输出样例结果但一换数据就错基本都是这两种情况。2.4 数字和为sum的方法数01背包方案数最后一道题输入一个大小为n的数组和一个目标值sum要求从数组中任意选取若干个数每个数最多选一次使得选出的数之和等于sum输出不同的选法总数。注意这里的“不同”指的是下标组合不同即使数值相同也按不同方案计算。这道题是典型的01背包求方案数。设dp[j]表示从已经遍历过的数字中选出若干个数使其和恰好为j的方案数。初始状态dp[0] 1因为不选任何数字时和为0这是一种方案。遍历每个数字a时对于所有 j 从 sum 递减到 a执行dp[j] dp[j - a]即可。为什么要倒序更新这是01背包和完全背包最核心的区别。如果正序遍历j那么当执行到dp[j] dp[j - a]时dp[j - a]可能已经包含了当前数字a被使用过的次数相当于同一个数字被重复选择了多次这就变成了完全背包。倒序遍历则保证每个数字只被考虑一次。这个坑每年都有无数人踩我自己也踩过。def main(): import sys data sys.stdin.read().strip().split() if not data: return n int(data[0]) s int(data[1]) arr list(map(int, data[2:2 n])) dp [0] * (s 1) dp[0] 1 for a in arr: if a s: continue for j in range(s, a - 1, -1): dp[j] dp[j - a] print(dp[s])代码很容易背但有几个隐藏的细节你需要知道。首先是跳过a s的情况。如果一个数本身就大于目标值sum它不可能出现在任何合法方案中直接跳过避免内层循环做无用功。其次是数组中如果存在0处理要小心0不会改变和的大小但每个0都能被选择或不选择会让方案数乘以2。原题的测试数据一般不会出现0但万一遇到标准的做法是单独统计0的个数最后把答案乘以2^cnt而不是直接套用上面的循环。直接套的话j从s到0递减时dp[j] dp[j - 0]会让每个dp值翻倍而且随着遍历次数不断增加最终结果会变成奇怪的倍数和“每个0可选可不选”的语义不一致。复杂度方面时间复杂度O(n * sum)空间复杂度O(sum)。当n和sum都达到1000时内循环总共执行约100万次Python完全能扛得住。如果sum给得很大比如1e9那就是另一类问题了不能用这个办法需要换思路但一般笔试不会这么出。3. 笔试现场实战调试、边界与心态3.1 我踩过的几个真实大坑前面每道题都提到了易错点这里把我在笔试现场和平时练习中真实遇到过的几个问题集中说一说。第一个大坑是连续最大和的输出结果被“0”污染。有一版题面把cur初始化为0导致数组全为负数时输出0而不是最大的负数。这个错误在牛客的测试用例里很容易被抓住因为判题系统往往会专门准备最小值的极端数据。我自己后来总结了一个习惯凡是求最大值或最小值的题目初始值一定要从第一个有效元素取或者根据题目语义设置成-float(inf)/float(inf)。第二个大坑是DFS回溯漏掉恢复现场。地下迷宫那题我在递归入口标记visited[nx][ny] True但在递归返回后忘了写visited[nx][ny] False结果第一条路径搜索完所有走过的格子都被锁死其他路径全部搜索不到。这个错误很隐蔽因为部分数据点即使漏掉恢复也能碰巧输出正确路径只有在需要比较多条路径的测试用例上才会现出原形。第三个大坑是输入解析问题。笔试题目经常有多组输入或整行整行读入的情况比如迷宫的行列矩阵如果用for i in range(n): row input().split()去读遇到行与行之间有空格或者换行不统一的情况就容易读串。我用sys.stdin.read().strip().split()一次性读入所有内容再按顺序解析可以规避绝大多数输入格式问题。3.2 遇到没思路的题怎么办笔试过程中最怕的不是题目难而是看到一道题完全没有头绪。我给自己定了一条铁律先花5分钟想暴力思路如果暴力都写不出来就果断跳题等最后有时间再回来看。暴力思路往往能带来突破口。比如地下迷宫那题一开始别想着最优路径先想“我能不能遍历所有可能的路径”DFS回溯就是基于这个最朴素的想法演化的。再比如末尾0的个数先想“能不能模拟阶乘”答案在数据范围面前行不通但顺着“计算过程肯定炸”这个念头你自然会去寻找数学规律。如果连题目都读不懂就把样例输入和输出抄下来手动模拟一遍看它是怎么从输入变成输出的。很多场景题比如迷宫、路线规划本质上都是“状态从一个点转移到另一个点每一步有代价最终求某种最优值”——把这个抽象出来模型自然就清楚了。3.3 输出格式与AC的最后一公里代码逻辑正确但AC不了输出格式往往是元凶。滴滴这套题当年就有不少人栽在输出上。地下迷宫的坐标输出要求是(0,0) (1,0) (1,1)这种格式每个坐标括号内用英文逗号坐标之间用空格。我看到有人用中文逗号有人末尾多打了一个空格还有人没加空格直接把坐标拼成一串——这些都是致命的。我的建议是在练习时就用原始题面给的输出格式写不要自己“优化”成更容易打印的格式。调试前先构造一个最小用例人工算出期望输出再跑代码对比尤其是空格、换行、逗号这些细节。笔试不像平时写项目没有容错空间差一个字符就是0分和满分的区别。4. 常见问题速查表与避坑指南我把这套题里最常见的错误类型整理成一张速查表方便你考前快速翻阅症状可能原因解决办法连续最大和答案变成0ans初始化为0初始化为数组第一个元素n!末尾0的个数偏小只统计了n//5循环统计5、25、125...的贡献迷宫DFS超时或死循环缺少visited标记或未回溯标记进入回溯恢复迷宫输出路径不是最优只取了第一条路径搜完所有路径按体力字典序比较方案数明显偏大背包j正序更新改为倒序更新保证每个数只用一次数组含0导致方案数异常0会翻倍方案数单独统计0的个数答案乘2^cnt输出格式不对AC不了括号、逗号、空格不一致严格按样例输出末尾不留空格刷题时我习惯把这些坑记在一个文档里而不是简单记在代码注释中。因为笔试题量一大很难把每道题的细节都装进脑子里考前翻一翻自己的避坑记录比临时刷十道新题更有效。5. 刷完这份题单后我建议你这样延伸这套题的价值不只在于能AC更在于帮你培养“识别模型”的敏感度。我刷完以后又顺手做了几个变形练习印象很深。连续最大和可以把一维数组扩展成二维矩阵求最大子矩阵和做法是先枚举行上下边界做前缀压缩再对压缩后的一维数组跑Kadane。末尾0的个数可以扩展成“求n!在二进制下末尾有多少个0”只需要把统计因子5换成因子2。地下迷宫这类带权搜索可以进一步思考如果每个方向代价不同能不能用Dijkstra或带优先队列的BFS求最小体力路径这实际上就是从DFS走向更高效算法的过程。数字和为sum的方法数则可以继续延伸物品无限使用的完全背包方案数以及物品数量有限的混合背包方案数。我发现笔试准备到最后拼的其实是“看到题目特征立刻想到对应算法”的反射速度。这份滴滴出行2017秋招笔试真题-编程题汇总里涉及的动态规划、数论、DFS搜索、背包DP正好是大部分公司笔试的最高频考点。等你把这几类题做顺了再回头看笔试其实考的不是智商而是熟练度。把一道题从AC到能讲清楚为什么这样做比闷头刷十道题更有用。