大厂真题 / 华为

华为研发岗 2026-09-11

本场考试概述

考试时间：2026-09-11

考试岗位：研发岗

考点分析：三道编程题，依次是因数跳跃（质因数分解与 BFS）、流水线任务最优调度（单调队列优化 DP）、算法题目设计方案（组合回溯）。难度评估为中等（编辑判断）。

本页包含三题完整题意、数据范围、全部样例与可运行 Python 解法。

建议策略：调度题必须检查开头、中间、末尾的跳过长度；组合题按编号递增搜索，先保证总数完整，再截取输出，不能找到三个方案就结束搜索。

第 1 题：因数跳跃

题目描述

给定正整数数组 nums，从下标 0 出发。在下标 i 处，可以选择 nums[i] 的任一质因数 p，跳到 i+p 或 i-p；每个目标分别检查是否在 [0,n-1] 内，不能越界，不取模。判断能否恰好到达下标 n-1。

例如 12 的不同质因数为 2、3，而不是 4、6 或 12。元素为 1 时没有出边；数组只有一个元素时，起点已经是终点。

输入描述

一行非空数组，以空格分隔，不额外输入长度。$1\le n\le 10^4$，$1\le nums[i]\le 10^3$。

输出描述

能到达末尾输出小写 true，否则输出小写 false。

样例 1

输入

5 2 3 5 1 10 7

输出

false

起点只能跳至下标 5；之后只能回到下标 0 或到达下标 3，无法到达末尾。

样例 2

输入

12 2 4 1 1

输出

true

沿下标 0 → 2 → 4，每次使用质因数 2。

样例 3

输入

1 1

输出

false

思路分析

第一步：把移动转为有向边。 下标是节点，当前数的每个不同质因数产生至多两条出边。目标节点的值不一定包含相同质因数，因此不能按无向图使用并查集。

第二步：预处理最小质因子。 令 V 为数组最大值，筛出每个整数的最小质因子。分解时取出质因子 p 并除尽其所有幂，避免重复生成相同步长。1 不产生任何步长。

第三步：BFS 判可达。 起点入队并标记，每次枚举合法且未访问的目标。到达末尾立即返回，否则队列耗尽即不可达。在入队时标记，防止环路导致重复搜索。

正确性说明

质因子分解恰好枚举当前值的所有不同质因数，分别检查左右目标，故生成的边与合法移动完全相同。BFS 只沿合法边扩展，因此访问的节点都能到达；反之，对任意合法路径按长度归纳，其每个节点最终都会被搜索访问。因此末尾被访问当且仅当存在合法跳跃方案。

题解代码

import sys
from collections import deque


def can_reach(nums):
    n = len(nums)
    limit = max(nums)
    smallest = [0] * (limit + 1)
    for p in range(2, limit + 1):
        if smallest[p] == 0:
            for value in range(p, limit + 1, p):
                if smallest[value] == 0:
                    smallest[value] = p
    seen = [False] * n
    seen[0] = True
    queue = deque([0])
    while queue:
        i = queue.popleft()
        if i == n - 1:
            return True
        value = nums[i]
        while value > 1:
            p = smallest[value]
            while value % p == 0:
                value //= p
            for target in (i - p, i + p):
                if 0 <= target < n and not seen[target]:
                    seen[target] = True
                    queue.append(target)
    return False


def solve():
    nums = list(map(int, sys.stdin.readline().split()))
    print('true' if can_reach(nums) else 'false')


if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：$O(V\log\log(V+2)+n\log(V+1))$，其中 V 为最大元素值。筛表后每个下标至多处理一次，每次分解至多进行对数次除法。

空间复杂度：$O(n+V)$，用于输入、访问数组、队列与最小质因子表。

易错点

• 左右目标分别判界，不要求两个方向同时合法。
• 1 不是质因数；重复质因数只需生成一次步长。
• 长度为 1 时即使元素为 1，也应输出 true。

第 2 题：流水线任务最优调度

题目描述

任务按数组顺序排列，每个元素是执行该任务的时间。每个任务可以执行或跳过，要求恰好执行 k 个任务，任意连续跳过的任务数不超过 max_skip，使执行时间总和最小。

开头没有执行的任务、两次执行之间的任务，以及完成最后一个任务后剩余的全部任务，都计入相应的连续跳过段。若无法完成要求，输出 -1。

