LC55---跳躍遊戲---LC45---跳躍遊戲II

​​55. 跳躍遊戲​​

難度中等1047

給定一個非負整數數組 ​

​nums​

​ ，你最初位于數組的 第一個下标 。

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

判斷你是否能夠到達最後一個下标。

示例 1：

輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下标 0 到達下标 1, 然後再從下标 1 跳 3 步到達最後一個下标。      

由最後一個開始,倒推

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

​​45. 跳躍遊戲 II​​

難度困難829

給定一個非負整數數組，你最初位于數組的第一個位置。

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

你的目标是使用最少的跳躍次數到達數組的最後一個位置。

示例:

輸入: [2,3,1,1,4]
輸出: 2
解釋: 跳到最後一個位置的最小跳躍數是 2。
     從下标為 0 跳到下标為 1 的位置，跳 1 步，然後跳 3 步到達數組的最後一個位置      

正向找到最大的

如果我們「貪心」地進行正向查找，每次找到可到達的最遠位置，就可以線上性時間内得到最少的跳躍次數。

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