大厂真题 / 滴滴

2026 年 8 月 30 日滴滴算法笔试：可恢复题目与题解

证据边界。现有材料的概述和章节标题声称选择题共有 20 道，但正文在第 10 题后立即进入编程题，只能恢复出以下 10 道；本文不补造其余 10 道。公式由 HTML 中 MathJax 的 data-mml-node 结构及 path[data-c] 字形恢复。第 3 题 A 项在现存 HTML 中本身止于“故可以由公式计算”，没有可恢复的后续公式，本文如实保留。下列答案均按题意独立核验，而不是仅照录答案。

一、选择题（正文可恢复的 10 道）

1. 正态随机变量的线性变换

如果随机变量 $X$ 服从均值为 $\mu$、标准差为 $\sigma$ 的正态分布 $N(\mu,\sigma^2)$，且 $Y=aX+b$（$a,b$ 为常数），则 $Y$ 的数学期望是（）。

A. $b$
B. $a\mu$
C. $a\mu+b$
D. 不确定

独立核验答案：C。期望具有线性性，$E(Y)=E(aX+b)=aE(X)+b=a\mu+b$。正态分布和标准差不影响这个结论。

2. 拉链法处理哈希冲突

运用拉链法解决哈希表冲突时，主要使用到的数据结构是：

A. 链表
B. 栈
C. 二叉树
D. 队列

独立核验答案：A。拉链法把映射到同一桶的元素串成链，定义上使用链表；某些实现把过长的桶树化只是额外优化。

3. 贝叶斯方法

关于贝叶斯方法的原理，下面哪个说法是错误的？

A. 对类条件概率 $P(\boldsymbol{x}\mid c)$ 来说，由于它涉及关于 $\boldsymbol{x}$ 所有属性的联合概率，故可以由公式计算
B. 为最小化总体风险，只需在每个样本上选择那个能使条件风险 $R(c\mid\boldsymbol{x})$ 最小的类别标记，即 $h^*(\boldsymbol{x})=\arg\min_c R(c\mid\boldsymbol{x})$
C. 对分类任务来说，在所有相关概率都已知的理想情形下，贝叶斯决策论考虑如何基于这些概率和误判损失来选择最优类别标记
D. 贝叶斯决策论（Bayesian decision theory）是概率框架下实施决策的基本方法

独立核验答案：A。高维类条件联合概率通常难以由有限样本直接估计，这正是朴素贝叶斯引入条件独立假设的原因。B 是逐样本最小化条件风险的贝叶斯判定准则，C、D 也是正确定义。A 项尾部公式在证据中缺失，但现存断言“涉及联合概率，故可以（直接）计算”的逻辑仍然错误。

4. 二叉树遍历（多选）

已知某二叉树的先序遍历序列和中序遍历序列，可以确定该二叉树的哪些信息？

A. 后序遍历序列
B. 高度
C. 叶子节点个数
D. 根节点

独立核验答案：A、B、C、D（需采用结点值互不相同这一通常前提）。先序首项给出根；在中序中定位根即可划分左右子树，递归后唯一还原整棵树。因此后序、高度、叶子数和根都确定。若允许重复值且没有额外标识，则树未必唯一，这是题目的隐含前提。

5. 稳定排序

某电商平台需要对订单列表按“价格升序，同价格按时间升序”排序。订单已按时间排好序，现按价格排序。哪种算法能保证同价格订单的时间顺序不变？

A. 归并排序
B. 快速排序
C. 希尔排序
D. 堆排序

独立核验答案：A。标准归并排序在相等时优先取左侧元素，是稳定排序；标准快速、希尔、堆排序都不稳定。

6. 支持向量机

下列关于支持向量机的说法错误的是？

A. 支持向量机的求解通常借助凸优化技术，例如 SMO
B. 支持向量机的决策边界是对学习样本求解的最大边距超平面
C. SVM 使用交叉熵损失计算经验风险，并加入正则化项优化结构风险，是具有稀疏性和稳健性的分类器
D. 核函数直接影响支持向量机与核方法的最终性能，而核函数选择尚无通用解决准则

