大厂真题 / 华为

华为 4.23 笔试真题 - 留学生研发岗

本场考试概述

考试时间：2026年4月23日 考试岗位：留学生非AI岗（研发） 难度评级：中等

考点分析：

第一题：字符串解析 + 自定义排序（难度中等）
第二题：Floyd-Warshall 全源最短路（难度中等）
第三题：完全背包计数 DP（难度中等）

建议策略：

第一题版本号比较规则细节多，把主版本号转为整数数组逐位比较，beta 版本单独处理
第二题 $n \leq 200$，多对查询建议 Floyd 预处理全源最短路，查询 $O(1)$
第三题先扣去强制购买总费用，剩余预算用完全背包计数

第一题：给软件版本号排序

题目描述

给出 $n$ 个软件版本号字符串，按升序排序。

主版本号由 . 分割的多组数字组成。在正式版本之前还存在 beta 版本，会在主版本号后加上 beta 版本号，用空格分隔。例如 1.0.0 是正式版本，1.0.0 beta1 是其第 1 个 beta 版本。

比较规则：

先比较主版本号再比较 beta 版本号，主版本号越大的版本越大。
主版本号比较：从左往右依次比较由 . 分割的每一组数字；若前缀数字全部相等，段数较多的更大（如 6.0.0 > 6.0）。
主版本号相等时比较 beta 号：beta 版本小于对应正式版本；两个 beta 之间按 beta 号升序。

每个版本号由 . 分割的数字不超过 10 组，数字无前导零，范围 $[0, 2^{31} - 1]$。

样例

输入

5
0.1.0
0.0.0 beta3
0.0.1 beta1
0.0.0 beta2
0.0.1

输出

0.0.0 beta2
0.0.0 beta3
0.0.1 beta1
0.0.1
0.1.0

思路分析

第一步：解析版本号字符串

每个版本号按空格拆成两部分：主版本号和可选的 beta 号。主版本号按 . 分割为整数数组（必须转整数，否则 "10" < "9" 的字符串比较会出错）。beta 号提取 beta 后的数字；无空格表示 release 版本。

第二步：定义多级比较规则

逐位比较主版本号的整数数组，遇到不等的位直接分出大小
前缀完全相等时，段数多的版本更大（如 6.0.0 > 6.0）
主版本号相同时：beta 版本小于 release 版本；两个 beta 按 beta 号升序

第三步：利用 Python 元组的字典序排序

将每个版本号解析为排序键 (main_nums, is_release, beta_num)，其中 is_release 为 0（beta）或 1（release），这样 beta 自然排在 release 前面。Python 元组的字典序比较天然支持逐位比较和长度不等的情况。

题解代码

import sys
input = sys.stdin.readline

def sort_key(s):
    parts = s.split(' ')
    main_nums = tuple(int(x) for x in parts[0].split('.'))
    if len(parts) > 1:
        beta_num = int(parts[1][4:])
        return (main_nums, 0, beta_num)
    return (main_nums, 1, 0)

n = int(input())
versions = [input().strip() for _ in range(n)]
versions.sort(key=sort_key)
print('\n'.join(versions))

复杂度分析

时间复杂度：$O(n \log n \cdot k)$，排序 $O(n \log n)$，每次比较 $O(k)$（$k$ 为版本号段数，不超过 10）。 空间复杂度：$O(nk)$，存储解析后的版本号。

第二题：AI 超节点内部计算单元通信最小时延

题目描述

AI 超节点内有 $N$ 个计算单元，彼此间可能存在互联通道，每条通道有不同的通信时延。不同计算单元通信时，时延为所经过的每段通道的时延累加。

给定 $N$ 个计算单元和 $M$ 条互联通道（双向带权边），回答 $K$ 次查询：给定源节点和目的节点，计算最小通信时延；若不可达，输出 $0$。

数据范围：$N \leq 200$，$M \leq N \times (N-1)/2$，$K \leq 1000$。

样例

输入

输出

30
0
40

思路分析

第一步：选择算法

$N \leq 200$ 且有多次查询，如果每次查询单独跑 Dijkstra 需要 $O(K \cdot N^2)$；而 Floyd-Warshall 只需 $O(N^3)$ 预处理，之后每次查询 $O(1)$。当 $K$ 较大时 Floyd 更优，而且实现简单。

第二步：Floyd-Warshall 的三层循环

核心思想：枚举中转站 $k$，对所有点对 $(i, j)$ 尝试经 $k$ 中转的路径是否更短。关键：$k$ 必须在最外层循环，因为枚举到 $k$ 时需要保证”只经过前 $k$ 个节点中转”的最短路已经完成。

