大厂真题 / 京东

京东 2026-9-5 笔试真题 - 算法岗

公式说明：数学公式保留为原始矢量图，避免抓取转换造成变量和约束缺失。

京东2026-9-5笔试真题 - 算法岗

题解整理了这场考试的完整题解和代码，希望能帮助大家更好地准备后续笔试。

本场考试概述

考试时间 ：2026年9月5日 考试岗位 ：算法岗 难度评级 ：中等偏难 考点分析 ：

• 第一题：排序 + 严格递增最长上升子序列（难度中等偏难）
• 第二题：numpy 手写逻辑回归 + 全批梯度下降（难度中等）

建议策略 ：

• 第一题的代码只有排序加一趟 LIS，分全在推导上：要证明”两人不相遇”等价于 $原题公式$ ，也就是起点顺序与终点顺序必须一致，再把它翻译成最长严格递增子序列。想不到这一步就只剩 $原题公式$ 建图， $原题公式$ 到 $原题公式$ 必挂。
• 第二题是口径复刻题，学习率、轮数、bias 拼接位置、clip 范围、判定阈值五处口径必须一字不差照抄题面，任何一处自作主张调参，预测就会整片翻转。
• 算法岗同学别把 ML 题当送分题裸写，先把维度对齐（增广后是 $原题公式$ ）再动手；输出记得转 int，否则 JSON 打出来是 true/false。

第一题：最多不相遇人数

题目描述

有 $原题公式$ 名成员站在一条直线上，第 $原题公式$ 个人的初始位置为 $原题公式$ ，目标位置为 $原题公式$ 。在 $原题公式$ 时刻，所有在这条直线上的人会同时开始行动，规则如下：

1. 如果还没有到达目标位置，就以速度 $原题公式$ 沿直线朝着目标位置移动（也就是每经过 $原题公式$ 秒，走过的路程为 $原题公式$ ）；
1. 当到达目标位置 $原题公式$ 后，就停在 $原题公式$ 不再移动。

位置与时间均为实数（也就是说， $原题公式$ 秒也是允许的时刻）。如果存在某个时刻 $原题公式$ ，两个人的位置相同，则称这两个人在时刻 $原题公式$ 相遇，特别地， $原题公式$ 的时刻也算在内。现在你可以从 $原题公式$ 个人中选出若干人，使得任意时刻都不存在两个人相遇，请输出最多能选出多少个人。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $原题公式$ 代表数据组数，每组测试数据描述如下：第一行输入一个整数 $原题公式$ ，表示队伍人数。第二行输入 $原题公式$ 个整数 $原题公式$ ，表示所有成员的初始位置。第三行输入 $原题公式$ 个整数 $原题公式$ ，表示所有成员的目标位置。除此之外，保证每个测试文件的 $原题公式$ 不超过 $原题公式$ 。

输出描述

对于每一组测试数据，新起一行，输出答案。

样例1

输入

输出

3
2

样例解释 第一组有四个人，起点是 $原题公式$ ，终点是 $原题公式$ 。第二个人从 $原题公式$ 走到 $原题公式$ ，第三个人从 $原题公式$ 走到 $原题公式$ ，两人相向而行，在 $原题公式$ 时都位于 $原题公式$ ，因此这两个人相遇。除此之外任意两人都不会碰面，所以去掉其中一人后剩下三个人两两不相遇，答案是 $原题公式$ 。第二组有三个人，起点是 $原题公式$ ，终点是 $原题公式$ 。前两个人在 $原题公式$ 时都站在位置 $原题公式$ ，按题意这已经算相遇；第一个人与第三个人始终相差 $原题公式$ ，第二个人与第三个人也始终碰不到。所以最多选出两个人，答案是 $原题公式$ 。

题解：排序 + 严格递增最长上升子序列

题目问题拆解

$原题公式$ 个人同时出发，各自朝目标匀速走一段后停住，要挑出尽可能多的人，使他们在任意时刻两两都不重合。这是一道判据推导远难于实现的题：代码只有排序加一趟 LIS，难点全在证明”两人会不会相遇”能压缩成一个不等式。

