大厂真题 / 美团

美团 4.25 笔试真题 - 算法岗

本场考试概述

考试时间：2026年4月25日 考试岗位：算法岗 难度评级：中等偏难

考点分析：

1. 第一题：贪心 + 字符串（难度中等）
2. 第二题：Decision Stump 决策树桩（难度中等，ML 实现题）
3. 第三题：按位贪心（难度困难）
4. 第四题：树上哈希 + 小到大合并（难度困难）

建议策略：

1. 前两道题是拿分关键——第一题贪心需要观察字符镜像操作对前后半字母表的不同效果，第二题是经典 ML 实现题
2. 第三题是异或类问题的通用套路：按位拆分后独立处理，掌握后遇到类似题能快速切入
3. 第四题是难题，涉及树上路径哈希和启发式合并，建议留到最后

第一题：镜像串

题目描述

给定一个仅由小写英文字母组成的字符串 $s$。可以选择至多一次，对任意一个连续区间 $[l, r]$ 执行”镜像”操作：将区间内每个字符 $c$ 替换为 $c’ = \text{chr}(\text{ord}(\text{‘a’}) + \text{ord}(\text{‘z’}) - \text{ord}(c))$。

即 $\text{‘a’} \leftrightarrow \text{‘z’}$，$\text{‘b’} \leftrightarrow \text{‘y’}$，$\text{‘c’} \leftrightarrow \text{‘x’}$，以此类推。

也可以选择不进行任何操作。要求在至多一次操作后，使字符串按字典序尽可能小，输出该最小结果。

多组测试数据，保证所有字符串长度之和不超过 $10^5$。

样例

输入

5
abcxyz
aaaa
zyx
az
b

输出

abccba
aaaa
abc
aa
b

思路分析

第一步：观察镜像操作对单个字符的影响

26 个字母以 $\text{‘n’}$ 为分界线分成两半：

• 前半 $\text{‘a’}$–$\text{‘m’}$：镜像后变成 $\text{‘z’}$–$\text{‘n’}$，字典序变大
• 后半 $\text{‘n’}$–$\text{‘z’}$：镜像后变成 $\text{‘m’}$–$\text{‘a’}$，字典序变小

所以镜像只对后半段字母有好处，前半段字母一旦被纳入区间只会变大。

第二步：贪心策略

从左到右扫描，遇到 $\text{‘a’}$–$\text{‘m’}$ 不动（它们已经足够小），找到第一个 $\geq \text{‘n’}$ 的字符开始镜像，一路向右直到再次遇到 $< \text{‘n’}$ 的字符时停下。

为什么不能跳过中间的 $< \text{‘n’}$ 去镜像后面的 $\geq \text{‘n’}$？因为题目要求区间连续，跳不过去——中间的小字母被镜像后会变大，得不偿失。

如果整个字符串没有 $\geq \text{‘n’}$ 的字符，就不做任何操作。

题解代码

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    s = list(input().strip())
    n = len(s)
    i = 0
    while i < n and s[i] < 'n':
        i += 1
    while i < n and s[i] >= 'n':
        s[i] = chr(ord('a') + ord('z') - ord(s[i]))
        i += 1
    print(''.join(s))

复杂度分析

时间复杂度：$O(n)$，每个字符最多访问一次。 空间复杂度：$O(n)$，存储字符数组。

第二题：AK机的决策树桩

题目描述

手写实现一个二分类的 Decision Stump（深度 = 1 的决策树），只使用 NumPy。模型遍历每个特征，寻找单一阈值划分，使得加权 Gini 不纯度最小。

训练阶段：

1. 输入 train 为二维列表，最后一列为标签 $y \in {0, 1}$，前面为数值型特征
2. 对每个特征：按该特征升序稳定排序；在所有相邻不同值中点及”最小值 $- \varepsilon$”处设阈值候选；计算每个候选阈值处的加权 Gini
3. 在所有特征最优阈值中选全局最小 Gini——若并列：先取特征索引最小，再取阈值最小
4. 左子集（$\leq$ 阈值）和右子集（$>$ 阈值）各取多数类作为预测；若 0/1 数量相等则输出 0；若子集为空则跳过该阈值

预测阶段：对每条测试样本，$\leq$ 阈值预测左叶类别，否则预测右叶类别。

输入为单行 JSON，输出为预测标签的 JSON 数组。

样例

输入

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

输出

[0, 0, 1]

