大厂真题 / 京东

京东 2026-8-29 笔试真题 - 算法岗

本场考试概述

考试时间：2026 年 8 月 29 日

考试岗位：算法岗

题型：2 道编程题

难度评级：中等

考点分析：

第 1 题：交替字符串、子序列计数、字典序定位、动态规划（中等）。
第 2 题：感知机二分类、在线训练、NumPy、JSON 输入输出（中等）。

建议策略：

第 1 题先观察交替串的形态和整体字典序，再统计每种候选串对应的下标集合数；计数超过查询名次后可以直接截断。
第 2 题严格复现题面给定的训练规则，尤其注意分数等于零时归入正类、训练样本不能打乱、权重必须在线更新。

第 1 题：字典序第 k 个交替串

题目描述

给定一个长度为 $n$ 的 01 字符串

\[s=s_1s_2\cdots s_n。\]

从 $s$ 中选择一个下标集合

\[1\le p_1<p_2<\cdots<p_m\le n，\]

并按下标顺序拼接得到子序列

\[t=s_{p_1}s_{p_2}\cdots s_{p_m}。\]

其中 $m$ 可以为 $0$，此时得到空串。

如果 $t$ 中不存在相邻的两个 0，也不存在相邻的两个 1，即对任意 $1\le i<\lvert t\rvert$ 都有

\[t_i\ne t_{i+1}，\]

则称 $t$ 为交替串。

考虑所有能够得到交替串的下标集合。不同下标集合视为不同方案，因此同一个字符串可能重复出现多次。将所有方案得到的字符串按字典序从小到大排序，求第 $k$ 个字符串；如果不存在第 $k$ 个字符串，输出 -1。

字典序规则如下：

从左到右比较，第一处不同字符较小者更小；
如果一个字符串是另一个字符串的前缀，则较短者更小；
空串也参与排序。

输入描述

第一行输入整数 $T$，表示测试数据组数，满足

\[1\le T\le 2\times10^3。\]

每组测试数据包含两行：

第一行输入两个整数 $n,k$，满足

\[1\le n\le2\times10^3，\qquad 2\le k\le10^{15}；\]

第二行输入一个长度为 $n$ 的 01 字符串 $s$。

保证单个测试文件中所有测试数据的 $n$ 之和不超过 $2\times10^3$。由于 $k\ge2$，答案不会是排在第一位的空串。

输出描述

对每组测试数据输出一行：如果第 $k$ 个字符串存在，输出该字符串；否则输出 -1。

样例 1

输入

输出

1
01

解释

第一组共有六个合法方案，排序后为：

空串, 0, 1, 1, 10, 10

第 $4$ 个字符串是 1。

第二组共有四个方案，排序后为：

空串, 0, 01, 1

第 $3$ 个字符串是 01。

样例 2

输入

输出

0101
-1

思路分析

1. 交替串的形态是唯一的

首字符和长度一旦确定，后续字符就必须在 0 与 1 之间交替。因此，长度为 $L$ 的候选串至多只有两种：

以 0 开头：0、01、010、……；
以 1 开头：1、10、101、……。

连同空串，一共只有 $2n+1$ 个候选字符串形态。某些候选串可能不是 $s$ 的子序列，此时它的方案数为零。

2. 候选串的字典序固定

所有以 0 开头的字符串都小于所有以 1 开头的字符串。同一起始字符下，较短的交替串是较长交替串的前缀，因此较短者更小。

所以所有方案的排序分段固定为：

空串；
以 0 开头的候选串，按长度递增；
以 1 开头的候选串，按长度递增。

同一个候选串若由多个下标集合得到，就在对应分段中连续出现多次。

3. 动态规划统计方案数

分别统计以 0 和 1 开头的交替串。固定起始字符 first，定义：

\[dp[L]=\text{已扫描前缀中，长度为 }L\text{ 的目标交替串的子序列方案数}。\]

初始化：

\[dp[0]=1，\qquad dp[L]=0\quad(L\ge1)。\]

目标串第 $L$ 位应为

\[\operatorname{expected}(L)=\text{first}\oplus((L-1)\bmod2)。\]

扫描到字符 bit 时，如果它等于目标串第 $L$ 位，就可以把它接在每个长度为 $L-1$ 的方案后面：

\[dp[L]\leftarrow dp[L]+dp[L-1]。\]

长度必须从大到小更新，以免同一个原字符串位置在一轮中被重复使用。

方案数可能非常大，但定位第 $k$ 个结果时只需要判断计数是否达到当前名次，所以每次加法后将计数截断到 $k$ 即可。

4. 按分段定位第 k 个方案

空串占据第一个位置，因此先令 remaining = k - 1。随后按照固定字典序遍历两种起始字符和所有长度：

若 remaining <= dp[L]，答案就是当前候选交替串；
否则令 remaining -= dp[L]，继续检查下一段；
所有分段都不足以覆盖目标名次时，输出 -1。

