讲师中心 微信公众号
AI工具推荐 视频效率加速

如何找到避开所有障碍物的最小固定跳跃长度

雨涛吖_7753

雨涛吖_7753

发布时间:2026-01-17 14:28:08

|

542人浏览过

|

来源于php中文网

原创

如何找到避开所有障碍物的最小固定跳跃长度

给定一条直线上障碍物的坐标数组,从原点0向右跳跃,每次跳跃长度必须相同且为整数;目标是找出能完全避开所有障碍物的最小跳跃长度。

在 CodeSignal Arcade 第5关“Avoid Obstacles”中,核心问题在于:你从坐标 0 出发,只能以固定整数步长向右跳跃(如每次跳 2、3、4…),要求不踩中任何一个障碍物坐标(即所有落点 0, jump, 2×jump, 3×jump, ... 均不能等于数组中任意一个值)。需返回满足条件的最小正整数跳跃长度

你的原始解法逻辑基本正确:对障碍数组排序后,枚举可能的跳跃长度 jump(从 2 开始),再模拟跳跃过程(用 binarySearch 快速判断落点是否为障碍),一旦发现某 jump 能全程避开所有障碍,立即返回。

但存在一个关键边界缺陷:

for (int jump = 2; jump <= 1000; jump++) { ... }

该循环上限设为 1000,而题目约束仅保证 inputArray[i] ≤ 1000,并未限制答案上限。反例正是答案为 1001 的最坏情况:当障碍物填满 [1, 2, 3, ..., 1000] 时,任何 ≤1000 的跳跃长度 k 都必然在某次落地时命中 k(因为 k ∈ [1,1000]),因此唯一安全的最小步长是 1001 —— 此时首次落地在 1001,已越过全部障碍。

Cad
Cad

CAD参考工具

下载

修复方案:将循环上界提升至 1001(或更稳妥地设为 max(obstacles) + 1):

int solution(int[] a) {
    Arrays.sort(a);
    int maxObstacle = a[a.length - 1];

    // 枚举跳跃长度:从 1 开始(注意:jump=1 必然失败,但逻辑应覆盖)
    // 上界必须至少为 maxObstacle + 1,因最坏情况下答案就是它
    for (int jump = 1; jump <= maxObstacle + 1; jump++) {
        boolean canAvoid = true;

        // 检查所有可能落点:jump, 2*jump, 3*jump, ... 直到超过最大障碍
        for (int pos = jump; pos <= maxObstacle; pos += jump) {
            // 使用 binarySearch 前需确保数组已排序(已做)
            if (Arrays.binarySearch(a, pos) >= 0) {
                canAvoid = false;
                break;
            }
        }

        if (canAvoid) {
            return jump;
        }
    }

    return maxObstacle + 1; // 理论上不会执行到这里,但保底返回
}

? 优化说明与注意事项

  • 不必模拟“连续跳跃”过程(如 now = next),只需检查所有形如 k × jump 且 ≤ maxObstacle 的点是否全都不在障碍数组中——更简洁、高效;
  • 起始 jump 可从 1 开始,逻辑更完整(尽管 jump=1 在有障碍时必失败,但代码健壮性更好);
  • 时间复杂度为 O(M × log N),其中 M = maxObstacle + 1 ≤ 1001,N = a.length ≤ 1000,完全满足 3 秒时限;
  • 无需额外 flag 变量,用 canAvoid 清晰表达意图;
  • 最终返回的是首个合法 jump,自然满足“最小”要求。

总结:算法本质是寻找一个最小正整数 j,使得集合 {j, 2j, 3j, ..., ⌊max/a⌋×j} 与障碍集无交集。边界意识(尤其是答案可能严格大于所有输入值)是此类枚举题的关键陷阱。

热门AI工具

更多
WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

VibeKnow
VibeKnow Hot

一款AI视频创作工具,主要用于全球首个AI知识视频创作平台,文档、文章、网页,一键生成视频,适合需要提升相关任务效率的用户。

切问学术

切问学术是一款AI论文写作工具,复旦大学NLP团队推出的AI学术智能体。

SkildArt
SkildArt Hot

SkildArt是一款AI文本写作工具,一站式 AI 视觉创作平台。

咔片AIPPT

一款在线AI演示文稿制作工具,可根据主题和内容需求辅助生成PPT结构与页面,提高演示材料制作效率。

立刻MV
立刻MV Hot

立刻MV是一款AI文本写作工具,AI 音乐视频(MV)创作工具。

DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

Atoms
Atoms Hot

Atoms是一款AI智能体工具,第一支自动构建真实业务的 AI 团队。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

相关专题

更多
length函数用法
length函数用法

length函数用于返回指定字符串的字符数或字节数。可以用于计算字符串的长度,以便在查询和处理字符串数据时进行操作和判断。 需要注意的是length函数计算的是字符串的字符数,而不是字节数。对于多字节字符集,一个字符可能由多个字节组成。因此,length函数在计算字符串长度时会将多字节字符作为一个字符来计算。更多关于length函数的用法,大家可以阅读本专题下面的文章。

1667

2023.09.19

页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

4596

2023.08.14

Aionclaw智能助手介绍
Aionclaw智能助手介绍

本专题汇总了AionClaw(AI龙虾助手)的功能介绍与在线使用入口。AionClaw是杭州趣猿人工智能有限公司推出的桌面级AI智能体,能直接在电脑上读写文件、运行脚本、操作浏览器,自动交付Word、PPT、Excel等成品。

20

2026.09.20

AionClaw AI智能体与电脑自动化任务执行功能使用教程
AionClaw AI智能体与电脑自动化任务执行功能使用教程

AionClaw专题整理AI智能体与电脑自动化相关功能使用教程,涵盖安装部署、AI任务执行、Skills技能、文件处理、浏览器控制、电脑操作、持久记忆、聊天工具连接以及办公、编程和内容创作等功能,帮助用户快速掌握AionClaw的实际使用方法。

0

2026.09.20

AI视频生成软件推荐
AI视频生成软件推荐

本专题汇总了当前主流的AI视频生成软件推荐与排行榜单,涵盖seko、AniShort、剧云、Lovart、LiblibAI及立刻mv等热门工具。同时整理了各软件在文生视频、图生视频、时长限制、画质表现及免费额度等方面的差异对比,助您快速选对适合创作需求的AI视频生成工具。

180

2026.09.16

ai生成视频的工具免费版合集
ai生成视频的工具免费版合集

本专题汇总了当前免费AI生成视频工具的排行榜与推荐清单,涵盖seko、讯飞智作、AniShort及剧云、Lovart等多模型集成平台。同时整理了各工具的免费额度、输出时长、水印政策及适用场景差异,助您快速选择合适工具开启AI视频创作。

100

2026.09.16

Pandas时间序列分析与可视化报表
Pandas时间序列分析与可视化报表

本专题整理Pandas日期转换、时间索引、重采样、滚动窗口、时区处理、plot绘图、Styler表格样式和报表输出方法。

80

2026.09.16

Pandas数据筛选索引与清洗处理
Pandas数据筛选索引与清洗处理

本专题整理Pandas中的loc、iloc、条件筛选、query查询、缺失值处理、重复值删除、类型转换和字符串列清洗方法。

60

2026.09.16

Pandas数据读取导入与文件导出处理
Pandas数据读取导入与文件导出处理

本专题整理Pandas读取CSV、Excel、JSON、SQL、Parquet等文件的方法,以及to_csv、to_excel、to_sql和to_parquet等常用数据导出流程。

40

2026.09.16

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
热门推荐
/
最新课程
关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn