大厂真题

华为研发岗 2026-09-09

本场考试概述

考试时间：2026-9-9 考试岗位：研发岗 难度评级：中等偏难

考点分析：

• 第一题 5G基站部署的双向干扰指数计算：单调栈 （难度中等）
• 第二题 挑选奖品：背包DP （难度中等）
• 第三题 网络流量路径规划：有向图欧拉路径 Hierholzer （难度困难）

建议策略：

• 三道题都是经典模型换了层业务外壳，先把题面翻译成模型再动手：找最近的更大元素就是单调栈、限件数限金额挑方案就是二维背包、每条边走一次就是欧拉路径
• 第一题的 k 是个纸老虎，先无视它求全局最近更大者，最后拿距离和 k 比一次即可，别真的每个位置往两边扫 k 格
• 第三题不要凭直觉每步挑字典序最小的目标，那样会中途走死；必须用 Hierholzer 后序压栈、结果逆序输出，而且要写显式栈防爆栈

第 1 题：5G基站部署的双向干扰指数计算

题目描述

在 网络规划中，需要在一条直线上的若干位置部署基站。现给定每个位置 的基站信号强度为 。针对每个基站，需要计算其受到左右两边相邻基站的干扰影响。

对于每个基站 ，定义：

1. 左侧干扰区间：在数组范围内，从位置 开始向左搜索（索引递减），最多搜索 个基站。
2. 右侧干扰区间：在数组范围内，从位置 开始向右搜索（索引递增），最多搜索 个基站。
3. 左侧干扰指数：在左侧干扰区间内，寻找第一个（即最近一个）信号强度严格大于 的基站位置 。若找到，则贡献值为 ；若未找到（即在搜索范围内无更强信号），则左侧贡献值为 （即取 ）。
4. 右侧干扰指数：在右侧干扰区间内，寻找第一个（即最近一个）信号强度严格大于 的基站位置 。若找到，则贡献值为 ；若未找到，则右侧贡献值为 （即取 ）。
5. 总干扰指数：所有基站的左侧干扰指数与右侧干扰指数之和。

请计算并输出基站的总干扰指数。

输入描述

第一行包含 所有基站的信号强度，以空格分隔，长度记为 ，每个元素满足 ，如 3 1 4 2 5。

第二行包含一个整数 ，表示连续搜索的基站数量，如 3。

题目保证输入合法，无需校验输入。

输出描述

一个整数，基站的总干扰指数，输出结果对 取模。

样例1

输入

7 2 5 3 9 4 6 1 8 3
5

输出

127

样例解释

以基站 （强度 ）为例，左侧没有基站，左侧干扰为 ；右侧依次查看索引 到 ，强度为 ，前三个都不超过 ，直到索引 的 严格大于 ，距离为 ，右侧干扰为 ，合计 。

以基站 （强度 ）为例，左侧查看索引 的 ，严格大于 ，距离为 ，左侧干扰为 ；右侧查看索引 的 ，严格大于 ，距离为 ，右侧干扰为 ，合计 。

以基站 （强度 ）为例，左侧依次查看索引 ，强度为 ，直到 严格大于 ，距离为 ，左侧干扰为 ；右侧依次查看索引 ，强度为 ，直到 严格大于 ，距离为 ，右侧干扰为 ，合计 。

十个基站的干扰指数依次为 ，总和为 ，对 取模仍为 。

样例2

输入

3 1 4 2 5
3

输出

20

样例解释

基站 （强度 ）左侧无基站干扰为 ，右侧查看 中最先严格大于 的是索引 的 ，距离为 ，干扰为 ，合计 。

基站 （强度 ）左侧的 严格大于 ，距离为 ，干扰为 ；右侧最先严格大于 的是索引 的 ，距离为 ，干扰为 ，合计 。

基站 （强度 ）左侧查看 都不超过 ，干扰为 ；右侧查看 ，直到 严格大于 ，距离为 ，干扰为 ，合计 。

基站 （强度 ）左侧最先严格大于 的是索引 的 ，距离为 ，干扰为 ；右侧的 距离为 ，干扰为 ，合计 。

基站 （强度 ）左侧查看 都不超过 ，右侧无基站，合计 。

五个基站合计 ，对 取模仍为 。