独立核验答案：C。经典软间隔 SVM 对应合页损失 $\max(0,1-yf(x))$，不是交叉熵。其优化问题是凸的，SMO 可求解对偶问题；最大间隔和核选择的其余描述成立。

7. Transformer

下面哪项是 Transformer 的核心特点？

A. 通过循环结构处理序列数据
B. 依赖卷积神经网络处理长距离依赖
C. 依赖递归结构处理序列
D. 通过自注意力机制并行处理序列

独立核验答案：D。Transformer 以自注意力直接建立位置间联系，训练时可并行处理序列位置，不依赖 RNN 的循环/递归结构。

8. 互异自然数拆分的最大乘积

将 $21$ 分成若干个互不相同的自然数之和，并使这些自然数的乘积最大。最大乘积为：

A. $840$
B. $1020$
C. $1008$
D. $630$

独立核验答案：A。拆成 $2+3+4+5+7=21$，乘积为 $840$。另外对 ${1,2,\ldots,21}$ 的所有子集进行穷举核验，和为 21 的互异自然数集合中最大乘积确为 840；因而不只是从四个选项中排除得到。

9. 机器学习的定义

机器学习致力于研究如何通过计算手段，利用经验改善系统自身性能。下列说法哪个错误？

A. 面对新的情况时，模型会提供相应判断
B. 机器学习是研究关于数据的学科，而不是“算法”的学问
C. 机器学习主要研究在计算机上从数据中产生模型的算法，即学习算法
D. 把经验数据提供给学习算法，它能基于这些数据产生模型

独立核验答案：B。机器学习的核心研究对象包括从经验数据产生模型的学习算法，因此将其排除为“不是算法的学问”不成立；A、C、D 描述了训练和预测过程。

10. GoogLeNet

GoogLeNet 的主要创新在于：

A. 使用 Inception 模块融合多尺度特征
B. 通过 Batch Normalization 加速训练
C. 引入残差连接
D. 采用 Dropout 防止过拟合

独立核验答案：A。GoogLeNet/Inception v1 的标志是并行的 $1\times1$、$3\times3$、$5\times5$ 卷积与池化分支，并以 $1\times1$ 卷积控制计算量。残差连接属于 ResNet；Dropout 更早已出现；BN 不是 v1 的主要原创。

第 1 题：找朋友

题目描述

有 $N$ 个 A 班同学和 $N$ 个 B 班同学，兴趣值分别为 $A_1,\ldots,A_N$ 与 $B_1,\ldots,B_N$。将两班一一配对。若 A 班第 $i$ 人与 B 班第 $p_i$ 人配对，矛盾值为

\[(A_i+B_{p_i})\bmod M,\]

其中 $p$ 是 $1$ 到 $N$ 的排列。求所有配对矛盾值之和的最小值。共有 $T$ 组数据。

输入与约束

第一行：$T$，$1\le T\le10^5$。
每组第一行：$N,M$，$1\le N\le10^5$，$1\le M\le10^9$。
每组第二、三行：各 $N$ 个整数 $A_i$、$B_i$，且 $0\le A_i,B_i<M$。
所有测试数据的 $N$ 之和不超过 $3\times10^5$。

每组输出一行最小总矛盾值。

样例

输入

输出

0
12

第一组可配成 $(3,2),(2,3),(1,4)$，三对取模结果均为 0。

算法：排序贪心 + 双指针

因为 $0\le A_i,B_j<M$，所以

\[(A_i+B_j)\bmod M=A_i+B_j-M[A_i+B_j\ge M].\]

所有对求和后，$\sum A_i+\sum B_i$ 与配法无关。设满足 $A_i+B_j\ge M$ 的配对数为 $cnt$，答案为

\[\sum A_i+\sum B_i-M\cdot cnt.\]

因此只需最大化达标配对数。将 A 降序、B 升序。依次处理当前最大的未处理 A 值 $x$：不断丢弃所有满足 $x+B_j<M$ 的最小 B；若仍有 B，就让 $x$ 与当前最小可达标 B 配对。

正确性证明

