跳跃游戏

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

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

暴力解法，深度优先法，尝试每一种走法，适当剪枝，但是依然会超时

class Solution {

    private static Map<Integer,Integer> book;

    public boolean canJump(int[] nums) {
        book = new HashMap<>();
        List<Integer> ans = new ArrayList<>();
        int maxStep = nums.length - 1;
        int curMaxStep = Math.min(nums[0],maxStep);
        dfs(nums,0,ans,curMaxStep);
        return ans.size() > 0;
    }

    private void dfs(int[] nums,int index,List<Integer> ans,int curMaxStep){
        if(index == nums.length -1 || ans.size() > 0){
            //到达终点
            ans.add(1);
            return;
        }
        int val = nums[index];
        //尝试可以跳跃的每一步
        int maxStep = nums.length - 1 - index;
        int canJumpStep = Math.min(val,maxStep);

        //如果当前可以跳的最远距离都比之前跳过的最大距离短，就不用尝试了
        if (index + canJumpStep < curMaxStep){
            return;
        }else{
            curMaxStep = index + canJumpStep;
        }

        for(int i=canJumpStep;i>0;i--){
            //下一步的坐标
            int nextStep = index+i;
            if(book.get(nextStep) != null || nextStep > nums.length)
                continue;
            //标记这步已经尝试过了
            book.put(nextStep,1);
            dfs(nums,nextStep,ans,curMaxStep);
            if(ans.size() > 0)
                return;
        }
    }
}

第二种解法：
思路：将0看做是沼泽地，如果0左边的数跳不过去，说明这个数相当于一个陷阱，那就索性将这个数也置为0，这样一直向左走。

class Solution {

    public boolean canJump(int[] nums) {
        int len = nums.length;
        //先判断一些特殊值
        if(len == 0 || len == 1) return true;
        if(len == 2) return nums[0] > 0;
        if(nums[0] == 0) return false;

        int right = len-3;
        int maxZeroIndex = -1;
        while(right >= 0){
            int cur = nums[right];
            if(cur > 0){
                //当前数大于0
                //判断右边是不是0
                if(nums[right+1] == 0){
                    //右边的数是0
                    if(maxZeroIndex == -1)
                        maxZeroIndex = right+1;
                    //判断当前这个数跳最远能不能跳出最右边的0
                    int target = cur + right;
                    if(target > maxZeroIndex){
                        //说明能跳出最远的0
                        maxZeroIndex = -1;
                    }else{
                        //跳不出去，将当前值置为0
                        nums[right] = 0;
                    }
                }
            }else{
                //当前数等于0
                if(maxZeroIndex == -1)
                    maxZeroIndex = right;
            }
            right--;
        }
        if(maxZeroIndex == -1)
            return true;
        return false;
    }

}

贪心算法：

class Solution {

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

}