滴滴 2017 秋招编程题汇总（6 题）
点击「查看答案」展开答案解析。
来源： 牛客原题 | 题量： 6 题
第1题（编程题） 一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3 输入描述：输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。 输出描述：所有连续子数组中和最大的值。 输入示例：3 -1 2 1 输出示例：3
查看答案
思路
经典 Kadane 算法求最大连续子数组和：cur = max(x, cur+x)，best = max(best, cur)。
def max_subarray(a):
cur = best = a[0]
for x in a[1:]:
cur = max(x, cur + x)
best = max(best, cur)
return best第2题（编程题） 某餐馆有n张桌子，每张桌子有一个参数：a 可容纳的最大人数； 有m批客人，每批客人有两个参数:b人数，c预计消费金额。 在不允许拼桌的情况下，请实现一个算法选择其中一部分客人，使得总预计消费金额最大 输入描述：输入包括m+2行。 第一行两个整数n(1 <= n <= 50000),m(1 <= m <= 50000) 第二行为n个参数a,即每个桌子可容纳的最大人数,以空格分隔,范围均在32位int范围内。 接下来m行，每行两个参数b,c。分别表示第i批客人的人数和预计消费金额,以空格分隔,范围均在32位int范围内。 输出描述：输出一个整数,表示最大的总预计消费金额 输入示例：3 5 2 4 2 1 3 3 5 3 7 5 9 1 10 输出示例：20
查看答案
思路 贪心：客人按消费金额降序排序；桌子容量存入有序集合（multiset），对每位客人用 lower_bound 找第一个能坐下的最小桌子并移除、累加消费。
from bisect import insort, bisect_left
def solve(tables, guests):
tables.sort()
guests.sort(key=lambda g: -g[1])
total = 0
for b, c in guests:
i = bisect_left(tables, b)
if i < len(tables):
total += c
tables.pop(i)
return total（pop 使 Python 退化为 O(n·m)，C++ 用 multiset 可 O(n log n)。）
第3题（编程题） 小青蛙有一天不小心落入了一个地下迷宫,小青蛙希望用自己仅剩的体力值P跳出这个地下迷宫。为了让问题简单,假设这是一个n*m的格子迷宫,迷宫每个位置为0或者1,0代表这个位置有障碍物,小青蛙达到不了这个位置;1代表小青蛙可以达到的位置。小青蛙初始在(0,0)位置,地下迷宫的出口在(0,m-1)(保证这两个位置都是1,并且保证一定有起点到终点可达的路径),小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值,向上爬一个单位距离需要消耗3个单位的体力值,向下移动不消耗体力值,当小青蛙的体力值等于0的时候还没有到达出口,小青蛙将无法逃离迷宫。现在需要你帮助小青蛙计算出能否用仅剩的体力值跳出迷宫(即达到(0,m-1)位置)。 输入描述：输入包括n+1行: 第一行为三个整数n,m(3 <= m,n <= 10),P(1 <= P <= 100) 接下来的n行: 每行m个0或者1,以空格分隔 输出描述：如果能逃离迷宫,则输出一行体力消耗最小的路径,输出格式见样例所示;如果不能逃离迷宫,则输出“Can not escape!”。 测试数据保证答案唯一 输入示例：4 4 10 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1 输出示例：[0,0],[1,0],[1,1],[2,1],[2,2],[2,3],[1,3],[0,3]
查看答案
思路
带权最短路：向下 0、水平 1、向上 3，求 (0,0)→(0,m-1) 的最小体力路径。用 Dijkstra（或 0-1 BFS 变形），记录前驱还原路径；体力不够输出 Can not escape!。
import heapq
def escape(grid, P):
n, m = len(grid), len(grid[0])
dist = [[float('inf')]*m for _ in range(n)]
pre = [[None]*m for _ in range(n)]
dist[0][0] = 0
pq = [(0, 0, 0)]
dirs = [(1,0,0),(0,1,1),(0,-1,1),(-1,0,3)] # 下/右/左/上
while pq:
d, x, y = heapq.heappop(pq)
if d > dist[x][y]: continue
if (x, y) == (0, m-1): break
for dx, dy, w in dirs:
nx, ny = x+dx, y+dy
if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 1:
nd = d + w
if nd < dist[nx][ny]:
dist[nx][ny] = nd; pre[nx][ny] = (x, y)
heapq.heappush(pq, (nd, nx, ny))
if dist[0][m-1] > P: return "Can not escape!"
# 沿 pre 回溯得到路径
path, cur = [], (0, m-1)
while cur:
path.append(cur); cur = pre[cur[0]][cur[1]]
return ','.join(f"[{x},{y}]" for x, y in path[::-1])第4题（编程题） 输入一个正整数n,求n!(即阶乘)末尾有多少个0？ 比如: n = 10; n! = 3628800,所以答案为2 输入描述：输入为一行，n(1 ≤ n ≤ 1000) 输出描述：输出一个整数,即题目所求 输入示例：10 输出示例：2
查看答案
思路 n! 末尾 0 的个数 = 因子 5 的个数（2 远多于 5）。
def trailing_zeros(n):
cnt = 0
while n:
n //= 5
cnt += n
return cnt第5题（编程题） 给定一个十进制数M，以及需要转换的进制数N。将十进制数M转化为N进制数 输入描述：输入为一行，M(32位整数)、N(2 ≤ N ≤ 16)，以空格隔开。 输出描述：为每个测试实例输出转换后的数，每个输出占一行。如果N大于9，则对应的数字规则参考16进制（比如，10用A表示，等等） 输入示例：7 2 输出示例：111
查看答案
思路 辗转相除法转 N 进制，处理负数先记符号取绝对值；N>9 用 A~F 表示。
def convert(m, n):
if m == 0: return "0"
sign = "-" if m < 0 else ""
m = abs(m)
digits = "0123456789ABCDEF"
res = ""
while m:
res = digits[m % n] + res
m //= n
return sign + res第6题（编程题） 给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。 当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。 输入描述：输入为两行: 第一行为两个正整数n(1 ≤ n ≤ 1000)，sum(1 ≤ sum ≤ 1000) 第二行为n个正整数Ai，以空格隔开。 输出描述：输出所求的方案数 输入示例：5 15 5 5 10 2 3 输出示例：4
查看答案
思路
0-1 背包计数：dp[j] 表示和为 j 的方案数，对每个数从大到小更新。
def count_subsets(a, s):
dp = [0]*(s+1)
dp[0] = 1
for x in a:
for j in range(s, x-1, -1):
dp[j] += dp[j-x]
return dp[s]—