目录题目思路Code题目题目内容在微服务网关中。为了防止某个用户短时间内发送过多请求通常会采用最小请求间隔策略:即同一个用户相邻两个请求的时间戳之差必大于等于minInterval 秒若minInterval2.则请求时间戳为1和3可以同时通过(差为2).但1和2不能时通过(差为1)现有一批属于同一用户的请求每个请求带有一个时间戳(单位:秒整数)。网关需要从这批请求中挑选一部分放行使得任意两个被放行的请求时间差都大于等于minInterval 请你计算一共有多少种合法的放行方案(包括空集)。例.请求为[1,3,4]. minInterval 2.则合法的方案有:[], [1], [3], [4], [1,3], [1,4].共6种(注意[3,4]非法因为差为12)输入描述int[] timestamps:整数数姐表示每个请求的时问戳(可能乱序无重复)。int minInterval: 最小许的请求间 (秒). minInterval1.输出描述int 合法放行方案的总数。数据规模1 timestamps.length 15时间戳取值范围 国:0 timestamp 10^9minInterval为正整数样例1输入1,2,42输出6样例2输入105输出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)。Codeimport 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()JSconst 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机试真题PythonJSJavaGo合集】【超值优惠】Py/JS/Java/Go合集【华为od机试真题Python】Python真题题库【华为od机试真题JavaScript】JavaScript真题题库【华为od机试真题JavaGo】JavaGo真题题库【华为od机试真题C】C真题题库【华为od机试真题C语言】C语言真题题库【华为od面试手撕代码题库】面试手撕代码题库【华为od机试面试交流群】【文章底部有二维码链接可扫码加交流群】华为OD机试:二本院校有机会吗?有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。