华为笔试 华为 0422 春招实习笔试真题解析
笔试时间：2026 年 4 月 22 日
本次笔试共涉及 5 道题，分别属于两场笔试：
- AI 岗机考（传统算法）：第 1、2 题
- 通用笔试：第 3、4、5 题
往年笔试合集：
第 1 题 — 统计二叉树中"平衡路径"的数量（150 分，中等，DFS）
题目
定义二叉树的平衡路径需同时满足以下 3 个条件：
- 路径从任意节点出发，仅能向下延伸（只能向左/右子节点，不可向上回溯）。
- 路径上所有节点的和相加为 0。
- 路径长度（包含的节点个数）至少为 2。
请实现一个函数，输入二叉树的根节点（按层序遍历规则构建），返回该树中所有"平衡路径"的总数。
注意：
- 建树规则：层序遍历列表按「从上到下、从左到右」的顺序构建二叉树，
None表示对应位置无节点。 - 路径延伸：从起点出发，仅沿左子节点 OR 右子节点单向向下（单链，不可分叉）。
- 统计方式：每个符合条件的单链路径独立计数（即使路径有重叠）。
输入描述
二叉树的层序遍历列表（元素为整数或 None，None 表示空节点）。
输出描述
整数，表示平衡路径的总数。
样例
样例 1
输入：
[10, -5, -5, 2, -2, 3, -3]
输出：
0
样例 2
输入：
[0, 0, None]
输出：
1
样例 3
输入：
[1, -1, 2, -2, None, 3, -3]
输出：
2
参考题解
解题思路：
核心是在二叉树中寻找从上到下、和为 0 且节点数 ≥ 2 的单链路径。
- 树的构建：通过按层遍历（BFS）解析输入列表，将节点还原成树状结构。
- 前缀和 + DFS：寻找和为 0 的路径可以转换为寻找两个节点 A 和 B（A 是 B 的祖先），使得它们到根节点的前缀和相等。通过 DFS 自顶向下遍历，用哈希表记录当前路径上出现过的前缀和及其次数，可在 O(N) 的时间复杂度内完成统计。
- 长度限制：题目要求节点数至少为 2。如果当前节点值为 0，它本身会产生一条长度为 1 的非法路径，此时需要将匹配数减 1 以排除。
- 回溯：递归返回时撤销当前节点的前缀和记录，避免跨分支污染。
C++
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};
long long ans = 0;
unordered_map<long long, int> prefixSums;
void dfs(TreeNode* node, long long currSum) {
if (!node) return;
currSum += node->val;
// 存在祖先前缀和等于当前前缀和，则该段路径和为 0
if (prefixSums.count(currSum)) ans += prefixSums[currSum];
// 排除长度为 1 的单节点路径（node.val == 0 时会自匹配）
if (node->val == 0) ans -= 1;
prefixSums[currSum]++;
dfs(node->left, currSum);
dfs(node->right, currSum);
prefixSums[currSum]--; // 回溯
}
int main() {
string line;
getline(cin, line);
// 提取 [ ... ] 之间的内容
size_t l = line.find('['), r = line.find(']');
string content = line.substr(l + 1, r - l - 1);
vector<pair<int,bool>> arr; // {值, 是否为空}
stringstream ss(content);
string tok;
while (getline(ss, tok, ',')) {
// trim
size_t a = tok.find_first_not_of(" \t");
size_t b = tok.find_last_not_of(" \t");
if (a == string::npos) continue;
tok = tok.substr(a, b - a + 1);
if (tok == "None" || tok == "null") arr.push_back({0, true});
else arr.push_back({stoi(tok), false});
}
if (arr.empty() || arr[0].second) { cout << 0 << endl; return 0; }
// 层序建树
TreeNode* root = new TreeNode(arr[0].first);
queue<TreeNode*> q; q.push(root);
int i = 1, n = arr.size();
while (!q.empty() && i < n) {
TreeNode* cur = q.front(); q.pop();
if (i < n && !arr[i].second) { cur->left = new TreeNode(arr[i].first); q.push(cur->left); }
i++;
if (i < n && !arr[i].second) { cur->right = new TreeNode(arr[i].first); q.push(cur->right); }
i++;
}
prefixSums[0] = 1; // 根节点本身直接出发
dfs(root, 0);
cout << ans << endl;
return 0;
}
Java
import java.util.*;
public class Main {
static class TreeNode {
int val; TreeNode left, right;
TreeNode(int v) { val = v; }
}
static long ans = 0;
static Map<Long, Integer> prefixSums = new HashMap<>();
static void dfs(TreeNode node, long currSum) {
if (node == null) return;
currSum += node.val;
ans += prefixSums.getOrDefault(currSum, 0);
if (node.val == 0) ans -= 1; // 排除单节点路径
prefixSums.merge(currSum, 1, Integer::sum);
dfs(node.left, currSum);
dfs(node.right, currSum);
prefixSums.merge(currSum, -1, Integer::sum); // 回溯
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String line = sc.nextLine().trim();
line = line.substring(line.indexOf('[') + 1, line.indexOf(']'));
String[] tokens = line.split(",");
List<Integer> vals = new ArrayList<>();
List<Boolean> isNull = new ArrayList<>();
for (String t : tokens) {
t = t.trim();
if (t.equals("None") || t.equals("null")) { vals.add(0); isNull.add(true); }
else { vals.add(Integer.parseInt(t)); isNull.add(false); }
}
if (vals.isEmpty() || isNull.get(0)) { System.out.println(0); return; }
TreeNode root = new TreeNode(vals.get(0));
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int i = 1, n = vals.size();
while (!q.isEmpty() && i < n) {
TreeNode cur = q.poll();
if (i < n && !isNull.get(i)) { cur.left = new TreeNode(vals.get(i)); q.offer(cur.left); }
i++;
if (i < n && !isNull.get(i)) { cur.right = new TreeNode(vals.get(i)); q.offer(cur.right); }
i++;
}
prefixSums.put(0L, 1);
dfs(root, 0);
System.out.println(ans);
}
}
Python
import sys
import json
class TreeNode:
def __init__(self, val=0):
self.val = val
self.left = None
self.right = None
def solve():
line = sys.stdin.readline().strip()
if not line:
return
line = line.replace("None", "null").replace("'", '"')
arr = json.loads(line)
# 层序遍历构建二叉树
root = TreeNode(arr[0])
queue = [root]
i = 1
n = len(arr)
while queue and i < n:
curr = queue.pop(0)
if i < n and arr[i] is not None:
curr.left = TreeNode(arr[i])
queue.append(curr.left)
i += 1
if i < n and arr[i] is not None:
curr.right = TreeNode(arr[i])
queue.append(curr.right)
i += 1
ans = 0
# 前缀和字典，初始化 0 出现 1 次，代表"从根节点直接出发"的情况
prefix_sums = {0: 1}
def dfs(node, curr_sum):
nonlocal ans
if not node:
return
curr_sum += node.val
# 查找是否存在祖先节点的前缀和与当前前缀和相同
ans += prefix_sums.get(curr_sum, 0)
# 排除长度为 1 的路径：node.val == 0 时需要减 1
if node.val == 0:
ans -= 1
prefix_sums[curr_sum] = prefix_sums.get(curr_sum, 0) + 1
dfs(node.left, curr_sum)
dfs(node.right, curr_sum)
# 回溯
prefix_sums[curr_sum] -= 1
dfs(root, 0)
print(ans)
if __name__ == '__main__':
solve()
第 2 题 — 网络异常流量传播链路溯源（300 分，困难，动态规划）
题目
在网络监控中，异常流量的流动通常具有局部聚集性。监控系统需要识别出高负载的基站（关键节点），并判断流量在这些节点之间定向的传播链的最长路径。
网络监控规则：
- 直接关联：对于基站 i 和 j，若其曼哈顿距离 ≤ E，则判定两者具有直接关联。
- 关键节点判定：计算一个基站及其所有具有"直接关联"属性的基站（含自身）的流量负载之和。若该总和 ≥ T，则该基站被判定为关键节点。
流量传播链路：
- 链路条件：若两个关键节点具有"直接关联"关系，且发生时间戳不同，则流量从时间较早的基站流向时间较晚的基站。
- 若两个关联的关键节点发生时间完全相同，则它们之间无法建立有效的传播链路。
传播链条：
传播链条是由一系列关键节点通过有向链路首尾相连构成的路径。链条的规模为该路径上所有节点服务的用户数 U 之和。任务：计算全网中可能形成的所有传播链条中，能够覆盖的最大用户总数。
处理流程：
- 节点识别：基于空间距离和流量负载阈值，从所有基站中筛选出满足要求的关键节点。
- 构建拓扑：在关键节点间，基于空间关联和时间先后顺序（早→晚）建立定向传播关系。
- 路径计算：在构成的有向传播网络中，寻找一条路径，使得累计服务的用户数达到最大。
输入描述
- 第一行：三个整数 N（基站总数）、E（直接关联的曼哈顿距离阈值）和 T（负载阈值）。
- 接下来的 N 行，每行包含 5 个整数：
x y t W U（坐标、时间戳、负载、用户数）。
所有坐标、时间戳、负载和用户数的取值范围均为非负整数。
输出描述
输出一个整数，代表最大用户数。若全网无法形成任何链路或关键节点，输出 0。
样例
样例 1
输入：
3 1 500 0 0 10 100 50 1 0 20 100 50 0 1 30 100 50
输出：
0
说明：三个基站互为邻居，但每个基站能查到的邻域最大负载和仅为 100 + 100 + 100 = 300。判定门槛 T = 500，因 300 < 500，图中没有任何基站能成为关键节点。无关键节点即无法形成链条，输出 0。
样例 2
输入：
4 1 150 0 0 10 100 10 1 0 20 100 10 5 5 10 200 100 5 6 30 200 100
输出：
200
说明：基站 0 和 1 曼哈顿距离为 1，互为邻居，连通块负载和 200 ≥ 150，均为关键节点；基站 2 和 3 曼哈顿距离为 1，连通块负载 400 ≥ 150，也均为关键节点。基站 2（t=10）→ 基站 3（t=30）可建立传播链路，用户数之和 = 100 + 100 = 200；基站 0、1 的用户数之和仅为 20。最大覆盖用户数为 200。
参考题解
解题思路：
这道题是图论与动态规划结合的题目。难点在于节点数量可能较多时，如何高效地找出"关键节点"并构建出流量传播网。
- 空间网格降维：直接两两计算曼哈顿距离的复杂度是 O(N²)，当 N 巨大时会超时。将地图划分为边长为 E 的网格，任何基站的潜在关联邻居一定在它所在网格及其周围 8 个网格内，使得寻找相邻基站的耗时从全局遍历降至常数级。
- 筛选关键节点：利用网格优化，求出每台基站的"局部负载和"，将负载和 ≥ T 的过滤为关键节点。
- 构建 DAG：遍历关键节点，若两者是邻居且时间戳不同，建立一条从早到晚的有向边。因为时间单调递增，形成的必然是无环的 DAG。
- 记忆化搜索：在 DAG 上使用 DFS + 记忆化求出一条路径，使其权值（用户数 U 之和）最大化。
C++
#include <bits/stdc++.h>
using namespace std;
int N, E, T;
vector<long long> x, y, tm, W, U;
vector<long long> adjSum;
map<pair<long long,long long>, vector<int>> grid;
vector<vector<int>> graph;
vector<long long> dp;
vector<bool> visited;
vector<bool> isCritical;
// 正确的向下取整除法（处理负坐标）
long long floorDiv(long long a, long long b) {
long long q = a / b;
if ((a ^ b) < 0 && q * b != a) q--;
return q;
}
long long dfs(int node) {
if (visited[node]) return dp[node];
visited[node] = true;
long long maxNext = 0;
for (int nxt : graph[node]) maxNext = max(maxNext, dfs(nxt));
dp[node] = maxNext + U[node];
return dp[node];
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> N >> E >> T;
x.assign(N, 0); y.assign(N, 0); tm.assign(N, 0);
W.assign(N, 0); U.assign(N, 0);
adjSum.assign(N, 0);
graph.assign(N, {});
dp.assign(N, 0);
visited.assign(N, false);
isCritical.assign(N, false);
long long S = max(1, E);
for (int i = 0; i < N; i++) {
cin >> x[i] >> y[i] >> tm[i] >> W[i] >> U[i];
grid[{floorDiv(x[i], S), floorDiv(y[i], S)}].push_back(i);
}
// 1. 邻域负载求和
for (int i = 0; i < N; i++) {
long long cx = floorDiv(x[i], S), cy = floorDiv(y[i], S);
long long sum = 0;
for (int dx = -1; dx <= 1; dx++)
for (int dy = -1; dy <= 1; dy++) {
auto it = grid.find({cx + dx, cy + dy});
if (it == grid.end()) continue;
for (int j : it->second)
if (abs(x[i]-x[j]) + abs(y[i]-y[j]) <= E) sum += W[j];
}
adjSum[i] = sum;
}
// 2. 筛选关键节点
vector<int> critical;
for (int i = 0; i < N; i++)
if (adjSum[i] >= T) { isCritical[i] = true; critical.push_back(i); }
if (critical.empty()) { cout << 0 << endl; return 0; }
// 3. 建立 DAG
for (int i : critical) {
long long cx = floorDiv(x[i], S), cy = floorDiv(y[i], S);
for (int dx = -1; dx <= 1; dx++)
for (int dy = -1; dy <= 1; dy++) {
auto it = grid.find({cx + dx, cy + dy});
if (it == grid.end()) continue;
for (int j : it->second) {
if (!isCritical[j] || i == j) continue;
if (abs(x[i]-x[j]) + abs(y[i]-y[j]) <= E && tm[i] < tm[j])
graph[i].push_back(j);
}
}
}
// 4. 记忆化 DFS
long long maxUsers = 0;
for (int c : critical) maxUsers = max(maxUsers, dfs(c));
cout << maxUsers << endl;
return 0;
}
Java
import java.util.*;
public class Main {
static int N, E, T;
static long[] x, y, tm, W, U, adjSum, dp;
static boolean[] visited, isCritical;
static Map<Long, List<Integer>> grid = new HashMap<>();
static List<List<Integer>> graph;
static long floorDiv(long a, long b) {
long q = a / b;
if ((a ^ b) < 0 && q * b != a) q--;
return q;
}
static long key(long cx, long cy) {
return cx * 2000003L + cy; // 简易哈希
}
static long dfs(int node) {
if (visited[node]) return dp[node];
visited[node] = true;
long maxNext = 0;
for (int nxt : graph.get(node)) maxNext = Math.max(maxNext, dfs(nxt));
dp[node] = maxNext + U[node];
return dp[node];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt(); E = sc.nextInt(); T = sc.nextInt();
x = new long[N]; y = new long[N]; tm = new long[N];
W = new long[N]; U = new long[N]; adjSum = new long[N];
dp = new long[N]; visited = new boolean[N]; isCritical = new boolean[N];
graph = new ArrayList<>();
for (int i = 0; i < N; i++) graph.add(new ArrayList<>());
long S = Math.max(1, E);
for (int i = 0; i < N; i++) {
x[i] = sc.nextLong(); y[i] = sc.nextLong();
tm[i] = sc.nextLong(); W[i] = sc.nextLong(); U[i] = sc.nextLong();
long k = key(floorDiv(x[i], S), floorDiv(y[i], S));
grid.computeIfAbsent(k, kk -> new ArrayList<>()).add(i);
}
// 邻域负载
for (int i = 0; i < N; i++) {
long cx = floorDiv(x[i], S), cy = floorDiv(y[i], S);
long sum = 0;
for (int dx = -1; dx <= 1; dx++)
for (int dy = -1; dy <= 1; dy++) {
List<Integer> cell = grid.get(key(cx + dx, cy + dy));
if (cell == null) continue;
for (int j : cell)
if (Math.abs(x[i] - x[j]) + Math.abs(y[i] - y[j]) <= E) sum += W[j];
}
adjSum[i] = sum;
}
List<Integer> critical = new ArrayList<>();
for (int i = 0; i < N; i++)
if (adjSum[i] >= T) { isCritical[i] = true; critical.add(i); }
if (critical.isEmpty()) { System.out.printl
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025 春招笔试合集 文章被收录于专栏
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
