目录

题目

思路

Code

题目

题目内容

在微服务网关中。为了防止某个用户短时间内发送过多请求，通常会采用最小请求间隔策略:即同一个用户相邻两个请求的时间戳之差必大于等于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)，
输入描述
int[] timestamps:整数数姐，表示每个请求的时问戳(可能乱序，无重复)。
int minInterval: 最小许的请求间 (秒). minInterval>1.
输出描述
int 合法放行方案的总数。
数据规模
1< timestamps.length < 15
时间戳取值范围 国:0<= timestamp <= 10^9
minInterval为正整数

样例1

输入
1,2,4
2
输出

6

样例2
输入

10
5
输出
2
说明
合法方案:[]、[10]。共2种

思路

排序 + DP。

1. 预处理
对时间戳升序排序。排序后，若 i < j 则 ts[i] <= ts[j]，便于利用单调性判断间隔。

2. 状态定义
dp[i] 表示「以第 i 个时间戳作为最后一个放行请求的所有合法方案数（即第 i 个请求必选）。

3. 状态转移

• 初始：dp[i] = 1，代表只选 timestamps[i] 自身这一种方案。
• 枚举所有 j < i，若 timestamps[i] - timestamps[j] >= minInterval，说明 i 可以接在「以 j 结尾的任意合法方案」之后，形成新的合法方案。
  数学推导：以 j 结尾的方案中，任意两个时间戳已满足间隔 ≥ minInterval，而 i 与 j 的间隔也 ≥ minInterval，又因排序后 i 的时间戳是最大值，所以 i 与该方案中所有时间戳的间隔都 ≥ minInterval（传递性），故可直接累加。
  转移方程：dp[i] = 1 + Σ dp[j]（对所有满足 ts[i] - ts[j] >= minInterval 的 j）。

4. 结果汇总

• 空集算 1 种方案。
• 所有非空方案由 dp[0..n-1] 累加得到。
  最终答案：result = 1 + Σ dp[i]

5. 复杂度

• 时间：O(n²)，n < 15，完全可接受。
• 空间：O(n)。

Code

import sys

def solve(timestamps, minInterval):
    # 先将时间戳从小到大排序
    timestamps.sort()
    n = len(timestamps)
    # dp[i] 表示以第 i 个时间戳为最后一个放行请求的方案数（即该请求必选）
    dp = [0] * n
    for i in range(n):
        # 只选第 i 个本身：1 种方案
        dp[i] = 1
        # 枚举前面所有满足间隔 >= minInterval 的请求 j
        for j in range(i):
            if timestamps[i] - timestamps[j] >= minInterval:
                dp[i] += dp[j]
    # 总方案数 = 空集(1) + 所有以某个请求结尾的方案数
    return 1 + sum(dp)


def main():
    data = sys.stdin.read().strip().splitlines()
    if not data:
        return
    # 第一行：逗号分隔的时间戳
    timestamps = list(map(int, data[0].strip().split(',')))
    # 第二行：minInterval
    minInterval = int(data[1].strip())
    print(solve(timestamps, minInterval))


if __name__ == "__main__":
    main()

JS

const readline = require('readline');

function solve(timestamps, minInterval) {
    // 先排序
    timestamps.sort((a, b) => a - b);
    const n = timestamps.length;
    // dp[i] 表示以第 i 个时间戳为最后一个放行请求的方案数
    const dp = new Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        dp[i] = 1;  // 只选第 i 个本身为 1 种方案
        for (let j = 0; j < i; j++) {
            if (timestamps[i] - timestamps[j] >= minInterval) {
                dp[i] += dp[j];
            }
        }
    }
    // 总方案数 = 空集 + 所有非空子集
    let total = 1;
    for (const v of dp) total += v;
    return total;
}

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let lineCount = 0;
let timestamps, minInterval;

rl.on('line', (line) => {
    if (lineCount === 0) {
        timestamps = line.trim().split(',').map(Number);
        lineCount++;
    } else {
        minInterval = parseInt(line.trim(), 10);
        console.log(solve(timestamps, minInterval));
        rl.close();
    }
});

【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java&Go】：Java&Go真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】

华为OD机试:二本院校有机会吗?
有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。