大厂真题 / 华为

华为 8.19 笔试真题 - 研发岗

本场考试概述

考试时间：2026 年 8 月 19 日
考试岗位：研发岗
难度评级：中等

考点分析：

迷宫逃脱：把剩余生命值纳入状态的分层 BFS。
网络数据流的有效传输段分析：前缀计数 + 最早位置。
流量均衡控制：等均值条件变形 + 带选取个数的 0/1 背包。

三题的模板都不复杂，关键是正确改写状态或判定条件。第一题不能只按坐标判重；第二题必须区分同步字符与干扰字符；第三题不能省略“选了多少条消息”这一维。

第 1 题：迷宫逃脱

题目描述

给定一个 m × n 网格，各单元格含义如下：

0：空地，可以通行；
1：墙，不能通行；
2：陷阱，进入后损失 1 点生命值；
3：起点，全图唯一；
4：出口，全图唯一；
5：生命药水，进入后生命值恢复到初始上限。

探险者初始生命值为 k，每次可向上、下、左、右移动一格。生命值降到 0 时立即倒下。求从起点到出口的最少步数；无法到达时输出 -1。

输入描述

第一行输入三个整数 m n k。接下来 m 行，每行输入 n 个整数表示网格。

样例

输入

输出

思路分析

普通网格 BFS 只用 (x, y) 判重并不正确。同一位置可能通过不同路径到达，而剩余生命值不同；较晚到达但生命值更高的状态，可能是之后穿过陷阱区的唯一可行状态。

因此将状态定义为 (x, y, hp)，其中 hp 是当前剩余生命值。转移到下一格时：

陷阱：hp -= 1；
药水：hp = k；
其他可通行格：生命值不变。

若新生命值不大于 0，该状态不能入队。每次移动代价均为 1，BFS 第一次到达出口时的层数就是最少步数。

还可以做一个安全的支配优化：对每个格子只记录此前到达时的最大生命值。若新状态的生命值不高于该值，则它不会比旧状态拥有更多后续选择，可以跳过。为使逻辑最直观，下面代码直接对三元组判重。

题解代码

import sys
from collections import deque


def solve():
    input = sys.stdin.buffer.readline
    m, n, full_hp = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(m)]

    start = None
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 3:
                start = (i, j)
                break
        if start is not None:
            break

    sx, sy = start
    queue = deque([(sx, sy, full_hp, 0)])
    seen = {(sx, sy, full_hp)}
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

    while queue:
        x, y, hp, steps = queue.popleft()
        if grid[x][y] == 4:
            print(steps)
            return

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < m and 0 <= ny < n):
                continue
            cell = grid[nx][ny]
            if cell == 1:
                continue

            next_hp = hp
            if cell == 2:
                next_hp -= 1
            elif cell == 5:
                next_hp = full_hp

            if next_hp <= 0:
                continue
            state = (nx, ny, next_hp)
            if state not in seen:
                seen.add(state)
                queue.append((nx, ny, next_hp, steps + 1))

    print(-1)


if __name__ == "__main__":
    solve()

复杂度分析

最多有 m × n × k 个状态。

时间复杂度：$O(mnk)$；
空间复杂度：$O(mnk)$。

易错点

不能只用二维坐标判重。
生命值降到 0 的状态不能进入队列。
药水恢复的是初始生命值上限，而不是增加固定数值。

第 2 题：网络数据流的有效传输段分析

题目描述

给定由大小写字母和数字组成的数据流字符串：

大写字母 A-Z 是同步字符；
小写字母 a-z 是干扰字符；
其他字符既不是同步字符，也不增加干扰度。

一个有效传输段是连续子串，必须以同步字符开头并以同步字符结尾。其干扰度为子串内小写字母的数量。

给定目标干扰度 limit，求干扰度恰好为 limit 的最长有效传输段长度；不存在时输出 0。

输入描述

第一行输入整数 limit，第二行输入数据流字符串。

样例

输入

1
X1bYYbY12

输出

长度为 5 的子串 X1bYY 以大写字母开头和结尾，且恰好包含一个小写字母。

思路分析

扫描到下标 j 时，令 count 表示此前已经出现的小写字母数量。因为合法右端点 j 自身是大写字母，所以以大写字母下标 i 开始、在 j 结束的子串，其小写字母数量为：

