大厂真题 / 华为

华为 6.24 笔试真题 - 研发岗（非AI方向）

本场考试概述

考试时间：2026年6月24日 考试岗位：研发岗（通软、嵌软、测试、普通算法、数据科学等非AI方向） 难度评级：中等

考点分析：

第一题：电影放映调度——贪心 + 区间调度（难度简单）
第二题：快来排队买包子——队列模拟（难度中等）
第三题：容器镜像 Top-K 大小统计——前序中序重建二叉树 + 路径和剪枝（难度中等）

建议策略：

第一题是经典区间调度，按结束时间排序后贪心选不重叠的区间即可稳拿
第二题队列模拟要抠清细节：多窗口同时叫号、优先分配编号最小的窗口、买完一笼还想买就回队尾重新取号
第三题先用前序加中序重建二叉树，再 DFS 累加路径和作为完整大小，完整大小 $\leq 0$ 时整棵子树剪枝，最后取最大的 $K$ 个排序输出

第 1 题：电影放映调度问题

题目描述

某电影院有一块银幕，每天需安排多部电影放映。给定 $n$ 部电影的放映时间区间 $[s_i, e_i]$，同一时间只能放映一部电影，前一场结束时间等于后一场开始时间可以连续放映。求最多可以放映多少部电影。

样例

输入

输出

输入

输出

思路分析

第一步：识别经典问题

从若干区间中选出尽量多的两两不重叠区间，这是最经典的区间调度问题。

第二步：按结束时间贪心

将所有电影按结束时间升序排序。结束越早的电影占用银幕时间越短，能给后续电影留出越多空间。维护上一部已选电影的结束时间 last_end，扫描时只要当前电影的开始时间 $\geq$ last_end，就选中它。

第三步：端点相接

题目规定结束时间等于开始时间可以连续放映，因此衔接判定用 $\geq$ 而非 $>$。

题解代码

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    movies = []
    for _ in range(n):
        s, e = map(int, input().split())
        movies.append((e, s))
    movies.sort()
    cnt = 0
    last_end = -1
    for end, start in movies:
        if start >= last_end:
            cnt += 1
            last_end = end
    print(cnt)

solve()

复杂度分析

时间复杂度：$O(n \log n)$，排序主导。 空间复杂度：$O(n)$。

第 2 题：快来排队买包子

题目描述

包子铺有 $m$ 个窗口，大厅中有 $n$ 位顾客按取号顺序排队。每个窗口每次服务一位顾客，服务时长 1 秒（买一笼包子）。规则如下：

多个窗口空闲时同时叫号，优先分配编号最小的窗口
每位顾客一次只能买一笼，若还想买更多需回到队尾重新取号
文本为空时的 POP 无效果

给定每位顾客想买的笼数数组和目标顾客编号 $k$（下标从 0 开始），求目标顾客买完所有包子的总耗时（秒）。

样例

输入

2 1 2
2
2

输出

输入

5 3 3 1 4
2
3

输出

思路分析

第一步：逐秒模拟

顾客数 $n \leq 100$，窗口数 $m \leq 100$，每人最多买若干笼，总笼数有限。直接按秒模拟整个过程即可。

第二步：模拟核心逻辑

每过 1 秒，所有在服务中的窗口各服务完一笼，然后：

剩余笼数为 0 的顾客离开
剩余笼数 > 0 的顾客按窗口编号从小到大的顺序追加回队尾
重新从队首取人填满空闲窗口

第三步：命中目标

若本秒离开的顾客正好是目标顾客 $k$，当前秒数即为答案。

题解代码

import sys
from collections import deque