题解：单调栈

思路分析

每个基站向左、向右各找一个强度严格大于自己的最近基站，找到就把”自身强度 距离”计入该侧贡献，找不到记 ，两侧搜索各限制在 个基站以内。 个基站的贡献求和后对 取模即为答案。

这是一道把”窗口内找第一个更大元素”化归成经典单调栈的题：栈本身不难写，难在说清 这个窗口限制为什么可以先摘掉。

算法实现

最直白的写法是对每个 向两侧各扫最多 个位置，遇到更大的就停。它是 ， 且 时约 次比较，远超时限。

再看 到底约束了什么。记 为 左侧最近的严格更大者下标， 为右侧最近的：

若 ， 落在窗口内，它正是窗口内第一个更大者；若 ，窗口 整段都在 右侧，而 已是最近的更大者，这段里不可能还有更大的，该侧贡献必为 。

所以先无视 求全局最近的更大者，再拿距离与 比一次即可。

求 用单调栈：从左往右扫，栈里存下标、对应强度从栈底到栈顶严格递减；当前元素进栈前把栈顶强度不大于它的全部弹掉，剩下的栈顶即 ，栈空则不存在。

弹掉的位置不会是任何人的答案：它强度不超过 ，既当不了 的答案，也当不了 右边位置的答案，因为那些位置要越过 才能看到它，而 既更大又更近。每个下标进栈出栈各一次。

弹栈判据必须写成”栈顶强度 当前强度”。题面要的是严格大于，写成 会把等值位置留在栈里，等值基站就被误当成更强的答案。

那一遍从右往左扫，其余完全对称。累加时单项最大约 ，必须用 位整数并每步取模。

复杂度分析

时间复杂度：O(n)。

空间复杂度：O(n)，包括输入数组与单调栈。

题解代码

import sys
input = sys.stdin.readline

def solve():
    power = list(map(int, input().split()))
    k = int(input())
    n = len(power)
    total = 0
    for indices in (range(n), range(n - 1, -1, -1)):
        stack = []
        for i in indices:
            while stack and power[stack[-1]] <= power[i]:
                stack.pop()
            if stack and abs(i - stack[-1]) <= k:
                total += power[i] * abs(i - stack[-1])
            stack.append(i)
    print(total % 1000000007)

solve()

正确性说明

扫描过程中，被弹出的下标比当前下标更远且强度不更大，不可能成为后续位置的最近严格更大者。剩余栈顶因此恰好是该侧答案；距离超过 k 时，窗口内也不存在更大者。两侧贡献相加即为所求。

易错点与边界

相等强度必须弹栈；索引从 0 开始，距离仍为下标之差。Python 整数无需手动模拟 64 位溢出。

第 2 题：挑选奖品

题目描述

小明 今年工作完成得非常好，是部门公认的优秀员工，部门准备奖励一下 小明。小明 可以从礼物清单里面选四个礼物，总价不能超过 元。每个礼物都有特定编号和价格，礼物编号不会重复，价格可能重复。

小明 想挑选四个总价最接近上限的礼物，如果总价一样，就选择礼物编号按照升序排序后数值序小的那一组。

输入描述

第一行包含一个整数 ，表示礼物个数。

接下来 行表示 个礼物，每行两个整数 ，分别表示礼物的编号和价格。

输出描述

如果有满足要求的礼品，输出礼品编号，礼品编号之间以空格分割，礼品编号按照升序排序。如果没有满足要求的 个礼物，输出 。

样例1

输入

6
1 100
3 10000
5 5000
8 3000
7 100
9 100

输出

1 5 7 8

样例解释

编号组合 与 与 这三组礼物价值之和全部是 ，且最接近 ，优选按照编号数值排序后数值序小的礼物组合，即 。

样例2

输入

5
1 100
3 10000
5 5000
8 5000
9 9988

输出

0

样例解释

这里面找不出 个礼物之和小于等于 元，输出 。

题解：背包DP

思路分析

从 件礼物里恰好挑 件，总价不超过 且尽量大；总价并列时，取编号升序排好后字典序最小的那一组。

这是一道件数与金额双限制的 01 背包题：求最大总价是常规操作，难点在并列时还要把编号字典序最小的那一组方案也挑出来。