丢弃安全。当前 $x$ 是剩余 A 中最大值。若 $x+b<M$，则任意剩余 $a\le x$ 都有 $a+b<M$，所以 $b$ 不可能出现在任何达标对中。
配对安全。当最小可达标值为 $b$ 时，若某个最优方案让 $x$ 配更大的 $b’$，而 $b$ 配某个 $a\le x$，交换后 $x+b\ge M$；原来若 $a+b’$ 达标，交换后 $a$ 得到的是 $b’$（等价地按两对重新安排），达标对数不会减少。也可视为：给最大 $x$ 使用刚好够用的最小 B，保留更大的 B 只会让余下较小 A 更容易达标。
重复上述交换，可把某个最优方案变成贪心方案而不减少达标对数，故贪心最大化 $cnt$，从而最小化原目标。

复杂度分析

每组排序耗时 $O(N\log N)$，双指针 $O(N)$；额外空间 $O(N)$（计输入及排序数组）。总规模约束下为 $O(\sum N\log N)$。

易错点

必须利用 $A_i,B_i<M$，否则一对可能减去多个 $M$，上述二值改写失效。
目标是最大化“和至少为 $M$”的配对数，不是逐对最小化原余数。
B 指针既表示丢弃也表示已使用，只能单调前进。
总和可能超过 32 位；其他语言应使用 64 位整数。

import sys


def min_conflict(a, b, m):
    total = sum(a) + sum(b)
    a.sort(reverse=True)
    b.sort()
    n = len(a)
    j = 0
    cnt = 0
    for x in a:
        while j < n and x + b[j] < m:
            j += 1
        if j == n:
            break
        cnt += 1
        j += 1
    return total - m * cnt


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    t = next(it)
    out = []
    for _ in range(t):
        n = next(it)
        m = next(it)
        a = [next(it) for _ in range(n)]
        b = [next(it) for _ in range(n)]
        out.append(str(min_conflict(a, b, m)))
    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    main()

第 2 题：滑动窗口

题目描述

给定长度为 $n$ 的下界序列 $b_1,\ldots,b_n$。构造整数序列 $a_1,\ldots,a_n$，满足：

对所有 $i$，$a_i\ge b_i$；
对每个长为 $L$ 的连续窗口， $\left(\sum_{i=p}^{p+L-1}a_i\right)\bmod m=0 \quad(1\le p\le n-L+1).$

求 $\sum_i a_i-\sum_i b_i$ 的最小值。输入保证 $0\le b_i<m$，但构造出的 $a_i$ 不必小于 $m$。

输入与约束

第一行：$n,m,L$，$1\le n,m\le500$，$1\le L\le n$。
第二行：$n$ 个整数 $b_i$，$0\le b_i<m$。
输出一个整数，即最小增量。

样例

输入

5 5 3
3 2 1 2 4

输出

例如构造 $a=[3,4,3,3,4]$，每个长度为 3 的窗口和均被 5 整除，增量为 $17-12=5$。

约束等价变换

令 $S_p=\sum_{i=p}^{p+L-1}a_i$。相邻窗口相减：

\[S_{p+1}-S_p=a_{p+L}-a_p.\]

若所有 $S_p\equiv0\pmod m$，则 $a_{p+L}\equiv a_p\pmod m$。因此按下标模 $L$ 分成 $L$ 组，每组元素必须具有同一余数 $r_j$。第一个窗口还要求

\[\sum_{j=0}^{L-1}r_j\equiv0\pmod m.\]

反过来，这两条也保证第一个窗口及其后的所有窗口和都为 0 模 $m$，故条件等价。

组 $j$ 选择公共余数 $r$ 时，每项只需增加到不小于 $b_i$ 的最近同余整数，代价为

\[cost[j][r]=\sum_{i\equiv j\pmod L}(r-b_i)\bmod m.\]

于是问题成为：每组选择一个余数，使余数和模 $m$ 为 0，并最小化总代价。

$O(nm)$ 分组 DP

