大厂真题 / 华为
华为 4.22 笔试真题 - 研发岗
本场考试概述
考试时间：2026年4月22日 考试岗位：研发岗（国内） 难度评级：中等偏难
考点分析：
- 第一题：DFS 三色判环 + 版本号规整（难度中等）
- 第二题：0-1 BFS 网格最少转弯（难度困难）
- 第三题：二维 DP 能量管理（难度中等）
建议策略：
- 第一题 DFS 判环是图论高频考点，掌握三色标记法后可稳拿本题
- 第三题二维 DP 状态设计清晰，先想清楚”打了 $k$ 个时最大剩余能量”的含义再动手
- 第二题 0-1 BFS 较难，有余力再做，不要在此死磕
第一题：简易的二进制包依赖关系检查和处理
题目描述
一个项目中，除了自研代码外，还会依赖很多二进制包，这些包也会依赖其它的包，每个被依赖的包还有版本号要求。需要完成一个简易的包依赖关系分析和处理模型：
- 依赖关系由三元组 $(a, b, v)$ 表示：包 $a$ 依赖包 $b$ 的 $v$ 版本
- 循环依赖检测：判断依赖关系中是否存在循环（如 $A \to B \to C \to A$），自己依赖自己也算循环。版本号不纳入判断
- 版本号规整：若无循环依赖，对于多个包依赖同一个包的情况，取被依赖包的最大版本号，替换所有引用
每次输入两组依赖关系，分别处理输出。每组第一行为正整数 $n$ 表示依赖关系个数，接下来 $n$ 行每行格式为 a,b,v。若存在循环依赖输出 false，否则输出版本号规整后的依赖关系。
样例
输入
3
1,2,23
2,3,34
4,2,25
3
1,2,23
2,3,34
3,1,12
输出
1,2,25
2,3,34
4,2,25
false
思路分析
第一步：将依赖关系建模为有向图
每个包看作一个节点，”包 $a$ 依赖包 $b$” 画一条 $a \to b$ 的有向边。循环依赖就是图中存在环——沿着箭头走能回到起点，比如 $A \to B \to C \to A$。自己依赖自己（$A \to A$）也是长度为 $1$ 的环。
第二步：三色 DFS 判环
用三种颜色标记每个节点的状态：
- 白色（0）：还没访问过
- 灰色（1）：正在访问中，从这个节点出发的 DFS 还没走完
- 黑色（2）：已经走完，确认从它出发无环
DFS 进入一个节点时标灰，离开时标黑。如果 DFS 过程中走到一个灰色节点，说明沿箭头绕了一圈回来——找到了环。
为什么需要三种颜色而不是两种？两种颜色（访问过/没访问过）会把”已经确认无环的节点”和”正在探索中的节点”混淆。只有灰色代表”正在当前路径上”才能精确判断是否回到了当前路径上的某个祖先。
第三步：版本号规整
如果没有环，对每个被依赖的包 $b$，遍历所有依赖关系找出版本号最大值。然后按输入顺序输出，把版本号替换为对应的最大值。
题解代码
import sys
from collections import defaultdict
input = sys.stdin.readline
def solve():
n = int(input())
deps = []
graph = defaultdict(list)
all_nodes = set()
for _ in range(n):
parts = input().strip().split(',')
a, b, v = int(parts[0]), int(parts[1]), int(parts[2])
deps.append((a, b, v))
graph[a].append(b)
all_nodes.add(a)
all_nodes.add(b)
color = {node: 0 for node in all_nodes}
def has_cycle(node):
color[node] = 1
for nei in graph[node]:
if color.get(nei, 0) == 1:
return True
if color.get(nei, 0) == 0 and has_cycle(nei):
return True
color[node] = 2
return False
for node in all_nodes:
if color[node] == 0 and has_cycle(node):
print("false")
return
max_ver = {}
for a, b, v in deps:
max_ver[b] = max(max_ver.get(b, 0), v)
for a, b, v in deps:
print(f"{a},{b},{max_ver[b]}")
solve()
solve()
复杂度分析
时间复杂度：$O(n)$，DFS 每个节点和边各访问一次，版本规整再扫一遍所有依赖关系 空间复杂度：$O(n)$，存邻接表和颜色数组
第二题：硬件布线
题目描述
硬件板上两个芯片之间需要布一条链路，两个芯片分别位于左上角和右下角。走线仅能向下和向右移动。板上已有一些器件或干扰源需要绕开。
给一个 $m \times n$ 的二维数组，0 表示可以布线，非零值（1/2/3/4 分别表示已有器件、开关电源、开孔等）均需要绕开。找从左上角到右下角通路的最少转弯次数。如果没有通路返回 $-1$。
特殊限制：若 $m < 3$ 或 $n < 3$，直接返回 $-1$。
样例
输入
4 4
0204
0130
0100
1000
输出
-1
输入
3 3
010
000
200
输出
2
输入
2 2
00
00
输出
-1
思路分析
第一步：明确”转弯”的含义
从一个格子走到下一个格子，有两种情况：保持原来的方向（不算转弯）或换方向（算一次转弯）。因此”从哪个方向到达当前格子”会影响后续代价，状态需要记录方向。
状态定义为三元组 $(r, c, d)$：行 $r$、列 $c$、上一步方向 $d$（$0$ 表示向右，$1$ 表示向下）。
第二步：识别 0-1 BFS 模型
从状态 $(r, c, d)$ 出发：
- 保持原方向移动：代价为 $0$
- 换方向移动：代价为 $1$
边权只有 $0$ 和 $1$ 两种，这正是 0-1 BFS 的典型场景——用双端队列替代优先队列：代价为 $0$ 的转移加入队首，代价为 $1$ 的转移加入队尾。队列中的状态始终按代价从小到大排列，第一次到达终点时的代价就是最少转弯次数。
第三步：起点处理
从 $(0, 0)$ 出发的第一步没有”上一步方向”，不存在转弯。分别尝试向右到 $(0, 1)$ 和向下到 $(1, 0)$，代价都算 $0$。
第四步：边界条件
- $m < 3$ 或 $n < 3$ 时直接返回 $-1$
- 起点或终点为非零格子也返回 $-1$
题解代码
import sys
from collections import deque
input = sys.stdin.readline
m, n = map(int, input().split())
grid = []
for _ in range(m):
grid.append(input().strip())
if m < 3 or n < 3 or grid[0][0] != '0' or grid[m - 1][n - 1] != '0':
print(-1)
else:
INF = float('inf')
dist = [[[INF, INF] for _ in range(n)] for _ in range(m)]
dq = deque()
dr = [0, 1]
dc = [1, 0]
if n > 1 and grid[0][1] == '0':
dist[0][1][0] = 0
dq.appendleft((0, 0, 1, 0))
if m > 1 and grid[1][0] == '0':
dist[1][0][1] = 0
dq.appendleft((0, 1, 0, 1))
while dq:
cost, r, c, d = dq.popleft()
if cost > dist[r][c][d]:
continue
for nd in range(2):
nr, nc = r + dr[nd], c + dc[nd]
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == '0':
ncost = cost + (0 if nd == d else 1)
if ncost < dist[nr][nc][nd]:
dist[nr][nc][nd] = ncost
if nd == d:
dq.appendleft((ncost, nr, nc, nd))
else:
dq.append((ncost, nr, nc, nd))
ans = min(dist[m - 1][n - 1][0], dist[m - 1][n - 1][1])
print(-1 if ans >= INF else ans)
复杂度分析
时间复杂度：$O(m \times n)$，每个格子最多以两种方向各入队一次，总状态数 $O(m \times n)$ 空间复杂度：$O(m \times n)$，存距离数组
第三题：星球大战
题目描述
在潘多拉星球上，有一群怪兽组成一道阵线，必须按顺序面对。初始能量值为 $E$，每个怪兽有攻击力 $d_i$ 和击败奖励 $r_i$。
面对第 $i$ 个怪兽时：
- 如果当前能量严格大于 $d_i$，可以选择战斗：先消耗 $d_i$ 点能量，再增加 $r_i$ 点能量
- 如果当前能量 $\leq d_i$，不能战斗，只能跳过
- 无论能否打过，也可以选择跳过
目标是最大化击败的怪兽数量。输入第一行为 $E$，第二行为各怪兽的攻击力（空格分隔），第三行为各怪兽的奖励（空格分隔）。
样例
输入
18
15 17 4 18
1 15 4 17
输出
2
输入
5
10 20 30
1 1 1
输出
0
输入
9
5 4 5
0 3 4
输出
2
思路分析
第一步：贪心为什么不行
最直觉的想法是”能打就打”，但这不对。打一个怪兽可能消耗大量能量，导致后面更”划算”的怪兽打不了。以样例 3 为例：初始能量 $9$，如果先打第 $1$ 个怪兽（$d=5, r=0$），能量变成 $4$，后面两个都打不了，只击败 $1$ 个。但跳过第 $1$ 个，打第 $2$、$3$ 个可以击败 $2$ 个。
需要全局规划哪些打哪些跳，这是动态规划的信号。
第二步：状态设计
要最大化击败数量。对于同样打了 $k$ 个怪兽的方案，剩余能量越多越好——能量多意味着后面还能打更多。所以 DP 不是直接算”最多打几个”，而是算”打了 $k$ 个时最多还剩多少能量”。
定义 $f[i][k]$：前 $i$ 个怪兽中恰好打了 $k$ 个时，剩余能量的最大值。初始 $f[0][0] = E$，其余为 $-\infty$ 表示不可达。
第三步：状态转移
处理第 $i$ 个怪兽时只有两种选择：
- 跳过：$f[i][k] = f[i-1][k]$
- 打：前提是 $f[i-1][k-1] > d_i$（能量严格大于攻击力），则 $f[i][k] = f[i-1][k-1] - d_i + r_i$
两者取最大值。
第四步：提取答案
所有怪兽处理完后，从 $k = n$ 往下找第一个满足 $f[n][k] \geq 0$ 的 $k$，就是最多能击败的怪兽数。
题解代码
import sys
input = sys.stdin.readline
E = int(input())
damage = list(map(int, input().split()))
reward = list(map(int, input().split()))
n = len(damage)
NEG = float('-inf')
f = [[NEG] * (n + 1) for _ in range(n + 1)]
f[0][0] = E
for i in range(1, n + 1):
for k in range(i + 1):
f[i][k] = f[i - 1][k]
if k > 0 and f[i - 1][k - 1] > damage[i - 1]:
f[i][k] = max(f[i][k], f[i - 1][k - 1] - damage[i - 1] + reward[i - 1])
ans = 0
for k in range(n, -1, -1):
if f[n][k] >= 0:
ans = k
break
print(ans)
复杂度分析
时间复杂度：$O(n^2)$，外层遍历 $n$ 个怪兽，内层遍历击败数 $k$ 空间复杂度：$O(n^2)$，二维 DP 数组
小结
- 第一题考察 DFS 三色标记法判环，是图论基础高频考点。判环后对版本号做一次聚合取最大值即可，属于必拿分题
- 第二题是 0-1 BFS 的经典应用——状态需要多记一个”方向”维度，权重 $0/1$ 对应同向/转弯，双端队列保证最优性
- 第三题是二维 DP，核心在于状态设计：”打了 $k$ 个时最大剩余能量”比直接记”最多打几个”更有力，因为它保留了后续决策的灵活性