大厂真题 / 百度

百度 2026-8-27 笔试真题 - 算法岗

本场考试概述

考试时间：2026年8月27日

考试岗位：算法岗

难度评级：中等

题型说明：已披露的题型信息显示，本场共有 19 道选择题和 3 道编程题。目前能够可靠还原的选择题只有 10 道，因此本文仅整理这 10 道，不补写其余 9 道；3 道编程题均完整整理。

考点分析：

选择题：数据结构、机器学习评价指标、深度学习损失函数与归一化、大模型评测与 RAG、概率统计；
编程第 1 题：排序贪心；
编程第 2 题：单调队列与滑动窗口最大值；
编程第 3 题：扫描线、优先队列与惰性删除。

建议策略：

选择题大多考查基本定义，先完成确定性强的题目；
第 1 道编程题的答案可能达到 $2\times 10^{14}$，应使用 64 位整数或 Python 整数；
第 2、3 道编程题的关键是把朴素的区间枚举优化为线性扫描；
所有编程题均为多组数据，且单个文件中的总数据规模较大，建议统一使用快速读入。

第 1 部分：基础知识单选题

本场据披露共有 19 道选择题。以下只收录题干、选项和答案均可靠可见的 10 道。

1. 跳表查找

跳表中高层索引用于快速跳过一段有序结点。查找目标值时，较合理的过程是？

A. 从最底层头结点线性扫描到链表结尾
B. 从最高层索引开始逐层向下并向右推进
C. 先重建高层索引，再从底层头结点顺序扫描查找目标
D. 每次随机选择一个结点作为根结点

答案：B

简析：跳表从最高层开始，在当前层向右移动，无法继续时下降一层，直至底层。其期望查找复杂度为 $O(\log n)$。A 会退化为 $O(n)$ 线性扫描；跳表的随机性主要用于插入时确定结点层数，并不是每次查找随机选根。

2. 公开基准的数据污染

模型在公开基准上异常高分，但业务集表现一般，且训练语料可能包含基准答案。应优先排查什么？

A. 线上样本分布变化使模型在公开基准上的得分被低估
B. 评测集污染使模型对公开基准的离线分数被高估
C. 模型参数量不足使业务集得分必然高于公开基准
D. 推理批次过小使基准答案随机进入模型生成结果

答案：B

简析：训练语料中包含评测题及答案，会使模型对公开基准产生记忆，离线成绩因此虚高。这属于评测集污染，而不是推理批次或参数量问题。

3. 多标签分类的输出与损失

一张图片可以同时包含“猫”和“狗”等多个标签。训练这类多标签分类模型时，更合适的输出与损失组合是？

A. 每个标签独立 sigmoid 输出，并配合二元交叉熵
B. 使用聚类簇编号替代监督标签
C. 对标签向量做一个 softmax 输出，并把概率最高的类别作为训练目标
D. 把标签字符串作为卷积核权重

答案：A

简析：多标签任务中，$C$ 个类别分别对应 $C$ 个独立的二分类判断，通常对每个 logit 使用 sigmoid，再逐类计算二元交叉熵。softmax 会强制类别概率和为 $1$，适用于互斥的单标签分类，不适合多个标签同时为真。

4. 类别不平衡与准确率

二分类数据中正例很少。如果只用总体准确率选模型，哪项能力最容易被掩盖？

A. 训练损失在每个批次中都无法执行反向传播
B. 模型对多数负例的整体识别能力可能明显不足
C. 模型对少数正例的识别能力可能明显不足
D. 预测概率无法用于排序，只能输出一个固定类别

答案：C

简析：正例稀少时，即使模型几乎全部预测为负例，也可能得到很高的准确率，但对正例的召回能力很差。应结合 Recall、F1、PR-AUC 等指标评估。

5. RAG 中的向量检索

向量检索把问题和文档片段编码为 embedding 后，相似度分数用于完成哪一步？

A. 根据 token 数量接近程度筛选长度相似的文档片段
B. 按文档写入时间从新到旧排序并返回前若干片段
C. 把查询向量转成类别编号，再按编号查找文档片段
D. 召回与用户问题语义相近的候选文档片段