若每组都枚举 $m$ 个余数，复杂度是 $O(Lm^2)$。利用代价函数的结构降维：当 $r$ 循环增加 1 时，若没有越过组内某个 $b_i$ 的余数，组内每项都多增 1，代价严格增加；只有到达组内出现过的 $b_i$ 时才可能发生向下跳变。因此局部低点只可能位于该组出现过的 $b_i$。

选元素数最少的一组 star 作为自由组，它保留全部 $m$ 个余数；其他组只枚举其不同的 $b_i$ 值。DP 定义 f[s] 为已处理非自由组的余数和模 $m$ 为 $s$ 时的最小代价。处理完后，自由组唯一选择 $(-s)\bmod m$ 补齐。

候选缩减与正确性证明

前述窗口差分证明了“合法序列”与“组内同余且组余数和为 0”完全等价。
固定组余数后，把每个 $b_i$ 增加 $(r-b_i)\bmod m$ 是满足下界的最小同余值，所以 cost 精确给出该选择的最低代价。
对任意最优余数组合，若某个非自由组 $j$ 的余数不是组内出现过的 $b_i$，将其余数沿循环方向向前减 1，直至到达最近候选点；每步使该组代价减少 $sz_j$。为维持总余数不变，同时让自由组余数加 1；自由组代价每步至多增加 $sz_{star}$。因为自由组规模最小，$sz_{star}\le sz_j$，总成本不增。循环跨越 0 时同样按模意义处理，若遇到自由组代价的向下跳变只会更优。故存在一个最优解，其所有非自由组余数均在候选集合中。
DP 穷举了上述所有规范化最优解，并为每个余数和保留最小代价；最后自由组补齐总余数，所以所得答案最优且可行。

复杂度分析

构造代价表为 $O(nm)$。非自由组候选数之和不超过 $n$，每个候选转移 $m$ 个状态，也是 $O(nm)$。总时间 $O(nm)$，空间 $O(Lm)$；滚动 DP 本身为 $O(m)$。

易错点

分组依据是下标模 $L$，不是值模 $L$；代码采用 0 基下标。
(r - b[i]) % m 在 Python 中天然非负；其他语言需手动修正负余数。
不能把所有组都只限制在出现过的 $b_i$ 上；必须留一个自由组吸收总余数。
自由组必须选规模最小者，交换论证才有 $sz_{star}\le sz_j$。
$m=1$ 时数组长度为 1，算法自然返回 0；$L=n$ 时也无需特判。

import sys


def minimum_increment(n, m, length, b):
    cost = [[0] * m for _ in range(length)]
    groups = []
    for j in range(length):
        values = b[j:n:length]
        groups.append(values)
        row = cost[j]
        for value in values:
            for r in range(m):
                row[r] += (r - value) % m

    free_group = min(range(length), key=lambda j: len(groups[j]))
    inf = 10**30
    dp = [inf] * m
    dp[0] = 0

    for j in range(length):
        if j == free_group:
            continue
        next_dp = [inf] * m
        for r in set(groups[j]):
            add = cost[j][r]
            for s, old in enumerate(dp):
                if old < inf:
                    ns = (s + r) % m
                    candidate = old + add
                    if candidate < next_dp[ns]:
                        next_dp[ns] = candidate
        dp = next_dp

    return min(dp[s] + cost[free_group][(-s) % m] for s in range(m))


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, m, length = data[:3]
    b = data[3:3 + n]
    print(minimum_increment(n, m, length, b))


if __name__ == "__main__":
    main()

四、验证记录

“找朋友”用全排列暴力枚举所有配对，对拍随机小数据：$n=1\ldots7$、$M=1\ldots8$，每组规模组合 100 例，共 5600 例，全部一致。
“滑动窗口”用 $m^L$ 暴力枚举所有组余数组合，对拍随机小数据：$n=1\ldots8$、$m=1\ldots6$、$L=1\ldots n$，每组参数 40 例，共 8640 例，全部一致。
两份程序均按样例执行核验，输出分别为 0 / 12 与 5。
第 8 题另以子集穷举独立核验，最大值为 $840$，拆分为 $2,3,4,5,7$。

这篇文章有帮助吗？

| GitHub 留言