思路分析

第一步：理解 Decision Stump

Decision Stump 就是只切一刀的决策树：选一个特征、定一个阈值，把样本分成两堆，让每堆尽量”纯”（同一类的尽量待在一起）。

第二步：搜索空间

两层循环：外层遍历 $m$ 个特征，内层遍历该特征上的候选阈值。$n, m \leq 1000$，暴力穷举完全够用。

第三步：候选阈值构造

对第 $j$ 个特征，把样本按特征值排序去重得到 $v_1, v_2, \dots, v_k$，候选阈值取：

• $v_1 - \varepsilon$（把所有样本划到右边的极端情况）
• 相邻不同值的中点 $\frac{v_i + v_{i+1}}{2}$

第四步：加权 Gini 计算

Gini 不纯度衡量样本的”混乱”程度。全是同一类 → Gini = 0（最纯）；一半 0 一半 1 → Gini = 0.5（最混乱）。

对阈值 $t$，左子集 $L$（$\leq t$）和右子集 $R$（$> t$），加权 Gini 为：

其中 $g = 1 - p_0^2 - p_1^2$，$p_i$ 是子集中类别 $i$ 的比例。某侧为空时跳过。

第五步：全局选优

所有 $(G, j, t)$ 中取最小的——元组比较天然满足”先比 Gini，再比特征编号，再比阈值”的并列消歧规则。

题解代码

import json
import numpy as np
import sys

raw = sys.stdin.readline()
data = json.loads(raw)
train = np.array(data["train"], dtype=float)
test_data = np.array(data["test"], dtype=float)

X = train[:, :-1]
y = train[:, -1].astype(int)
n, m = X.shape
eps = 1e-7

best = (float('inf'), -1, float('inf'))

for j in range(m):
    idx = np.argsort(X[:, j], kind='stable')
    vals = X[idx, j]
    labels = y[idx]
    unique_vals = np.unique(vals)

    thresholds = [unique_vals[0] - eps]
    for i in range(len(unique_vals) - 1):
        thresholds.append((unique_vals[i] + unique_vals[i + 1]) / 2.0)

    for thresh in thresholds:
        mask = vals <= thresh
        n_L = int(np.sum(mask))
        n_R = n - n_L
        if n_L == 0 or n_R == 0:
            continue
        left_y = labels[mask]
        right_y = labels[~mask]
        g_L = 1.0 - (np.sum(left_y == 0) / n_L) ** 2 - (np.sum(left_y == 1) / n_L) ** 2
        g_R = 1.0 - (np.sum(right_y == 0) / n_R) ** 2 - (np.sum(right_y == 1) / n_R) ** 2
        G = (n_L / n) * g_L + (n_R / n) * g_R

        if (G, j, thresh) < best:
            best = (G, j, thresh)

best_feat = best[1]
best_thresh = best[2]

left_y = y[X[:, best_feat] <= best_thresh]
right_y = y[X[:, best_feat] > best_thresh]

def majority(labels):
    c0 = int(np.sum(labels == 0))
    c1 = int(np.sum(labels == 1))
    return 0 if c0 >= c1 else 1

left_pred = majority(left_y)
right_pred = majority(right_y)

preds = []
for t in test_data:
    preds.append(left_pred if t[best_feat] <= best_thresh else right_pred)

print(json.dumps(preds))

复杂度分析

时间复杂度：$O(m \cdot n \log n)$，对 $m$ 个特征各排序一次 $O(n \log n)$，再遍历 $O(n)$ 个候选阈值。 空间复杂度：$O(mn)$，存储特征矩阵。

第三题：AK机的异或问题

题目描述

给定长度为 $n$ 的数组 $a$ 和整数 $k$。可以执行任意次操作：选择下标 $i$ 和整数 $x$（满足 $0 \leq x \leq k$），将 $a_i$ 赋值为 $a_i \oplus x$（$\oplus$ 为按位异或），代价为 $x$。

需要最大化操作后所有两两异或和 $\sum_{i < j} (a_i \oplus a_j)$。若有多种操作序列使该值最大化，选择总代价最小的。输出最大值和最小代价。

样例

输入

3 3
0 1 9

输出

22 2

思路分析

第一步：按位拆分