答案：D

简析：embedding 将查询与文本映射到向量空间，余弦相似度或内积用于衡量语义相关性，据此取 Top-K 候选片段就是 RAG 的召回阶段。

6. Transformer 中的 LayerNorm

Transformer 使用 LayerNorm 时，均值和方差通常沿哪个范围计算？

A. 在全部训练样本上预先计算一组固定均值和方差
B. 在一个批次内按同一隐藏位置聚合不同样本的统计量
C. 只对注意力权重矩阵的每一列做全局归一化处理
D. 沿单个样本的隐藏维度计算归一化统计量

答案：D

简析：LayerNorm 通常对单个样本、单个 token 的隐藏维度 $d_{model}$ 计算均值和方差，不依赖同一批次中的其他样本。B 更接近 BatchNorm 的统计方式。

7. 可解释输出与敏感信息保护

企业模型要说明结论依据，但不能泄露隐藏推理、系统提示词或密钥。回答应包含什么？

A. 给出结论、简洁依据和可核验的关键证据
B. 完整输出内部逐步思考过程，同时隐藏最终使用的证据来源
C. 同时返回系统提示词和工具密钥，交由用户自行审计
D. 只给结论而不提供依据，避免暴露任何模型相关信息

答案：A

简析：合理的可解释输出应给出面向用户的简洁理由与可核验证据，而不是泄露内部推理草稿、系统提示词或密钥。

8. 无偏样本方差

从总体中独立抽取 $n$ 个样本估计总体方差。常见的无偏样本方差公式分母使用哪一项？

A. $n$
B. $2n$
C. $n-1$
D. $n+1$

答案：C

简析：无偏样本方差为

\[s^2=\frac{1}{n-1}\sum_{i=1}^{n}(x_i-\bar{x})^2.\]

因为使用样本均值 $\bar{x}$ 后损失了一个自由度，所以分母取 $n-1$；直接除以 $n$ 会低估总体方差。

9. 最小栈

某最小栈依次执行 push(4)、push(2)、push(5)、pop()。此时调用 getMin()，返回值应为？

A. 4
B. 5
C. 栈为空
D. 2

答案：D

简析：三次入栈后栈内自底向上为 $4,2,5$，pop() 弹出 $5$，剩余元素为 $4,2$，最小值仍为 $2$。

10. 快速排序的一次划分

数组 $[5,2,8,1,4]$ 以 $5$ 为基准做一次快速排序划分。无论具体交换过程如何，基准最终有序位置的下标应为？

A. 2
B. 1
C. 3
D. 4

答案：C

简析：比基准 $5$ 小的元素是 $2,1,4$，共 3 个，因此划分后 $5$ 位于从 0 开始计数的下标 $3$。具体划分过程可能不同，但基准的最终有序位置不变。

第 2 部分：编程题

第 1 题：刀盾分配最小总伤害

题目描述

你将连续遭遇 $n$ 轮怪物攻击，第 $i$ 轮怪物造成的伤害为 $a_i$。你有 $m$ 把刀和 $k$ 面盾，每件道具只能使用一次。每一轮必须选择以下一种策略：

使用 1 把刀，直接击杀怪物，本轮受到 $0$ 点伤害；
使用 1 面盾，抵挡 $p$ 点伤害，本轮实际受到 $\max(0,a_i-p)$ 点伤害；
不使用道具，受到 $a_i$ 点伤害。

请合理分配刀与盾，使 $n$ 轮攻击的总伤害最小。

输入描述

第一行输入整数 $T$，表示测试数据组数，满足 $1\le T\le 10^5$。

每组数据包含两行：

第一行输入 $n,m,k,p$，满足 $1\le n\le 2\times 10^5$，$0\le m,k\le n$，$1\le p\le 10^9$；
第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，满足 $0\le a_i\le 10^9$。

保证所有测试数据的 $n$ 之和不超过 $2\times 10^5$。

输出描述

对于每组测试数据，输出一个整数，表示最优策略下受到的最小总伤害。

样例

输入

输出

7
140

