大厂真题 / 华为

华为 5.9 笔试真题 - 研发岗

本场考试概述

考试时间：2026年5月9日 考试岗位：研发岗（国内） 难度评级：中等

考点分析：

第一题：位图 Bitmap（难度中等）
第二题：滑动窗口 + 单调队列（难度中等）
第三题：完全背包 + 方案重构（难度中等）

建议策略：

第一题需要意识到内存限制，用位图把 1 亿个槽位压缩到 12.5MB
第二三题均为经典模版题，背熟滑动窗口和完全背包模版可快速 AC

第一题：商品购买查询

题目描述

某商城使用长度为 8 位的十进制手机号作为用户标识，取值范围为 $0$ 到 $99999999$。每个商品都有一份购买用户清单，记录了买过该商品的所有手机号。

读入两个清单后，输出同时出现在两个清单中的用户个数。同一个用户仅统计一次。

提示：内存限制，试试位运算压缩！

输入格式为数字，前导 0 会被省略。由于可能多次购买，输入可能重复。

样例

输入

输出

思路分析

第一步：分析内存瓶颈

手机号取值约 $10^8$ 个，每个清单最多也可能有 $10^7$ 条记录。如果用 set 存 A 清单，每个手机号在哈希表中约占 40 字节，最坏内存接近 4GB，超出限制。

第二步：位图压缩

每个手机号只需标记”是否出现过”——一个比特就够。$10^8$ 个比特只占 $10^8 / 8 = 12.5$ MB，完全可行。

第三步：实现细节

开一个字节数组 bitmap（长度约 $12.5 \times 10^6$），把它看作 $10^8$ 个比特首尾相连。第 $x$ 个比特代表手机号 $x$ 是否在 A 清单中出现过。

字节下标：$x \gg 3$（即 $x / 8$）
字节内偏移：$x \mathbin{\&} 7$（即 $x \bmod 8$）

读 A 清单时，用按位或把该位置 1。读 B 清单时，用按位与查询：若该位为 1，答案加 1 并立即清零。清零是为了让 B 清单中重复出现的同一手机号不被重复计数。

