最小请求间隔限流策略2026 华为OD机试真题 5月24日华为OD上机新系统考试真题 100 分题型点击查看华为 OD 机试真题完整目录2026最新华为OD机试新系统卷 双机位C卷 真题题库目录全覆盖题库 逐点算法考点详解题目描述在微服务网关中为了防止某个用户短时间内发送过多请求通常会采用最小请求间隔限流策略即同一个用户相邻两个请求的时间戳之差必须大于等于 minInterval 秒。例如若 minInterval2则请求时间戳为 1 和 3 可以同时通过差为 2但 1 和 2 不能同时通过差为 1。现有一批属于同一用户的请求每个请求带有一个时间戳单位秒整数。网关需要从这批请求中挑选一部分放行使得任意两个被放行的请求时间差都 ≥minInterval。请你计算一共有多少种合法的放行方案包括空集。例如请求时间戳为 [1,3,4]minInterval2则合法的放行方案有[]、[1]、[3]、[4]、[1,3]、[1,4]共6种注意 [3,4] 非法因为差为 12。2026 华为OD机试真题 5月24日华为OD上机新系统考试真题 100 分题型输入描述int[] timestamps整数数组表示每个请求的时间戳可能乱序无重复。int minInterval最小允许的请求间隔秒minInterval≥1。输出描述int合法放行方案的总数。数据规模1≤timestamps.length≤15时间戳取值范围0≤timestamp≤109minInterval 为正整数示例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 个子集直接枚举完全可行算法步骤排序处理将时间戳数组按升序排列。排序后间隔问题变得更容易处理。位掩码枚举使用 0 到 (1 n) - 1 的整数作为掩码其中 - 第 i 位为 1 表示选择第 i 个时间戳 - 第 i 位为 0 表示不选择第 i 个时间戳合法性检查对于每个掩码表示的方案检查任意两对被选中时间戳的间隔是否都 ≥ minInterval。计数统计统计所有合法方案的数量。复杂度分析时间复杂度O(n × 2^n)共有 2^n 个子集对每个子集需要 O(n²) 的时间检查间隔由于 n ≤ 1532768 × 225 ≈ 740万次操作可接受空间复杂度O(n)主要用于存储排序后的时间戳和临时选中的子集正确性证明定理算法返回的计数等于所有满足最小间隔约束的放行方案数量。证明 1.完备性算法遍历了所有 2^n 个可能的放行方案包括空集因为每个请求有放行或不放行两种状态。正确性检查对于每个方案算法检查所有任意两对时间戳 (i, j)确保 timestamps[j] - timestamps[i] ≥ minInterval。由于时间戳已排序只需检查相邻元素即可。计数准确只有通过合法性检查的方案才会被计入答案因此最终计数恰好是合法方案的数量。**Q.E.