算法实现

四重枚举有 种组合， 稍大就跑不完。换成背包：每件礼物只有选与不选两种，把件数和总价一起当限制，状态就只剩 个。

先解决怎么比字典序。把一组升序编号拼成一个 进制的数，编号最大 ，进位不会串到相邻位上：

小编号放在高位，所以两组长度相同的编号比 的大小就等于比字典序，而 最大约 ，一个 位整数装得下。有了它，方案本身就能塞进状态里，不必另外记录路径。

状态方程定义：礼物先按编号升序排。 表示恰好选 件、总价为 时，字典序最小的那组编号的 ，凑不出记 。

状态方程初始化：

一件不选、总价为 是唯一的起点，其余格子都是 。

状态方程转移：按编号升序逐件处理，件数与总价都从大往小刷新，也就是 01 背包的倒序写法，保证每件礼物只被用一次。设当前礼物编号为 、价格为 ：

只在 时才转移。礼物按编号升序处理， 一定大于旧组合里的所有编号，接在末尾仍然是升序。

取 不会丢解：两组长度相同的旧编号，谁的 小谁的字典序就小，后面接上同一个 之后大小关系不变，所以每个状态只留 最小的那组就够了。

最后从 往下找第一个 ，它就是答案；把这个 反复除以 取余数，就拆回四个编号。 时 整行都是 ，与凑不出总价共用输出 的分支，不必特判。

复杂度分析

时间复杂度：O(N log N + 4NV)，V=10000。

空间复杂度：O(N+4V)，包括礼物列表和状态表。

题解代码

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    gifts = sorted(tuple(map(int, input().split())) for _ in range(n))
    limit, base = 10000, 10001
    f = [[-1] * (limit + 1) for _ in range(5)]
    f[0][0] = 0
    for gift_id, price in gifts:
        for count in range(4, 0, -1):
            cur, prev = f[count], f[count - 1]
            for total in range(limit, price - 1, -1):
                old = prev[total - price]
                if old >= 0:
                    candidate = old * base + gift_id
                    if cur[total] < 0 or candidate < cur[total]:
                        cur[total] = candidate
    for total in range(limit, -1, -1):
        if f[4][total] >= 0:
            code = f[4][total]
            ids = []
            for _ in range(4):
                ids.append(code % base)
                code //= base
            print(*reversed(ids))
            return
    print(0)

solve()

正确性说明

按已处理礼物数归纳，f 保留每个件数、总价下最小编号编码。倒序件数确保当前礼物至多使用一次；追加相同且更大的编号不改变字典序关系，所以丢弃较大编码不会损失最优解。最终逆序枚举总价实现价格优先、编号次优。

易错点与边界

必须恰好四件而非至多四件，编号排序按整数而非字符串；倒序件数避免重复选同一礼物。Python 对象内存高于紧凑整数数组，不能照搬 Java 的字节数。

第 3 题：网络流量路径规划

题目描述

在大型数据通信网络中，网络管理员需要分析流量在网络设备之间的传输路径。给定一系列的网络链路配置，其中每条链路表示一个连接关系 ，表示数据包从源设备 发送到目标设备 。

请对该流量链路进行重新规划排序，所有这些链路都属于一个从核心交换机 Core-SW-01 开始的流量流，因此该路径必须从 Core-SW-01 开始。如果存在多种有效的流量路径，请按设备名称的字典排序返回最小的路径组合。

在网络运维和流量分析场景中，网络设备之间形成了一张复杂的拓扑图。当网络中出现异常流量或进行网络架构优化时，需要明确流量在设备之间的传输序列。本题模拟了根据预配置的链路信息，还原流量在网络中的实际传输路径的过程。

举例来说，若链路配置为 SW-A SW-B、Core-SW-01 SW-A、Router-X Router-Y、SW-B Router-X，则最终形成的流量路径依次为 Core-SW-01、SW-A、SW-B、Router-X、Router-Y，输出结果为 Core-SW-01 SW-A SW-B Router-X Router-Y。

在有多条可选链路时，优先选择目标设备名称字典序较小的链路进行跳转。题目保证所有链路至少构成一条从 Core-SW-01 开始的有效路径。

输入描述

若干行，每行两个由空格分隔的设备名称，表示一条链路的源设备和目标设备，行数记为 。

