大厂真题 / 华为
华为 6.17 笔试真题 - 研发岗（非AI方向）
本场考试概述
考试时间：2026年6月17日 考试岗位：研发岗（通软、嵌软、测试、普通算法、数据科学等非AI方向） 难度评级：中等
考点分析：
- 第一题：公交线路换乘优化——枚举交汇站（难度中等）
- 第二题：迷你文本编辑器——双栈撤销重做模拟（难度中等）
- 第三题：最小颜色修改代价——枚举目标颜色 + 网格 DP（难度中等）
建议策略：
- 第一题数据规模很小（线路数和站数均不超过 20），直接枚举所有直达和一次换乘走法即可，注意换乘站只算一次
- 第二题用 undo、redo 两个栈维护可撤销与可重做操作，注意执行新编辑后要清空 redo 栈
- 第三题枚举最终统一颜色，把每格修改代价当权值跑一遍网格最小路径和 DP，再对所有颜色取最小
第 1 题：公交线路换乘优化
题目描述
某城市有 $n$ 条公交线路，每条线路包含若干站点（按行驶方向排列）。从起点站 $A$ 到终点站 $B$，可以选择同一线路直达，或最多换乘一次（在两条线路的交汇站换乘）。起点和终点各算一次，换乘站只算一次。求从 $A$ 到 $B$ 经过的最少站点总数（包含起点和终点）。如果无法到达输出 $-1$。
样例
输入
2
4 1 2 3 4
3 5 6 7
1 7
输出
-1
输入
3
5 1 2 3 4 5
4 3 6 7 8
3 5 9 10
1 8
输出
6
思路分析
第一步：观察题目性质
线路是单向的，站点按顺序排列。从某站走到同线另一站经过的站数就是下标之差加一。线路数和站数都不超过 20，规模极小，可以暴力枚举所有走法。
第二步：路径只有两种形态
要么直达（$A$、$B$ 在同一线路上且 $A$ 在 $B$ 前面），要么恰好换乘一次。换乘一次意味着：前半程在线路 $i$ 上从 $A$ 坐到交汇站 $T$，后半程在线路 $j$ 上从 $T$ 坐到 $B$。
第三步：枚举所有可能的交汇站
对每条含 $A$ 的线路 $i$ 和每条含 $B$ 的线路 $j$（$i \neq j$），枚举线路 $i$ 上 $A$ 之后的每个站作为候选交汇站 $T$。$T$ 需要同时出现在线路 $j$ 上且在 $B$ 之前。
前半程经过 $(\text{pos_i}(T) - \text{pos_i}(A) + 1)$ 站，后半程经过 $(\text{pos_j}(B) - \text{pos_j}(T) + 1)$ 站，交汇站被两段各数了一次，合并时减一，总站数为二者之和减一。
第四步：取所有合法走法的最小值
遍历所有直达和换乘方案，取最小。如果不存在任何可行方案则输出 $-1$。
题解代码
import sys
input = sys.stdin.readline
def solve():
n = int(input())
lines = []
pos = []
for _ in range(n):
parts = list(map(int, input().split()))
m = parts[0]
stops = parts[1:m+1]
lines.append(stops)
mp = {}
for i, s in enumerate(stops):
mp[s] = i
pos.append(mp)
a, b = map(int, input().split())
best = float('inf')
# 直达：A、B在同一线路且A在B前面
for k in range(n):
if a in pos[k] and b in pos[k]:
ia, ib = pos[k][a], pos[k][b]
if ia < ib:
best = min(best, ib - ia + 1)
# 换乘一次：枚举前半程线路i、后半程线路j、交汇站T
for i in range(n):
if a not in pos[i]:
continue
ai = pos[i][a]
for j in range(n):
if i == j:
continue
if b not in pos[j]:
continue
bj = pos[j][b]
for p in range(ai, len(lines[i])):
t = lines[i][p]
if t in pos[j]:
tj = pos[j][t]
if tj <= bj:
best = min(best, (p - ai) + (bj - tj) + 1)
print(-1 if best == float('inf') else best)
solve()
复杂度分析
时间复杂度：$O(N^2 \times M)$，其中 $N$ 为线路数、$M$ 为单条线路最大站数。$N, M \leq 20$，约 $8000$ 次操作。 空间复杂度：$O(N \times M)$，存储每条线路的站点位置映射。
第 2 题：迷你文本编辑器的撤销与重做功能
题目描述
设计一个迷你文本编辑器，支持以下四种操作：
APPEND x：在文本末尾插入字符串 $x$POP：删除文本末尾最后一个字符（文本为空时无效果，不进入历史记录）UNDO：撤销上一次APPEND或POP操作REDO：重做上一次被撤销的操作。若在撤销后执行了新的APPEND或POP，之前的重做记录将被清空
初始时文本为空。给定一系列操作，输出最终文本内容（若为空输出 nothing）。
样例
输入
5
APPEND abc
APPEND d
UNDO
POP
REDO
输出
ab
输入
5
APPEND ab
UNDO
REDO
UNDO
REDO
输出
ab
思路分析
第一步：识别核心数据结构
撤销/重做是典型的双栈模型。done 栈记录已执行、可被撤销的操作；redo 栈记录已被撤销、可被重做的操作。
第二步：为每个操作记录逆操作信息
APPEND x：撤销时需要从末尾删掉 $\lvert x \rvert$ 个字符，所以记录整串 $x$POP：撤销时需要把被删的字符加回来，所以记录被删字符
第三步：栈间搬运
UNDO：从done弹出一条记录，执行它的逆操作，再压入redoREDO：从redo弹出一条记录，重新执行原操作，再压回done- 执行新的
APPEND或POP后，立即清空redo栈（之前的重做记录作废）
第四步：边界处理
POP 在文本为空时无效果且不入历史。UNDO 和 REDO 在对应栈为空时忽略。
题解代码
import sys
input = sys.stdin.readline
def solve():
n = int(input())
text = []
done = []
redo = []
for _ in range(n):
line = input().strip()
if line.startswith("APPEND "):
x = line[7:]
text.append(x)
done.append(('A', x))
redo.clear()
elif line == "POP":
if text:
last_seg = text[-1]
if len(last_seg) == 1:
c = text.pop()
else:
c = last_seg[-1]
text[-1] = last_seg[:-1]
done.append(('P', c))
redo.clear()
elif line == "UNDO":
if done:
act = done.pop()
if act[0] == 'A':
to_remove = len(act[1])
while to_remove > 0:
if len(text[-1]) <= to_remove:
to_remove -= len(text[-1])
text.pop()
else:
text[-1] = text[-1][:-to_remove]
to_remove = 0
else:
text.append(act[1])
redo.append(act)
else: # REDO
if redo:
act = redo.pop()
if act[0] == 'A':
text.append(act[1])
else:
last_seg = text[-1]
if len(last_seg) == 1:
text.pop()
else:
text[-1] = last_seg[:-1]
done.append(act)
result = ''.join(text)
print(result if result else "nothing")
solve()
复杂度分析
时间复杂度：$O(n + S)$，其中 $n$ 为操作数、$S$ 为所有插入字符的总数。每条操作只在文本末尾做一次增删，整体与输入规模同阶。 空间复杂度：$O(S)$。栈中保存的操作记录总长度不超过插入字符总数。
第 3 题：最小颜色修改代价
题目描述
有一个 $n \times m$ 的网格，每个格子有一个颜色值（$1$ 到 $C$ 的正整数）。从左上角 $(0,0)$ 出发只能向右或向下移动到右下角 $(n-1, m-1)$。要求路径上所有格子最终颜色相同，将某格颜色从 $a$ 改为 $b$ 的代价为 $\lvert b - a \rvert$。求最小总修改代价。
样例
输入
3 3 3
2 3 3
1 2 3
2 3 1
输出
3
输入
2 3 20
1 2 20
20 20 20
输出
19
思路分析
第一步：拆解问题——目标颜色和路径都要选
总代价取决于两个决策：走哪条路径、统一成哪种颜色。如果固定了目标颜色 $v$，每个格子的修改代价就是 $\lvert v - a_{i,j} \rvert$，问题退化为带权网格最小路径和。
第二步：目标颜色只需在 $1$ 到 $C$ 内枚举
对于任意一条路径，使总代价最小的 $v$ 一定是路径上颜色值的中位数，而中位数不会超出路径颜色的取值范围，因此 $v \in [1, C]$。外层枚举 $v$，内层对每个 $v$ 跑一次网格 DP 即可覆盖所有情况。
第三步：网格 DP
固定 $v$ 后，令 $f[i][j]$ 表示从 $(0,0)$ 走到 $(i,j)$ 的最小总代价。转移方程为：
\[f[i][j] = \min(f[i-1][j],\ f[i][j-1]) + \lvert v - a_{i,j} \rvert\]第一行只能从左走来、第一列只能从上走来，作为边界。$f[n-1][m-1]$ 就是颜色 $v$ 下的最优路径代价。
第四步：对所有颜色取最小
遍历 $v$ 从 $1$ 到 $C$，取 $f[n-1][m-1]$ 的全局最小值即为答案。
题解代码
import sys
input = sys.stdin.readline
def solve():
n, m, c = map(int, input().split())
a = []
for _ in range(n):
a.append(list(map(int, input().split())))
ans = float('inf')
for v in range(1, c + 1):
f = [[0] * m for _ in range(n)]
f[0][0] = abs(v - a[0][0])
for j in range(1, m):
f[0][j] = f[0][j-1] + abs(v - a[0][j])
for i in range(1, n):
f[i][0] = f[i-1][0] + abs(v - a[i][0])
for i in range(1, n):
for j in range(1, m):
f[i][j] = min(f[i-1][j], f[i][j-1]) + abs(v - a[i][j])
ans = min(ans, f[n-1][m-1])
print(ans)
solve()
复杂度分析
时间复杂度：$O(C \times n \times m)$，外层枚举 $C$ 种颜色，内层做一遍 $n \times m$ 的网格 DP。$C \leq 1000$，$n, m \leq 100$，约 $10^7$。 空间复杂度：$O(n \times m)$，DP 表的空间。
小结
- 第一题是小规模枚举题，核心在于理清”直达”和”一次换乘”两种路径形态，用站点位置映射快速计算经过站数
- 第二题是经典的可撤销操作模型，双栈分别维护已执行和已撤销的操作，关键点是新操作执行后要清空 redo 栈
- 第三题将”选路径 + 选颜色”解耦为外层枚举颜色、内层跑网格 DP 两个独立子问题，是枚举 + DP 结合的典型范式