LeetCode - 跳跃游戏

Leetcode.55

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
示例1：
?输入**: [2,3,1,1,4]
?输出: true
?解释: 位置0 -> 位置1 -> 末尾
示例2：
?输入: [3,2,1,0,4]
?输出: false
?解释: 最远到达位置3，之后再无法向后跳

思路一：贪心法

贪心算法的思路跟简单，从前向后遍历每个位置，若当前位置能达到，则更新可以到达的最远的位置，最后若能到达最后一个位置返回true。

class Solution {
    public boolean canJump(int[] nums) {
        int maxposition = 0;
        for(int i = 0; i < nums.length; i++){
            if(maxposition >= i){  // 能到达当前位置则更新可以到达的最远位置
                maxposition = maxposition > (i + nums[i]) ? maxposition : i + nums[i];
            }
            else{   //当前位置不可到达，返回false
                return false;
            }
        }
        return true;
    }
}

思路二：从后往前遍历（不知道叫什么方法好）

如果最后一个位置可以到达，那在它的前面一定存在位置i,i到最后一个位置的距离小于等于nums[i]。这么讲好像不是很清楚，先看代码吧

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

LeetCode - 跳跃游戏

原文：https://www.cnblogs.com/rezero/p/13040311.html