算法实现

朴素做法是两两判相遇、把互不相遇的人连边求最大团，但最大团是 NP 难的， $原题公式$ 到 $原题公式$ 时连建图的 $原题公式$ 都过不去，只能去看穿”不相遇”这个关系本身。每个人的运动只有一个相位，先以速度 $原题公式$ 走向目标，到了就永久停下： $原题公式$ 速度因此只取 $原题公式$ ，且一旦变成 $原题公式$ 就不再变回去。看两人的差值 $原题公式$ ，它的斜率只在某人停下的瞬间改变。设 $原题公式$ 先降后升，上升段必在其中一人停下之后：若先停的是 $原题公式$ ，该段斜率为 $原题公式$ ，而下降段斜率 $原题公式$ 要求 $原题公式$ ；先停的是 $原题公式$ 则同理要求 $原题公式$ 。两者都超出速度上限，故 $原题公式$ 没有内部极小值，最小值必在 $原题公式$ 或 $原题公式$ 取到。由介值定理，相遇当且仅当 $原题公式$ 在这两端异号或有一端为零，取反即得不相遇的判据： $原题公式$ 起点的先后与终点的先后必须一致，且两处都不许并列。这是严格偏序，选出的人两两可比、必构成一条链，故答案等于按 $原题公式$ 升序排好后终点序列的最长严格递增子序列长度。起点并列要单独安排： $原题公式$ 的两人在 $原题公式$ 就站在一起，至多留一个。把同组内的终点按降序排，该组终点递减，求严格递增时自然只会选中一个，不必另写去重。求 LIS 用 $原题公式$ 数组， $原题公式$ 存长度 $原题公式$ 的递增子序列中最小的结尾值，每个终点用 bisect_left 替换第一个不小于它的位置，越界则追加。不能换成 bisect_right：等值被替换掉才是严格递增，否则终点相同的两人会被一起选进来，而他们最终停在同一点上。

时空复杂度分析

时间复杂度 ： $原题公式$ ，瓶颈是排序与 LIS 两趟， $原题公式$ 时约 $原题公式$ 次比较。把相遇判定从两两比较换成一次排序，正是绕开 $原题公式$ 建图的关键。 空间复杂度 ： $原题公式$ ，存下 $原题公式$ 数组与 $原题公式$ 。 Python

# 最多不相遇人数 - 排序 + 严格递增最长上升子序列
from bisect import bisect_left

def order_by_start(p, q):
    """第一步：把 n 个人按起点排队，返回排好队之后的终点序列"""
    people = list(zip(p, q))
    # 起点相同的两人在 t = 0 就站在一起，必定相遇；让他们的终点降序排列，
    # 后面求"严格递增"时同一起点里最多只能选中一个，不用再额外判重
    people.sort(key=lambda person: (person[0], -person[1]))
    return [end for _, end in people]

def strict_lis(ends):
    """第二步：求终点序列的最长严格递增子序列长度，即能选出的最多人数"""
    # tails[k] 存放长度为 k+1 的递增子序列中最小的那个结尾值，整体单调递增
    tails = []
    for end in ends:
        # bisect_left 找第一个 >= end 的位置，等值也会被替换掉，得到的才是严格递增
        pos = bisect_left(tails, end)
        if pos == len(tails):
            tails.append(end)
        else:
            tails[pos] = end
    return len(tails)

t = int(input())
for _ in range(t):
    n = int(input())
    p = list(map(int, input().split()))
    q = list(map(int, input().split()))
    # 两人永不相遇 <=> 起点的先后与终点的先后一致，
    # 于是"任意两人都不相遇的最大人群"就是起点、终点同时严格递增的最长链
    print(strict_lis(order_by_start(p, q)))

第二题：逻辑回归二分类

题目描述

