大厂真题 / 华为
华为 5.13 笔试真题 - 研发岗
本场考试概述
考试时间：2026年5月13日 考试岗位：研发岗（国内） 难度评级：中等偏难
考点分析：
- 第一题：滑动窗口 + 哈希表（难度中等）
- 第二题：二叉树层序解析 + 递归合并（难度中等偏难）
- 第三题：二维 Dijkstra（节点 + 电量）（难度中等偏难）
建议策略：
- 第一题为”至多 k 种不同元素”滑窗模版，先拿下保底分
- 第二题题面复杂，先吃透「层序约定」和「同名节点对齐」两层抽象，再写递归合并
- 第三题把电量当成第二维状态，Dijkstra 模版直接套，关键是不要忘记充电也是一种转移
第一题：浏览片段统计
题目描述
某电商平台需要分析用户的商品浏览历史，以优化推荐系统。给定用户在某段时间内的商品浏览记录序列，每个商品属于一个类别（如”手机”、”电脑”、”家电”等）。平台希望统计出：用户在连续浏览过程中，不同商品类别数不超过 $k$ 种的浏览片段数量。
浏览片段：浏览记录中一段连续的记录序列。例如，浏览记录 手机 电脑 手机 家电 中，手机 电脑 是一个浏览片段。
不同商品类别数：浏览片段中不重复的商品类别个数。例如，浏览片段 手机 电脑 手机 家电 的不同商品类别数为 3（类别为手机、电脑、家电）。
输入描述
第一行包含两个整数 $n, k$，分别表示浏览记录数量和允许的最大不同商品类别数。
第二行包含 $n$ 个整数，表示浏览记录中的商品类别编号。
输出描述
输出一个整数，表示不同商品类别数不超过 $k$ 种的浏览片段数量。
样例
输入
3 3
1001 2002 3003
输出
6
所有浏览片段的不同类别数都不超过 3，因此结果即为所有子数组的数量，长度 3 的数组共有 $3 \times 4 / 2 = 6$ 个子数组。
输入
5 2
1 40 1 12 5000
输出
10
思路分析
第一步：问题转化
统计「不同元素种数 $\leq k$」的连续子数组数量。$n$ 可能很大，必须线性扫描完成。
第二步：双指针框架
枚举子数组的右端点 $r$，固定 $r$ 后只需关心「以 $r$ 结尾的合法子数组数量」。设以 $r$ 结尾的最小合法左端点为 $l$。$r$ 右移时窗口只增不减，类别数单调不减，因此最小合法 $l$ 也单调不减。
单调不减意味着双指针不会回头，$l$ 整段累计移动至多 $n$ 次，整体均摊 $O(n)$。
第三步：累加贡献
窗口 $[l, r]$ 合法时，以 $r$ 结尾的合法子数组共 $r - l + 1$ 段（左端点取值 $l, l+1, \ldots, r$），把这个数字累加到答案。
第四步：窗口元素计数
用哈希表 cnt 记录窗口内每种类别的出现次数，变量 distinct 同步维护窗口内的类别数。右移 $r$ 时若某类别从 0 变 1，意味着出现一个新类别，distinct 加 1。
第五步：收缩左端点
当 distinct > k 时不断右移 $l$，每次将 cnt[a[l]] 减 1，若减到 0 则 distinct 减 1，直至窗口重新合法。
题解代码
import sys
from collections import defaultdict
def solve():
data = sys.stdin.buffer.read().split()
idx = 0
n = int(data[idx]); k = int(data[idx + 1]); idx += 2
a = [int(data[idx + i]) for i in range(n)]; idx += n
cnt = defaultdict(int)
distinct = 0
l = 0
ans = 0
for r in range(n):
if cnt[a[r]] == 0:
distinct += 1
cnt[a[r]] += 1
while distinct > k:
cnt[a[l]] -= 1
if cnt[a[l]] == 0:
distinct -= 1
l += 1
ans += r - l + 1
print(ans)
solve()
复杂度分析
时间复杂度：$O(n)$。左右指针各自最多移动 $n$ 次，哈希表操作均摊 $O(1)$。 空间复杂度：$O(n)$。哈希表最多存储窗口内的所有不同类别。
第二题：树的合并
题目描述
某公司用二叉树来管理服务，随着部门业务的调整，需要对服务进行合并以节约管理成本。具体合并规则为：
- 当两棵二叉树部分重叠，且其余节点不冲突，则重叠部分可以合并得到新的树。
- 如果两棵树的节点有冲突（部分子节点无法合并），则不可合并。
- 如果树 B 可以往树 A 合并，树 A 也可往树 B 合并，则采用树 B 往树 A 合并。
树采用层序遍历（按行）加空节点表示空缺的方式表示。
输入描述
输入是两棵树，每棵树占一行，用字符串表示，长度不超过 10000 个字符。合并前树的节点不重名，null 为特殊字符表示空节点。节点名仅由字母和数字组成，节点间用空格分隔。
输出描述
如果可以合并，则在一行内按层序遍历输出合并后的树（空节点用 null 表示，末尾的连续 null 可省略）；如果不可合并，则输出 0。
样例
输入
a b c d null e f null null null null ff
c e f null null it
输出
0
树 A 中节点 c 与树 B 中节点 c 完全重合，但 c 的子节点 e 和 it 冲突，无法合并。
输入
a b c d null e f null null null null g
c e f null null null q
输出
a b c d null e f null null null null g q
树 A 中节点 c 与树 B 中节点 c 完全重合，在树 A 的子节点 g 位于 e 的左孩子，在树 B 的子节点 q 位于 e 的右孩子，分别处于不同位置，可以合并。
思路分析
第一步：字符串建树
输入按层序排列，规则是空节点不再列出其子节点。用队列建树：取第一个 token 作为根入队；之后每出队一个非空节点，从输入中再取两个 token 给它当左右孩子。每取到一个非空节点就入队等待分配孩子，取到 null 直接跳过。
第二步：合并函数定义
设 $h$ 是树 A 当前位置的节点，$g$ 是树 B 当前位置的节点。合并按四种情况分别处理：
- 两边都空：结果还是空
- 只有一边空：保留另一边整棵子树
- 两边都非空但名字不一致：判为冲突，整次合并失败
- 两边都非空且名字一致：保留该名字、递归合并左右子树
只要任一子调用返回冲突，外层立即向上返回失败。
第三步：对齐起点
题目保证一棵树内节点不重名，所以树 B 的根在树 A 里最多出现一次。在树 A 中 DFS 找到该节点，把它作为合并的对齐点。
第四步：双向尝试
规则三规定：两个方向都能合并时优先树 B 合并到树 A。等价于先试树 B→树 A，成功直接输出；失败再试树 A→树 B；两次都失败输出 0。
第五步：层序输出
最终树按 BFS 层序输出，空位置填 null。结尾连续的 null 不写出。
题解代码
import sys
from collections import deque
def solve():
lines = sys.stdin.read().strip().split('\n')
toks1 = lines[0].split()
toks2 = lines[1].split()
def parse(toks):
if not toks or toks[0] == 'null':
return None
root = {'name': toks[0], 'l': None, 'r': None}
q = deque([root])
i = 1
while q and i < len(toks):
cur = q.popleft()
if i < len(toks):
if toks[i] != 'null':
cur['l'] = {'name': toks[i], 'l': None, 'r': None}
q.append(cur['l'])
i += 1
if i < len(toks):
if toks[i] != 'null':
cur['r'] = {'name': toks[i], 'l': None, 'r': None}
q.append(cur['r'])
i += 1
return root
def clone(node):
if node is None:
return None
return {'name': node['name'], 'l': clone(node['l']), 'r': clone(node['r'])}
def find(root, name):
if root is None:
return None
if root['name'] == name:
return root
f = find(root['l'], name)
return f if f else find(root['r'], name)
def overlay(host, guest):
if guest is None:
return True
if host['name'] != guest['name']:
return False
if guest['l'] is not None:
if host['l'] is None:
host['l'] = clone(guest['l'])
elif not overlay(host['l'], guest['l']):
return False
if guest['r'] is not None:
if host['r'] is None:
host['r'] = clone(guest['r'])
elif not overlay(host['r'], guest['r']):
return False
return True
def try_merge(host, guest):
if guest is None:
return host
if host is None:
return None
target = find(host, guest['name'])
if target is None:
return None
if not overlay(target, guest):
return None
return host
def serialize(root):
if root is None:
return ''
out = []
q = deque([root])
while q:
cur = q.popleft()
if cur is None:
out.append('null')
else:
out.append(cur['name'])
q.append(cur['l'])
q.append(cur['r'])
while out and out[-1] == 'null':
out.pop()
return ' '.join(out)
t1 = parse(toks1)
t2 = parse(toks2)
res = try_merge(clone(t1), clone(t2))
if res is None:
res = try_merge(clone(t2), clone(t1))
if res is None:
print(0)
else:
print(serialize(res))
solve()
复杂度分析
时间复杂度：$O(n)$。建树、找对齐点、递归合并、层序输出各为一次线性遍历。 空间复杂度：$O(n)$。递归栈与合并结果的存储。
第三题：智能电动公交系统
题目描述
你正在参与开发一款智能公交调度系统，该系统需要为自动驾驶的电动公交规划从起点到终点的最短时间路径。城市道路网络由 $N$ 个交叉路口（编号 $0 \sim N-1$）构成，道路为单向，每条道路有固定的通行时间，其中有 $K$ 个路口建有充电站。
需要规划电动公交车从起点 $S$ 到终点 $T$ 的路线，存在以下约束：
- 车辆的电池电量有限，且不同路段的能耗不同，不能在电量不足的情况下通过某条道路（即剩余电量小于通过该道路需要的电量时禁止通过）。
- 车辆只能在充电站进行充电，不能在路段中途充电。
- 在充电站可以选择恢复电池至满电，也可以不充电；无论剩余多少电量每次充满电耗时为 1，不充电不耗时。
请设计算法，找出从起点 $S$ 到终点 $T$ 的总耗时最少的路径，并返回最小耗时。
输入描述
第一行包含七个整数 $N, K, M, S, T, E, maxE$，分别表示交叉路口数量、充电站数量、单向道路数量、起点、终点、初始电量和满电电量。
接下来 $M$ 行，每行包含四个整数 $u, v, t, c$，表示一条从 $u$ 路口到 $v$ 路口的有向道路，通行时间为 $t$，能耗为 $c$。
最后一行包含 $K$ 个整数，表示充电站所在的路口编号。
输出描述
输出一个整数，表示从起点 $S$ 到终点 $T$ 的最小总耗时；若无法到达终点，则输出 $-1$。
样例
输入
5 2 6 0 4 3 3
0 1 2 1
0 2 5 2
1 3 3 1
2 3 1 3
3 4 1 2
1 4 2 3
2 3
输出
7
最优路径为 $0 \to 1 \to 3 \to \text{充电} \to 4$。耗时 2，耗电 1，剩电 2；耗时 3，耗电 1，剩电 1；在充电站充满电，耗时 1，剩电 3；耗时 1，耗电 2。总耗时为 $2+3+1+1=7$。
思路分析
第一步：状态建模
单看节点不够，因为「到达某节点时剩多少电」直接决定后续可达性。必须把电量纳入状态。
把「当前节点 $u$」和「当前剩余电量 $e$」打包成一个二维状态 $(u, e)$。状态总数为 $N \times (maxE + 1)$。
距离 $\text{dist}[u][e]$ 表示到达该状态的最小总耗时，起点 $\text{dist}[S][E] = 0$，其余为 $\infty$。
第二步：转移规则
从 $(u, e)$ 出发有两类转移：
- 行驶转移：对 $u$ 的每条出边 $(v, t, c)$，要求 $e \geq c$，则可转移到 $(v, e-c)$，耗时加 $t$。
- 充电转移：当 $u$ 是充电站且 $e < maxE$ 时，可转移到 $(u, maxE)$，耗时加 1。
第三步：Dijkstra 求解
所有边权都是非负整数，Dijkstra 算法适用。用小根堆按耗时排序，第一次弹出终点 $T$ 时的耗时即为最优解。
第四步：不可达判定
堆为空仍未弹出任何终点状态，说明终点不可达，输出 $-1$。
题解代码
import sys
import heapq
def solve():
data = sys.stdin.buffer.read().split()
idx = 0
N = int(data[idx]); K = int(data[idx+1]); M = int(data[idx+2])
S = int(data[idx+3]); T = int(data[idx+4])
E = int(data[idx+5]); maxE = int(data[idx+6]); idx += 7
g = [[] for _ in range(N)]
for _ in range(M):
u = int(data[idx]); v = int(data[idx+1])
t = int(data[idx+2]); c = int(data[idx+3]); idx += 4
g[u].append((v, t, c))
is_cp = [False] * N
for _ in range(K):
is_cp[int(data[idx])] = True; idx += 1
INF = float('inf')
dist = [[INF] * (maxE + 1) for _ in range(N)]
dist[S][E] = 0
pq = [(0, S, E)]
while pq:
d, u, e = heapq.heappop(pq)
if d > dist[u][e]:
continue
if u == T:
print(d)
return
for v, t, c in g[u]:
if c <= e:
nd = d + t
ne = e - c
if nd < dist[v][ne]:
dist[v][ne] = nd
heapq.heappush(pq, (nd, v, ne))
if is_cp[u] and e < maxE:
nd = d + 1
if nd < dist[u][maxE]:
dist[u][maxE] = nd
heapq.heappush(pq, (nd, u, maxE))
print(-1)
solve()
复杂度分析
时间复杂度：$O(N \cdot maxE \cdot \log(N \cdot maxE))$。状态数 $N \times (maxE+1)$，每个状态至多触发出边数条转移。 空间复杂度：$O(N \cdot maxE)$，主要为二维 dist 表。
小结
- 第一题（浏览片段统计）：经典”至多 k 种不同元素”的滑动窗口模板题。维护哈希表记录窗口内各类别计数，右端扩张时类别数超 k 就收缩左端。每个右端点贡献 $r - l + 1$ 个合法子数组。
- 第二题（树的合并）：难点在于理解层序建树的规则（空节点不生孩子）和对齐合并的逻辑。核心是在 host 树中找到 guest 根的对齐点，然后递归检查每个重叠位置名字是否一致，不一致即冲突。双向尝试取先成功的方向。
- 第三题（智能电动公交系统）：把电量作为第二维状态，将问题转化为二维最短路。关键转移有两类：沿边行驶（消耗电量）和在充电站充满电（固定耗时 1）。Dijkstra 第一次弹出终点即为答案。