华为笔试 华为笔试题 0409
笔试时间：2025年04月09日
历史笔试传送门：
第一题
题目：补丁版本升级
输入描述
第一行为记录的版本迭代关系个数N，范围是[1，100000];
第二行到第N+1行：每行包含两个字符串，第一个字符串为当前版本，第二个字符串为前序版本，用空格隔开。
字符串包含字符个数为[1，100]，没有前序版本的第二个字符串固定为NA。
输出描述
所有迭代次数最多的补丁版本号字符串列表，多个版本号以字典序排序排列，用空格隔开。
样例输入
6
CN001 BF0001
BF001 AZ2001
AZ0001 NA
BF0010 AZ0001
AWOO01 NA
BF0011 AZ0001
样例输出
CN0010
解释：
AZ0001和AWV0001没有前序版本，各选代了0次;
BF0001，BF0010和BF0011的前序版本为AZ0001，各选代了1次;
CN0010的前序版本为BF0001，BF0001的前序版本为AZ0001，选代了2次。
根据要求选择迭代次数最多的补丁版本，因此输出CN0010。
参考题解
拓扑排序。我们需要找到依赖链最长的补丁版本，即迭代次数最多的版本。每个版本的迭代次数等于其到根节点的路径长度，其实就是拓扑排序加一个计数就可以了。从所有根节点（入度为0的节点）开始，使用广度优先搜索（BFS）进行拓扑排序。在处理每个节点时，计算其所有子节点的深度（当前节点深度加1），确保父节点处理完成后才处理子节点。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
unordered_map<string, vector<string>> G;
unordered_map<string, int> indegree;
unordered_set<string> nodes;
for (int i = 0; i < n; ++i) {
string a, b;
cin >> a >> b;
nodes.insert(a);
if (b != "NA") {
nodes.insert(b);
G[b].push_back(a);
indegree[a] = 1;
} else {
indegree[a] = 0;
}
}
unordered_map<string, int> MAX;
queue<string> q;
for (const auto& node : nodes) {
if (indegree[node] == 0) {
q.push(node);
MAX[node] = 0;
}
}
while (!q.empty()) {
string u = q.front();
q.pop();
for (const auto& v : G[u]) {
MAX[v] = MAX[u] + 1;
indegree[v]--;
if (indegree[v] == 0) {
q.push(v);
}
}
}
int max_val = 0;
for (const auto& kv : MAX) {
max_val = max(max_val, kv.second);
}
vector<string> ans;
for (const auto& kv : MAX) {
if (kv.second == max_val) {
ans.push_back(kv.first);
}
}
sort(ans.begin(), ans.end());
for (int i = 0; i < ans.size(); ++i) {
if (i > 0) cout << " ";
cout << ans[i];
}
cout << endl;
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = Integer.parseInt(scanner.nextLine());
Map<String, List<String>> G = new HashMap<>();
Map<String, Integer> indegree = new HashMap<>();
Set<String> nodes = new HashSet<>();
for (int i = 0; i < n; i++) {
String[] parts = scanner.nextLine().split(" ");
String a = parts[0], b = parts[1];
nodes.add(a);
if (!b.equals("NA")) {
nodes.add(b);
G.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
indegree.put(a, 1);
} else {
indegree.put(a, 0);
}
}
Map<String, Integer> MAX = new HashMap<>();
Queue<String> q = new LinkedList<>();
for (String node : nodes) {
if (indegree.getOrDefault(node, 0) == 0) {
q.offer(node);
MAX.put(node, 0);
}
}
while (!q.isEmpty()) {
String u = q.poll();
for (String v : G.getOrDefault(u, new ArrayList<>())) {
MAX.put(v, MAX.get(u) + 1);
indegree.put(v, indegree.get(v) - 1);
if (indegree.get(v) == 0) {
q.offer(v);
}
}
}
int maxVal = 0;
for (int val : MAX.values()) {
maxVal = Math.max(maxVal, val);
}
List<String> ans = new ArrayList<>();
for (Map.Entry<String, Integer> entry : MAX.entrySet()) {
if (entry.getValue() == maxVal) {
ans.add(entry.getKey());
}
}
Collections.sort(ans);
System.out.println(String.join(" ", ans));
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
from collections import defaultdict, deque
def solve():
n = int(input())
G = defaultdict(list)
indegree = defaultdict(int)
nodes = set()
for _ in range(n):
parts = input().split()
a, b = parts[0], parts[1]
nodes.add(a)
if b != 'NA':
nodes.add(b)
G[b].append(a)
indegree[a] = 1
else:
indegree[a] = 0
MAX = defaultdict(int)
q = deque()
for node in nodes:
if indegree[node] == 0:
q.append(node)
MAX[node] = 0
while q:
u = q.popleft()
for v in G[u]:
MAX[v] = MAX[u] + 1
indegree[v] -= 1
if indegree[v] == 0:
q.append(v)
max_val = max(MAX.values())
ans = [k for k, v in MAX.items() if v == max_val]
ans.sort()
print(' '.join(ans))
solve()
第二题
题目：地铁耗时最短的线路
大湾区某城市地铁线路非常密集，乘客很难一眼看出选择哪条线路乘坐比较合适，为了解决这个问题，地铁公司希望你开发一个程序帮助乘客挑选合适的乘坐线路，使得乘坐时间最短，地铁公司可以提供的数据是各相邻站点之间的乘坐时间。
输入描述
第一行:N，站点总数,3<=N<=20.
第二行:乘宫的出发和到达站点。
第三行起:相邻站点之间的乘坐时间，每对站点一行，站点名称是单个小写字母，站点名一定包括出发和到
达站点，输入保证只有一个唯一解;
结束行:0000
输出描述
耗时最短的线路
样例输入
12
a e
a b 2
b c 2
c d 2
d e 2
f b 3
b g 3
g h 2
h i 3
j h 2
h e 3
e k 2
k i 4
0000
样例输出
a b c d e
参考题解
迪杰斯特拉+回溯路径。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <string>
#include <limits>
#include <algorithm>
using namespace std;
typedef pair<int, string> PIS;
int main() {
int n;
cin >> n;
string s, e;
cin >> s >> e;
unordered_map<string, vector<pair<string, int>>> G;
unordered_set<string> nodes;
while (true) {
string a, b;
int c;
cin >> a;
if (a == "0000") break;
cin >> b >> c;
G[a].push_back({b, c});
nodes.insert(a);
nodes.insert(b);
}
unordered_map<string, int> dis;
unordered_map<string, string> pre;
const int INF = numeric_limits<int>::max();
for (auto node : nodes) dis[node] = INF;
dis[s] = 0;
priority_queue<PIS, vector<PIS>, greater<PIS>> pq;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (u == e) break;
if (d > dis[u]) continue;
for (auto [v, weight] : G[u]) {
int new_dist = d + weight;
if (new_dist < dis[v]) {
dis[v] = new_dist;
pre[v] = u;
pq.push({new_dist, v});
}
}
}
vector<string> path;
string current = e;
while (current != s) {
path.push_back(current);
current = pre[current];
}
path.push_back(s);
reverse(path.begin(), path.end());
for (int i = 0; i < path.size(); i++) {
if (i > 0) cout << " ";
cout << path[i];
}
cout << endl;
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.*;
public class Main {
static class Node implements Comparable<Node> {
String name;
int dist;
Node(String name, int dist) {
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025 春招笔试合集 文章被收录于专栏
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