\[count_j-count_i.\]

要使该值等于 limit，只需找到此前满足

\[count_i=count_j-limit\]

的大写字母位置。为了使子串最长，对每个前缀计数只保留最早的大写字母下标。

遇到大写字母时必须先查询、后登记。否则当 limit = 0 时，当前位置会和自己配对，错误地得到长度为 1 的“传输段”。

题解代码

import sys


def solve():
    input = sys.stdin.buffer.readline
    limit_line = input()
    if not limit_line:
        print(0)
        return

    limit = int(limit_line)
    line = input()
    stream = line.decode().strip() if line else ""

    first = {}
    lowercase_count = 0
    answer = 0

    for index, char in enumerate(stream):
        if "A" <= char <= "Z":
            target = lowercase_count - limit
            if target in first:
                answer = max(answer, index - first[target] + 1)

            # 先查后登记，保证左右端点是两个不同位置。
            if lowercase_count not in first:
                first[lowercase_count] = index
        elif "a" <= char <= "z":
            lowercase_count += 1

    print(answer)


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度：$O(n)$；
空间复杂度：$O(n)$。

易错点

数字不增加干扰度，但可以出现在有效传输段内部。
两个端点都必须是大写字母。
更新最早位置时不能覆盖已有下标。
查询必须发生在登记当前大写字母之前。

第 3 题：流量均衡控制

题目描述

一组消息的权重构成数组，权重只可能是 5、10、15、20。需要把全部消息划分给两个端口，每条消息恰好属于一个端口，且两个端口都至少得到一条消息。

判断能否使两个端口收到的消息权重均值相同：

无法划分时输出 0；
可以划分时第一行输出 1，第二行输出两组元素和中较小的一个。

输入为一行以空格分隔的消息权重。

样例

输入

15 20 5 20

输出

1
15

可以划分为 [15] 和 [20, 5, 20]，两组均值都是 15，较小组的元素和为 15。

思路分析

设数组总和为 $S$、元素个数为 $n$。某一组选择了 $k$ 个元素，元素和为 $s$；另一组则有 $n-k$ 个元素，元素和为 $S-s$。

两组均值相等意味着：

\[\frac{s}{k}=\frac{S-s}{n-k}.\]

交叉相乘并化简：

\[sn=Sk,\]

即某组均值必须等于全局均值 $S/n$。因此，只需判断能否恰好选出 k 个元素，使其和为 S × k / n。

状态 dp[k][s] 表示能否恰好选择 k 条消息，且权重和为 s。逐个加入元素，并让 k 和 s 倒序枚举，保证每个元素只使用一次。

不能只做普通子集和：相同的元素和可能由不同数量的元素组成，而均值同时依赖元素和与元素个数。

题解代码

import sys


def solve():
    values = list(map(int, sys.stdin.buffer.read().split()))
    n = len(values)
    if n < 2:
        print(0)
        return

    total = sum(values)
    # dp[k] 用一个整数位集表示可达的元素和：第 s 位为 1 表示和 s 可达。
    dp = [0] * (n + 1)
    dp[0] = 1  # 只包含和为 0 的状态。

    used = 0
    for value in values:
        for count in range(used, -1, -1):
            dp[count + 1] |= dp[count] << value
        used += 1

    # 只枚举到 n // 2，即可直接得到两组中元素和较小的一组。
    for count in range(1, n // 2 + 1):
        numerator = total * count
        if numerator % n != 0:
            continue
        target = numerator // n
        if (dp[count] >> target) & 1:
            print(1)
            print(target)
            return

    print(0)


if __name__ == "__main__":
    solve()

复杂度分析

设总权重为 $S$。使用普通二维布尔数组时：

时间复杂度：$O(n^2S)$；
空间复杂度：$O(nS)$。

代码使用 Python 整数位集并行维护和的可达性，实际速度通常明显优于逐格更新；其逻辑状态数仍为 $O(nS)$。

易错点

两个分组都必须非空。
S × k 不能被 n 整除时，该组大小无需检查。
背包必须保留选取个数维度。
为得到较小组和，只需检查 k <= n // 2；两组均值相同且权重为正时，元素较少的一组元素和不会更大。

这篇文章有帮助吗？

| GitHub 留言