大厂真题 / 华为
华为 2026-10-14 笔试真题 - 研发岗
本场考试概述
考试时间：2026年10月14日
考试岗位：研发岗
难度评级：中等
考点分析：
- 第一题：规则模拟，严格区分低价与同价、成交与后续涨价。
- 第二题：单调栈校验并还原二叉搜索树，BFS 求右视图。
- 第三题：位掩码、最少候选格优先搜索，判断数独是否恰有一个解。
建议策略：第二题应直接选用迭代线性算法，避免链状树上的递归退化。第一题先逐条落实交易规则，再考虑扫描常数；第三题找到一个解还不能结束，必须继续排除第二个解。
第 1 题：股票交易订单匹配
题目描述
给定卖方订单列表和买方订单列表，每张订单由价格、数量组成。卖方列表的输入顺序表示时间优先级，买方也严格按输入顺序处理。
每轮交易遵循以下规则：
- 在仍有余量、且当前价格不高于该买方购买价格的卖方中，选出价差最小的订单，即当前价格最高的订单。同价时选择输入最早的卖方。
- 按双方剩余数量的最小值成交，成交价格为选中卖方的当前价格。
- 这一轮成交后，仍有余量、且价格严格低于本轮成交价格的落选卖方，分别涨价 $x$ 元。同价落选卖方不涨，选中订单的剩余部分也不涨。
- 买方还有余量时，在更新后的价格上重新匹配；没有买得起的卖方则结束该买方，继续下一个买方。买方刚好买满时，本轮的涨价仍须执行。
求所有成功交易的“成交价格乘成交数量”之和。题目将它称为“最终成交量”，但实际要求的是成交金额，不是成交件数。
输入格式：
- 第一行是涨价幅度 $x$，$0\le x\le10^9$。
- 第二行是卖方数量 $n$，$0\le n\le10^4$；随后 $n$ 行为卖方的价格和数量。
- 接着一行是买方数量 $m$，$0\le m\le10^4$；随后 $m$ 行为买方的价格和数量。
- 输入的价格和数量均在 $[1,10^9]$ 内。
输出格式：一个整数，表示总成交金额。
样例 1
输入
8
3
10 1
10 1
3 1
1
20 5
输出
39
解释：先以 10 元成交最早的卖方，同价的第二个卖方不涨，3 元的卖方涨到 11。第二轮应选 11 元的卖方，而不是原来的第二个 10 元卖方；后者这次涨到 18。最后以 18 元成交，总额为 $10+11+18=39$。
样例 2
输入
1
4
8 3
12 2
18 1
25 1
3
10 2
20 1
15 3
输出
70
解释：四次成交分别是 8×2、18×1、13×2、10×1，总额为 $16+18+26+10=70$。第二个买方买满之后，低价卖方仍须涨价，影响第三个买方的匹配结果。
样例 3
输入
1
4
16 4
17 3
18 2
19 1
3
20 11
17 5
18 3
输出
190
解释：第一个买方依次买走数量 1、2、3、4 的订单，经过涨价后，四次成交价都是 19。所有卖方都耗尽，总金额为 $19\cdot(1+2+3+4)=190$。
思路分析
第一步：把价差优先改写为最大价格。 对固定买价 $b$，最小化 $b-p_i$ 等价于最大化 $p_i$。扫描卖方时仅在发现严格更高的可成交价格时更新最优下标，便能自然保留同价时最早的订单。
第二步：每轮重新判断，而不是预先排序后一路取出。 涨价会使低价订单越过原本更贵的订单。样例一中 3 涨到 11 就改变了下一轮的选择。每轮必须使用当前价格，不能沿用初始顺序中的价格排名。
设本轮成交价为 $p$，成交数量为 $t=\min(q,rest_k)$。金额增加 $p\cdot t$，双方余量减少 $t$。随后只对仍有余量且当前价格小于 $p$ 的卖方加上 $x$。涨价判断使用本轮已经保存的成交价，不能使用下一轮最高价。
第三步：把收尾和下一轮选单合成一次扫描。 对仍在场的卖方按原顺序扫描：先移除耗尽的订单，再按严格小于成交价的条件涨价，最后在买方尚未买满时顺带寻找下一轮最优卖方。用读写指针原地压缩两个数组，避免另建列表；保留下来的订单仍保持原时间顺序。
第四步：给模拟轮数建立上界。 每次成功交易至少耗尽一张买方或卖方订单，所以成功交易次数至多 $n+m$。没有候选卖方时直接结束当前买方，不会陷入空转。涨价和数量无关：同一轮只涨一次，不是每成交一件就涨一次。
正确性说明：初次扫描根据价格和时间优先级选出正确卖方。一次交易准确扣减双方余量并累加金额；收尾扫描恰好移除耗尽订单、更新所有严格低价订单，且不改变剩余订单的时间顺序。顺带得到的下一轮候选因此与再次完整扫描相同。逐轮保持这些性质，直到所有买方处理完，累加值即题目要求的金额。
Python 性能说明：下面使用纯标准库，便于直接在 ACM IDE 运行，且将收尾合并为一趟扫描。但该模拟的最坏扫描量仍为 $O(n(n+m))$，当两类订单都达到 $10^4$ 时，Python 的解释器循环可能成为瓶颈。题面没有给出时间限制，不能仅凭样例通过就保证最大数据在任意评测时限内通过；若评测环境支持向量化库，可另做批量扫描优化，但不能默认环境已经安装 NumPy。
题解代码
import sys
def match_orders(increment, sellers, buyers):
prices = [price for price, quantity in sellers]
remaining = [quantity for price, quantity in sellers]
count = len(prices)
total = 0
for buy_price, need in buyers:
best = -1
best_price = -1
for i in range(count):
price = prices[i]
if best_price < price <= buy_price:
best = i
best_price = price
while best != -1:
trade_price = prices[best]
amount = min(need, remaining[best])
total += trade_price * amount
need -= amount
remaining[best] -= amount
next_best = -1
next_price = -1
write = 0
for i in range(count):
quantity = remaining[i]
if quantity == 0:
continue
price = prices[i]
if price < trade_price:
price += increment
prices[write] = price
remaining[write] = quantity
if need > 0 and next_price < price <= buy_price:
next_best = write
next_price = price
write += 1
count = write
best = next_best
return total
def solve():
values = iter(map(int, sys.stdin.read().split()))
increment = next(values)
n = next(values)
sellers = [(next(values), next(values)) for _ in range(n)]
m = next(values)
buyers = [(next(values), next(values)) for _ in range(m)]
print(match_orders(increment, sellers, buyers))
if __name__ == "__main__":
solve()
复杂度分析
时间复杂度：$O(n+m+n(n+m))$。每个买方有一次初选扫描，每次成功交易有一次收尾扫描，成功交易至多 $n+m$ 次，每次扫描至多 $n$ 个卖方；输入读取为 $O(n+m)$。在 $n=0$ 时仍须读取买方输入。
空间复杂度：$O(n+m)$，包括输入、订单列表和当前价格、剩余数量数组。
整数边界：卖方只有在价格低于某次成交价时才涨价，因此当前价格始终小于 $2\cdot10^9$。但总金额可能超过有符号 64 位范围：当 $x=0$、有 $10^4$ 张价格和数量均为 $10^9$ 的匹配订单时，金额可达 $10^{22}$。Python 整数自动扩展，不会溢出；其他语言不能仅凭单笔金额小于 $10^{18}$ 就断言总金额可用有符号 64 位保存。
第 2 题：星际通讯塔的信号校验
题目描述
收到一个信号强度序列，各值为正整数且互不相同。它应是一棵二叉搜索树（BST）的后序遍历，即按照“左子树、右子树、根”的顺序输出节点。
判断序列是否能还原为合法 BST。如果合法，输出这棵树的右侧天际线节点值之和：从树右侧观察，每层看到的最右侧节点各贡献一次；如果不合法，输出 -1。
输入格式：一个空格分隔的整数序列，没有额外的长度字段。序列长度 $1\le N\le10000$，每个值在 $[1,10^9]$ 内，无重复。
输出格式：合法时输出右视图节点值之和，否则输出 -1。题目要求重建时间控制为 $O(N)$。
样例 1
输入
2 4 3 6 8 7 5
输出
20
解释：根为 5，左右孩子为 3、7，再下一层从左到右为 2、4、6、8。右视图是 5、7、8，和为 20。
样例 2
输入
4 6 2 5
输出
-1
解释：根为 5。末尾的 2 必须属于左子树，但在它之前出现的 6 又大于 5，无法符合“左、右、根”的连续分段要求。
样例 3
输入
10 20 30
输出
60
解释：这是一条根为 30、依次向左连接 20、10 的链。右视图并不等于沿着右孩子一直走：每层只有一个节点时，左孩子也在右视图中，故和为 60。
思路分析
第一步：反向读取后序。 后序反过来是“根、右、左”，父节点先于孩子出现，适合在线建树。递归寻找左右分界会在链状树上退化成 $O(N^2)$，并带来深度为 $N$ 的递归栈，因此改用迭代单调栈。
第二步：栈决定新节点挂在哪里。 栈中保存尚未完成左侧处理的祖先边界，节点值从栈底到栈顶严格递增。当前值 $v$ 大于栈顶时，挂为栈顶节点的右孩子。若 $v$ 小于栈顶，则弹出所有值大于 $v$ 的节点，最后弹出的节点就是新节点的父节点，把 $v$ 挂为它的左孩子。这里的栈是压缩后的祖先边界，不要求相邻栈元素始终互为直接父子。
第三步：维护进入左子树后的上界。 一旦开始处理某个节点的左子树，之后的值就必须小于该节点值。每次弹栈时将 upper 更新为被弹出的值；最后一次弹栈留下的值最小，是最新的有效上界。如果发现 $v\ge upper$，立即判为非法。题目保证无重复，写成严格上界能直接表达 BST 的要求。
以样例二为例，反向序列为 5、2、6、4。2 使根 5 弹栈并开始其左子树，upper 变为 5；随后 6 超过上界，输出 -1。
第四步：层序遍历取每层最后一个节点。 建好左右孩子数组后，队列按先左后右的顺序入队。每层预先记录队列长度，处理完这一层时最后出队的值就是本层右视图节点。
正确性说明：反向后序先处理右子树再处理左子树，弹栈恰好标记由右侧处理转入某个祖先的左侧处理。单调栈保证当前值满足尚保留的右侧边界，上界保证它满足已经进入的左子树边界；因此未被拒绝的节点都有正确的 BST 位置，得到的树也具有输入所指定的后序遍历。先左后右的 BFS 则保证每层最后访问的节点恰为最右侧节点。
题解代码
import sys
from collections import deque
def right_view_sum(values):
n = len(values)
left = [-1] * n
right = [-1] * n
stack = []
upper = float("inf")
for i in range(n - 1, -1, -1):
value = values[i]
if value >= upper:
return -1
parent = -1
while stack and value < values[stack[-1]]:
parent = stack.pop()
upper = values[parent]
if parent != -1:
left[parent] = i
elif stack:
right[stack[-1]] = i
stack.append(i)
queue = deque([n - 1])
total = 0
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if left[node] != -1:
queue.append(left[node])
if right[node] != -1:
queue.append(right[node])
total += values[node]
return total
def solve():
values = list(map(int, sys.stdin.read().split()))
print(right_view_sum(values))
if __name__ == "__main__":
solve()
复杂度分析
时间复杂度：$O(N)$。每个节点入栈一次、至多出栈一次，BFS 也仅访问每个节点一次。
空间复杂度：$O(N)$，包括输入、左右孩子数组、单调栈与队列。没有递归，因此链状树不会导致递归栈溢出。
第 3 题：超级数独游戏
题目描述
数独棋盘大小为 $n\times n$，其中 $n$ 取 4、9、16。棋盘由 $n$ 个小宫组成，每个小宫的边长为 $s=\sqrt n$，大小为 $s\times s$。
每个格子应填入 $1$ 到 $n$ 的数字，且每行、每列、每个小宫中均不能重复。输入中 0 表示空白，其他数字不可修改。
只有当棋盘恰好有一个解时才输出完整解；如果无解或者存在多个解，都输出 0。
输入格式：第一行是 $n$，随后 $n$ 行，每行 $n$ 个用空格分隔的整数，取值为 $0$ 到 $n$。第一行不是小宫边长，例如输入 9 表示 $9\times9$ 棋盘，其小宫边长是 3。
输出格式：唯一解时输出 $n$ 行，每行 $n$ 个数字，以空格分隔；否则输出一行 0。题面没有进一步给出空格数量或搜索时限限制。
样例 1
输入
4
1 2 3 4
0 3 1 0
0 0 0 1
0 0 0 0
输出
1 2 3 4
4 3 1 2
3 4 2 1
2 1 4 3
样例 2
输入
9
5 3 4 1 7 9 8 2 6
7 0 0 4 3 8 9 1 5
9 8 1 2 0 6 3 7 0
2 5 6 7 9 1 4 8 3
8 7 9 3 0 2 5 6 1
4 0 3 0 8 5 2 9 0
0 2 7 0 6 4 1 5 9
6 9 8 5 1 3 7 4 2
1 4 0 9 2 7 6 3 8
输出
5 3 4 1 7 9 8 2 6
7 6 2 4 3 8 9 1 5
9 8 1 2 5 6 3 7 4
2 5 6 7 9 1 4 8 3
8 7 9 3 4 2 5 6 1
4 1 3 6 8 5 2 9 7
3 2 7 8 6 4 1 5 9
6 9 8 5 1 3 7 4 2
1 4 5 9 2 7 6 3 8
思路分析
第一步：用位掩码表示已使用数字。 数字 $v$ 对应第 $v-1$ 位。rows[r]、cols[c]、boxes[b] 分别记录行、列、宫已经使用的数字。格子 $(r,c)$ 的宫编号为
full = (1 << n) - 1 的低 $n$ 位全部为 1。候选掩码在代码中计算为 full & ~(rows[r] | cols[c] | boxes[b])，即所有未被该行、列、宫使用的数字。与 full 做按位与也会截断 Python 按位取反产生的高位。
初始化时就检查给定数字。如果某数字在所在行、列或宫中已经出现，直接判无解，不能先把它们合并到掩码中再继续搜索。
第二步：优先填候选最少的空格。 固定按行搜索可能在约束很弱的格子上制造大量分支。每一步扫描尚未填的空格，计算候选数，选取最小者，称为 MRV 策略。若任意空格没有候选，当前分支立即失败；若只有一个候选，则没有选择分支。这里仍完成扫描以发现后面的零候选格，而不是看到一个候选就提前跳过潜在矛盾。
空格列表的前 depth 项是已经填过的格子，后半段是未填格子。选中位置与 depth 位置交换，递归结束后再交换回来，避免额外维护“是否填过”数组。
第三步：逐个尝试候选并严格恢复现场。 用 bit = mask & -mask 取最低有效位，bit.bit_length() 正好得到对应数字。填数时修改棋盘和三个掩码；返回时清空棋盘该格，并恢复三个掩码。由于候选位原本没有被使用，撤销时按位异或该位是安全的。
第四步：搜索到第二个解即可停止。 第一次填满时复制棋盘，保留一个解；第二次填满时即可证明不唯一，不再继续搜索。搜索彻底结束后，如果计数为 1，输出第一次保存的棋盘；计数为 0 或 2 都输出 0。保存时必须深拷贝每一行，否则后续回溯会改坏答案。
正确性说明：初始化拒绝所有给定数字冲突。每步候选恰为不与行、列、宫冲突的数字，逐个尝试不会遗漏任何合法扩展；MRV 只调整搜索顺序，并不删除合法方案。每次填满均为满足规则且保留给定数字的完整解。计数截断在 2 不影响“恰有一个解”的判断，故输出符合题意。
题解代码
import sys
from math import isqrt
def unique_sudoku(board):
n = len(board)
side = isqrt(n)
full = (1 << n) - 1
rows = [0] * n
cols = [0] * n
boxes = [0] * n
blanks = []
for r in range(n):
for c in range(n):
box = r // side * side + c // side
value = board[r][c]
if value == 0:
blanks.append((r, c, box))
continue
bit = 1 << (value - 1)
if (rows[r] | cols[c] | boxes[box]) & bit:
return None
rows[r] |= bit
cols[c] |= bit
boxes[box] |= bit
found = 0
answer = None
def search(depth):
nonlocal found, answer
if found >= 2:
return
if depth == len(blanks):
found += 1
if found == 1:
answer = [row[:] for row in board]
return
pick = depth
pick_mask = 0
pick_count = n + 1
for i in range(depth, len(blanks)):
r, c, box = blanks[i]
mask = full & ~(rows[r] | cols[c] | boxes[box])
count = mask.bit_count()
if count == 0:
return
if count < pick_count:
pick, pick_mask, pick_count = i, mask, count
blanks[depth], blanks[pick] = blanks[pick], blanks[depth]
r, c, box = blanks[depth]
mask = pick_mask
while mask and found < 2:
bit = mask & -mask
mask ^= bit
board[r][c] = bit.bit_length()
rows[r] |= bit
cols[c] |= bit
boxes[box] |= bit
search(depth + 1)
rows[r] ^= bit
cols[c] ^= bit
boxes[box] ^= bit
board[r][c] = 0
blanks[depth], blanks[pick] = blanks[pick], blanks[depth]
search(0)
return answer if found == 1 else None
def solve():
values = list(map(int, sys.stdin.read().split()))
n = values[0]
board = [values[1 + r * n:1 + (r + 1) * n] for r in range(n)]
answer = unique_sudoku(board)
if answer is None:
print(0)
else:
print("\n".join(" ".join(map(str, row)) for row in answer))
if __name__ == "__main__":
solve()
复杂度分析
时间复杂度：设初始空格数为 $K$，实际访问搜索节点数为 $S$，则为 $O(n^2+S(K+1))$。每个节点进行至多 $K$ 次候选检查；最坏搜索仍为指数级，对 $n\ge4$ 可给出宽松上界 $O(n^2+(K+1)n^K)$，不能将 MRV 剪枝视为多项式时间保证。
空间复杂度：$O(n^2+K)$，用于棋盘、保存的唯一解候选、空格列表、行列宫掩码和深度至多 $K$ 的递归栈。这里使用整数的 bit_count()，不需要大小为 $2^n$ 的计数表。题面最大 $K\le256$，无需提高默认递归上限。
小结
- 订单匹配的重点是规则精确：最高可成交价格、同价按时间优先、严格低价才涨价，以及买方买满后也必须完成涨价。
- BST 后序逆向读取，结合单调栈与上界即可线性校验、建树；右视图应逐层判断，不能只遍历右孩子链。
- 数独的位掩码缩短约束检查，MRV 减少分支，但判唯一必须继续搜索至第二个解或穷尽搜索空间。