样例解释：第一组中，对伤害 $20$ 的一轮使用刀，对伤害 $10$ 的一轮使用盾，最后一轮直接承受 $2$ 点伤害，总伤害为 $0+5+2=7$。第二组没有刀，把盾用于伤害 $100$ 的一轮，总伤害为 $90+20+20+10=140$。

思路

不使用道具时，总伤害为 $\sum a_i$。对伤害 $a_i$ 的一轮：

使用刀的减伤收益为 $a_i$；
使用盾的减伤收益为 $\min(a_i,p)$。

两种收益都随 $a_i$ 单调不减，因此道具一定可以安排在伤害最大的若干轮上。将伤害降序排列后，还需决定刀和盾的先后次序。

若 $x\ge y$，原方案对 $x$ 使用刀、对 $y$ 使用盾，其收益为

\[x+\min(y,p).\]

交换两件道具后的收益为

\[y+\min(x,p).\]

二者之差为

\[\bigl(x+\min(y,p)\bigr)-\bigl(y+\min(x,p)\bigr) =\max(0,x-p)-\max(0,y-p)\ge 0.\]

所以更大的伤害优先使用刀不会更差。最终只需将数组降序排序：前 $m$ 轮使用刀，接下来的 $k$ 轮使用盾，其余轮次直接承受伤害。

正确性证明

引理 1：存在一个最优方案，使所有被分配道具的轮次构成降序数组的一个前缀。

证明：若某个较小伤害 $y$ 使用了某类道具，而更大的伤害 $x\ge y$ 没有使用道具，则把该道具从 $y$ 移到 $x$。刀的收益从 $y$ 变为 $x$，盾的收益从 $\min(y,p)$ 变为 $\min(x,p)$，均不会减小。反复交换即可得到前缀形式。引理得证。

引理 2：在使用道具的前缀中，可以让所有刀排在所有盾之前而不降低收益。

证明：若较大的伤害 $x$ 使用盾、较小的伤害 $y$ 使用刀，则交换后收益变化为

\[\max(0,x-p)-\max(0,y-p)\ge 0.\]

因此交换不会使收益下降。消除所有这类逆序后，刀均位于盾之前。引理得证。

由引理 1 和引理 2，降序数组中前 $m$ 个位置用刀、随后 $k$ 个位置用盾、其余位置不用道具的方案至少与任意最优方案同样好，因此算法得到的总伤害最小。

Python ACM 题解

import sys


def min_damage(a, knives, shields, block):
    a.sort(reverse=True)
    total = 0
    n = len(a)

    knife_end = min(knives, n)
    shield_end = min(knives + shields, n)

    for i in range(knife_end, shield_end):
        total += max(0, a[i] - block)
    for i in range(shield_end, n):
        total += a[i]
    return total


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    ptr = 0
    t = data[ptr]
    ptr += 1
    out = []

    for _ in range(t):
        n, m, k, p = data[ptr:ptr + 4]
        ptr += 4
        a = data[ptr:ptr + n]
        ptr += n
        out.append(str(min_damage(a, m, k, p)))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度：每组数据排序耗时 $O(n\log n)$，之后扫描耗时 $O(n)$，总计 $O(n\log n)$。

空间复杂度：包含输入数组与排序占用，总计 $O(n)$。

易错点

刀应优先分配给最大伤害，盾分配给其后的较大伤害，不能只按两类道具各自的局部收益独立选择；
盾后伤害为 $\max(0,a_i-p)$，不能出现负数；
$m+k$ 可能大于 $n$，下标要截断；
答案最大可达 $2\times 10^{14}$，非 Python 语言需使用 64 位整数。

第 2 题：窗口内严格极峰位置

题目描述

给定长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$，以及非负整数窗口距离 $d$。

定义位置 $i$ 是一个 $d$-极峰，当且仅当对所有满足

\[1\le j\le n,\qquad 1\le \lvert j-i\rvert\le d\]

的位置 $j$，都有 $a_i>a_j$。

请找出所有 $d$-极峰的位置，并按从小到大输出。特别地，当 $d=0$ 时，每个位置都是 $d$-极峰。

