leetcode(55)跳跃游戏

红太狼 2021-11-01 08:30 332阅读 0赞

跳跃游戏

1、解题思路：自底向上，动态规划

class Solution {
        public boolean canJump(int[] nums) {
            int len = nums.length;
            if(len<=1){
                return true;
            }
            boolean[] temps = new boolean[len];
            return canJump2(nums,len,0,temps);
        }
        public boolean canJump2(int[] nums,int len,int start,boolean[] temps){
            if(temps[start]){
               return false; 
            }
            if(start+nums[start]>=len-1){
                return true;
            }
            for(int i=nums[start];i>0;i--){
                if(canJump2(nums,len,start+i,temps)){
                    return true;
                }
            }
            temps[start]=true;
            return false;
        }
    }

2、动态规划，自顶向下

3、一种很巧的方法

解题思路：从右向左进行遍历，始终记住最左边的可以到达的点，这样子，如果最左边的点等于0，证明就可以到达了。

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

转载于:https://www.cnblogs.com/erdanyang/p/11140528.html

发表评论取消回复

表情：

评论列表（有 0 条评论，332人围观）

还没有评论，来说两句吧...

相关阅读

相关 Leetcode 55. 跳跃游戏

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

港控/mmm°/ 2022年10月14日 01:14/ 0 赞/ 177 阅读

相关 Leetcode 55. 跳跃游戏

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

小灰灰/ 2022年09月14日 14:20/ 0 赞/ 179 阅读

相关 leetcode55跳跃游戏

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

你的名字/ 2022年09月04日 06:41/ 0 赞/ 217 阅读

相关 leetcode 55 跳跃游戏

前言题目：[55. 跳跃游戏][55.] 参考题解：[跳跃游戏-代码随想录][-] -------------------- 提交代码方法一：回溯

偏执的太偏执、/ 2022年08月28日 09:00/ 0 赞/ 165 阅读

相关【LeetCode】55. 跳跃游戏

题目链接：[https://leetcode-cn.com/problems/jump-game/description/][https_leetcode-cn.com_pro

ゝ一纸荒年。/ 2022年05月10日 15:10/ 0 赞/ 207 阅读

相关 leetcode:55. 跳跃游戏

题目: 给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。示例 1: 输入

不念不忘少年蓝@/ 2022年04月08日 09:58/ 0 赞/ 263 阅读

相关 leetcode 55. 跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。示例 1: 输入: [2,

旧城等待，/ 2022年01月18日 23:35/ 0 赞/ 271 阅读

相关 leetcode:55.跳跃游戏

题目描述：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。示例1：

深碍√TFBOYSˉ_/ 2021年12月18日 06:19/ 0 赞/ 267 阅读

相关 leetcode(55)跳跃游戏

跳跃游戏 1、解题思路：自底向上，动态规划 class Solution { public boolean canJump(int[] nums)

红太狼/ 2021年11月01日 08:30/ 0 赞/ 333 阅读

相关 LeetCode55. 跳跃游戏

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

拼搏现实的明天。/ 2021年09月26日 20:14/ 0 赞/ 313 阅读