8.5跳跃游戏(LC55-M)

算法:

其实跳几步无所谓,关键在于可跳的覆盖范围!

不一定非要明确一次究竟跳几步,每次取最大的跳跃步数,这个就是可以跳跃的覆盖范围。

这个范围内,别管是怎么跳的,反正一定可以跳过来。

那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点!

每次移动取最大跳跃步数(得到最大的覆盖范围),每移动一个单位,就更新最大覆盖范围。

局部最优:每次取最大跳跃步数(取最大覆盖范围)

整体最优解:最后得到整体最大覆盖范围,看是否能到终点

正确代码:

class Solution {
    public boolean canJump(int[] nums) {
       int coverrange = 0;
       if(nums.length==1){
           return true;
       }
       //i表示覆盖范围内可以跳跃的索引下标
       for(int i=0;i<=coverrange;i++){
           coverrange = Math.max(coverrange, i+nums[i]);
           if (coverrange>=nums.length-1){
               return true;
           }

       }
       return false;

    }
}

时间空间复杂度:

时间复杂度:O(n),其中 n为数组的大小。只需要访问 nums 数组一遍,共 n个位置。

空间复杂度:O(1),不需要额外的空间开销。

相关推荐

  1. 55.跳跃游戏

    2024-01-23 07:30:07       52 阅读
  2. 55. 跳跃游戏

    2024-01-23 07:30:07       56 阅读
  3. 55. 跳跃游戏

    2024-01-23 07:30:07       41 阅读
  4. 55. 跳跃游戏

    2024-01-23 07:30:07       40 阅读
  5. leetcode 55.跳跃游戏

    2024-01-23 07:30:07       45 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-01-23 07:30:07       98 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-01-23 07:30:07       106 阅读
  3. 在Django里面运行非项目文件

    2024-01-23 07:30:07       87 阅读
  4. Python语言-面向对象

    2024-01-23 07:30:07       96 阅读

热门阅读

  1. Selenium 自动化截取网页指定区域截图

    2024-01-23 07:30:07       49 阅读
  2. Flink对接Kafka的topic数据消费offset设置参数

    2024-01-23 07:30:07       61 阅读
  3. Eureka基础知识总结(微服务)

    2024-01-23 07:30:07       56 阅读
  4. jupyter notebook删除kernel & conda 删除虚拟环境

    2024-01-23 07:30:07       50 阅读
  5. Chrome扩展之通信

    2024-01-23 07:30:07       52 阅读
  6. C语言常见面试题:什么是宏,宏的作用是什么?

    2024-01-23 07:30:07       38 阅读
  7. Linux Bash编程man帮助手册

    2024-01-23 07:30:07       45 阅读
  8. 【数据结构】树套树

    2024-01-23 07:30:07       69 阅读
  9. 【webrtc】AudioSendStream的创建

    2024-01-23 07:30:07       59 阅读