大厂真题 / DeepSeek
DeepSeek 2026-7-12 笔试真题 - Agent 开发岗
本场考试概述
考试时间：2026年7月12日 考试岗位：研发岗（Agent harness / 全栈工程师） 考试时长：3 小时 难度评级：中等偏难
考点分析：
- 第一题：文本格式化——字符串模拟（难度中等）
- 第二题：流式分词器——贪心最长匹配 + 哈希表（难度中等）
- 第三题：正方形覆盖得分——覆盖计数 + 数学推导 + 前 $k$ 大求和（难度困难）
建议策略：
- 三道题都不是套模板的动态规划或 DFS，考的是把新问题读懂、再一步步实现的能力
- 前两道理解题意后按要求耐心写就能拿下，第三题要看穿”除以放法数会把因子约掉、答案是整数”这层
- 别被第三题又长又绕的题干带偏，先从覆盖数的对称性入手
第 1 题：文本格式化
题目描述
给定一段英文文本，其中排版可能是混乱的：单词之间可能夹着多个连续空格，可能出现多个连续的标点符号，标点符号后面可能没有空格而直接跟着字母。请把这段文本整理成规范的排版。
处理分两步：
归一化：把文本切分成若干单词（由连续字母组成）与标点符号，空格只起分隔作用。两个单词之间不论出现多少个标点符号（其间也可能夹杂空格），都只保留最先出现的那一个，并把它紧贴到前面单词的末尾；若某个标点前面没有任何单词，则丢弃。相邻两个单词（连同紧贴其后的标点）之间用恰好一个空格分隔，整段文本首尾不留空格。标点符号集合为 , . ; : ! ?。
折行：把归一化后的文本按每行最多 $W=80$ 个字符输出，且每一行都不能以空格开头。折行以单词为单位、不拆开单词，采用贪心策略：从左到右依次把单词放入当前行，若加入下一个单词（连同分隔它的一个空格）会使当前行超过 $W$ 个字符，就另起一行。若某个单词自身长度超过 $W$，则它从新的一行开始，按每行前 $W-1$ 个字母加一个连字符 - 的方式切分，最后剩余不足一行的部分留在当前行。
样例
输入
the quick,brown fox ?? jumps.Over the lazy dog
输出
the quick, brown fox? jumps. Over the lazy dog
思路分析
第一步：将问题拆成两个独立子任务
题目要求很清楚——先归一化再折行，两步互不干扰。归一化只需要一次线性扫描；折行也是一次线性扫描。重点是把归一化的规则吃透。
第二步：归一化规则梳理
从左到右逐字符扫描原串：
- 遇到空格：跳过，空格只是分隔符
- 遇到字母：连续字母切出一个单词，压入结果列表，同时清除”本间隙已保留标点”的标记
- 遇到标点：如果本间隙还没保留过标点、且前面已有单词，就把标点贴到前一个单词末尾并标记”已保留”；否则丢弃
这样一遍扫完，结果列表里每个元素就是”一个单词 + 可能紧贴的一个标点”。
第三步：贪心折行
维护当前行字符串 cur。对每个单元 t：
- 如果
cur为空，直接放入（放不下说明是超长词） - 如果
len(cur) + 1 + len(t) <= W，接上 - 否则结算当前行，
t放到新行
超长单词特殊处理：每行取前 $W-1$ 个字母加 -，循环切到剩余部分不超过 $W$ 为止。
题解代码
import sys
input = sys.stdin.readline
WIDTH = 80
def solve():
s = input().rstrip('\n').rstrip('\r')
puncts = set(',.;:!?')
units = []
n = len(s)
i = 0
prev_punct = False
while i < n:
c = s[i]
if c == ' ':
i += 1
continue
if c.isalpha():
j = i
while j < n and s[j].isalpha():
j += 1
units.append(s[i:j])
prev_punct = False
i = j
else:
if not prev_punct and units:
if units[-1][-1].isalpha():
units[-1] += c
prev_punct = True
i += 1
lines = []
cur = ""
for t in units:
if not cur:
fits = len(t) <= WIDTH
else:
fits = len(cur) + 1 + len(t) <= WIDTH
if fits:
if cur:
cur += ' '
cur += t
else:
if cur:
lines.append(cur)
cur = ""
if len(t) <= WIDTH:
cur = t
else:
while len(t) > WIDTH:
lines.append(t[:WIDTH - 1] + '-')
t = t[WIDTH - 1:]
cur = t
if cur:
lines.append(cur)
print('\n'.join(lines))
solve()
复杂度分析
时间复杂度：$O(n)$，归一化和折行各扫描一次 空间复杂度：$O(n)$，存储单词列表与输出行
第 2 题：流式分词器
题目描述
给定一个从字符串到整数编号（token-id）的映射表，再给定一段由小写字母组成的文本。请把文本从左到右切分成若干 token：在当前位置，总是贪心匹配能匹配到的最长 token，输出它的编号，然后从该 token 之后继续。
保证文本中出现的每个字符本身都是映射表中的一个 token（即所有长度为 $1$ 的 token 都存在），因此贪心匹配总能成功。
样例
输入
5
a 1
ab 2
abc 3
b 4
c 5
abcab
输出
3 2
思路分析
第一步：理解贪心最长匹配
站在当前位置 $i$，所有以 $s[i]$ 开头且出现在映射表中的 token 都是候选。我们要选最长的那个，输出编号后跳过它的长度。题目保证每个单字符都是 token，所以至少能匹配长度 $1$，不会卡死。
第二步：为什么从长往短试
事先不知道最长匹配有多长。最直接的做法是从最大可能长度往下逐一尝试：设所有 token 中最长的长度为 $L_{\max}$，在位置 $i$ 处候选长度上界为 $\min(L_{\max},\, n-i)$。从这个上界开始递减，第一个在哈希表里命中的就是最长匹配。
第三步：时间复杂度
每个位置最多尝试 $L_{\max}$ 次（本题 $L_{\max} \leq 20$），每次截子串 + 查表 $O(L_{\max})$，总共 $O(n \cdot L_{\max}^2)$，在 $n \leq 10^5$ 时绰绰有余。
题解代码
import sys
input = sys.stdin.readline
def solve():
n = int(input())
token2id = {}
max_len = 1
for _ in range(n):
parts = input().split()
tok, tid = parts[0], parts[1]
token2id[tok] = tid
if len(tok) > max_len:
max_len = len(tok)
s = input().strip()
N = len(s)
res = []
i = 0
while i < N:
L = min(max_len, N - i)
for l in range(L, 0, -1):
sub = s[i:i + l]
if sub in token2id:
res.append(token2id[sub])
i += l
break
print(' '.join(res))
solve()
复杂度分析
时间复杂度：$O(n \cdot L_{\max}^2)$，其中 $L_{\max}$ 为最长 token 长度（$\leq 20$） 空间复杂度：$O(S)$，$S$ 为所有 token 的总长度
第 3 题：正方形覆盖得分
题目描述
在一个 $n$ 行 $m$ 列的矩阵中放置一个边长为 $d$ 的正方形，正方形必须完整落在矩阵内部。左上角行号可取 $a = n-d+1$ 种、列号可取 $b = m-d+1$ 种，放置方式总数为 $a \times b$。
对矩阵中每个格子 $(i,j)$ 定义得分：等于”覆盖到第 $i$ 行的放置方式数”乘以”覆盖到第 $j$ 列的放置方式数”。请选出得分最高的前 $k$ 个格子，求出这 $k$ 个得分之和，再除以放置方式总数 $a \times b$。保证比值是整数。
输入一行四个整数 $n, m, k, d$。输出一个整数。
样例
输入
3 3 3 2
输出
8
思路分析
第一步：推导每行的覆盖数
边长为 $d$ 的正方形在竖直方向上压住第 $i$ 行（$0$-indexed），等价于窗口左端 $\leq i$ 且窗口右端 $\geq i$。设左上角行号可取 $0 \sim a-1$（共 $a = n-d+1$ 个位置），则能压住第 $i$ 行的位置数为：
\[R(i) = \min(i+1,\; d,\; a,\; n-i)\]这就是一个长度为 $d$ 的窗口在 $n$ 行上滑动时盖住第 $i$ 行的窗口个数。列方向完全对称，得到 $C(j)$。
第二步：约掉放法数
格子 $(i,j)$ 被覆盖的放法数 = “竖直方向压住第 $i$ 行的位置数 $\times$ 水平位置总数 $b$” $\times$ “水平方向压住第 $j$ 列的位置数 $\times$ 竖直位置总数 $a$” 的某种组合？不，更简单：覆盖到第 $i$ 行的完整正方形个数 = $R(i) \times b$（竖直选了 $R(i)$ 种，水平随便选 $b$ 种）。覆盖到第 $j$ 列的完整正方形个数 = $C(j) \times a$。
于是得分 = $R(i) \times b \times C(j) \times a$，除以放法总数 $a \times b$ 后恰好约掉：
\[\text{答案中每个格子的贡献} = R(i) \times C(j)\]所以问题简化为：对 $R(i) \times C(j)$ 的所有 $n \times m$ 个值取前 $k$ 大求和。
第三步：用频次避免逐格枚举
$n, m$ 可能很大（$\leq 10^9$），逐格枚举不可能。但 $R(i)$ 的取值种类很少——它的值域是 $1$ 到 $\min(d, a)$，呈先递增再平台再递减的对称形状，不同取值不超过 $O(\min(d, n))$ 种。用哈希表统计每种值出现多少次即可。
列方向同理得到 $C$ 的频次表。将所有 $(R \text{值}, C \text{值})$ 配对得到若干”档”，每档得分为 $R \times C$，格子数为对应频次之积。按得分从大到小排序后贪心取满 $k$ 个格子即为答案。
题解代码
import sys
input = sys.stdin.readline
def solve():
n, m, k, d = map(int, input().split())
a = n - d + 1
b = m - d + 1
freq_r = {}
for i in range(n):
r = min(i + 1, d, a, n - i)
freq_r[r] = freq_r.get(r, 0) + 1
freq_c = {}
for j in range(m):
c = min(j + 1, d, b, m - j)
freq_c[c] = freq_c.get(c, 0) + 1
pairs = []
for r, fr in freq_r.items():
for c, fc in freq_c.items():
pairs.append((r * c, fr * fc))
pairs.sort(key=lambda x: -x[0])
remaining = k
total = 0
for score, cnt in pairs:
take = min(cnt, remaining)
total += score * take
remaining -= take
if remaining == 0:
break
print(total)
solve()
复杂度分析
时间复杂度：$O(n + m + P \log P)$，其中 $P$ 为不同 $(R,C)$ 配对数，$P \leq \min(d,n) \times \min(d,m)$ 空间复杂度：$O(P)$，存放所有得分档
小结
- 第一题（文本格式化）：纯模拟题，考点是归一化规则的理解和实现。关键是用布尔标记控制”每个间隙只保留第一个标点”，以及超长单词切分时每段 $W-1$ 字母加连字符
- 第二题（流式分词器）：贪心最长匹配的经典写法——哈希表存映射，每个位置从长到短试探。$L_{\max}$ 很小时直接暴力即可
- 第三题（正方形覆盖得分）：本题的核心洞察是除以放法数后分子分母完美约分，答案简化为 $R(i) \times C(j)$ 的前 $k$ 大之和。再利用覆盖数取值种类少这一性质，用频次表配对排序解决大规模数据