输入描述

第一行是任务耗时数组，以空格分隔；空行表示空数组。第二行为 k，第三行为 max_skip。数据范围：$0\le n\le 1000$，$1\le cost[i]\le 10^4$，$0\le k\le n$，$0\le max_skip\le 1000$。

输出描述

一个整数，表示最小总耗时；不存在合法方案则为 -1。

样例 1

输入

1 2 3 4 5
3
0

输出

-1

不允许跳过任何任务，却只执行三个，因而无解。

样例 2

输入

3 1 4 2 5
3
2

输出

6

执行第 1、2、4 个任务，总耗时为 6，所有跳过段均不超限。

样例 3

输入

1 100 1 100 1
3
1

输出

3

执行第 1、3、5 个任务。

样例 4

输入

0
1

输出

0

首行为空，表示没有任务；后两行分别为 k=0 和 max_skip=1。复制输入时须保留第一行。

补充自测

输入

8 1 9 2 7
2
1

输出

3

执行编号 2、4（从 1 开始）两个任务，开头、中间、末尾各跳过一个，总耗时为 3。

思路分析

第一步：把全局约束改成位置间隔。 假设最后执行的任务下标为 i，上一次执行下标为 p，则两者之间跳过 i-p-1 个任务，所以 p 必须在 [i-max_skip-1, i-1] 内。

第二步：定义 DP。 f[j][i] 表示恰好执行 j 个任务，且第 j 个任务是下标 i 时的最小总耗时。第一层只有 i <= max_skip 的位置可达，值为 cost[i]；后续层在上述窗口中取上一层最小值，再加 cost[i]。

第三步：使用单调队列。 对同一层，随着 i 向右移动，前驱窗口也单调移动。队列保存上一层下标，对应 DP 值递增；新值不大于队尾时淘汰队尾，下标过旧时淘汰队头。于是每层从枚举全部前驱变为 O(n) 扫描。只需保留前后两层，不需要 O(kn) 的整张表。

第四步：检查尾段和特殊情况。 答案只在 i >= n-1-max_skip 的最后位置中取最小值。k 为 0 时全部任务都是一个跳过段，只有 n <= max_skip 才合法。k 大于 n 时直接无解。

正确性说明

任一合法的 j 次执行方案删去最后一次执行，必落到允许前驱窗口内的某个 f[j-1][p]。反过来，将 i 接到窗口内的任一可达前驱后，中间跳过长度一定合法。转移因此既不漏解也不引入非法解。初始化约束开头跳过段，最终取值约束尾段，单调队列只优化求最小值而不改变转移。

题解代码

import sys
from collections import deque


def min_total_time(cost, k, max_skip):
    n = len(cost)
    if k == 0:
        return 0 if n <= max_skip else -1
    if k > n:
        return -1
    infinity = float('inf')
    prev = [infinity] * n
    for i in range(min(n, max_skip + 1)):
        prev[i] = cost[i]
    for _ in range(2, k + 1):
        current = [infinity] * n
        queue = deque()
        for i in range(1, n):
            while queue and prev[queue[-1]] >= prev[i - 1]:
                queue.pop()
            queue.append(i - 1)
            while queue and queue[0] < i - max_skip - 1:
                queue.popleft()
            if queue and prev[queue[0]] != infinity:
                current[i] = prev[queue[0]] + cost[i]
        prev = current
    answer = min(prev[max(0, n - 1 - max_skip):], default=infinity)
    return -1 if answer == infinity else answer


def solve():
    input = sys.stdin.readline
    cost = list(map(int, input().split()))
    k = int(input())
    max_skip = int(input())
    print(min_total_time(cost, k, max_skip))


if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：常规 k ≥ 1 时 O(nk)，每层各下标进出队列至多一次；包括 k 为 0 的输入读取时，总体上界可写 O(n(k+1))。

空间复杂度：O(n)，输入数组、滚动 DP 数组及队列。

易错点

• 不能在完成第 k 个任务后忽略尾部，否则可能把不可行方案判成最优。
• 前驱最远可到 i-max_skip-1，不是 i-max_skip。
• 空数组需要按行读取；全局 split() 会抹去代表空数组的首行。

第 3 题：算法题目设计方案

题目描述

有 n 个知识点模块，编号从 1 到 n，每个模块有一个正整数难度系数。选择 k 个模块，并按编号递增排列：