输入描述

第一行输入整数 $T$，表示测试数据组数，满足 $1\le T\le 10^5$。

每组数据包含两行：

第一行输入 $n,d$，满足 $1\le n\le 2\times 10^5$，$0\le d\le 2\times 10^5$；
第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，满足 $-10^9\le a_i\le 10^9$。

保证所有测试数据的 $n$ 之和不超过 $2\times 10^5$。

输出描述

对于每组测试数据输出两行：

第一行输出 $d$-极峰的数量 $k$；
第二行输出 $k$ 个严格递增的位置下标。若 $k=0$，仍需输出一个空行。

样例

输入

2
2
3 3 2 5 4 4 6
0
2 1 3 3

输出

样例解释：第一组中，位置 5 的值为 5，严格大于距离不超过 2 的其他位置；位置 8 的值为 6，也严格大于其窗口内其他值。位置 2 与位置 3 的值相等，因此二者都不是严格极峰。第二组中 $d=0$，每个位置都不需要与其他位置比较，所以全部满足条件。

思路

对每个位置逐一检查左右至多 $2d$ 个邻居，最坏复杂度为 $O(nd)$，无法通过。极峰条件可以改写为

\[a_i> \max\left( \max_{\max(1,i-d)\le j\le i-1}a_j, \max_{i+1\le j\le \min(n,i+d)}a_j \right).\]

因此只需预处理每个位置左侧窗口和右侧窗口的最大值。

使用单调队列求左侧窗口最大值：队列存下标，对应数值保持单调不增。扫描到 $i$ 时，先移除小于 $i-d$ 的过期下标，此时队首就是区间 $[i-d,i-1]$ 的最大值；再移除队尾不大于 $a_i$ 的元素并将 $i$ 入队。每个下标至多进队、出队各一次。

把数组反转后运行同一过程，再将结果反转，即可得到原数组每个位置的右侧窗口最大值。空窗口的最大值用负无穷表示。

正确性证明

引理 1：扫描位置 $i$、删除过期下标后，单调队列的队首是左侧有效窗口中的最大值。

证明：队列只保留当前窗口内尚未过期的下标。若一个旧元素不大于后来入队的元素，则在旧元素仍有效的任何未来窗口里，后者也有效且不小于前者，所以删除旧元素不会丢失未来窗口最大值。保留下来的值单调不增，故队首就是最大值。引理得证。

引理 2：算法计算的 right[i] 是位置 $i$ 右侧距离不超过 $d$ 的元素最大值。

证明：反转数组后，原数组位置 $i$ 的右侧窗口恰好映射为反转数组对应位置的左侧窗口。由引理 1，该窗口最大值被正确求出，再反转结果即可恢复原下标。引理得证。

对任意位置 $i$，算法仅在 $a_i$ 同时严格大于左右窗口最大值时将其输出。这等价于 $a_i$ 严格大于距离不超过 $d$ 的所有其他位置，因此算法输出且仅输出全部 $d$-极峰。

Python ACM 题解

import sys
from collections import deque


NEG_INF = float("-inf")


def left_window_max(a, d):
    n = len(a)
    result = [NEG_INF] * n
    queue = deque()

    for i, value in enumerate(a):
        while queue and queue[0] < i - d:
            queue.popleft()

        if queue:
            result[i] = a[queue[0]]

        while queue and a[queue[-1]] <= value:
            queue.pop()
        queue.append(i)

    return result


def find_peaks(a, d):
    left = left_window_max(a, d)
    right = left_window_max(a[::-1], d)[::-1]

    peaks = []
    for i, value in enumerate(a):
        if value > left[i] and value > right[i]:
            peaks.append(i + 1)
    return peaks


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    ptr = 0
    t = data[ptr]
    ptr += 1
    out = []

    for _ in range(t):
        n, d = data[ptr], data[ptr + 1]
        ptr += 2
        a = data[ptr:ptr + n]
        ptr += n

        peaks = find_peaks(a, d)
        out.append(str(len(peaks)))
        out.append(" ".join(map(str, peaks)))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度：左右两次单调队列扫描均为 $O(n)$，总计 $O(n)$。

