大厂真题 / 网易
网易算法岗 2026-09-29
内容边界：本文整理本场披露的 4 道编程题，不补写未披露的题目、样例与约束。机器学习题使用 NumPy；列表输入用
ast.literal_eval解析，不执行输入中的代码。
本场考试概述
考试时间：2026年9月29日
考试岗位：算法岗
难度评级：中等
考点分析：
- 第一题：混淆矩阵与加权 F-Score（简单）。
- 第二题：线性回归与批量、随机、小批量梯度下降（简单）。
- 第三题：连续段压缩与乘法原理（中等）。
- 第四题：队列、栈与纸牌规则模拟（中等）。
建议策略：先完成两道机器学习基础题，特别核对零分母、更新顺序和输出格式。计数题按连续段而不是按子串枚举；模拟题先确定收牌顺序、额外出牌和空钩规则，再写循环。
第 1 题：实现二分类的 F-Score
题目描述
给定等长的真实标签数组与预测标签数组，元素为 $0$ 或 $1$，计算二分类的 $F_\beta$ 指标。
记 $TP$ 为真实标签与预测标签均为 $1$ 的数量，$FP$ 为真实标签为 $0$、预测标签为 $1$ 的数量，$FN$ 为真实标签为 $1$、预测标签为 $0$ 的数量。精确率与召回率分别为
\[P=\frac{TP}{TP+FP},\qquad R=\frac{TP}{TP+FN}.\]某个比值的分母为 $0$ 时，该指标取 $0$。最终结果为
\[F_\beta=\frac{(1+\beta^2)PR}{\beta^2P+R}.\]若 $\beta^2P+R=0$，结果取 $0$。
输入描述
三行依次给出真实标签列表、预测标签列表、浮点数 $\beta$。两个列表均为 Python 列表字面量，长度 $n$ 满足 $1\le n\le1000$，且 $0<\beta\le5$。
输出描述
输出 F-Score，固定保留三位小数。
样例
输入
[1, 1, 0, 0]
[1, 0, 0, 1]
1.0
输出
0.500
思路分析
第一步：只统计三个计数。 每个样本独立贡献给 $TP$、$FP$、$FN$ 中的一项，或者属于真负例而不影响公式。注意假正例增加精确率的分母，假负例增加召回率的分母，不可交换。
第二步：消去中间分数。 将 $P,R$ 代入后，可把公式写成
\[F_\beta=\frac{(1+\beta^2)TP}{(1+\beta^2)TP+\beta^2FN+FP}.\]当 $TP=0$ 时，题面定义的最终结果必为 $0$，直接返回即可。当 $TP>0$ 时，原公式涉及的两个计数分母都为正，上述化简合法，最终分母也严格为正。这样无需连续处理三个除零分支。
$\beta>1$ 时对漏掉正例的惩罚更重；$\beta=1$ 时就是 F1。样例中三个计数均为 $1$，代入得到 $0.5$，但输出应为 0.500。
正确性说明
逐项检查两个标签，代码恰好统计定义中的三个互斥事件。$TP=0$ 时按题面零分母约定返回 $0$；否则计算代数等价的计数公式，因此结果与指定 F-Score 一致。
题解代码
import ast
import sys
input = sys.stdin.readline
def f_score(y_true, y_pred, beta):
tp = fp = fn = 0
for actual, predicted in zip(y_true, y_pred):
if actual == 1 and predicted == 1:
tp += 1
elif actual == 0 and predicted == 1:
fp += 1
elif actual == 1 and predicted == 0:
fn += 1
if tp == 0:
return 0.0
b2 = beta * beta
return (1 + b2) * tp / ((1 + b2) * tp + b2 * fn + fp)
def solve():
y_true = ast.literal_eval(input())
y_pred = ast.literal_eval(input())
beta = float(input())
print(f"{f_score(y_true, y_pred, beta):.3f}")
if __name__ == "__main__":
solve()
复杂度分析
时间复杂度：$O(n)$，每对标签检查一次。
空间复杂度：$O(n)$，用于读入两个列表；计数过程只使用常数个变量。
第 2 题：实现三种梯度下降
题目描述
线性回归的预测向量为 $\hat y=Xw$。给定特征矩阵、目标向量、初始权重和训练参数，以均方误差为损失，执行指定轮数的梯度下降。
三种方法严格按以下规则更新：
batch：每轮使用全部 $m$ 个样本，梯度为 $\frac{2}{m}X^T(Xw-y)$，更新一次。stochastic：每轮按输入顺序逐个处理样本。第 $i$ 个样本的梯度为 $2x_i(x_i^Tw-y_i)$，算完立刻更新，不随机打乱。mini_batch：每轮按输入顺序分成大小为batch_size的连续批次。每批梯度为 $\frac{2}{batch_size}X_b^T(X_bw-y_b)$，算完立即更新。尾批即使不足指定大小，分母仍固定为batch_size。
每次更新均为 $w\leftarrow w-\eta g$，其中 $\eta$ 为学习率，不另加偏置项。
输入描述
七行依次输入：
X：形状为 $(m,n)$ 的二维列表。y：长度为 $m$ 的列表。weights：长度为 $n$ 的初始权重列表。learning_rate：学习率。n_iterations：迭代轮数。batch_size：批量大小。method：带引号的字符串，为上述三种方法之一。
数据范围：$1\le m\le50$，$1\le n\le5$；X 与 y 的元素绝对值不超过 $10$，初始权重元素绝对值不超过 $1$；$0<\eta\le0.01$，$1\le n_iterations\le1000$，$1\le batch_size\le m$。数据保证迭代过程不会发散。
输出描述
返回最终权重向量，按 NumPy 数组默认打印格式输出，即直接 print(weights)，不添加逗号，不自行固定小数位数。
样例
输入
[[1, 2], [3, 4], [5, 6]]
[2, 4, 6]
[0.5, 0.5]
0.01
100
2
'batch'
输出
[0.46201996 0.63526154]
思路分析
第一步：写清一批数据的梯度。 设本次参与更新的样本下标集合为 $B$，题目规定的归一化分母为 $d$，则损失可表示为
\[L_B(w)=\frac{1}{d}\sum_{i\in B}(x_i^Tw-y_i)^2.\]对每个权重求导，平方项产生系数 $2$，内积对权重的导数为特征分量，因此梯度向量为
\[\nabla L_B(w)=\frac{2}{d}X_B^T(X_Bw-y_B).\]先计算残差，再左乘转置矩阵，就能一次得到所有权重的梯度。批内所有分量必须基于同一个旧权重计算，不能更新一个分量后再计算下一个分量。
第二步：把三种方法的差别归结为批次和分母。 批量方法一轮只有一个批次且 $d=m$；随机方法每批一个样本且 $d=1$；小批量方法每批最多 batch_size 个样本且 $d=batch_size$。依次处理这些批次即可复用更新公式。
“随机”只是方法名称，本题明确要求顺序遍历，不做洗牌。后一批的残差应使用前一批更新后的权重。尾批固定分母也是本题特定口径，不能替换为常见实现中的实际尾批长度。
第三步：保持浮点类型和输出格式。 输入矩阵与权重转为浮点数组。样例使用 batch，所以每轮一次更新，batch_size=2 不参与该方法的梯度计算。
正确性说明
初始权重与输入相同。假设某次更新前权重正确，代码选出的样本集合和分母与当前方法的规定一致，计算的矩阵表达式正是上述梯度，再按学习率更新，所得权重也正确。按批次、轮次归纳，完成指定轮数后得到要求的最终权重。
题解代码
import ast
import sys
import numpy as np
input = sys.stdin.readline
def gradient_descent(X, y, weights, learning_rate,
n_iterations, batch_size, method):
m = len(X)
w = weights.copy()
if method == "batch":
step = m
elif method == "stochastic":
step = 1
else:
step = batch_size
for _ in range(n_iterations):
for start in range(0, m, step):
xb = X[start:start + step]
yb = y[start:start + step]
residual = xb @ w - yb
gradient = (2.0 / step) * xb.T @ residual
w = w - learning_rate * gradient
return w
def solve():
X = np.array(ast.literal_eval(input()), dtype=float)
y = np.array(ast.literal_eval(input()), dtype=float)
weights = np.array(ast.literal_eval(input()), dtype=float)
learning_rate = float(input())
n_iterations = int(input())
batch_size = int(input())
method = ast.literal_eval(input())
print(gradient_descent(X, y, weights, learning_rate,
n_iterations, batch_size, method))
if __name__ == "__main__":
solve()
复杂度分析
时间复杂度：$O(Tmn)$，$T$ 为迭代轮数。三种方法每轮都处理所有样本，每个样本的计算量与特征数成正比。
空间复杂度：$O(mn)$，主要用于特征矩阵以及向量；切片不需要复制整个矩阵。
第 3 题：恰好按键 k 次的子串
题目描述
游戏机有 0、1 两个按钮。按住一个按钮可以连续打印任意多个对应字符，换字符时必须重新按键。给定长度为 $n$ 的 01 字符串，统计最少恰好按键 $k$ 次就能打印出的非空子串数量。
这里的“最少恰好”表示 $k$ 次可以完成，而 $k-1$ 次不能完成；不是统计最少次数大于等于 $k$ 的子串。不同位置的子串分别计数，即使字符内容相同。
输入描述
第一行两个正整数 $n,k$，第二行为长度为 $n$ 的 01 字符串。
数据范围为 $1\le n,k\le10^6$。分档范围分别为：20% 的数据不超过 $5$，40% 不超过 $300$，60% 不超过 $5000$，100% 不超过 $10^6$。
输出描述
输出符合条件的子串数量。
样例 1
输入
6 2
001100
输出
8
样例 2
输入
3 1
110
输出
4
思路分析
第一步：按键次数就是连续段数。 相邻字符不同时必须换按钮，而一整段相同字符只需按住同一个按钮。因此任意非空子串的最少次数，等于其内部相邻字符变化次数加一。
把整个字符串压缩为连续段长度数组 $a$，共 $r$ 段。例如 001100 得到 $[2,2,2]$。直接枚举子串需要二次方的工作量；压段以后，只需枚举子串起点在哪一段。
第二步：当 $k\ge2$ 时使用乘法原理。 若左端点位于第 $i$ 段，恰好覆盖 $k$ 段就意味着右端点位于第 $i+k-1$ 段。中间各段只能全部包含，不存在额外选择。左端点有 $a_i$ 种选法，右端点有 $a_{i+k-1}$ 种选法，且两端所在段不同，任意组合均合法。
\[ans=\sum_{i=0}^{r-k}a_i a_{i+k-1}\qquad(k\ge2).\]样例 1 有两组相邻段，每组贡献 $2\times2=4$，总计 $8$。
第三步：单独处理 $k=1$。 两端在同一段时必须保证左端点不在右端点之后，不能直接相乘。长度为 $a_i$ 的一段包含 $a_i(a_i+1)/2$ 个非空子串，累加即可。样例 2 的段长为 $[2,1]$，贡献为 $3+1=4$。
如果 $k>r$，不存在足够多的段，答案为 $0$。Python 整数可以直接保存结果，不会发生 32 位溢出。
正确性说明
每个子串由唯一的左右端点确定，也属于唯一的起始段和结束段。$k\ge2$ 时，上式恰好枚举所有相距 $k-1$ 段的端点段组合，并将其中每对合法端点计数一次；$k=1$ 时逐段枚举所有段内子串。两种情况都无重无漏，因此答案正确。
题解代码
import sys
from itertools import groupby
input = sys.stdin.readline
def count_substrings(s, k):
runs = [sum(1 for _ in group) for _, group in groupby(s)]
if k > len(runs):
return 0
if k == 1:
return sum(length * (length + 1) // 2 for length in runs)
return sum(runs[i] * runs[i + k - 1]
for i in range(len(runs) - k + 1))
def solve():
n, k = map(int, input().split())
s = input().strip()
print(count_substrings(s, k))
if __name__ == "__main__":
solve()
复杂度分析
时间复杂度：$O(n)$，压缩与统计各进行一次线性遍历。
空间复杂度：$O(n)$，保存字符串及至多 $n$ 个段长。
第 4 题：金钩钓鱼
题目描述
两位玩家 sanqiu 和 xiran 玩纸牌游戏。牌的点数包括 A、2 至 10、J、Q、K，不区分花色，不使用大小王和空白牌。
给定按牌堆从顶到底排列的字符串，两人轮流摸走全部牌，sanqiu 先摸。每位玩家按摸牌顺序形成一个手牌队列，先摸的牌先打。之后由 sanqiu 先出牌，按以下规则进行：
- 当前玩家取手牌队首的一张牌放到桌面末尾。
- 若打出非
J的牌，且桌上原本有相同点数，就收走从那张旧牌到新牌之间的所有牌，包含两端。 - 若打出
J且此前桌面非空，收走全部桌面牌，包含新打出的J。若此前桌面为空，则J留在桌面，不收牌，称为空钩。 - 收回的牌依次加入自己的手牌队尾，最后打出的牌最先入队。收牌后仍由当前玩家继续出牌；没有收牌则轮到对方。
- 某人没有手牌时立即结束。但如果打出最后一张牌后又收回了牌，不判定其失败。
输入描述
输入一个牌堆字符串 $S$，$1\le\lvert S\rvert\le56$。例如 A2345610KKQQ 中 A 是顶牌，10 是一张牌但占两个字符。
数据保证游戏在 $10^4$ 回合内结束。
输出描述
输出两行：第一行为胜者 xiran 或 sanqiu；第二行为胜者剩余手牌，按下一张出牌到最后一张的顺序排列，牌之间用一个空格分隔。
样例
输入
5102297A1010562388JQAK869A754537286K444J3KJ9Q91067J3QKQA
输出
sanqiu
2 2 J Q 8 8 8 A 5 A J Q 7 J 3 4 9 10 9 Q 9 K A Q 10 10 6 5 6 K 4 8 K 7 6 7 3 K 2 4 7 6 3 5 2 10 5
思路分析
第一步：正确拆牌并发牌。 扫描字符串，遇到 1 时连同后面的 0 读成 10，其他点数各占一个字符。从下标 $0$ 开始，偶数位置的牌给 sanqiu，奇数位置的牌给 xiran。手牌用双端队列，支持从左取牌、向右收牌。
第二步：用栈记录桌面顺序。 桌面列表末尾是最后打出的牌。要收牌时，从末尾逐张弹出，再追加到当前玩家队尾，自然满足“最后打出的最先入队”，无需额外翻转。
若旧桌面中相同点数的位置为 $p$，放上新牌后一直弹出，直到桌面只剩前 $p$ 张，便恰好收走两张相同牌及中间所有牌。对于 J，只需判断打出之前桌面是否为空；非空则全部弹出，空桌则保留。
第三步：收牌后不换人。 可以用变量 collected 记录本轮是否发生收牌。若收到牌，当前玩家保持不变；否则换人。将“双方仍都有牌”作为循环条件，使胜负判定发生在本轮收牌处理之后，避免误判打出末张却马上收回牌的情况。
桌面同一点数不会同时留下两张非 J 的牌，因为第二张出现就会触发收牌。线性查找相同点数不会有多个候选位置。无论收牌多少次，手牌与桌面的牌总数始终保持不变。
正确性说明
初始两个队列恰好是轮流摸牌得到的顺序。假设一轮开始时双方手牌、桌面和当前玩家均与真实游戏一致，代码从队首取出相同的牌，按 J、相同点数、无收牌三种情况执行规则，并按桌面逆序追加队尾，所以本轮结束后的牌序正确。当前玩家是否切换也与规则一致。逐轮归纳，结束时输出的胜者及其手牌均正确。
题解代码
import sys
from collections import deque
input = sys.stdin.readline
def parse_cards(s):
cards = []
i = 0
while i < len(s):
if s[i] == "1":
cards.append("10")
i += 2
else:
cards.append(s[i])
i += 1
return cards
def play(cards):
hands = [deque(cards[::2]), deque(cards[1::2])]
table = []
current = 0
while hands[0] and hands[1]:
card = hands[current].popleft()
collected = False
if card == "J" and table:
table.append(card)
while table:
hands[current].append(table.pop())
collected = True
elif card != "J" and card in table:
position = table.index(card)
table.append(card)
while len(table) > position:
hands[current].append(table.pop())
collected = True
else:
table.append(card)
if not collected:
current = 1 - current
winner = 0 if hands[0] else 1
return ("sanqiu", "xiran")[winner], list(hands[winner])
def solve():
winner, hand = play(parse_cards(input().strip()))
print(winner)
print(" ".join(hand))
if __name__ == "__main__":
solve()
复杂度分析
时间复杂度：$O(\lvert S\rvert+TC)$，$T$ 为实际回合数、$C$ 为牌数。每轮查找与收牌最多遍历 $C$ 张牌；这里给出直接实现的保守上界。
空间复杂度：$O(C)$，两个队列、桌面与解析列表所用存储均与牌数成正比。
小结
- F-Score 可以化为三个计数的公式，但必须先对齐零分母口径。
- 梯度下降的更新顺序与归一化分母属于题目要求，不能用熟悉的训练库默认行为替代。
- 连续段计数把端点枚举降到按段计算，同段与跨段必须分开讨论。
- 纸牌模拟的关键不是复杂数据结构，而是保持队列顺序、收牌顺序与换人时机一致。