当前位置:首页 » 《随便一记》 » 正文

力扣hot100 55题跳跃游戏打卡_getinobacar的博客

14 人参与  2022年05月12日 13:59  分类 : 《随便一记》  评论

点击全文阅读


2021年11月22日

55. 跳跃游戏

给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

 解题思路:从题目的要求来看做法应该是动态规划或者是贪心算法,此题两种算法均可解决。

方法一:贪心算法

用数组下标来记录位置的话,我们可以使用一个变量 rightMax 用来记录能够到达数组位置的最大值,通过for循环来不断的修改rightMax的值,一旦for循环中变量 i 走到的位置比目前的rightMax大,则循环结束,返回false。如果循环结束,没有问题,则返回true。

其中rightMax的更新方程为:Math.max(rightMax,i + nums[i])。

代码实现及提交结果如下图所示:

class Solution {
    public boolean canJump(int[] nums) {
        int len = nums.length;
        int rightmax = 0;
        for(int i = 0 ; i < len ; i++ ){
            if(i <= rightmax){
                rightmax = Math.max(rightmax,i + nums[i]);
            }else{
                return false;
            }
        }
        return true;
    }
}

方法二:动态规划

动态规划方法的大致思路就是定义一个dp数组用来存储每个位置还能够向前走的最大步数,状态转移方程为:dp[i] = Math.max(dp[i-1]-1,num[i]),但是此题因为只需要使用 dp[i-1] 是否等于 0 来判断是否还能接着往回走,所以仅仅使用一个变量来保存dp[i]的值即可。

2.1:正常使用dp数组来进行计算

设定一个dp数组,dp[i]表示在下标i处能够跳跃的最大值。
对于dp[i],它等于dp[i-1]跳一格到达i处后剩余的步数,和nums[i]的最大值。因此得出状态转移方程为:dp[i]=max(dp[i-1]-1,nums[i])
边界条件:dp[0]=nums[0]
在每次循环开始,我们判断dp[i-1]是否等于0,若是,则不可能到达下标i处,dp[i] = 0;

代码和运行结果如下:

class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length == 1){
            return true;
        }
        int len = nums.length;
        int dp[] = new int[len];
        dp[0] = nums[0];
        for(int i = 1 ; i < len ; i++ ){
            if(dp[i-1] > 0){
                dp[i] = Math.max(dp[i-1]-1,nums[i]);
            }else{
                dp[i] = 0;
            }
        }
        for(int i = 0 ; i < len ;i++){
            if(dp[i] == 0 && i != len-1){
                return false;
            }
        }
        return true;
    }
}

 2.1:使用常量来代替dp[i]进行计算
因为转移状态数组dp只和前一位有关,因此可以用滚动数组简化空间复杂度,并且每次之前进行检查 dp[i-1] 是否等于 0 ,如果等于,则说明根本到不了下一个坐标,直接返回false。

代码和结果如下:

class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length == 1){
            return true;
        }
        int len = nums.length;
        int  a = nums[0];
        for(int i = 1 ; i < len ; i++ ){
            if(a==0){
                return false;
            }else{
                a = Math.max(a-1,nums[i]);
            }
        }
        return true;
    }
}

 

总结:动态规划和贪心相比:贪心只是每一步都是最优,并且不考虑上一步的结果,但是动态规划的动态转移方程需要考虑到上一步甚至更上一步的状态。从两个方程便可明显的区别,贪心算法中,方程为:rightmax = Math.max(rightmax,i + nums[i]);很显然并没有用到上一步的结果。但是动态规划解题的状态转移方程当中,方程为:max = Math.max(dp[i-1]-1,num[i]),用到了上一步的最优结果。这也是区分贪心还是动态规划的一个地方。菜鸡,如有说错的地方,还望指出。


点击全文阅读


本文链接:http://zhangshiyu.com/post/39993.html

数组  方程  下标  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 夫君立筷子定我灾星罪名,我改嫁冷宫皇子后他追悔莫及好评_赵荀孟如安青瑶精心编著_小说后续在线阅读_无删减免费完结_
  • 邻居低素质,而我没素质独家番外_老太太赖皮欣欣超长版_小说后续在线阅读_无删减免费完结_
  • 重生后我转嫁首富瘸腿独子,总裁前夫却疯了一口气看完_妹妹傅云琛沈明辉独家番外_小说后续在线阅读_无删减免费完结_
  • 我拒绝给系花捐款后,全系同学悔疯了在线阅读_小说后续在线阅读_无删减免费完结_
  • 我让位给女友的透视眼竹马,他却说如果能重生再也不来了。虐心反转_玉石林若女友推荐_小说后续在线阅读_无删减免费完结_
  • 相国独子的丫鬟砸坏我的玉佩后,我当场拒婚阅读_玉佩陈郡谢氏全新_小说后续在线阅读_无删减免费完结_
  • 手术时,我看着病人惨死最新试读_淼淼陆知衍姜颜全本完结_小说后续在线阅读_无删减免费完结_
  • 男友霸道给我开黑卡,转头却骂我是捞女最新章节_肖年顾客黑卡热文_小说后续在线阅读_无删减免费完结_
  • 他在回忆尽头全集_贺南舟许清梨叶絮完结txt_小说后续在线阅读_无删减免费完结_
  • 旅游结婚那天未婚夫另娶女秘书,我让他们一无所有连载_老公迎宾超长版_小说后续在线阅读_无删减免费完结_
  • 完结文异界修仙我的直播间能打赏核弹列表_完结文异界修仙我的直播间能打赏核弹(江流年沈红菱)
  • 全书浏览陪弟弟混骑行圈,离婚你哭什么?(韩星河柳千雪)_陪弟弟混骑行圈,离婚你哭什么?(韩星河柳千雪)全书结局

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1