空间复杂度：最大值数组和队列共占用 $O(n)$。

易错点

条件是严格大于，相等的邻居也会使当前位置不成立；
左窗口不包含当前位置，必须先记录最大值，再将当前位置入队；
$d=0$ 时左右窗口都为空，所有位置都应输出；
当 $d>n$ 时窗口自然截断到数组边界，不能访问越界；
没有极峰时，数量行之后仍要输出空白的第二行。

第 3 题：雾幕聚光最终亮度

题目描述

一条直线舞台上有编号为 $1$ 到 $n$ 的灯位，第 $i$ 个灯位的初始亮度为整数 $a_i$。有两类覆盖连续灯位的装置同时生效：

雾幕：给定区间 $[l,r]$ 及上界 $p$，限制区间内灯位的亮度不超过 $p$；
聚光：给定区间 $[l,r]$ 及下界 $q$，限制区间内灯位的亮度不低于 $q$。

对于每个位置 $i$：

将覆盖它的所有聚光下界的最大值记为 $L_i$；若没有聚光覆盖，令 $L_i=0$；
将覆盖它的所有雾幕上界的最小值记为 $U_i$；若没有雾幕覆盖，令 $U_i=+\infty$。

最终亮度为

\[b_i=\min\bigl(\max(a_i,L_i),U_i\bigr).\]

请输出所有位置的最终亮度 $b_1,b_2,\ldots,b_n$。

输入描述

第一行输入整数 $T$，表示测试数据组数，满足 $1\le T\le 10^5$。

每组数据格式如下：

第一行输入 $n,m_f,m_s$，满足 $1\le n\le 2\times 10^5$，$0\le m_f,m_s\le 2\times 10^5$；
第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，满足 $0\le a_i\le 10^9$；
接下来 $m_f$ 行，每行输入 $l,r,p$，表示一个雾幕，满足 $1\le l\le r\le n$，$0\le p\le 10^9$；
接下来 $m_s$ 行，每行输入 $l,r,q$，表示一个聚光，满足 $1\le l\le r\le n$，$0\le q\le 10^9$。

保证所有测试数据的 $n$ 之和、$m_f$ 之和、$m_s$ 之和均不超过 $2\times 10^5$。

输出描述

对于每组测试数据，输出一行 $n$ 个整数，依次表示 $b_1,b_2,\ldots,b_n$。

样例

输入

输出

6 3 3 2 3
1 4 4 1

样例解释：第一组中，各位置的聚光下界为 $6,6,6,2,2$，雾幕上界为 $+\infty,3,3,3,5$，代入公式后得到 $6,3,3,2,3$。第二组中，雾幕将整个区间的上界限制为 $4$；位置 2、3 虽分别有下界 $7$、$8$，仍会被上界截断，最终结果为 $1,4,4,1$。

思路

$L_i$ 和 $U_i$ 相互独立，可以拆成两个同构问题：给定若干带权区间，求每个位置被覆盖区间权值的最大值或最小值。

从左到右扫描位置。预先按左端点把区间挂到对应位置：

扫描到位置 $i$ 时，把左端点为 $i$ 的区间加入堆；
若堆顶区间的右端点小于 $i$，说明它已经过期，将其弹出，直到堆顶仍覆盖 $i$；
此时堆顶就是覆盖 $i$ 的有效区间中权值最优者。

求聚光下界 $L_i$ 时使用大根堆；Python 中可把权值取负后放入小根堆。求雾幕上界 $U_i$ 时直接使用小根堆。过期但不在堆顶的区间暂时保留，等它到达堆顶时再删除，这就是惰性删除。

无聚光覆盖时取 $L_i=0$；无雾幕覆盖时可用 $2\times 10^9$ 作为正无穷哨兵，因为它大于所有 $a_i$、$p$ 和 $q$。

正确性证明

引理 1：扫描到位置 $i$ 并完成堆顶过期元素删除后，堆顶区间一定覆盖位置 $i$。