正确性证明

引理 1：固定首字符和长度后，至多存在一个交替串。

证明：首字符已知。交替串中每一位都必须与前一位不同，而字符集只有 0 和 1，因此其余各位均被唯一确定。证毕。

引理 2：算法遍历候选串的顺序与所有合法方案按字典序排序后的分段顺序一致。

证明：空串是所有非空串的前缀，故排在第一位。以 0 开头的串均小于以 1 开头的串。同一起始字符下，由引理 1，较短候选串是较长候选串的前缀，所以按长度递增。相同候选串对应的多个方案在排序后连续出现。证毕。

引理 3：动态规划得到的 dp[L] 等于目标长度为 $L$ 的交替串在 $s$ 中的子序列方案数。

证明：初始时空串恰有一种方案。扫描一个新字符时，原有方案仍然存在；当新字符等于目标串第 $L$ 位时，每个长度为 $L-1$ 的旧方案都能唯一扩展为一个以当前字符结尾的长度 $L$ 方案。倒序更新保证当前字符只使用一次。这两类方案互不重叠且覆盖全部可能，故结论成立。计数截断不会改变其是否覆盖不超过 $k$ 的查询名次。证毕。

定理：算法输出排序后的第 $k$ 个交替串；若不存在，则输出 -1。

证明：由引理 2，算法按正确的字典序依次遍历所有候选分段；由引理 3，每个分段的大小均被正确计算。因此逐段扣减后首次覆盖 remaining 的候选串就是第 $k$ 个结果。若遍历结束仍未覆盖，合法方案总数小于 $k$，输出 -1 正确。证毕。

ACM Python 代码

import sys


def count_patterns(s, first, cap):
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1

    for ch in s:
        bit = ord(ch) - ord("0")
        for length in range(n, 0, -1):
            expected = first ^ ((length - 1) & 1)
            if bit == expected:
                dp[length] = min(cap, dp[length] + dp[length - 1])

    return dp


