当前位置: 首页 > article >正文

LeetCode-跳跃游戏 II

方法一:反向查找出发位置

我们的目标是到达数组的最后一个位置,因此我们可以考虑最后一步跳跃前所在的位置,该位置通过跳跃能够到达最后一个位置。

如果有多个位置通过跳跃都能够到达最后一个位置,那么我们应该如何进行选择呢?直观上来看,我们可以「贪心」地选择距离最后一个位置最远的那个位置,也就是对应下标最小的那个位置。因此,我们可以从左到右遍历数组,选择第一个满足要求的位置。

找到最后一步跳跃前所在的位置之后,我们继续贪心地寻找倒数第二步跳跃前所在的位置,以此类推,直到找到数组的开始位置。

var jump = function(nums) {
    let position = nums.length - 1;
    let steps = 0;
    while (position > 0) {
        for (let i = 0; i < position; i++) {
            if (i + nums[i] >= position) {
                position = i;
                steps++;
                break;
            }
        }
    }
    return steps;
};


http://www.kler.cn/a/587600.html

相关文章:

  • std::invoke详解
  • 【C++】string类
  • <rust><tauri><GUI>基于tauri和rust,编写一个二维码生成器
  • 【鸿蒙开发】Hi3861学习笔记-Visual Studio Code安装(New)
  • 在线招聘小程序:AI简历筛选与精准职位推荐服务
  • 【生日蛋糕——DFS剪枝优化】
  • 网络安全系统集成
  • 微信小程序项目 tabBar 配置问题:“pages/mine/mine“ need in [“pages“]
  • 缓存之美:Guava Cache 相比于 Caffeine 差在哪里?
  • 游戏引擎学习第157天
  • neo4j中常用cql命令汇总(基础版)
  • Spark eventlog
  • [文献阅读] 可变形卷积DCN - Deformable Convolutional Networks
  • 服务性能防腐体系:基于自动化压测的熔断机制
  • 【软考-架构】3.4、数据库新技术-SQL语言
  • 基于牛优化( OX Optimizer,OX)算法的多个无人机协同路径规划(可以自定义无人机数量及起始点),MATLAB代码
  • 【eNSP实战】将路由器配置为DHCP服务器
  • 数据库原理10
  • 锂电池保护板测试仪:守护能源安全的科技卫士
  • 【STM32】USART串口收发HEX数据包收发文本数据包