\[\text{dist}[i][j] = \min(\text{dist}[i][j],\; \text{dist}[i][k] + \text{dist}[k][j])\]

第三步：不可达判定

查询时若 $\text{dist}[u][v]$ 仍为 $\infty$，表示不可达，按题意输出 $0$。

题解代码

import sys
input = sys.stdin.readline

INF = float('inf')
N, M = map(int, input().split())

dist = [[INF] * N for _ in range(N)]
for i in range(N):
    dist[i][i] = 0

for _ in range(M):
    a, b, c = map(int, input().split())
    dist[a][b] = min(dist[a][b], c)
    dist[b][a] = min(dist[b][a], c)

# Floyd-Warshall：k 在最外层
for k in range(N):
    dk = dist[k]
    for i in range(N):
        if dist[i][k] == INF:
            continue
        di = dist[i]
        dik = di[k]
        for j in range(N):
            new_dist = dik + dk[j]
            if new_dist < di[j]:
                di[j] = new_dist

K = int(input())
results = []
for _ in range(K):
    u, v = map(int, input().split())
    if u >= N or v >= N or dist[u][v] == INF:
        results.append('0')
    else:
        results.append(str(dist[u][v]))
print('\n'.join(results))

复杂度分析

时间复杂度：Floyd-Warshall $O(N^3)$，查询 $O(K)$。总计 $O(N^3 + K)$。 空间复杂度：$O(N^2)$，距离矩阵。

第三题：奖品采购

题目描述

你负责为公司年会采购商品。给定整数数组 $\text{prices}$ 表示不同商品的价格和整数 $\text{budget}$ 表示总预算。要求：列表中每种奖品至少购买一件（即使两种奖品价格相同也视为不同奖品）。满足前提后，剩余预算可随意采购任意数量的奖品（每种库存无限）。

计算恰好花完总预算的采购方案数。方案仅与每种商品购买的数量有关，与购买顺序无关。若无法满足基本条件或无法恰好凑出，返回 $0$。

样例

输入

10
1 2

输出

思路分析

第一步：扣除强制购买

每种商品至少买一件，花费 $\text{total} = \sum \text{prices}$。如果 $\text{total} > \text{budget}$，直接返回 $0$。否则剩余预算 $R = \text{budget} - \text{total}$。

第二步：转化为完全背包计数

问题变成：用 $R$ 元预算，每种商品可买任意件（包括 $0$ 件），恰好花完的方案数。这是经典的完全背包计数 DP。

第三步：状态转移

定义 $f[j]$ 为恰好凑出 $j$ 元的方案数，初始化 $f[0] = 1$（不买任何商品凑 $0$ 元只有一种方案）。

依次处理每种商品（价格 $p$），正序遍历 $j$ 从 $p$ 到 $R$：

\[f[j] = f[j] + f[j - p]\]

为什么正序遍历？因为完全背包允许同一种商品选多次。以价格 $[1, 2]$、$R = 7$ 为例：处理价格 $1$ 的商品时，$f[2]$ 先被更新（含一件价格 $1$ 的方案），随后 $f[3]$ 使用已更新的 $f[2]$，相当于选了两件价格 $1$ 的商品。如果逆序遍历，则 $f[j-p]$ 尚未被当前商品更新，每件最多选一次（0-1 背包）。

样例推导：$\text{prices} = [1, 2]$，$\text{budget} = 10$，强制花 $3$，$R = 7$。用 $[1, 2]$ 凑 $7$ 的方案：$(7,0), (5,1), (3,2), (1,3)$，共 $4$ 种。

题解代码

import sys
input = sys.stdin.readline

budget = int(input())
prices = list(map(int, input().split()))

total = sum(prices)
if total > budget:
    print(0)
else:
    remaining = budget - total
    f = [0] * (remaining + 1)
    f[0] = 1
    for p in prices:
        # 正序遍历：完全背包，同一商品可多次选取
        for j in range(p, remaining + 1):
            f[j] += f[j - p]
    print(f[remaining])

复杂度分析

时间复杂度：$O(n \cdot R)$，$n$ 种商品各遍历一轮 DP 数组。 空间复杂度：$O(R)$，一维 DP 数组。

小结

第一题考察字符串解析和自定义排序，关键是将版本号解析为可比较的元组，利用 Python 元组字典序天然支持多级比较
第二题是 Floyd-Warshall 全源最短路的直接应用，$N \leq 200$ 的规模下 $O(N^3)$ 完全够用
第三题是完全背包计数 DP 的经典变形：先扣除强制购买，再用正序遍历的一维 DP 计数

这篇文章有帮助吗？

| GitHub 留言