企业官网建设流程全解析

目录

题目

思路

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。让他帮助你查询原因。