def solve_one(s, k):
    remaining = k - 1  # 跳过排在第一位的空串

    for first in (0, 1):
        counts = count_patterns(s, first, k)
        base = "01" if first == 0 else "10"

        for length in range(1, len(s) + 1):
            if remaining <= counts[length]:
                return (base * ((length + 1) // 2))[:length]
            remaining -= counts[length]

    return "-1"


def main():
    input = sys.stdin.readline
    test_cases = int(input())
    answers = []

    for _ in range(test_cases):
        n, k = map(int, input().split())
        s = input().strip()
        answers.append(solve_one(s, k))

    print("\n".join(answers))


if __name__ == "__main__":
    main()

复杂度分析

对一组长度为 $n$ 的数据，两种起始字符各执行一次二维枚举。

时间复杂度：$O(n^2)$。

空间复杂度：$O(n)$。

因为所有测试数据的长度之和不超过 $2000$，最坏情况下总运算量不超过 $O(2000^2)$。

易错点

不同下标集合算不同方案，不能只统计不同字符串的个数。
空串参与排序并占据第一位，定位前要先扣除这一项。
同一起始字符下按长度递增，而不是把所有候选串直接按长度混排。
子序列 DP 必须倒序更新长度，避免重复使用当前字符。
计数会迅速增大，应截断到查询所需上限，避免无意义的大整数运算。

第 2 题：感知机二分类

题目描述

仅使用 NumPy 实现经典的 Perceptron（感知机）二分类算法，并对测试集输出预测标签。

原始标签为 $y\in{0,1}$。训练时将其映射为

\[y'=2y-1，\]

即 0 映射为 $-1$，1 映射为 $+1$。

对原始特征向量

\[x=[x_1,x_2,\ldots,x_d]\]

在最前面补一个常数 $1$，得到包含偏置项的增广向量

\[\bar{x}=[1,x_1,x_2,\ldots,x_d]。\]

权重向量初始化为全零，学习率固定为 $1.0$，训练轮数固定为 $10$。每一轮都必须按照训练样本的原始顺序逐条处理。

对当前样本，计算分数

\[z=w^\mathsf{T}\bar{x}。\]

预测符号定义为

\[\operatorname{sign}(z)= \begin{cases} +1,&z\ge0,\\ -1,&z<0。 \end{cases}\]

如果预测标签与真实映射标签不同，则立即更新

\[w\leftarrow w+1.0\times y'\bar{x}。\]

预测正确时不更新。测试阶段使用同一套符号规则，再把 $-1$ 映射回 0、$+1$ 映射回 1。

输入描述

标准输入为一个 JSON 对象，包含两个键：

train：训练列表，每个元素为 [特征列表, 标签]，标签只取 0 或 1；
test：测试列表，每个元素为一组特征，维度与训练特征一致。

输入结构示例：

{"train": [[[0], 0], [[1], 0], [[4], 1]], "test": [[0], [2], [4]]}

输出描述

输出一行 JSON 整数数组，每个元素为 0 或 1，顺序与 test 中的样本顺序一致。

样例 1

输入

{"train": [[[0], 0], [[1], 0], [[4], 1], [[5], 1]], "test": [[0], [1], [2], [3], [4], [5]]}

输出

[0, 0, 1, 1, 1, 1]

样例 2

输入

{"train": [[[0, 0], 0], [[2, 0], 1]], "test": [[0, 0], [2, 0], [1, 0]]}

输出

[0, 1, 1]

思路分析

这是一道规则复现题。感知机本身并不复杂，关键是准确实现给定的训练过程。

1. 标签与偏置统一表示

将标签映射到 $-1$ 和 $+1$ 后，正负两类误分类都能使用同一个更新式。把常数 $1$ 添加到每条特征最前面后，偏置也成为权重向量的一部分，无需单独维护。

2. 严格执行在线训练

感知机是在线算法：当前样本触发的权重更新必须立即影响下一条样本。因此训练阶段需要双重循环，不能把一轮内所有样本的梯度一次性相加，也不能改变样本顺序。

分数等于零时必须预测为 $+1$。初始权重全为零，所以第一条训练样本的分数必然为零；若把判断误写成 score > 0，后续整条更新轨迹都可能改变。

3. 测试阶段批量计算

训练完成后，权重不再变化，各测试样本彼此独立。此时可以用一次矩阵乘法计算所有分数，并通过 scores >= 0 批量映射为 0/1 标签。

正确性证明

引理 1：增广向量上的点积等价于包含独立偏置项的线性分类器。

证明：设增广权重为 $w=[b,w_1,\ldots,w_d]$，则

\[w^\mathsf{T}\bar{x}=b+\sum_{j=1}^{d}w_jx_j，\]

恰好是带偏置的线性模型分数。证毕。

引理 2：训练循环的每一步都与题目规定的感知机更新一致。

证明：算法按原始顺序处理样本，使用 score >= 0 映射为 $+1$，否则映射为 $-1$。仅在预测与真实映射标签不同时执行 $w\leftarrow w+y’\bar{x}$，且更新立即生效。因此每一步的预测、判断和权重变化均与题意一致。证毕。

引理 3：测试阶段输出值与规定的标签反向映射一致。

证明：对每条测试样本，算法使用训练后的同一权重计算分数。分数非负时输出 1，对应 $+1$；分数为负时输出 0，对应 $-1$。证毕。

定理：算法输出题目规定的感知机在固定训练流程下对全部测试样本的预测标签。

证明：由引理 1，算法使用正确的带偏置模型；由引理 2，经过 10 轮后得到的权重与规定训练过程完全相同；由引理 3，测试预测和标签映射正确。因此最终 JSON 数组正确。证毕。

ACM Python 代码

import json
import sys

import numpy as np


EPOCHS = 10
LEARNING_RATE = 1.0


def main():
    data = json.load(sys.stdin)
    train = data["train"]
    test = data["test"]

    train_x = np.asarray([record[0] for record in train], dtype=np.float64)
    labels = np.asarray([record[1] for record in train], dtype=np.int64)
    train_y = 2.0 * labels.astype(np.float64) - 1.0

    sample_count, dimension = train_x.shape
    train_augmented = np.hstack(
        (np.ones((sample_count, 1), dtype=np.float64), train_x)
    )
    weights = np.zeros(dimension + 1, dtype=np.float64)

    for _ in range(EPOCHS):
        for features, target in zip(train_augmented, train_y):
            score = float(weights @ features)
            prediction = 1.0 if score >= 0.0 else -1.0
            if prediction != target:
                weights += LEARNING_RATE * target * features

    if not test:
        print("[]")
        return

    test_x = np.asarray(test, dtype=np.float64)
    test_augmented = np.hstack(
        (np.ones((test_x.shape[0], 1), dtype=np.float64), test_x)
    )
    scores = test_augmented @ weights
    predictions = (scores >= 0.0).astype(np.int64)

    print(json.dumps(predictions.tolist()))


if __name__ == "__main__":
    main()

复杂度分析

设训练样本数为 $n$，测试样本数为 $m$，特征维数为 $d$，固定训练轮数为 $E=10$。

时间复杂度：$O(End+md)$；由于 $E$ 为常数，也可写作 $O(nd+md)$。

空间复杂度：$O(nd+md)$，主要用于增广后的训练和测试矩阵；额外权重空间为 $O(d)$。

易错点

分数等于零时属于正类，判断条件必须是 score >= 0。
每一轮都要保持训练样本的原始顺序，不能随机打乱。
在线更新必须立刻生效，不能改成批量梯度更新。
必须固定训练满 10 轮，不能因为某一轮没有误分类就自行提前停止。
偏置常数放在特征最前面，训练集和测试集必须采用相同的增广方式。
标准输出只能包含预测 JSON 数组，不能混入调试信息。

这篇文章有帮助吗？

| GitHub 留言