请你在仅使用 numpy 的前提下，手写实现二分类 Logistic Regression，并用全批 Batch Gradient Descent（全批梯度下降）在训练集上训练，最后对测试集输出 $原题公式$ 预测。训练口径固定如下：学习率 $原题公式$ ；迭代次数 $原题公式$ ； $原题公式$ 正则系数 $原题公式$ ；需要包含 bias 项，即对特征矩阵最左侧拼接一列全 $原题公式$ ；sigmoid 输入 $原题公式$ 要做截断 $原题公式$ （防止 exp 溢出）；预测规则为若 $原题公式$ 预测为 $原题公式$ ，否则为 $原题公式$ 。训练目标：设训练集为 $原题公式$ ，训练数据为 $原题公式$ ， $原题公式$ ，模型为 $原题公式$ 其中 $原题公式$ 为权重矩阵， $原题公式$ 为 Sigmoid 函数。全批梯度下降更新为 $原题公式$ 本题实现不需要随机数（权重初始化为全 $原题公式$ ），因此无需设置随机种子。为保证通过测试用例，仅允许使用 numpy。

输入描述

标准输入为一行 JSON，形如 $原题公式$ 。 $原题公式$ 为 $原题公式$ 行训练样本，每行最后一列是标签 $原题公式$ ，其余为特征值， $原题公式$ 。 $原题公式$ 为 $原题公式$ 行测试样本，仅包含特征，维度 $原题公式$ 与训练一致， $原题公式$ 。数据不包含缺失值。

输出描述

标准输出仅一行：一个 JSON 数组，长度为 $原题公式$ ，表示测试集预测标签，例如 $原题公式$ 。

样例1

输入

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

输出

[0, 0, 1, 1]

样例解释 训练集是一维特征，特征值 $原题公式$ 标签为 $原题公式$ ，特征值 $原题公式$ 标签为 $原题公式$ 。按固定口径训练 $原题公式$ 轮后权重为 $原题公式$ ，决策边界落在 $原题公式$ 附近，因此测试点 $原题公式$ 预测为 $原题公式$ ，测试点 $原题公式$ 预测为 $原题公式$ 。

样例2

输入

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

输出

[0, 1, 1]

样例解释 训练集是二维特征，训练后权重为 $原题公式$ 。三个测试点代入 $原题公式$ 分别得到 $原题公式$ ，经 Sigmoid 后第一个概率小于 $原题公式$ 、后两个大于 $原题公式$ ，所以预测为 $原题公式$ 。

题解：全批梯度下降训练 Logistic Regression

题目问题拆解

按题面写死的口径训练一个带偏置的二分类逻辑回归，再用 $原题公式$ 把测试集映射成 $原题公式$ 标签。这是一道口径复刻型的 ML 题：算法本身是教科书里的逻辑回归，难点不在想法，而在把学习率、轮数、bias 拼接位置、clip 范围、判定阈值五处口径一字不差地照搬，任一处偏了预测就整片翻转。

算法实现

特征增广 ：每条特征最左侧拼一列常数 $原题公式$ ，得 $原题公式$ ，训练矩阵维度由 $原题公式$ 变成 $原题公式$ 。偏置于是并进权向量 $原题公式$ 一起更新，不必单独维护。 Sigmoid 与数值稳定性 ： $原题公式$ 截断不是可选项： $原题公式$ 小于 $原题公式$ 时 $原题公式$ 会溢出成 inf。而 $原题公式$ 与 $原题公式$ 相差不到 $原题公式$ ，改不动 $原题公式$ 的判定，属于只挡溢出、不动语义的处理。 梯度与更新 ：交叉熵损失对 $原题公式$ 求导后化简得 $原题公式$ 残差 $原题公式$ 是每条样本的预测误差，左乘 $原题公式$ 把它按特征方向摊回各维权重，除以 $原题公式$ 取全体样本的平均。 $原题公式$ 意味着正则项恒为零，梯度里不再补 $原题公式$ 。 为什么能整批向量化 ：同一轮里所有样本共用同一个 $原题公式$ ，彼此没有先后依赖，一轮因此能压成两次矩阵乘法；感知机那类在线更新则因第 $原题公式$ 条会改变第 $原题公式$ 条的预测而只能串行。 维度变化 ：前向 $原题公式$ ；回传 $原题公式$ ；预测 $原题公式$ 。权重初值全零、不引入随机数，固定跑满 $原题公式$ 轮，线性不可分时不收敛也照跑，结果才可复现。输出前须把布尔数组转成整型，否则 JSON 打印出的是 true 与 false，而非题面要求的 $原题公式$ 。