题解代码

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    MAX_NUM = 100000000
    bitmap = bytearray((MAX_NUM + 7) // 8)

    n = int(data[idx]); idx += 1
    for _ in range(n):
        x = int(data[idx]); idx += 1
        bitmap[x >> 3] |= (1 << (x & 7))

    m = int(data[idx]); idx += 1
    ans = 0
    for _ in range(m):
        x = int(data[idx]); idx += 1
        mask = 1 << (x & 7)
        if bitmap[x >> 3] & mask:
            ans += 1
            bitmap[x >> 3] &= ~mask

    print(ans)

solve()

复杂度分析

时间复杂度：$O(n + m)$，线性扫描两个清单。 空间复杂度：$O(10^8 / 8) \approx 12.5$ MB。

第二题：设备运行监控

题目描述

某医院有 $n$ 台医疗设备，依次编号为 $1$ 到 $n$，每台设备有一个当前的运行状态值。找出最长的连续设备序列，使得序列中任意两台设备的运行状态值之差的绝对值不超过给定阈值 $d$。

如果存在多个长度相同的最长序列，输出起始编号最小的序列。

样例

输入

9 3
1 4 2 5 7 4 3 8 1

输出

1 3

思路分析

第一步：问题转化

“任意两台设备差不超过 $d$”等价于段内 $\max - \min \leq d$。问题转化为：找最长连续段使其极差不超过 $d$。

第二步：滑动窗口框架

用滑动窗口 $[l, r]$，$r$ 从左往右扫描。每当新元素让窗口极差超过 $d$，收缩左端 $l$ 直到窗口重新合法。

第三步：单调队列维护极值

关键问题是 $O(1)$ 获取窗口的最大、最小值。用两个单调队列：

max_q：队首到队尾对应值递减，队首即当前窗口最大值
min_q：队首到队尾对应值递增，队首即当前窗口最小值

加入下标 $r$ 时，从 max_q 队尾弹掉所有值 $\leq a[r]$ 的下标——它们既比 $a[r]$ 小又比 $r$ 先进窗口，永远不可能再成为最大值。min_q 对称处理。

若极差超过 $d$，让 $l$ 右移；若队首恰好等于旧的 $l$，从队首弹出。重复直到合法。

第四步：更新答案

只在窗口严格更长时才更新答案，长度相等不更新。这样自然保留起点最小的那个。

题解代码

import sys
from collections import deque

input = sys.stdin.readline

def solve():
    n, d = map(int, input().split())
    a = list(map(int, input().split()))

    max_q = deque()
    min_q = deque()

    l = 0
    best_l, best_r = 0, 0

    for r in range(n):
        while max_q and a[max_q[-1]] <= a[r]:
            max_q.pop()
        max_q.append(r)
        while min_q and a[min_q[-1]] >= a[r]:
            min_q.pop()
        min_q.append(r)

        while a[max_q[0]] - a[min_q[0]] > d:
            if max_q[0] == l:
                max_q.popleft()
            if min_q[0] == l:
                min_q.popleft()
            l += 1

        if r - l > best_r - best_l:
            best_l = l
            best_r = r

    print(best_l + 1, best_r + 1)

solve()

复杂度分析

时间复杂度：$O(n)$，每个下标进出两个队列各至多一次。 空间复杂度：$O(n)$。

第三题：虚拟机任务调度问题

题目描述

虚拟机环境中有 4 种不同类型的任务，分别消耗不同单位的 RAM。这 4 种任务可以无限次调度。有 $m$ 台机器，每台机器有不同的 RAM 容量。

要求每台机器都被任务占满，并且分配到该机器上的任务数量尽量少。如果存在多个最少任务数的方案，把每个方案的任务消耗值升序排列后，按位逐个比较，输出字典序最小的那个。

已知 4 种消耗值互不相同，且其中至少有一个为 1，因此机器一定可以被填满。

样例

输入

输出

7+7
1+3

思路分析

第一步：问题转化

把每种任务的资源消耗看作硬币面值，机器 RAM 看作目标金额。问题转化为经典的”最少硬币凑数”——又因为可以无限次使用同一种任务，这是典型的完全背包。

由于至少存在一种消耗为 1 的任务，任意 RAM 都可以被凑出，保证有解。

第二步：DP 求最少任务数

定义 $f[i]$ 表示填满内存 $i$ 所需的最少任务数。初始 $f[0] = 0$，其余 $\infty$。

转移：从 1 到 max_ram 枚举 $i$，对每个 4 种任务消耗 $c$：若 $c \leq i$ 且 $f[i-c] + 1 < f[i]$，则更新 $f[i]$。

第三步：字典序最小方案重构

先把 4 种消耗值升序排列。对于每台机器，记当前剩余 remain、剩余任务数 cnt。

每一步从小到大尝试消耗值 $c$：如果 $c \leq \text{remain}$ 且 $f[\text{remain} - c] = \text{cnt} - 1$（说明选了 $c$ 后还能用最优方案完成剩余），就选 $c$ 加入方案。

为什么”能选最小的就选最小的”得到字典序最小？因为每一步都在保持总任务数最优的前提下让首位选择尽量小，升序排列后自然字典序最小。

题解代码

import sys
input = sys.stdin.readline

def solve():
    coins = list(map(int, input().split()))
    coins.sort()

    m = int(input())
    machines = []
    max_x = 0
    for _ in range(m):
        v = int(input())
        machines.append(v)
        if v > max_x:
            max_x = v

    INF = float('inf')
    f = [INF] * (max_x + 1)
    f[0] = 0
    for i in range(1, max_x + 1):
        for c in coins:
            if c > i:
                break
            if f[i - c] + 1 < f[i]:
                f[i] = f[i - c] + 1

    out = []
    for ram in machines:
        remain = ram
        cnt = f[remain]
        parts = []
        while remain > 0:
            for c in coins:
                if c <= remain and f[remain - c] == cnt - 1:
                    parts.append(str(c))
                    remain -= c
                    cnt -= 1
                    break
        out.append("+".join(parts))

    print("\n".join(out))

solve()

复杂度分析

时间复杂度：$O(\text{max_ram} \times 4)$ 预处理 DP，加上所有机器方案重构的总长度。 空间复杂度：$O(\text{max_ram})$。

小结

第一题（商品购买查询）：经典位图应用。关键是识别出内存限制，用 1 比特表示一个手机号的出现状态，将空间从 GB 级压缩到 12.5MB。查询时清零避免重复计数。
第二题（设备运行监控）：滑动窗口 + 单调队列的模板题。用两个单调队列 $O(1)$ 维护窗口最大最小值，极差超阈值时收缩左端。注意仅严格更长时更新答案以保持起点最小。
第三题（虚拟机任务调度）：完全背包求最少硬币数 + 贪心重构字典序最小方案。DP 预处理后，方案重构阶段从小到大尝试每种面值，只要选了还能最优完成剩余就选，保证输出字典序最小。

这篇文章有帮助吗？

| GitHub 留言