异或是逐位运算，第 $b$ 位的操作不影响第 $b’$ 位。所以两两异或和也可以按位拆开算：第 $b$ 位的贡献是 $c_0 \cdot c_1 \cdot 2^b$，其中 $c_0$、$c_1$ 分别是第 $b$ 位上 0 和 1 的个数。一对元素在第 $b$ 位上产生贡献，当且仅当这一位不同（一个 0、一个 1），这样的配对数恰好是 $c_0 \cdot c_1$。

第二步：单位贡献最大化

$c_0 \cdot c_1$（其中 $c_0 + c_1 = n$）是一个开口朝下的抛物线，顶点在 $c_1 = n/2$ 处，0 和 1 的个数尽量均分时乘积最大。目标是让每一位都尽量均分。

第三步：可翻转判定

• 若 $2^b \leq k$：可以用 $x = 2^b$ 单独翻转该位而不影响其他位，一定能达到均分。需要翻转的个数是 $\lvert c_1 - \lfloor n/2 \rfloor \rvert$，每次代价 $2^b$。
• 若 $2^b > k$：翻不了，该位的贡献固定为原始的 $c_0 \cdot c_1 \cdot 2^b$。

第四步：代价最优性

逐位各翻一次的代价恰好等于最小代价——对同一个元素做多次操作，净效果是异或一个值，但代价是各次 $x$ 之和（不小于逐位翻转的代价）。

以样例 $a = [0, 1, 9]$，$k = 3$ 走一遍：

• 第 0 位：$c_1 = 2$，已均分，贡献 $1 \times 2 \times 1 = 2$
• 第 1 位：$c_1 = 0$，全是 0，需翻 1 个，代价 $1 \times 2 = 2$，贡献 $1 \times 2 \times 2 = 4$
• 第 2 位：$c_1 = 1$，已均分，贡献 $2 \times 1 \times 4 = 8$
• 第 3 位：$c_1 = 1$，$2^3 = 8 > 3$，翻不了，贡献 $2 \times 1 \times 8 = 16$（不是均分后的值）

等等，让我重算。$a = [0, 1, 9]$，$9 = 1001_2$，$1 = 0001_2$，$0 = 0000_2$。

• 第 0 位：bits = [0, 1, 1]，$c_1 = 2$，$c_0 = 1$。均分目标 $\lfloor 3/2 \rfloor = 1$，$\lceil 3/2 \rceil = 2$，已在范围内。贡献 $1 \times 2 \times 1 = 2$。
• 第 1 位：bits = [0, 0, 0]，$c_1 = 0$。$2^1 = 2 \leq 3$，可翻。翻 1 个到 $c_1 = 1$。代价 $1 \times 2 = 2$。贡献 $1 \times 2 \times 2 = 4$。
• 第 2 位：bits = [0, 0, 0]，$c_1 = 0$。$2^2 = 4 > 3$，翻不了。贡献 $0$。
• 第 3 位：bits = [0, 0, 1]，$c_1 = 1$。$2^3 = 8 > 3$，翻不了。贡献 $2 \times 1 \times 8 = 16$。

总和 = $2 + 4 + 0 + 16 = 22$，代价 = $2$。与样例输出一致。

题解代码

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a = list(map(int, input().split()))

half_lo = n // 2
half_hi = (n + 1) // 2
max_sum = 0
min_cost = 0

for b in range(30):
    cnt1 = sum(1 for x in a if (x >> b) & 1)
    cnt0 = n - cnt1

    if (1 << b) <= k:
        if cnt1 < half_lo:
            flips = half_lo - cnt1
        elif cnt1 > half_hi:
            flips = cnt1 - half_hi
        else:
            flips = 0
        min_cost += flips * (1 << b)
        max_sum += half_lo * half_hi * (1 << b)
    else:
        max_sum += cnt0 * cnt1 * (1 << b)

print(max_sum, min_cost)

复杂度分析

时间复杂度：$O(n \log V)$，遍历 30 个位，每位统计 $O(n)$。 空间复杂度：$O(n)$，存储输入数组。

第四题：树上操作

题目描述

给定一棵 $n$ 个节点的有根树（根节点为 1），第 $i$ 个节点上有一个小写字母 $s_i$。

对每个节点 $u$，定义权值 $\text{val}(u)$：从以 $u$ 为根的子树中选两个节点 $x, y$（可以相同），满足 $\text{LCA}(x, y) = u$，且 $x$ 到 $y$ 的简单路径上的字母拼接后是回文串。在所有满足条件的 $(x, y)$ 中，$\text{val}(u)$ 等于路径点数的最大值。如果不存在这样的配对，$\text{val}(u) = 1$（选 $x = y = u$）。

