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;
    } 
}