055 Jump Game 跳跃游戏

给定一个非负整数数组，您最初位于数组的第一个索引处。
数组中的每个元素表示您在该位置的最大跳跃长度。
确定是否能够到达最后一个索引。
示例：
A = [2,3,1,1,4]，返回 true。
A = [3,2,1,0,4]，返回 false。
详见：https://leetcode.com/problems/jump-game/description/

Java实现：

方法一：

class Solution {

    public boolean canJump(int[] nums) {

        int n=nums.length;

        // maxJump是维护的当前能跳到的最大位置

        int maxJump=0;

        for(int i=0;i<n;++i){

        	// i>maxJump表示无法到达i的位置,失败

			// maxJump >= (n - 1),此时的距离已经足够到达终点，成功

            if(i>maxJump||maxJump>=(n-1)){

                break;

            }

            // nums[i]+i当前跳最远距离 maxJump为i之前跳最远距离

            maxJump=maxJump>(i+nums[i])?maxJump:(i+nums[i]);

        }

        return maxJump>=(n-1);

    }

}

方法二：

class Solution {

    public boolean canJump(int[] nums) {

        int n=nums.length;

        // dp[i]表示当前跳跃的最大距离

        int[] dp=new int[n];

        dp[0]=nums[0];

        // i表示当前距离，也是下标

        for(int i=1;i<n;++i){

        	// i点可达

            if(i<=dp[i-1]){

                dp[i]=dp[i-1]>(nums[i]+i)?dp[i-1]:(nums[i]+i);

            }else{

                dp[i]=dp[i-1];

            }

        }

        return dp[n-1]>=(n-1);

    }

}

参考：https://blog.csdn.net/mine_song/article/details/69791029

巴特西

055 Jump Game 跳跃游戏

最新文章

热门文章