• 相邻选中编号之差必须大于冲突阈值 d。
• 难度系数之和必须在闭区间 [low, high] 内。

统计所有合法方案，并按编号数值的字典序输出最小的至多三个方案。总数统计不能只统计打印的方案。

输入描述

第一行五个整数 n、k、d、low、high；第二行 n 个正整数难度系数。数据范围：$1\le n\le 20$，$1\le k\le n$，$0\le d\le n$，$1\le low\le high\le 1000$，每个难度系数在 [1,100] 内。

输出描述

第一行合法方案总数，随后输出按字典序排列的前 min(3, 总数) 个方案，一行一个，编号空格分隔。无方案时只输出 0。

样例 1

输入

5 3 1 10 20
3 5 2 4 6

输出

1
1 3 5

三个编号之间至少相差 2，仅有 1、3、5，难度和为 11。

样例 2

输入

4 2 0 5 15
2 3 4 5

输出

6
1 2
1 3
1 4

任意两个不同编号都不冲突，六种组合的难度和均在范围内。

样例 3

输入

6 3 1 10 30
5 5 5 5 5 5

输出

4
1 3 5
1 3 6
1 4 6

第四个方案为 2、4、6；仍须计入总数，但不打印。

思路分析

第一步：按递增编号构造。 搜索状态包括下一可选编号 start、当前路径和难度和 total。选择编号 i 后，下一个编号至少为 i+d+1，因此不需要额外检查已经满足的冲突条件。

第二步：让遍历顺序就是字典序。 每一层按编号从小到大选，两个完整方案首次不同的位置上，更小编号对应的搜索分支先访问。于是无需先存储并排序全部方案，只保存最早找到的三个，同时持续累加总数。

第三步：进行安全剪枝。 还需要选 remaining 个模块时，当前第一个编号 i 后必须放得下 remaining-1 个间距至少为 d+1 的编号，所以 i <= n-(remaining-1)*(d+1)。难度都为正数，选入当前模块就超过 high 时，可以跳过该模块，但不能结束整层循环，因为后续编号的难度并不保证更大。

正确性说明

每个合法方案只有一种递增编号序列，DFS 会沿唯一分支访问它。编号下界保证冲突约束，数量剪枝只丢弃空间不足的分支，正数和剪枝只丢弃不可能满足上界的分支；选满后检查下界，故计数恰好覆盖所有合法方案。递增枚举保证最先记录的三个方案是数值字典序最小的三个。

题解代码

import sys


def design_plans(difficulty, k, d, low, high):
    n = len(difficulty)
    count = 0
    best = []
    path = []

    def dfs(start, total):
        nonlocal count
        remaining = k - len(path)
        if remaining == 0:
            if low <= total <= high:
                count += 1
                if len(best) < 3:
                    best.append(path.copy())
            return
        last = n - (remaining - 1) * (d + 1)
        for i in range(start, last + 1):
            new_total = total + difficulty[i - 1]
            if new_total > high:
                continue
            path.append(i)
            dfs(i + d + 1, new_total)
            path.pop()

    if 0 <= k <= n:
        dfs(1, 0)
    return count, best


def solve():
    input = sys.stdin.readline
    n, k, d, low, high = map(int, input().split())
    difficulty = list(map(int, input().split()))
    count, best = design_plans(difficulty, k, d, low, high)
    print(count)
    for plan in best:
        print(*plan)


if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：O(n + Σ C(n,t) + k)，求和范围为 t=0 到 k。n 项为输入读取；不计剪枝时，每次尝试对应一条长度不超过 k 的递增序列，每个节点常数次运算，至多复制三个长度 k 的方案。它是指数级枚举上界，不能仅因保留三个方案就写成 O(k)。

空间复杂度：O(n+k)，包括输入、递归路径与栈、至多三个输出方案。递归深度最多为 20，符合本题小规模回溯的限制。

易错点

• 难度上、下界均包含等号，编号差却必须严格大于 d。
• 必须复制路径，不能保存后续会被修改的同一个列表。
• 找到三个方案后仍需搜索，才能得到真实总数。

小结

三题分别练习有向图可达性、滑动窗口优化 DP 和按字典序回溯计数。先严格翻译跳跃方向、首尾间隔与冲突不等式，再考虑优化，可避免大部分边界错误。