大厂真题 / 华为

华为 6.12 笔试真题 - 研发岗（非AI方向）

本场考试概述

考试时间：2026年6月12日 考试岗位：研发岗（通软、嵌软、测试、普通算法、数据科学等非AI方向） 难度评级：中等

考点分析：

第一题：循环异或加密器——字符串模拟 + 位运算（难度简单）
第二题：容器镜像平均大小统计——前序中序重建二叉树 + 路径和剪枝（难度中等）
第三题：楼内救人——双层网格 BFS 最短路（难度中等）

建议策略：

第一题是送分题，用下标对 key 长度取模就能同时处理”循环使用”和”截断”，先稳稳拿下
第二题是二叉树重建模板题，难点在于一边还原一边递推完整大小、并对非正子树整体剪枝，注意累加和要用 64 位整数
第三题把每个格子建模成”楼层 + 行 + 列”三维状态，楼梯作为唯一的跨层边，套 BFS 即可

第 1 题：循环异或加密器

题目描述

给定一个十六进制密钥 key 和一个十六进制数据 data，实现循环异或操作。将 key 和 data 的每个十六进制字符转换为 4 位二进制数值，对 data 的每一位与 key 的对应位进行异或。对齐方式为从左向右对齐：当 key 长度小于 data 时循环使用 key；当 key 长度大于 data 时截断多余部分。

输入 $T$ 组数据，每组一对 key 和 data，输出异或后的十六进制大写字符串。

样例

输入

2
AB 12345
FF A5

输出

B99FF
5A

思路分析

第一步：观察题目性质

两个十六进制字符逐位异或等价于将它们各自转换为 0~15 的数值后直接做整数异或运算，因为异或是按比特操作的，4 位二进制恰好对应一个十六进制字符。

第二步：处理循环和截断

data 的第 $i$ 个字符固定与 key 的第 $i \mod \text{len(key)}$ 个字符异或。取模运算天然实现了 key 不足时循环、超长时截断两种情形，无需显式拼接或裁剪 key。

第三步：实现

Python 内置 int(ch, 16) 将十六进制字符转数值，异或后用 f"{v:X}" 转回大写十六进制字符。

题解代码

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    key, data = input().split()
    klen = len(key)
    res = []
    for i, ch in enumerate(data):
        dv = int(ch, 16) ^ int(key[i % klen], 16)
        res.append(f"{dv:X}")
    print("".join(res))

复杂度分析

时间复杂度：$O(\sum L)$，$L$ 为每组 data 的长度

空间复杂度：$O(L)$

第 2 题：容器镜像平均大小统计

题目描述

容器镜像层采用二叉树管理，节点值表示镜像层大小，节点的镜像完整大小为自身层大小与所有父镜像层大小之和（即根到该节点的路径和）。输入为容器镜像二叉树的前序遍历数组和中序遍历数组，各节点值互不相同。

当镜像完整大小 $\leq 0$ 时，该节点异常，需要连同其整棵子树一并剪枝。输出剩余存活节点的平均镜像完整大小（向下取整）。当结果为空树时输出 $0$。

样例

输入

1 2 3 -5 6
2 1 3 -5 6

输出

思路分析

第一步：前序 + 中序重建二叉树

前序遍历的首元素是当前子树的根；在中序遍历中定位这个根，其左侧为左子树、右侧为右子树。对左右两段递归套用同一规则即可唯一还原整棵树。

为避免树退化成链时递归过深（栈溢出），使用迭代写法：顺序扫描前序序列，用栈维护当前尚未接上右孩子的祖先链，中序指针标记下一个待回溯的节点。

第二步：路径和计算与剪枝

从根做 DFS，向下传递路径和。节点 $u$ 的完整大小 $S(u) = S(\text{父}) + \text{val}(u)$。一旦 $S(u) \leq 0$，立即跳过（等价于删除整棵子树，因为子树中任一节点都以 $u$ 为必经祖先）。

第三步：统计结果

遍历中累计存活节点的完整大小之和 total 与数量 count。空树输出 $0$，否则输出 $\lfloor \text{total} / \text{count} \rfloor$。存活节点的完整大小恒为正数，整除即向下取整。

题解代码

import sys
input = sys.stdin.readline

pre = list(map(int, input().split()))
ino = list(map(int, input().split()))
n = len(pre)
if n == 0:
    print(0)
    sys.exit()

lc = [-1] * n
rc = [-1] * n