设备名称由大写字母、数字、短横线组成，长度在 到 个字符之间。

输出描述

一行，按流量传输顺序输出经过的设备名称，设备名称之间以空格分割。

样例1

输入

Core-SW-01 Switch-B
Core-SW-01 Switch-A
Switch-A Switch-B
Switch-A Core-SW-01
Switch-B Switch-A

输出

Core-SW-01 Switch-A Core-SW-01 Switch-B Switch-A Switch-B

样例解释

另一种有效的路径是 Core-SW-01、Switch-B、Switch-A、Core-SW-01、Switch-A、Switch-B，但是它的字典排序更大，应排在更靠后的位置。

题解：有向图欧拉路径(Hierholzer)

思路分析

把每条链路看成有向图的一条边，要求从 Core-SW-01 出发、每条链路恰好走一次，依次输出走过的设备；这样的走法可能不止一条，取字典序最小的那条。

每条边恰好走一次、一次把图走完的路线，图论里叫欧拉路径，也就是小时候玩的一笔画。所以这是一道有向图上的一笔画题，难点不在遍历本身，而在于”每步都挑名字最小的目标”这个直觉走法会中途走死，必须靠 Hierholzer 的后序压栈把走死的那一段挪到路径末尾。

算法实现

先看直觉走法为什么不够。三条链路 Core-SW-01 SW-A、Core-SW-01 SW-B、SW-B Core-SW-01，从 Core-SW-01 挑最小目标就是 SW-A，可 SW-A 没有出边，只用掉一条链路就停了；正确答案是 Core-SW-01 SW-B Core-SW-01 SW-A，得让 SW-A 留到最后走。

停下的位置并不是随机的。从起点任意往前走到走不动，停在的设备必然是欧拉路径的终点：中途经过的设备每进入一次就要离开一次，出入边成对消耗，只有终点进得去出不来。所以随手走出的这段一定是最终路径的一个后缀，剩下的链路构成若干条起终点相同的回路，各挂在这段路径的某个设备上，在挂点处展开插入即可。

Hierholzer 就是这个插入过程。维护一个显式栈，初始只有 Core-SW-01；栈顶还有未用出边时走目标名字典序最小的那条并压栈，走不动时把栈顶弹出、追加到结果尾部，链路用完后把结果逆序输出。

逆序是关键：先弹出的是先走死的设备，逆序后落到输出末尾，后来展开的回路自动补进前面的挂点。

出边按目标名降序排一次，取用时从末尾弹出即最小目标。比较必须用字符串字典序而非数字大小：SW-10 与 SW-9 逐字符比时 1 小于 9，SW-10 在前，按数字理解会走出另一条路径。

栈要显式写。链状拓扑下深度可达链路条数 ，递归实现在部分语言里会爆栈。

复杂度分析

时间复杂度：。瓶颈是各设备出边的排序，总量为 条边；Hierholzer 本身每条边只被取用一次、每个设备只被弹出一次，是 。

空间复杂度：。邻接表、显式栈与结果序列各最多存 项。

题解代码

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

def solve():
    adj = defaultdict(list)
    for line in sys.stdin:
        parts = line.split()
        if parts:
            source, destination = parts
            adj[source].append(destination)
    for edges in adj.values():
        edges.sort(reverse=True)
    stack = ['Core-SW-01']
    order = []
    while stack:
        if adj[stack[-1]]:
            stack.append(adj[stack[-1]].pop())
        else:
            order.append(stack.pop())
    print(*reversed(order))

solve()

正确性说明

Hierholzer 在无剩余出边时才将顶点写入逆序结果，使提前抵达终点的分支留到最后。每条边仅弹出一次，拼接后形成使用全部边的路径；有序出边使能被插入当前位置的闭合子路优先使用较小目标，从而得到固定起点下的字典序最小欧拉路径。

易错点与边界

重复链路应作为独立边保留。题面名称字符说明与 Core-SW-01、Switch-A 样例的大小写不完全一致，按输入原字符串比较，不做大小写转换。

小结

优先从题面约束提炼模型，再用样例检查边界。本文保留题面数学符号的原始 SVG，代码统一为 Python 3；未给出的评测限制或规则不补作事实。