LeetCode-Java：55.跳跃游戏

题目

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

解

①暴力递归法，将情况分解为当前元素是0则此路不通，非0的话看元素是几就递归几次，如果出现下标是最后一个元素的话就说明找到一条通路。此解超出时间限制。

class Solution {
    private boolean can=false;
    public boolean canJump(int[] nums) {
        dfs(nums,0);
        return can;
    }
    private void dfs(int[] nums,int index){
        //数组，当前下标
        if(index==nums.length-1){
            can=true;
            return;
        }
        else if(nums[index]==0){
            //如果当前的下标元素是0，就返回
            return;
        }
        for(int i=1;i<=nums[index];i++){
            if(index+i>=nums.length){
                break;
            }
            dfs(nums,index+i);
        }
    }
}

②用一个数组遍历所有元素，考虑了各种可能情况，用了很多if-else。简单说，是找到一个元素为0的，然后存储当前下标，往前一个个回溯，查找上一个元素的数据加上元素的下标能否跳过0，如果可以跳过0，则不再向前查找，从跳过的部分开始继续向下。超过99%，50min50s完成

class Solution {
    public boolean canJump(int[] nums) {
       int index_now = 0;
        boolean zero = false;
        for (int i = 0; i < nums.length; ) {
            if (zero == true) {
                //向前回溯想办法跳过index_now的那个0
                if (i == -1) {
                    //如果数组下标变成-1，则表示找不到办法，返回假
                    return false;
                }
                if (nums[i] + i > index_now) {
                    //如果可以跳过存储的0位置
                    if(nums[i]+i>=nums.length){
                        //如果跳过后数组已经遍历完成，则返回真
                        return true;
                    }
                    zero = false;
                    i += nums[i];
                } else {
                    i--;
                }
            }
            else if (nums[i] == 0) {
                //如果当前元素是0，则向上寻找跳过该零的方法
                index_now = i;//记录当前0的位置,找办法跳过
                zero = true;//设置回溯条件，为true时要i--找到可以跳过这个0元素的情况
                if(i==nums.length-1)return true;
                i--;
            } else {
                if (i + nums[i] > nums.length - 1) {
                    //如果往下走会超过数组大小，返回真
                    return true;
                }
                i = i + nums[i];
            }
        }
        return false;
    } 
}

③leetcode解题思路，详细见注释

class Solution {
    public boolean canJump(int[] nums) {
        //如果一个位置可以到达，那么左侧的所有位置都应该可以到达
        int max=0;
        for(int i=0;i<nums.length;i++){
            //如果当前元素已经超过了能到达的最远距离，就说明不能到达数组最后
            if(i>max) return false;
            max=Math.max(max,nums[i]+i);//记录当前能到达的最远距离
        }
        return true;
    } 
}