大厂真题 / 华为
华为 7.15 笔试真题 - 研发岗（非AI方向）
本场考试概述
考试时间：2026年7月15日 考试岗位：研发岗（通软、嵌软、测试、普通算法、数据科学等非AI方向） 难度评级：中等
考点分析：
- 第一题：前后缀最大值 / 双指针（难度简单）
- 第二题：回溯枚举 + 位掩码 + 上界剪枝（难度中等）
- 第三题：最长公共子序列 + 滚动数组（难度中等）
建议策略：
- 第一题先分清“槽位水面高度”和经典柱状图接雨水的区别，确认模型后线性扫描即可
- 第二题的数据范围只有 $N \leq 25$、$K \leq 8$，适合枚举组合；用位掩码快速判断频段重复与冲突，再用乐观上界剪枝
- 第三题先把“最少插入”转化为“最多复用”，随后套用 LCS；Python 使用一维滚动数组控制内存
第 1 题：水槽存水
题目描述
一条直线水槽中从左到右插入了 $n$ 块厚度忽略不计的竖直挡板，第 $i$ 块挡板高度为 $h_i$。左右两端始终开口，相邻挡板之间形成一个槽位，共有 $n-1$ 个槽位；每个槽位底面积为 $1$，雨水充足直到水面稳定。
对任意槽位，它左侧所有挡板中的最高值记为 $L$，右侧所有挡板中的最高值记为 $R$。水面超过较矮的一侧就会流出，因此该槽位的水面高度为 $\min(L,R)$，数值也就是存水量。求所有槽位的总存水量。
输入第一行是挡板数量 $n$（$1 \leq n \leq 30000$），第二行是 $n$ 个挡板高度（$1 \leq h_i \leq 30000$）。若只有一块挡板，则没有槽位，答案为 $0$。
样例
输入
5
1 2 3 4 5
输出
10
思路分析
第一步：明确水量的含义
这道题与经典“柱状图接雨水”不同。挡板之间的槽位没有一根需要扣除的柱子，槽底面积又是 $1$，所以槽位存水量就是绝对水面高度，而不是“水面高度减当前位置柱高”。
第二步：确定单个槽位的水面
槽位左侧的最高挡板限制水从左端流出，右侧的最高挡板限制水从右端流出。两侧中较矮的一侧决定最终水面，因此槽位 $i$ 的水量为：
\[\min\left(\max(h_0,\ldots,h_i),\ \max(h_{i+1},\ldots,h_{n-1})\right)\]直接预处理前缀最大值和后缀最大值可以做到 $O(n)$ 时间、$O(n)$ 空间。还可以进一步用双指针把额外空间降到 $O(1)$。
第三步：双指针为什么成立
维护左右指针及已经扫描部分的最高挡板 left_max、right_max：
- 当
left_max <= right_max时，右侧至少已有一块不低于left_max的挡板，因此左侧当前槽位的水面一定是left_max - 否则，左侧至少已有一块不低于
right_max的挡板，右侧当前槽位的水面一定是right_max
每轮确定一个尚未计算的槽位，一共恰好处理 $n-1$ 个槽位。
题解代码
import sys
input = sys.stdin.readline
def solve():
n = int(input())
heights = list(map(int, input().split()))
if n < 2:
print(0)
return
left, right = 0, n - 1
left_max, right_max = heights[left], heights[right]
total = 0
while left < right:
if left_max <= right_max:
total += left_max
left += 1
left_max = max(left_max, heights[left])
else:
total += right_max
right -= 1
right_max = max(right_max, heights[right])
print(total)
solve()
复杂度分析
时间复杂度：$O(n)$，每个指针最多移动 $n-1$ 次。
空间复杂度：$O(1)$，除输入数组外只使用常数个变量。
第 2 题：手机多载波冲突选择
题目描述
基站有 $N$ 个候选载波，第 $i$ 个载波提供带宽 $b_i$，并属于某个频段。需要选择至多 $K$ 个载波，使总带宽最大，同时满足：
- 同一频段最多选择一个载波
- 给定的冲突频段不能同时出现，冲突关系不传递
- 选择数量不能超过 $K$
频段名称不区分大小写。输出最大总带宽，并在第二行输出所选载波的下标；下标从 $0$ 开始、按升序排列。若有多个最优组合，输出数值序最小的一组。
数据范围：$1 \leq N \leq 25$，$1 \leq K \leq 8$，$K \leq N$，$1 \leq b_i \leq 1000$；频段名以 n 开头、长度不超过 $10$；冲突对数量 $0 \leq C \leq 25$。
样例
输入
6 2
100 200 150 300 250 180
n78 n41 n78 n28 n41 n28
1
n28 n41
输出
450
2 3
思路分析
第一步：从数据范围判断算法
$N$ 最大为 $25$，直接枚举全部 $2^N$ 个子集偏大；但最多只选 $K \leq 8$ 个，大小不超过 $K$ 的组合总数仍在可控范围内。因此可以按载波编号递增做回溯，只生成合法组合。
第二步：用位掩码检查频段约束
先把频段名统一转为小写并映射为整数编号。用整数 used_bands 的第 $g$ 位表示频段 $g$ 是否已被选择，再用 conflict_mask[g] 记录所有与 $g$ 冲突的频段。
尝试载波 $i$ 时只需检查：
used_bands & (1 << g)是否非零，判断同一频段是否已选conflict_mask[g] & used_bands是否非零，判断是否与已选频段冲突
两次位运算就能决定该载波能否加入。
第三步：构造可证明安全的上界
仅有回溯已经可以通过大部分数据，但还可以预处理 upper[i][r]：忽略所有频段约束，从后缀 $i\ldots N-1$ 中至多选择 $r$ 个载波能获得的最大带宽。
这个值只会高估当前分支真正能获得的收益。如果“当前带宽 + 乐观上界”仍小于全局最优值，该分支不可能翻盘，可以立即停止。等于最优值时不能剪枝，因为仍可能出现数值序更小的并列方案。
第四步：显式处理并列规则
回溯始终按编号递增，当前选择自然有序。每到一个状态都比较：总带宽更大则更新；总带宽相同则直接用列表字典序比较，保留数值序更小的组合。这样无需依赖遍历顺序的隐含性质。
题解代码
import sys
input = sys.stdin.buffer.readline
def solve():
n, k = map(int, input().split())
bandwidth = list(map(int, input().split()))
band_names = [name.lower() for name in input().split()]
band_id = {}
for name in band_names:
if name not in band_id:
band_id[name] = len(band_id)
band_of = [band_id[name] for name in band_names]
conflict_mask = [0] * len(band_id)
conflict_count = int(input())
for _ in range(conflict_count):
first, second = (name.lower() for name in input().split())
if first not in band_id or second not in band_id:
continue
a, b = band_id[first], band_id[second]
conflict_mask[a] |= 1 << b
conflict_mask[b] |= 1 << a
# upper[i][r]: 忽略约束时，从后缀 i 开始至多选 r 个的最大带宽
upper = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
for r in range(1, k + 1):
upper[i][r] = max(
upper[i + 1][r],
bandwidth[i] + upper[i + 1][r - 1],
)
best_sum = -1
best_pick = None
current = []
def dfs(start, total, used_bands):
nonlocal best_sum, best_pick
if total > best_sum or (
total == best_sum and (best_pick is None or current < best_pick)
):
best_sum = total
best_pick = current.copy()
if len(current) == k:
return
remaining = k - len(current)
if total + upper[start][remaining] < best_sum:
return
for i in range(start, n):
group = band_of[i]
bit = 1 << group
if used_bands & bit:
continue
if conflict_mask[group] & used_bands:
continue
current.append(i)
dfs(i + 1, total + bandwidth[i], used_bands | bit)
current.pop()
dfs(0, 0, 0)
print(best_sum)
print(*best_pick)
solve()
复杂度分析
时间复杂度：最坏为 $O\left(K\sum_{r=0}^{K}\binom{N}{r}\right)$，剪枝会减少实际搜索量；上界预处理为 $O(NK)$。
空间复杂度：$O(NK + G + K)$，其中 $G$ 为不同频段数量；分别用于上界表、冲突掩码和递归路径。
第 3 题：字符补全
题目描述
给定目标字符串 $T$ 和源字符串 $S$，只能在 $S$ 的任意位置插入字符，不能删除或修改已有字符。求最少插入多少个字符，才能使 $T$ 成为插入后字符串的子序列。
没有参与匹配的 $S$ 中原字符可以继续保留，判断子序列时会跳过它们。插入的字符必须来自 $T$。两串只包含小写字母，且 $1 \leq \lvert S\rvert,\lvert T\rvert \leq 2500$。
输入第一行是目标字符串 $T$，第二行是源字符串 $S$。
样例
输入
aaab
ab
输出
2
思路分析
第一步：把“最少插入”换成“最多复用”
目标串 $T$ 的每个字符有两种来源：复用 $S$ 中一个相同字符，或者新插入一个字符。如果能复用 $x$ 个字符，需要插入的数量就是 $\lvert T\rvert-x$，因此目标变成让 $x$ 尽量大。
第二步：识别最长公共子序列
被复用的字符必须同时保持它们在 $T$ 和 $S$ 中的相对顺序，所以它们构成两串的一个公共子序列；反过来，任意公共子序列都可以作为复用方案，其余目标字符依次插入即可。
因此最多能复用的字符数恰好是 $\operatorname{LCS}(T,S)$，答案为：
\[\lvert T\rvert - \operatorname{LCS}(T,S)\]第三步：用滚动数组降低内存
经典 LCS 二维 DP 需要 $O(\lvert T\rvert \cdot \lvert S\rvert)$ 个整数，在 Python 中内存开销较大。每一行只依赖上一行与本行左侧，可以用一维数组 dp 滚动更新。
遍历当前字符时，previous_diagonal 保存更新前的左上角状态：字符相同就在左上角基础上加 $1$；字符不同则取“上一行同列”和“本行左侧”的较大值。把较短字符串放在列方向，空间降为 $O(\min(\lvert T\rvert,\lvert S\rvert))$。
题解代码
import sys
input = sys.stdin.buffer.readline
def solve():
target = input().strip()
source = input().strip()
target_length = len(target)
rows, columns = target, source
if len(columns) > len(rows):
rows, columns = columns, rows
dp = [0] * (len(columns) + 1)
for row_char in rows:
previous_diagonal = 0
for j, column_char in enumerate(columns, 1):
old_value = dp[j]
if row_char == column_char:
dp[j] = previous_diagonal + 1
elif dp[j - 1] > dp[j]:
dp[j] = dp[j - 1]
previous_diagonal = old_value
print(target_length - dp[-1])
solve()
复杂度分析
时间复杂度：$O(\lvert T\rvert \cdot \lvert S\rvert)$。
空间复杂度：$O(\min(\lvert T\rvert,\lvert S\rvert))$。
小结
- 第一题的关键是建立正确模型：槽位存水量等于两侧最高挡板中较矮者，而不是经典接雨水公式；双指针可以在线性时间、常数额外空间内求和
- 第二题利用 $K \leq 8$ 做组合回溯，用频段位掩码把合法性检查降为常数时间，再用后缀乐观上界剪枝并显式处理并列方案
- 第三题把最少插入转化为最多复用，核心就是 LCS；一维滚动数组能避免 Python 二维整数表的高内存开销