证明：所有入堆区间的左端点都不大于 $i$。删除过程保证堆顶右端点不小于 $i$，因此堆顶满足 $l\le i\le r$。引理得证。

引理 2：求最大值时，堆顶给出覆盖位置 $i$ 的最大权值；求最小值时，堆顶给出最小权值。

证明：若堆中权值更优的区间已经过期，它会排在当前堆顶之前，并在删除循环中被弹出。循环结束后，根据堆序，当前堆顶的权值不劣于任何仍在堆中的区间；由引理 1，它又是有效区间，因此就是所有覆盖 $i$ 的区间中的最优权值。非堆顶的过期区间不会影响堆顶选择。引理得证。

由引理 2，两次扫描分别正确求出每个位置的 $L_i$ 与 $U_i$。题目规定最终亮度为 $\min(\max(a_i,L_i),U_i)$，算法逐位置代入该式，所以输出的所有 $b_i$ 均正确。

Python ACM 题解

import heapq
import sys


INF = 2 * 10 ** 9


def range_maximums(n, segments):
    starts = [[] for _ in range(n + 2)]
    for left, right, value in segments:
        starts[left].append((value, right))

    result = [0] * (n + 1)
    heap = []

    for i in range(1, n + 1):
        for value, right in starts[i]:
            heapq.heappush(heap, (-value, right))

        while heap and heap[0][1] < i:
            heapq.heappop(heap)

        if heap:
            result[i] = -heap[0][0]

    return result


def range_minimums(n, segments):
    starts = [[] for _ in range(n + 2)]
    for left, right, value in segments:
        starts[left].append((value, right))

    result = [INF] * (n + 1)
    heap = []

    for i in range(1, n + 1):
        for value, right in starts[i]:
            heapq.heappush(heap, (value, right))

        while heap and heap[0][1] < i:
            heapq.heappop(heap)

        if heap:
            result[i] = heap[0][0]

    return result


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    ptr = 0
    t = data[ptr]
    ptr += 1
    out = []

    for _ in range(t):
        n, fog_count, spot_count = data[ptr:ptr + 3]
        ptr += 3

        initial = data[ptr:ptr + n]
        ptr += n

        fog = []
        for _ in range(fog_count):
            left, right, upper = data[ptr:ptr + 3]
            ptr += 3
            fog.append((left, right, upper))

        spot = []
        for _ in range(spot_count):
            left, right, lower = data[ptr:ptr + 3]
            ptr += 3
            spot.append((left, right, lower))

        lower_bounds = range_maximums(n, spot)
        upper_bounds = range_minimums(n, fog)

        final = []
        for i in range(1, n + 1):
            brightness = max(initial[i - 1], lower_bounds[i])
            brightness = min(brightness, upper_bounds[i])
            final.append(brightness)

        out.append(" ".join(map(str, final)))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

复杂度分析

每个区间至多入堆、出堆各一次。

时间复杂度：单组总计

\[O\bigl((n+m_f+m_s)\log(m_f+m_s+1)\bigr),\]

空间复杂度：总计 $O(n+m_f+m_s)$。

易错点

聚光取覆盖下界的最大值，雾幕取覆盖上界的最小值，两类堆不要写反；
区间端点均为闭区间，只有当 $r<i$ 时才过期；
新区间必须先入堆，再查询当前位置；
最终操作顺序是先执行下界约束，再执行上界约束，即 $\min(\max(a_i,L_i),U_i)$；
当 $L_i>U_i$ 时无需特判，公式会自然得到 $U_i$；
无覆盖时的默认值分别是 $0$ 与 $+\infty$。

复盘建议

遇到“有限资源分配给若干位置”的题目，先把操作转换成收益，再研究收益的单调性和交换性质；
“严格大于一个区间内所有元素”通常可以转化为区间最大值查询；
大量区间共同作用于每个点时，可考虑扫描线，并用堆维护当前仍有效的区间；
单调队列要特别注意窗口是否包含当前位置，以及相等元素对严格不等式的影响；
ACM 模式下应统一处理快速输入、空输出行和整数溢出。

这篇文章有帮助吗？

| GitHub 留言