大厂真题 / 携程
携程 4.23 笔试真题 - 算法岗
本场考试概述
考试时间：2026年4月23日 考试岗位：算法岗 难度评级：中等偏难
考点分析：
- 第一题：奇偶性分析（难度简单）
- 第二题：区间覆盖推导 / 数学思维（难度中等）
- 第三题：KNN 元学习 + LogisticRegression（难度中等）
- 第四题：并查集 + 倍数筛（难度困难）
建议策略：
- 第一、二题为纯思维题，优先完成，争取满分
- 第三题熟悉 scikit-learn 基本流程即可快速 AC，按题意四步实现
- 第四题并查集 + 调和级数枚举是经典套路，时间充裕再攻克
第一题：炒鸡回文构造
题目描述
定义一个长度为 $n$ 的数组 $a$ 是回文数组，当且仅当对于任意 $i$ 都有 $a_i = a_{n+1-i}$。
给定一个正整数长度 $n$，判断：对于所有满足 $m \geq n$ 的正整数 $m$，是否都存在一个长度为 $n$ 的回文数组，使其所有元素均为正整数且元素之和恰好等于 $m$。
如果满足条件，输出 Yes；否则，输出 No。
输入格式：第一行一个整数 $T$ 表示数据组数，此后每组一行一个整数 $n$。$n$ 可达 $10^9$。
输出格式：每组数据输出 Yes 或 No。
样例
输入
4
1
2
1000000000
999999999
输出
Yes
No
No
Yes
思路分析
第一步：观察回文数组的结构
回文数组满足 $a_i = a_{n+1-i}$，因此元素天然成对出现。当 $n$ 为偶数时恰好有 $n/2$ 对，当 $n$ 为奇数时有 $(n-1)/2$ 对再加一个中心元素。
第二步：分析总和的奇偶性
- 偶数长度：所有元素严格成对，总和 $= 2 \times (\text{各对之和})$，永远是偶数。但 $m$ 可以是奇数（例如 $m = n + 1$），所以无法覆盖所有 $m \geq n$，答案是
No。 - 奇数长度：把每一对都设为 $1$（贡献 $n - 1$），中心元素设为 $m - (n - 1)$。只要 $m \geq n$，中心元素 $\geq 1$，是合法正整数。因此任意 $m \geq n$ 都可构造，答案是
Yes。
结论：$n$ 为奇数输出 Yes，$n$ 为偶数输出 No。
题解代码
import sys
input = sys.stdin.readline
T = int(input())
results = []
for _ in range(T):
n = int(input())
results.append("Yes" if n % 2 == 1 else "No")
print('\n'.join(results))
复杂度分析
时间复杂度：$O(T)$，每组数据 $O(1)$ 判断。 空间复杂度：$O(1)$。
第二题：炒鸡钞票构造
题目描述
有两种面额的钞票，各无限张：一种面值为 $n$ 元，另一种面值为 $n+1$ 元。想要购买一件价格为 $m$ 元的商品。商店没有找零系统，付款金额不能少于商品价格。计算最少需要额外多支付多少元；若能刚好支付则额外花费为 $0$。
输入格式：第一行整数 $T$ 表示数据组数，每组一行两个整数 $n, m$。$n, m$ 可达 $10^{18}$。
输出格式：每组输出最少额外支付金额。
样例
输入
3
3 8
4 6
5 7
输出
0
2
3
思路分析
第一步：分析可支付区间
用 $s$ 张钞票（$a$ 张面额 $n$，$b$ 张面额 $n+1$，$a + b = s$），总额 $= s \cdot n + b$。由于 $0 \leq b \leq s$，用 $s$ 张钞票能凑出闭区间 $[s \cdot n,\; s \cdot (n+1)]$ 内的任意整数。
第二步：找最少张数
为使区间右端覆盖 $m$，需要 $s \cdot (n+1) \geq m$，即 $s \geq \lceil m / (n+1) \rceil$。取 $s = \lceil m / (n+1) \rceil$。
第三步：判断能否精确支付
若 $s \cdot n \leq m$，则 $m$ 落在区间 $[s \cdot n,\; s \cdot (n+1)]$ 内，可精确凑出，多付 $0$。若 $s \cdot n > m$，最小付款为 $s \cdot n$，多付 $s \cdot n - m$。
样例推导：$n=5,\; m=7$。$s = \lceil 7/6 \rceil = 2$，区间 $[10, 12]$。因为 $10 > 7$，多付 $10 - 7 = 3$。
题解代码
import sys
import math
input = sys.stdin.readline
T = int(input())
results = []
for _ in range(T):
n, m = map(int, input().split())
s = math.ceil(m / (n + 1))
ans = max(0, s * n - m)
results.append(str(ans))
print('\n'.join(results))
复杂度分析
时间复杂度：$O(T)$，每组数据 $O(1)$ 计算。 空间复杂度：$O(1)$。
第三题：用历史数据挑选 Logistic C
题目描述
给定一张历史元数据表（每行包含数据集的简单特征和其最优 $C$）以及一份当前任务的训练/测试数据，实现一个基于 KNN 的超参数元学习器：
- 元特征计算：对每个数据集计算三维向量 $(n, d, \text{imbalance})$，其中 $n$ 为训练样本数，$d$ 为特征维度，$\text{imbalance} = \lvert n_{\text{pos}} - n_{\text{neg}} \rvert / n$。
- KNN 检索（K=3）：计算当前任务元向量到所有历史数据的 $L_2$ 距离，取 $3$ 个最近邻；距离并列按行号升序决定。
- *汇聚选 $C^$*：对 $3$ 个最近邻中出现过的所有 $C$ 值分组计算平均 score；取平均分最高者为 $C^$；若并列则取数值最小的 $C$。
- 模型训练 + 预测：使用
LogisticRegression(C=C*, random_state=42)拟合训练数据，输出测试集的 0/1 标签。
输入格式：单行 JSON，包含 train_X、train_y、test_X、history 字段。history 每条含 meta（三维元特征）、C、score。
输出格式：一行 JSON {"C_star": ..., "pred": [...]}。
样例
输入
{"train_X": [[0.0,0.0],[0.2,0.4],[0.3,0.5],[0.1,0.2],[1.0,1.1],[1.2,1.3],[1.3,1.4],[1.1,1.0]], "train_y": [0,0,0,0,1,1,1,1], "test_X": [[0.15,0.25],[1.15,1.25]], "history": [{"meta":[50,2,0.10],"C":0.1,"score":0.82},{"meta":[48,2,0.20],"C":0.3,"score":0.79},{"meta":[60,2,0.00],"C":1.0,"score":0.85},{"meta":[40,4,0.30],"C":3.0,"score":0.80},{"meta":[55,3,0.18],"C":0.3,"score":0.83},{"meta":[52,2,0.10],"C":1.0,"score":0.81},{"meta":[58,2,0.05],"C":10.0,"score":0.78}]}
输出
{"C_star": 0.1, "pred": [0, 1]}
思路分析
第一步：理解元学习的框架
这道题的本质是”用历史经验指导超参数选择”。每个历史数据集都已经知道了最优的正则化参数 $C$ 和对应的评分，我们希望找到与当前任务最相似的历史数据集，借用它们的最优 $C$。
第二步：元特征的作用
元特征是对数据集”长什么样”的粗略描述：样本数 $n$、特征维度 $d$、类别不平衡度。两个数据集的元特征越接近（欧氏距离越小），它们”长得越像”，最优超参数也越可能相似。
第三步：按题目四步流程直接实现
- 计算当前任务的元特征向量 $(n, d, \lvert n_{\text{pos}} - n_{\text{neg}} \rvert / n)$
- 对每条历史记录算 $L_2$ 距离，按 (距离, 行号) 排序取前 3
- 在 3 个最近邻中按 $C$ 值分组，计算各组平均 score，选平均分最高的 $C$（平分取数值最小）
- 用选出的 $C^*$ 训练
LogisticRegression并预测
数据规模很小（$n \leq 1000$，history $\leq 100$），按流程直接实现即可。
题解代码
import json
import numpy as np
from sklearn.linear_model import LogisticRegression
raw = input()
data = json.loads(raw)
train_X = np.array(data["train_X"])
train_y = np.array(data["train_y"])
test_X = np.array(data["test_X"])
history = data["history"]
# 步骤1：计算当前任务的元特征向量
n = len(train_y)
d = train_X.shape[1]
n_pos = int(np.sum(train_y == 1))
n_neg = n - n_pos
imbalance = abs(n_pos - n_neg) / n
m_cur = np.array([n, d, imbalance])
# 步骤2：KNN 检索，取 K=3 个最近邻
dists = []
for i, h in enumerate(history):
m_h = np.array(h["meta"])
dist = np.linalg.norm(m_cur - m_h)
dists.append((dist, i))
dists.sort(key=lambda x: (x[0], x[1]))
neighbors = dists[:3]
# 步骤3：按 C 值分组，取平均分最高的 C
c_scores = {}
for _, idx in neighbors:
h = history[idx]
c, score = h["C"], h["score"]
if c not in c_scores:
c_scores[c] = []
c_scores[c].append(score)
best_c, best_avg = None, -1.0
for c in sorted(c_scores.keys()):
avg = sum(c_scores[c]) / len(c_scores[c])
if avg > best_avg:
best_avg = avg
best_c = c
# 步骤4：训练 Logistic 回归并预测
clf = LogisticRegression(penalty="l2", C=best_c, solver="lbfgs",
max_iter=1000, random_state=42)
clf.fit(train_X, train_y)
pred = clf.predict(test_X).tolist()
c_out = best_c if best_c != int(best_c) else int(best_c)
result = {"C_star": c_out, "pred": pred}
print(json.dumps(result, separators=(', ', ': ')))
复杂度分析
时间复杂度：$O(H \log H)$ 计算距离并排序，$O(nd)$ 训练模型。总体 $O(nd + H \log H)$，规模下约 $O(10^3)$。 空间复杂度：$O(nd)$，存储训练数据矩阵。
第四题：序列倍数交换
题目描述
给定一个长度为 $n$ 的序列 $a$，其中第 $i$ 个元素的值为 $a_i$（$1 \leq a_i \leq n$）。可以对序列进行任意次如下操作：选择两个不同的下标 $i, j$，且 $a_i$ 与 $a_j$ 满足倍数关系（即 $a_i \mid a_j$ 或 $a_j \mid a_i$），然后交换 $a_i$ 和 $a_j$。
求在任意次操作后，字典序最小的序列。
输入格式：第一行整数 $T$ 表示数据组数。每组第一行一个整数 $n$，第二行 $n$ 个整数。单个测试文件的 $n$ 之和不超过 $10^5$。
输出格式：每组输出 $n$ 个整数。
样例
输入
2
5
1 4 3 2 5
6
3 4 2 2 6 5
输出
1 2 3 4 5
2 2 3 4 6 5
思路分析
第一步：发现可传递性
如果 $a_i$ 和 $a_j$ 可以交换，$a_j$ 和 $a_k$ 也可以交换，那么经过中间步骤 $a_i$ 和 $a_k$ 也能到达任意排列。因此”能交换”是一个传递关系，所有互相可达的位置形成一个等价类。
第二步：问题转化
在同一个等价类内部，元素可以任意重排。要让整个序列字典序最小，只需在每个等价类内部把最小的值分配给最小的位置。
第三步：用并查集 + 倍数筛建图
暴力枚举所有位置对是 $O(n^2)$ 的，太慢。观察到：如果值 $v$ 和值 $2v$ 都在数组中出现过，那么持有这两个值的位置可以交换（因为 $v \mid 2v$）。因此枚举每个出现过的值 $v$，将 $v$ 和 $2v, 3v, \ldots$ 的代表位置用并查集合并。枚举量为 $\sum_{v=1}^{n} n/v = O(n \log n)$（调和级数），比暴力快得多。
第四步：分量内排序
对每个连通分量，收集其所有位置和对应值，分别排序后逐一对应填回。位置从小到大、值从小到大，保证字典序最小。
样例推导：$a = [3, 4, 2, 2, 6, 5]$。值 $2$ 与 $4$（$2 \mid 4$）、$2$ 与 $6$（$2 \mid 6$）、$3$ 与 $6$（$3 \mid 6$）连通，位置 ${0, 1, 2, 3, 4}$ 形成一个分量，值 ${3, 4, 2, 2, 6}$ 排序后填入得 $[2, 2, 3, 4, 6]$；位置 ${5}$ 独立，值 $5$ 不动。结果 $[2, 2, 3, 4, 6, 5]$。
题解代码
import sys
from collections import defaultdict
input_data = sys.stdin.read().split()
idx = 0
def read_int():
global idx
val = int(input_data[idx]); idx += 1
return val
T = read_int()
output_parts = []
for _ in range(T):
n = read_int()
a = [read_int() for _ in range(n)]
parent = list(range(n))
rank = [0] * n
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(x, y):
rx, ry = find(x), find(y)
if rx == ry:
return
if rank[rx] < rank[ry]:
rx, ry = ry, rx
parent[ry] = rx
if rank[rx] == rank[ry]:
rank[rx] += 1
# rep[v] = 值为 v 的某个代表位置
rep = [-1] * (n + 1)
for i in range(n):
if rep[a[i]] == -1:
rep[a[i]] = i
else:
union(i, rep[a[i]])
# 倍数筛：将 v 与 2v, 3v, ... 的代表位置合并
for v in range(1, n + 1):
if rep[v] == -1:
continue
mult = 2 * v
while mult <= n:
if rep[mult] != -1:
union(rep[v], rep[mult])
mult += v
# 每个连通分量内排序，最小值填最小位置
comp_pos = defaultdict(list)
comp_vals = defaultdict(list)
for i in range(n):
root = find(i)
comp_pos[root].append(i)
comp_vals[root].append(a[i])
result = [0] * n
for root in comp_pos:
positions = sorted(comp_pos[root])
values = sorted(comp_vals[root])
for p, v in zip(positions, values):
result[p] = v
output_parts.append(' '.join(map(str, result)))
print('\n'.join(output_parts))
复杂度分析
时间复杂度：倍数筛 $O(n \log n)$（调和级数）；并查集操作近 $O(n)$；分量内排序 $O(n \log n)$。总计 $O(n \log n)$。 空间复杂度：$O(n)$，并查集数组和值映射表。
小结
- 第一题是纯数学思维题：偶数长度回文总和必为偶数，奇数长度可通过中心元素自由调节
- 第二题利用”$s$ 张钞票可凑出连续区间 $[sn, s(n+1)]$”的关键观察，$O(1)$ 得出答案
- 第三题是 ML 综合题，按题目四步流程（元特征 → KNN 检索 → 汇聚选 $C$ → 训练预测）直接实现
- 第四题是经典的并查集 + 调和级数枚举，核心在于将倍数关系转化为连通分量内自由排列