def solve():
    data = sys.stdin.read().split('\n')
    remaining = list(map(int, data[0].split()))
    n = len(remaining)
    k = int(data[1].strip())
    m = int(data[2].strip())

    hall = deque(range(n))
    windows = [-1] * m

    # 初始叫号：编号小的窗口优先从队首取人
    for w in range(m):
        if hall:
            windows[w] = hall.popleft()

    t = 0
    while True:
        t += 1
        returners = []
        done = False
        for w in range(m):
            c = windows[w]
            if c == -1:
                continue
            remaining[c] -= 1
            windows[w] = -1
            if remaining[c] == 0:
                if c == k:
                    done = True
            else:
                returners.append(c)
        for c in returners:
            hall.append(c)
        if done:
            print(t)
            return
        # 重新叫号填满空闲窗口
        for w in range(m):
            if windows[w] == -1 and hall:
                windows[w] = hall.popleft()

solve()

复杂度分析

时间复杂度：$O(S \times m)$，其中 $S$ 为所有顾客需求总笼数。每秒最多消化 $m$ 笼，模拟最多 $S/m$ 轮。 空间复杂度：$O(n + m)$。

第 3 题：容器镜像 Top-K 大小统计

题目描述

容器镜像层用二叉树管理，节点值表示镜像层大小（可为负数，表示裁剪文件）。节点的”镜像完整大小”为从根到该节点路径上所有值之和。

给定二叉树的前序遍历和中序遍历（各节点值互不相同），还原二叉树后：

若某节点的镜像完整大小 $\leq 0$，则该节点连同整棵子树剪枝
输出剩余节点中最大的 $K$ 个镜像完整大小，按从小到大排序

若剪枝后为空，输出 null。

样例

输入

8 2 -3 9 5
2 8 9 -3 5
3

输出

10 10 14

输入

1 2 3 -5 5 6
2 1 3 5 -5 6
1

输出

思路分析

第一步：前序中序重建二叉树

前序第一个元素是当前子树的根。在中序中找到该根的位置，左边为左子树中序、右边为右子树中序，由左子树节点个数分割前序序列。

第二步：路径和即镜像完整大小

从根往下递推：$\text{size}(v) = \text{parent_sum} + \text{layer}(v)$。在重建过程中同步计算，无需额外遍历。

第三步：剪枝

当 $\text{size}(v) \leq 0$ 时，该节点和整棵子树异常，直接停止对该子树的递归——任何子节点的路径和只会在此基础上累加，恢复为正数的可能性存在但题目要求整棵子树一律剪掉。

第四步：取 Top-K

收集所有合法节点的镜像完整大小后排序，取最大的 $K$ 个升序输出。用显式栈代替递归避免链状树的栈溢出。

题解代码

import sys

def solve():
    data = sys.stdin.read().split('\n')
    preorder = list(map(int, data[0].split()))
    inorder = list(map(int, data[1].split()))
    K = int(data[2].strip())
    n = len(preorder)

    pos = {}
    for i, v in enumerate(inorder):
        pos[v] = i

    sizes = []
    stack = []
    if n > 0:
        stack.append((0, n-1, 0, n-1, 0))
    while stack:
        pl, pr, il, ir, parent = stack.pop()
        if pl > pr:
            continue
        root = preorder[pl]
        size = parent + root
        if size <= 0:
            continue
        sizes.append(size)
        kidx = pos[root]
        left_cnt = kidx - il
        stack.append((pl + 1, pl + left_cnt, il, kidx - 1, size))
        stack.append((pl + left_cnt + 1, pr, kidx + 1, ir, size))

    if not sizes:
        print("null")
    else:
        sizes.sort()
        start = max(0, len(sizes) - K)
        print(" ".join(map(str, sizes[start:])))

solve()

复杂度分析

时间复杂度：$O(n \log n)$，重建 $O(n)$，排序 $O(n \log n)$。 空间复杂度：$O(n)$。

小结

第一题是签到级的经典区间调度，按结束时间排序后贪心选取即可
第二题队列模拟看似简单，但多窗口同时叫号、窗口编号优先级、买完回队尾这些细节容易漏，建议用样例手动走一遍确认
第三题是二叉树重建模板题的变形，核心在于同步计算路径和并做剪枝，用显式栈代替递归处理极端链状树

这篇文章有帮助吗？

| GitHub 留言