大厂真题 / DeepSeek

DeepSeek 2026-7-12 笔试真题 - Agent 开发岗

本场考试概述

考试时间：2026年7月12日 考试岗位：研发岗（Agent harness / 全栈工程师） 考试时长：3 小时 难度评级：中等偏难

考点分析：

1. 第一题：文本格式化——字符串模拟（难度中等）
2. 第二题：流式分词器——贪心最长匹配 + 哈希表（难度中等）
3. 第三题：正方形覆盖得分——覆盖计数 + 数学推导 + 前 $k$ 大求和（难度困难）

建议策略：

1. 三道题都不是套模板的动态规划或 DFS，考的是把新问题读懂、再一步步实现的能力
2. 前两道理解题意后按要求耐心写就能拿下，第三题要看穿”除以放法数会把因子约掉、答案是整数”这层
3. 别被第三题又长又绕的题干带偏，先从覆盖数的对称性入手

第 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$ 行的位置数为：

这就是一个长度为 $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$ 后恰好约掉：

所以问题简化为：对 $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)$，存放所有得分档

小结

1. 第一题（文本格式化）：纯模拟题，考点是归一化规则的理解和实现。关键是用布尔标记控制”每个间隙只保留第一个标点”，以及超长单词切分时每段 $W-1$ 字母加连字符
2. 第二题（流式分词器）：贪心最长匹配的经典写法——哈希表存映射，每个位置从长到短试探。$L_{\max}$ 很小时直接暴力即可
3. 第三题（正方形覆盖得分）：本题的核心洞察是除以放法数后分子分母完美约分，答案简化为 $R(i) \times C(j)$ 的前 $k$ 大之和。再利用覆盖数取值种类少这一性质，用频次表配对排序解决大规模数据