时空复杂度分析

时间复杂度 ：训练 $原题公式$ ， $原题公式$ 轮、每轮两次 $原题公式$ 规模的矩阵乘法；预测 $原题公式$ 。瓶颈在轮数， $原题公式$ 是题面钉死的省不掉，但每轮已压成 BLAS 矩阵乘法， $原题公式$ 且 $原题公式$ 时总量不足 $原题公式$ 。 空间复杂度 ： $原题公式$ ，增广后的训练矩阵与测试矩阵。 Python

# 逻辑回归二分类 - 全批梯度下降训练 Logistic Regression
import json

import numpy as np

# 这三个都是题面写死的工艺参数，不是要自己调的超参：固定跑满 800 轮，不看是否收敛
LR = 0.2
EPOCHS = 800
CLIP = 30.0  # sigmoid 入参的截断范围

def sigmoid(z):
    """σ(z) = 1 / (1 + e^{-z})。先把 z 截到 [-30, 30] 再算：
    z 稍大一点 e^{-z} 就会溢出成 inf 并打出 RuntimeWarning，
    而截断只影响概率的第 14 位小数，不改变 p >= 0.5 的判定结果。"""
    z = np.clip(z, -CLIP, CLIP)
    return 1.0 / (1.0 + np.exp(-z))

# ---- 第一步：读入并整理数据 ----
# 输入是单行 JSON，读一行直接解析
data = json.loads(input())
train = data["train"]
test = data["test"]

# 训练集每行的格式是"d 个特征 + 最后一列标签"，整体读成矩阵后按列切开
train_mat = np.asarray(train, dtype=np.float64)  # (n, d+1)
train_x = train_mat[:, :-1]                      # (n, d) 特征矩阵
train_y = train_mat[:, -1]                       # (n,)   标签，取值 0/1

n = train_x.shape[0]
# 每条特征最左侧拼一列常数 1 当 bias，偏置就并进权向量一起更新，不必单独维护
train_v = np.hstack([np.ones((n, 1)), train_x])  # (n, 1) 拼 (n, d) -> (n, d+1)

w = np.zeros(train_v.shape[1])  # 权重全 0 起步，题面规定不做随机初始化

# ---- 第二步：全批梯度下降训练 ----
# "全批"的含义是每轮都拿全部 n 条样本算一次平均梯度、再统一走一步。
# 同一轮里所有样本用的是同一个 w，彼此没有先后依赖，所以能整批矩阵运算，
# 不像感知机那种在线更新必须逐条扫
for _ in range(EPOCHS):
    p = sigmoid(train_v @ w)              # (n, d+1) @ (d+1,) -> (n,) 当前预测概率
    # 交叉熵损失对 w 的梯度恰好化简成 X̄ᵀ(p - y)/n，(p - y) 就是每条样本的预测误差
    grad = train_v.T @ (p - train_y) / n  # (d+1, n) @ (n,) -> (d+1,)
    # 题面固定 l2 = 0.0，正则项恒为 0，所以梯度里不再额外加 l2 * w
    w -= LR * grad

# ---- 第三步：预测 ----
# 训练结束权重就固定了，各测试样本互不影响，一次矩阵乘法批量算完
test_x = np.asarray(test, dtype=np.float64)                  # (m, d)
test_v = np.hstack([np.ones((test_x.shape[0], 1)), test_x])  # (m, d+1)
prob = sigmoid(test_v @ w)                                   # (m,)

# 概率 >= 0.5 判正类 1、否则判 0；先转成 int64 再 tolist()，
# 否则 bool 数组会让 json 打印出 true/false 而不是题面要求的 0/1
result = (prob >= 0.5).astype(np.int64)

print(json.dumps(result.tolist()))

这篇文章有帮助吗？

| GitHub 留言