跳躍游戲

給定一個非負整數(shù)數(shù)組爸黄，你最初位于數(shù)組的第一個位置瓮下。

數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度域庇。

判斷你是否能夠到達最后一個位置该编。

示例 1:

輸入: [2,3,1,1,4]
輸出: true
解釋: 我們可以先跳 1 步赠摇，從位置 0 到達 位置 1, 然后再從位置 1 跳 3 步到達最后一個位置

示例 2:

輸入: [3,2,1,0,4]
輸出: false
解釋: 無論怎樣货徙，你總會到達索引為 3 的位置芍瑞。但該位置的最大跳躍長度是 0 晨仑， 所以你永遠不可能到達最后一個位置

方法一：遞歸（超時）

public boolean canJump(int[] nums) {
    return dfs(nums, 0);
}

public boolean dfs(int[] nums, int pos) {
    if (pos >= nums.length - 1) {//應該是>=，因為可能跳過了最后一個位置
        return true;
    }
    for (int i = 1; i <= nums[pos]; i++) {
        if (dfs(nums, pos + i)) {
            return true;
        }
    }
    return false;
}

方法二：記憶優(yōu)化

public boolean canJump(int[] nums) {
    int[] dp = new int[nums.length - 1];
    return dfs(nums, 0, dp);
}

public boolean dfs(int[] nums, int pos, int[] dp) {
    if (pos >= nums.length - 1) {
        return true;
    }
    if (dp[pos] != 0) {
        return dp[pos] == 1;
    }
    for (int i = 1; i <= nums[pos]; i++) {
        if (dfs(nums, pos + i, dp)) {
            dp[pos] = 1;
            return true;
        }
    }
    dp[pos] = -1;
    return false;
}

貪心：
方法三：可以到達最遠位置
在遍歷數(shù)組過程中，依次記錄能到達的最遠位置洪己，如果i大于能到達的最遠位置妥凳，說明不能達到i，返回false

public boolean canJump(int[] nums) {
    int maxReach=0;
    for(int i = 0; i < nums.length; i++){
        if(i > maxReach) return false;
        maxReach = Math.max(maxReach, i + nums[i]);
        if(maxReach >= nums.length - 1) break;//小優(yōu)化：已經(jīng)判斷出可以跳到末尾答捕，直接退出
    }
    return true;
}

方法四：最早開始位置
從后開始往前遍歷逝钥，記錄能達到最后一個位置的最早開始位置

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

跳躍游戲 II

給定一個非負整數(shù)數(shù)組，你最初位于數(shù)組的第一個位置拱镐。

數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度艘款。

你的目標是使用最少的跳躍次數(shù)到達數(shù)組的最后一個位置。

示例:

