LeetCode 55：跳躍遊戲
（中等）
題目
描述
給定一個非負整數數組 nums ，你最初位于數組的 第一個下标 。
數組中的每個元素代表你在該位置可以跳躍的最大長度。
判斷你是否能夠到達最後一個下标。
示例 1：
輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下标 0 到達下标 1, 然後再從下标 1 跳 3 步到達最後一個下标。
示例 2：
輸入：nums = [3,2,1,0,4]
輸出：false
解釋：無論怎樣，總會到達下标為 3 的位置。但該下标的最大跳躍長度是 0 ， 是以永遠不可能到達最後一個下标。
思路
可用一個變量 maxIndex 來動态記錄目前能到達的最遠距離，若最終 maxIndex 大于最後一個數組元素的下标，那麼則跳躍成功，而關于如何去動态更新 maxIndex 值，我們可以從 0 開始，到倒數第二個元素（不能周遊到最後一個下标，因為本身問題就是問能否到達最後一個下标，應通過”跳躍“到達，而不是”周遊“到達）結束進行周遊數組，maxIndex 動态更新的結果應為 maxIndex 之前的值，與目前下标加上目前下标可以”跳躍“的最大距離的值，這兩者中較大的那一個，而能夠繼續周遊進行更新的條件是 maxIndex >= 目前周遊的下标，因為隻有這樣，在貪心算法的局部最優解中考慮才是可行的，即至少到達目前下标的位置是可行的，進而才能最終得出全局最優解，即能否到達最後的下标。
實作
public class TX5跳躍遊戲 {
public boolean canJump(int[] nums) {
int maxIndex = 0;
for (int i = 0; i < nums.length - 1; i++) {
if (maxIndex >= i) {
maxIndex = Math.max(i + nums[i], maxIndex);
}
}
return maxIndex >= nums.length - 1;
}
public static void main(String[] args) {
TX5跳躍遊戲 s = new TX5跳躍遊戲();
System.out.println("s.canJump(new int[]{2, 3, 1, 1, 4}) = " + s.canJump(new int[]{2, 3, 1, 1, 4}));
System.out.println("s.canJump(new int[]{2, 0, 0}) = " + s.canJump(new int[]{2, 0, 0}));
System.out.println("s.canJump(new int[]{3, 2, 1, 0,4}) = " + s.canJump(new int[]{3, 2, 1, 0, 4}));
System.out.println("s.canJump(new int[]{0, 2, 3}) = " + s.canJump(new int[]{0, 2, 3}));
}
} 
LeetCode 45：跳躍遊戲 II
（中等）
題目
描述
給你一個非負整數數組 nums ，你最初位于數組的第一個位置。
數組中的每個元素代表你在該位置可以跳躍的最大長度。
你的目标是使用最少的跳躍次數到達數組的最後一個位置。
假設你總是可以到達數組的最後一個位置。
示例 1:
輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最後一個位置的最小跳躍數是 2。
從下标為 0 跳到下标為 1 的位置，跳 1 步，然後跳 3 步到達數組的最後一個位置。
示例 2:
輸入: nums = [2,3,0,1,4]
輸出: 2
思路
此題的要求是在上一題的基礎上，“總是可以到達數組的最後一個位置”，是以，我們可以不再考慮無法到達的情況，而可以專心考慮到達最後一個下标至少要幾次。
我們還是利用上一題中的關鍵語句：maxIndex = Math.max(i + nums[i], maxIndex)，用于動态更新目前下标 i 及其之前能到達的最遠距離，因為下标 i 是在周遊過程中不斷變化的，是以 maxIndex 的值，也就是上述語句也要在每次循環時都要執行一次，但是并不是每次執行都需要跳躍一次，這是需要厘清楚的，而應該在什麼時候跳躍一次呢？注意，因為要求是最小的跳躍次數，是以，我們不到不得已時，就不能去跳躍，而應在迫不得已時，也就是再不跳就沒法到終點時才應該進行跳躍，而這個關鍵的時間點，就是：i == farIndex，即目前下标，已經等于上次記錄的最遠下标時，這時候就不得不去跳躍了，并且，這個跳躍的距離，應該也是從貪心的局部最優解角度去考慮，應該盡可能跳得遠，而具體應該跳多遠呢？這時候我們之前用于動态記錄目前下标 i 及其之前能到達的最遠距離的變量 maxIndex 就可以發揮作用了，同時，我們令 farIndex = maxIndex，并記錄一次跳躍次數，這樣，最終，我們在過程中滿足了局部最優解：不得不跳時才跳，若要是跳，就應該往可行的最遠處跳，是以，在全局上，就可以滿足全局最優解：使用最少的跳躍次數到達數組的最後一個位置。
實作
public class TX6跳躍遊戲II {
public int jump(int[] nums) {
int maxIndex = 0;
int farIndex = 0;
int count = 0;
for (int i = 0; i < nums.length - 1; i++) {
maxIndex = Math.max(i + nums[i], maxIndex);
if (maxIndex == nums.length - 1) {
return count + 1;
}
if (i == farIndex) {
farIndex = maxIndex;
count++;
}
}
return count;
}
public static void main(String[] args) {
TX6跳躍遊戲II s = new TX6跳躍遊戲II();
System.out.println("s.canJump(new int[]{2, 3, 1, 1, 4}) = " + s.jump(new int[]{2, 3, 1, 1, 4}));
System.out.println("s.canJump(new int[]{2, 3, 0, 1, 4}) = " + s.jump(new int[]{2, 3, 0, 1, 4}));
System.out.println("s.canJump(new int[]{2, 0, 0}) = " + s.jump(new int[]{2, 0, 0}));
}
}