stack = [0]
ii = 0
for k in range(1, n):
    if pre[stack[-1]] != ino[ii]:
        lc[stack[-1]] = k
    else:
        last = stack[-1]
        while stack and pre[stack[-1]] == ino[ii]:
            last = stack.pop()
            ii += 1
        rc[last] = k
    stack.append(k)

total = 0
count = 0
stk = [(0, 0)]
while stk:
    node, parent_sum = stk.pop()
    full_size = parent_sum + pre[node]
    if full_size <= 0:
        continue
    count += 1
    total += full_size
    if lc[node] != -1:
        stk.append((lc[node], full_size))
    if rc[node] != -1:
        stk.append((rc[node], full_size))

print(0 if count == 0 else total // count)

复杂度分析

时间复杂度：$O(n)$，重建和遍历各扫一遍

空间复杂度：$O(n)$，存储左右孩子数组和栈

第 3 题：楼内救人

题目描述

游戏地图是一个 $m \times n \times 2$ 的双层楼地图，每个格子代表一个区域：$0$ 是空地（可通行），$1$ 是墙壁（不可通行），$2$ 是起点（有且仅一个），$3$ 是终点（有且仅一个），$4$ 是楼梯（每层有且仅一个）。

玩家从起点出发，每次只能上下左右移动一格，不能穿过墙壁。通过楼梯跨层算 $1$ 步，除楼梯外无法跨层移动。求从起点到终点的最短路径长度（步数），无法到达返回 $-1$。

样例

输入

输出

思路分析

第一步：建模为图论问题

把每个可通行格子看作一个节点，用三元组 $(\text{层}, \text{行}, \text{列})$ 标识。同层四邻接各连一条权为 $1$ 的边；每层有且仅有一个楼梯，两层楼梯之间连一条权为 $1$ 的跨层边。

第二步：为什么用 BFS

所有边权都等于 $1$，BFS 按距离逐层扩展，节点首次出队时记录的距离即为最短距离，无需 Dijkstra。

第三步：实现要点

用三维数组 dist[层][行][列] 记录步数，初值 $-1$ 同时充当未访问标记
节点出队后向四个方向扩展，目标格需在界内、非墙壁、未访问
仅当出队节点本身是楼梯（值为 $4$）时，才允许花 $1$ 步跳至另一层楼梯所在格
BFS 首次取出终点格时其 dist 即最短步数；队列耗尽仍未取出终点则输出 $-1$

题解代码

import sys
from collections import deque
input = sys.stdin.readline

m, n = map(int, input().split())
g = [[[0] * n for _ in range(m)] for _ in range(2)]
for l in range(2):
    for r in range(m):
        row = list(map(int, input().split()))
        for c in range(n):
            g[l][r][c] = row[c]

sl = sr = sc = 0
stair = [[0, 0], [0, 0]]
for l in range(2):
    for r in range(m):
        for c in range(n):
            if g[l][r][c] == 2:
                sl, sr, sc = l, r, c
            elif g[l][r][c] == 4:
                stair[l] = [r, c]

dist = [[[-1] * n for _ in range(m)] for _ in range(2)]
dist[sl][sr][sc] = 0
q = deque()
q.append((sl, sr, sc))
ans = -1
dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]

while q:
    l, r, c = q.popleft()
    d = dist[l][r][c]
    if g[l][r][c] == 3:
        ans = d
        break
    for k in range(4):
        nr, nc = r + dr[k], c + dc[k]
        if 0 <= nr < m and 0 <= nc < n and g[l][nr][nc] != 1 and dist[l][nr][nc] == -1:
            dist[l][nr][nc] = d + 1
            q.append((l, nr, nc))
    if g[l][r][c] == 4:
        ol = 1 - l
        tr, tc = stair[ol]
        if dist[ol][tr][tc] == -1:
            dist[ol][tr][tc] = d + 1
            q.append((ol, tr, tc))

print(ans)

复杂度分析

时间复杂度：$O(m \cdot n)$，每个状态至多入队出队各一次

空间复杂度：$O(m \cdot n)$，三维距离数组

小结

第一题是纯模拟，取模运算一招搞定循环和截断
第二题结合了经典的前序+中序重建二叉树与路径和计算，剪枝条件是”完整大小 $\leq 0$ 则连同子树删除”
第三题是 BFS 最短路的变体，关键建模思路是把楼梯看作跨层边，三维状态空间确保每个位置只访问一次

这篇文章有帮助吗？

| GitHub 留言