2026 华为OD机试真题 5月24日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

在微服务网关中，为了防止某个用户短时间内发送过多请求，通常会采用最小请求间隔限流策略：即同一个用户相邻两个请求的时间戳之差必须大于等于 minInterval 秒。例如，若 minInterval=2，则请求时间戳为 1 和 3 可以同时通过（差为 2），但 1 和 2 不能同时通过（差为 1）。

现有一批属于同一用户的请求，每个请求带有一个时间戳（单位：秒，整数）。网关需要从这批请求中挑选一部分放行，使得任意两个被放行的请求时间差都 ≥minInterval。请你计算一共有多少种合法的放行方案（包括空集）。

例如，请求时间戳为 [1,3,4]，minInterval=2，则合法的放行方案有：[]、[1]、[3]、[4]、[1,3]、[1,4]，共 6 种（注意 [3,4] 非法，因为差为 1<2）。

2026 华为OD机试真题 5月24日华为OD上机新系统考试真题 100 分题型

输入描述

• int[] timestamps：整数数组，表示每个请求的时间戳（可能乱序，无重复）。
• int minInterval：最小允许的请求间隔（秒），minInterval≥1。

输出描述

• int：合法放行方案的总数。

数据规模

• 1≤timestamps.length≤15
• 时间戳取值范围：0≤timestamp≤109
• minInterval 为正整数

示例1

输入

[1,2,4],2

输出

6

说明

合法方案：[]、[1]、[2]、[4]、[1,4]、[2,4]，共 6 种

示例2

输入

[10],5

输出

2

说明

合法方案：[]、[10]，共 2 种

解题思路

核心思想

本题的核心在于枚举所有可能的放行方案，并验证其合法性。

关键观察：

1. 给定 n 个请求时间戳 (1 ≤ n ≤ 15)，我们可以枚举所有可能的放行子集
2. 对于每个子集，需要验证任意两个被选中的时间戳之间的间隔都 ≥ minInterval
3. 由于 n ≤ 15，最多有 2^15 = 32768 个子集，直接枚举完全可行

算法步骤

1. 排序处理：将时间戳数组按升序排列。排序后，间隔问题变得更容易处理。

2. 位掩码枚举：使用 0 到 (1 << n) - 1 的整数作为掩码，其中：

   • 第 i 位为 1 表示选择第 i 个时间戳
   • 第 i 位为 0 表示不选择第 i 个时间戳

3. 合法性检查：对于每个掩码表示的方案，检查任意两对被选中时间戳的间隔是否都 ≥ minInterval。

4. 计数统计：统计所有合法方案的数量。

复杂度分析

• 时间复杂度：O(n × 2^n)

  • 共有 2^n 个子集
  • 对每个子集需要 O(n²) 的时间检查间隔
  • 由于 n ≤ 15，32768 × 225 ≈ 740万次操作，可接受

• 空间复杂度：O(n)

  • 主要用于存储排序后的时间戳和临时选中的子集

正确性证明

定理：算法返回的计数等于所有满足最小间隔约束的放行方案数量。

证明：

1. 完备性：算法遍历了所有 2^n 个可能的放行方案（包括空集），因为每个请求有"放行"或"不放行"两种状态。

2. 正确性检查：对于每个方案，算法检查所有任意两对时间戳 (i, j)，确保 timestamps[j] - timestamps[i] ≥ minInterval。由于时间戳已排序，只需检查相邻元素即可。

3. 计数准确：只有通过合法性检查的方案才会被计入答案，因此最终计数恰好是合法方案的数量。

**Q.E.