大厂真题 / 华为
华为研发岗 2026-09-23
内容边界：概述列出 3 道编程题，原始正文实际披露 3 道，均含题意、约束和正式样例，逐题对应无缺项；未披露的额外考试内容不作推断。
本场考试概述
考试时间：2026-09-23
考试岗位：研发岗
难度评级：中等偏难
考点分析：字符串扫描、持剑状态 BFS、线段树与前后缀分解。
建议策略：先确认字符串题的注释与空白规则，再用持剑状态分层 BFS；第三题先推导单段收益，再处理双段严格不相交和字典序。
第 1 题：YANG 模型配置精简器
题目描述
读入整段 YANG 文本直到文件结束，删除以 description、default、mandatory 为关键字的语句，从关键字第一个字符删至有效结束分号 ;，但保留删除区间内的所有换行。关键字前的缩进不在删除区间内，必须保留。
- 行注释
//到行尾、块注释/* ... */（可跨行）必须原样保留。 - 关键字前必须是行首、空格、制表符、
{或;。 - 关键字后必须是空格、制表符、换行或双引号。
mydescription、description_ext不匹配。 - 输入保证语法基本合法，分号总是有效语句结束符；待删关键字语句内不会出现注释，引号内也不会再次出现关键字。不额外扩展为完整 YANG 语法解析器。
输入格式：长度 $1\le L\le2\times10^5$ 的字符串，读取至 EOF。
输出格式：清洗后的原字符串，保留行数、区间外空白与完整注释。样例空白行中的缩进也是输出的一部分，以下原样例保留这些空格。
样例 1
输入
container system {
leaf hostname {
type string;
description "Device hostname";
default "router";
}
/*
这是一段注释，里面有个假的 description "test";
不要删除它
*/
leaf mode {
type string;
description
"Multi-line
text";
mandatory true;
}
}输出
container system {
leaf hostname {
type string;
}
/*
这是一段注释，里面有个假的 description "test";
不要删除它
*/
leaf mode {
type string;
}
}样例 2
输入
leaf x {
description "x";
}输出
leaf x {
}思路分析
第一步：先保护注释。 直接用正则删除关键字到分号，会误删注释中的同名词。扫描到注释起点时，将整段注释原样复制，并直接跳到注释结尾，使其中的字符不参与关键字识别。
第二步：检查原文本中的两侧边界。 非注释位置才匹配三个关键字。前一字符与关键字结束后的字符必须满足题面边界；边界检查针对原输入，避免前一次删除创造新的匹配。
第三步：只删除非换行字符。 匹配成功后找该语句的分号，统计这一段的换行数，向结果追加同样数量的换行，再跳到分号后。其余字符逐个复制。指针永不回退，扫描过的区间不会再次处理。
正确性证明
保持不变式：每轮开始时，位置 $i$ 之前的输入已按规则处理。若是注释，整体复制正好满足保护规则；若是合法目标关键字，删除到分号并保留所有换行恰好执行删除规则；否则当前字符不属于任何应删除区间，原样复制正确。三类互斥且覆盖全部位置，终止时整个输出正确。
题面提示纠正：材料一处将“删除、保护注释、验证边界”列成执行顺序。若真先删再验证，就无法恢复误删内容。正确实现顺序必须是先识别注释，再验证关键字边界，最后执行删除。
样例 1 的第 $4,5,13,16$ 行保留四个前导空格；第 $14,15$ 行完全处在跨行删除区间内，只剩换行。样例 2 的第二行保留两个空格。使用 sys.stdout.write，避免额外补一个换行。
题解代码
import sys
input = sys.stdin.readline
def clean(text):
result = []
i = 0
n = len(text)
keywords = ('description', 'default', 'mandatory')
while i < n:
if text.startswith('//', i):
end = text.find('\n', i)
end = n if end == -1 else end
result.append(text[i:end])
i = end
continue
if text.startswith('/*', i):
end = text.find('*/', i + 2) + 2
result.append(text[i:end])
i = end
continue
matched = False
if i == 0 or text[i - 1] in ' \t\n{;':
for keyword in keywords:
end = i + len(keyword)
if (text.startswith(keyword, i) and end < n
and text[end] in ' \t\n"'):
semi = text.find(';', end)
result.append('\n' * text.count('\n', i, semi + 1))
i = semi + 1
matched = True
break
if not matched:
result.append(text[i])
i += 1
return ''.join(result)
def solve():
sys.stdout.write(clean(sys.stdin.read()))
solve()
复杂度分析
时间复杂度：$O(L)$，关键字长度为常数，每段扫描和复制次数有常数上界。
空间复杂度：$O(L)$，输入字符串和输出片段。
第 2 题：王子拯救公主
题目描述
在 $n\times m$ 迷宫中从 S 出发，到达公主 P。每一步可向上下左右走一格，不能进入墙 # 或地图外。
M 为怪物，未持剑时不能进入怪物所在格和它的上下左右相邻格，不包含斜对角。W 为宝剑，进入后永久持剑，此后可以通过危险格，也可进入怪物所在格并杀死该格怪物；不是一次杀死所有怪物。
宝剑即使位于怪物的相邻格，也允许进入并拾取。起点即使位于危险格，也允许从那里开始行动一次，后续进入的格子仍需按规则检查。
输入格式：第一行 $n,m$，$1\le n,m\le100$；后续 $n$ 行每行 $m$ 个字符，字符取自 .#SPMW。保证 S 和 P 各一个。
输出格式：最少步数；无法到达输出 $-1$。
样例 1
输入
4 5
S....
.M...
....M
...MP
输出
-1
样例 2
输入
4 5
S....
W....
...M.
....P
输出
7
样例 3
输入
1 4
S..P
输出
3
思路分析
第一步：位置不足以描述未来。 同一个格子，无剑时可能无法继续，取剑后却能穿过怪物区。只用二维 visited 会把“绕路取剑再回来”的合法路线剪掉。
第二步：把迷宫分成两层。 预处理怪物格及四邻格组成的危险集合。状态为 $(x,y,s)$，$s\in{0,1}$ 表示是否持剑。从无剑层进入 W 时转到持剑层；持剑后不会退回。
第三步：在状态图上 BFS。 每条移动边耗时都是 $1$，因此按队列逐层扩展即可。进入相邻格前检查边界、墙、持剑状态和宝剑例外；起点直接入队，不因危险标记而拒绝。首次出队的公主状态给出最短路。
正确性证明
状态图中的每条边都对应规则允许的一步移动，任一实际移动也都能映射到这样的边，因此实际路径与状态图路径一一对应。虽然只杀死当前格怪物，但持剑者始终可进入其他危险格，不需要额外记录死亡怪物集合。所有边权均为 $1$，BFS 第一次访问状态时距离最小；第一个出队的公主状态即为两层中最小距离。队列耗尽则不存在可行路径。
样例 1 无剑，公主无法接近；样例 2 先在 $(1,0)$ 拾剑，可沿 $(2,0),(2,1),(2,2),(2,3),(3,3),(3,4)$ 到达，共 $7$ 步；样例 3 直行 $3$ 步。
题解代码
import sys
from collections import deque
input = sys.stdin.readline
def rescue(grid):
n, m = len(grid), len(grid[0])
directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
danger = [[False] * m for _ in range(n)]
for r in range(n):
for c in range(m):
if grid[r][c] == 'S':
start = (r, c)
if grid[r][c] == 'M':
danger[r][c] = True
for dr, dc in directions:
x, y = r + dr, c + dc
if 0 <= x < n and 0 <= y < m:
danger[x][y] = True
distance = [[[-1, -1] for _ in range(m)] for _ in range(n)]
sr, sc = start
distance[sr][sc][0] = 0
queue = deque([(sr, sc, 0)])
while queue:
r, c, sword = queue.popleft()
steps = distance[r][c][sword]
if grid[r][c] == 'P':
return steps
for dr, dc in directions:
x, y = r + dr, c + dc
if not (0 <= x < n and 0 <= y < m) or grid[x][y] == '#':
continue
if not sword and danger[x][y] and grid[x][y] != 'W':
continue
next_sword = int(sword or grid[x][y] == 'W')
if distance[x][y][next_sword] == -1:
distance[x][y][next_sword] = steps + 1
queue.append((x, y, next_sword))
return -1
def solve():
n, m = map(int, input().split())
grid = [input().strip() for _ in range(n)]
print(rescue(grid))
solve()
复杂度分析
时间复杂度：$O(nm)$，最多 $2nm$ 个状态，每个状态检查四条边。
空间复杂度：$O(nm)$，地图、危险标记、距离数组及 BFS 队列。
第 3 题：武林高手
题目描述
神秘岛上有 $N$ 个事件，事件 $i$ 在 $[S_i,E_i]$ 持续，奖励为 $V_i$。若在 $s$ 进入、$e$ 退出，只有 $s\le S_i\le E_i\le e$ 的事件能获得奖励，同时消耗 $(e-s)M$ 功力。
最多选择两段进入区间，也可只选一段或不进入。若选择两段，必须 $s_2>e_1$，不能共享端点。进入和退出可以同一时刻；所有进出时刻必须来自事件起止时间集合。每个选中区间的净收益必须严格大于零。
求最大总收益及对应方案。同收益时，将进出时间按 [s1,e1,s2,e2]（一段时只有前两项）展开，取字典序最小数组；一个数组为另一个的前缀时，更短者更小。
输入格式：首行 $N,M$，后续 $N$ 行 $S_i,E_i,V_i$。约束为 $1\le N\le10^4$、$0\le M\le10^9$、$1\le S_i\le E_i\le10^9$、$0\le V_i\le10^9$。事件可重叠或完全重合。
输出格式：第一行最大功力；无正收益方案时第二行输出 NA，否则按开始时间升序，每行输出一段 s,e。
样例 1
输入
3 5
1 3 4
1 2 2
4 6 2
输出
0
NA
样例 2
输入
5 2
1 3 4
1 2 6
4 6 2
10 11 7
100 101 7
输出
11
1,3
10,11
样例 3
输入
3 2
1 3 4
1 2 6
5 10 1
输出
6
1,3
思路分析
第一步：将一次进入的收益拆开。 离散化全部端点为递增数组 $t$。固定退出时刻 $e$，一次进入的收益为
\[R(s,e)=\sum_{i:E_i\le e,\ S_i\ge s}V_i+sM-eM.\]其中 $-eM$ 与进入时刻无关。为每个候选进入时刻保存 $A[s]=sM$，再按结束时间扫描事件。事件 $i$ 到期时，它会对所有 $s\le S_i$ 的候选贡献 $V_i$，因此进行一次前缀区间加；查询 $s\le e$ 的最大值后减去 $eM$，便得到以 $e$ 退出的最优单段。
第二步：线段树同时维护收益和端点。 区间加使用懒标记，最大值相同时选较早的进入时刻。代码将父节点标记留在父节点，查询时累加祖先标记，回填时再加父节点自己的标记，避免重复下传。
第三步：反转时间求另一方向。 将事件 $[S_i,E_i]$ 变成 $[-E_i,-S_i]$，再次扫描，得到原时间轴上以每个时刻进入的最优单段。反向扫描并列时应选较大的反向进入下标，映射回来才是较早的原退出时刻；不能照搬正向的并列规则。
第四步：前后缀合并两段。 prefix[j] 保存退出下标不超过 $j$ 的最佳单段，suffix[j+1] 保存进入下标不小于 $j+1$ 的最佳单段。枚举分界 $j$，两段天然满足严格不重叠。先比较收益，再比较 $(s,e)$；最终在空方案、所有正收益单段和合法双段之间比较总收益和完整时间数组。
正确性证明
扫描至退出时刻 $e$ 时，已加入线段树的恰是所有 $E_i\le e$ 的事件。一次前缀加仅影响能覆盖该事件起点的进入时刻，因此每个叶子的值恰为奖励和加 $sM$，前缀最大查询正确得到最优单段。时间反转保持区间包含关系和时长，故反向结果也正确。
任意合法双段都存在一个分界 $j$，使第一段在其左侧、第二段在其右侧。该分界两侧相互独立，各取最大单段收益不会变差；同收益取最小端点对也使拼接数组字典序最小。枚举全部分界并与所有单段、空方案比较，得到所求最优方案。严格正收益过滤保证不输出零收益装饰区间。
样例 2 中 $[1,3]$ 收益 $6$，$[10,11]$ 和 $[100,101]$ 均为 $5$，因此选字典序更小的 $[1,3,10,11]$，总收益 $11$。样例 3 只有前一段值得选择，收益 $6$。$M=0$、同刻事件、重复事件和多方案并列都沿用同一套比较规则。
题解代码
import sys
input = sys.stdin.readline
def sweep(times, events, rate, prefer_right=False):
size = len(times)
maximum = [0] * (4 * size)
lazy = [0] * (4 * size)
position = [0] * (4 * size)
def better(a, b):
if a[0] != b[0]:
return a if a[0] > b[0] else b
if prefer_right:
return a if a[1] > b[1] else b
return a if a[1] < b[1] else b
def pull(node):
value, index = better((maximum[node * 2], position[node * 2]),
(maximum[node * 2 + 1], position[node * 2 + 1]))
maximum[node] = value + lazy[node]
position[node] = index
def build(node, left, right):
if left == right:
maximum[node] = times[left] * rate
position[node] = left
return
middle = (left + right) // 2
build(node * 2, left, middle)
build(node * 2 + 1, middle + 1, right)
pull(node)
def add(node, left, right, end, value):
if right <= end:
maximum[node] += value
lazy[node] += value
return
middle = (left + right) // 2
add(node * 2, left, middle, end, value)
if end > middle:
add(node * 2 + 1, middle + 1, right, end, value)
pull(node)
def query(node, left, right, end, inherited=0):
if right <= end:
return maximum[node] + inherited, position[node]
inherited += lazy[node]
middle = (left + right) // 2
result = query(node * 2, left, middle, end, inherited)
if end > middle:
result = better(result, query(node * 2 + 1, middle + 1,
right, end, inherited))
return result
build(1, 0, size - 1)
buckets = [[] for _ in times]
for start, end, value in events:
buckets[end].append((start, value))
result = []
for end in range(size):
for start, value in buckets[end]:
add(1, 0, size - 1, start, value)
value, start = query(1, 0, size - 1, end)
result.append((value - rate * times[end], start, end))
return result
def best_plan(events, rate):
times = sorted({t for start, end, _ in events for t in (start, end)})
index = {value: i for i, value in enumerate(times)}
size = len(times)
indexed = [(index[s], index[e], v) for s, e, v in events]
ending = sweep(times, indexed, rate)
reversed_times = [-t for t in reversed(times)]
reversed_events = [(size - 1 - e, size - 1 - s, v) for s, e, v in indexed]
reversed_best = sweep(reversed_times, reversed_events, rate, True)
starting = [None] * size
for value, start, end in reversed_best:
original_start = size - 1 - end
starting[original_start] = (value, original_start, size - 1 - start)
def pick(a, b):
return min(a, b, key=lambda item: (-item[0], item[1], item[2]))
prefix = ending[:]
suffix = starting[:]
for i in range(1, size):
prefix[i] = pick(prefix[i - 1], prefix[i])
for i in range(size - 2, -1, -1):
suffix[i] = pick(suffix[i], suffix[i + 1])
total, plan = 0, ()
def consider(value, candidate):
nonlocal total, plan
if value > total or (value == total and candidate < plan):
total, plan = value, candidate
for value, start, end in ending:
if value > 0:
consider(value, (start, end))
for split in range(size - 1):
first, second = prefix[split], suffix[split + 1]
if first[0] > 0 and second[0] > 0:
consider(first[0] + second[0], first[1:] + second[1:])
return total, tuple(times[i] for i in plan)
def solve():
n, rate = map(int, input().split())
events = [tuple(map(int, input().split())) for _ in range(n)]
total, plan = best_plan(events, rate)
print(total)
if not plan:
print('NA')
else:
for i in range(0, len(plan), 2):
print(f'{plan[i]},{plan[i + 1]}')
solve()
复杂度分析
时间复杂度：$O(N\log N)$，排序及正反两次线段树扫描，前后缀合并为 $O(N)$。
空间复杂度：$O(N)$，端点、事件桶、线段树和单段最优数组。
小结
- YANG 模型配置精简器：注释优先，边界准确，空白必须按原规则保留。
- 王子拯救公主：未来通行能力不同，就必须拆成不同搜索状态。
- 武林高手：区间包含收益转成前缀加，双段由前后缀独立最优合并。