輸入: [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數(shù)是 2沃琅。
從下標為 0 跳到下標為 1 的位置哗咆，跳 1 步，然后跳 3 步到達數(shù)組的最后一個位置益眉。

說明:
假設你總是可以到達數(shù)組的最后一個位置

方法一：dfs（超時）

private int minStep;

public int jump(int[] nums) {
    minStep = nums.length - 1;
    dfs(nums, 0, 0);
    return minStep;
}

public void dfs(int[] nums, int pos, int step) {
    if (pos >= nums.length - 1) {
        minStep = Math.min(minStep, step);
        return;
    }
    for (int i = 1; i <= nums[pos]; i++) {
        dfs(nums, pos + i, step + 1);
    }
}

方法二：反向查找出發(fā)位置
我們的目標是到達數(shù)組的最后一個位置岳枷，因此我們可以考慮最后一步跳躍前所在的位置，該位置通過跳躍能夠到達最后一個位置呜叫。

如果有多個位置通過跳躍都能夠到達最后一個位置，那么我們應該如何進行選擇呢殿衰？直觀上來看朱庆，我們可以「貪心」地選擇距離最后一個位置最遠的那個位置，也就是對應下標最小的那個位置闷祥。因此娱颊，我們可以從左到右遍歷數(shù)組，選擇第一個滿足要求的位置凯砍。

找到最后一步跳躍前所在的位置之后箱硕，我們繼續(xù)貪心地尋找倒數(shù)第二步跳躍前所在的位置，以此類推悟衩，直到找到數(shù)組的開始位置剧罩。

public int jump(int[] nums) {
    int step = 0;
    int pos = nums.length - 1;
    while (pos > 0){
        for (int i = 0; i < pos; i++) {
            if(i + nums[i] >= pos){
                pos = i;
                step++;
                break;
            }
        }
    }
    return step;
}

時間復雜度O(n²)

方法三：正向查找可到達的最大位置
維護當前能夠到達的最大下標位置，記為邊界end座泳。我們從左到右遍歷數(shù)組惠昔，到達邊界時，更新邊界并將跳躍次數(shù)增加 1挑势。

把從nums[0]能到達的最遠距離看成一段镇防，遍歷此段中的內(nèi)容，以找到從此段中出發(fā)可以到達的最遠距離潮饱，一直遍歷到此段的最后一位来氧，再跳到之前找到的最遠距離。

跳后，上一段的最后一位成為下一段的開始啦扬，繼續(xù)遍歷中狂。

由于段與段是鏈接的，直接遍歷nums即可完成對段的遍歷考传。

也可以以圖形的方法形象的想一下吃型，方便理解。

思想大約是當前每段的最優(yōu)解僚楞，即總體最優(yōu)解勤晚。

public int jump(int[] nums) {
    int step = 0;
    int maxPos = 0;
    int end = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        maxPos = Math.max(maxPos, i + nums[i]);
        if (i == end) {
            end = maxPos;
            step++;
        }
    }
    return step;
}

時間復雜度O(n)

跳躍游戲 III

這里有一個非負整數(shù)數(shù)組 arr，你最開始位于該數(shù)組的起始下標 start 處泉褐。當你位于下標 i 處時赐写，你可以跳到 i + arr[i] 或者 i - arr[i]。

請你判斷自己是否能夠跳到對應元素值為 0 的 任意 下標處膜赃。

注意挺邀，不管是什么情況下，你都無法跳到數(shù)組之外跳座。

示例 1：

輸入：arr = [4,2,3,0,3,1,2], start = 5
輸出：true
解釋：
到達值為 0 的下標 3 有以下可能方案：
下標 5 -> 下標 4 -> 下標 1 -> 下標 3
下標 5 -> 下標 6 -> 下標 4 -> 下標 1 -> 下標 3

示例 2：

輸入：arr = [4,2,3,0,3,1,2], start = 0
輸出：true
解釋： 到達值為 0 的下標 3 有以下可能方案：
下標 0 -> 下標 4 -> 下標 1 -> 下標 3

示例 3：

輸入：arr = [3,0,2,1,2], start = 2
輸出：false
解釋：無法到達值為 0 的下標 1 處端铛。

提示：

• 1 <= arr.length <= 5 * 10^4
• 0 <= arr[i] < arr.length
• 0 <= start < arr.length

方法一：DFS
如果跳到了已經(jīng)到過的位置，說明這個位置不能跳疲眷，回退到上一步

public boolean canReach(int[] arr, int start) {
    return dfs(arr, start, new boolean[arr.length]);
}

public boolean dfs(int[] arr, int i, boolean[] used) {
    if (used[i]) {
        return false;
    }
    if (arr[i] == 0) {
        return true;
    }
    used[i] = true;
    return i + arr[i] < arr.length && dfs(arr, i + arr[i], used)
        || i - arr[i] >= 0 && dfs(arr, i - arr[i], used);
}

時間復雜度O(n)

方法二：BFS

public boolean canReach(int[] arr, int start) {
    boolean[] used = new boolean[arr.length];
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    while (!queue.isEmpty()) {
        int pos = queue.poll();
        used[pos] = true;
        if (arr[pos] == 0) {
            return true;
        }
        if (arr[pos] + pos < arr.length && !used[pos + arr[pos]]) {
            queue.offer(arr[pos] + pos);
        }
        if (pos - arr[pos] >= 0 && !used[pos - arr[pos]]) {
            queue.offer(pos - arr[pos]);
        }
    }
    return false;
}

時間復雜度O(n)