输出每个节点的 $\text{val}(u)$。

$n \leq 10^5$。

样例

输入

7
aaaaaaa
1 2
1 3
2 4
2 5
3 6
3 7

输出

5 3 3 1 1 1 1

思路分析

第一步：回文路径的结构

路径 $x \to \text{LCA} \to y$ 以 $u$ 为中心、两侧等长。左半是从 $u$ 向 $x$ 方向走的字符序列，右半是从 $u$ 向 $y$ 方向走的字符序列。回文要求正读等于倒读，中心 $u$ 本身在奇数长度的正中间没有额外约束，所以条件就是：左半和右半逐层字符相同。

以样例为例（所有节点都是 ‘a’）：从节点 1 向左走两步（1→2→4）字符 “aa”，向右走两步（1→3→6）也是 “aa”，每层一样，回文成立。路径长度为 $2 \times 2 + 1 = 5$。

第二步：路径哈希

给每个节点 $v$ 算一个指纹 $h(v)$，把从根到 $v$ 经过的全部字符压缩成一个数字（多项式哈希）：

两个同深度节点 $x$、$y$ 的 $h$ 值相等，说明从根到它们走过的字符完全一样。如果它们还在节点 $u$ 的不同子树里，根到 $u$ 这段是共享前缀，$u$ 往下那段逐层字符必然相同——回文条件满足。

第三步：小到大合并

自底向上处理。每个节点维护一个集合，存子树内所有后代的 $(depth, hash)$。合并时，碰到两个来自不同子树、深度相同且哈希相同的后代，就找到了一对合法的 $(x, y)$，回文路径长度为 $2 \times (depth - dep_u) + 1$。

关键优化：保留最大的子树集合不动，只把较小子树的元素逐个搬进去。这样每个元素每次被搬后所在集合至少翻倍，一个元素一生最多被搬 $O(\log n)$ 次，总搬运量 $O(n \log n)$。

题解代码

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
s = input().strip()

if n == 1:
    print(1)
else:
    adj = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int, input().split())
        adj[u - 1].append(v - 1)
        adj[v - 1].append(u - 1)

    dep = [-1] * n
    par = [-1] * n
    dep[0] = 0
    queue = deque([0])
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            if dep[v] == -1:
                dep[v] = dep[u] + 1
                par[v] = u
                queue.append(v)

    BASE, MOD = 131, 10 ** 9 + 7
    h = [0] * n
    h[0] = ord(s[0]) - 96
    for u in order[1:]:
        h[u] = (h[par[u]] * BASE + ord(s[u]) - 96) % MOD

    children = [[] for _ in range(n)]
    for u in order[1:]:
        children[par[u]].append(u)

    val = [1] * n
    node_map = [None] * n

    for u in reversed(order):
        if not children[u]:
            node_map[u] = {dep[u] * MOD + h[u]}
            continue

        heaviest = max(children[u], key=lambda c: len(node_map[c]) if node_map[c] else 0)
        merged = node_map[heaviest]
        node_map[heaviest] = None

        for c in children[u]:
            if c == heaviest:
                continue
            cm = node_map[c]
            if cm is None:
                continue
            for key in cm:
                if key in merged:
                    d = key // MOD
                    val[u] = max(val[u], 2 * (d - dep[u]) + 1)
            merged.update(cm)
            node_map[c] = None

        merged.add(dep[u] * MOD + h[u])
        node_map[u] = merged

    print(' '.join(map(str, val)))

复杂度分析

时间复杂度：$O(n \log n)$，小到大合并保证每个节点被移动 $O(\log n)$ 次，哈希集合的查找和插入均摊 $O(1)$。 空间复杂度：$O(n)$，BFS 数组和哈希集合的总条目数为 $O(n)$。

小结

• 第一题是贪心字符串题，核心是观察镜像操作对字母表前后半的不对称效果——前半变大、后半变小，找到第一段后半字母连续镜像即可
• 第二题是 ML 实现题（Decision Stump），按题意模拟即可，关键是理清候选阈值的构造规则和加权 Gini 的计算公式
• 第三题利用异或的按位独立性将问题分解——每一位独立最优化，能翻就均分，翻不了就保持原样
• 第四题是树上算法难题，将回文路径条件转化为”路径哈希相等”的判定，再用启发式合并高效处理子树间的配对查找