55 - Jump Game && 45 - Jump Game II

55 - Jump Game

#medium

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

思路

只看覆蓋範圍

剛看到本題一開始可能想：當前位置元素如果是3，我究竟是跳一步呢，還是兩步呢，還是三步呢，究竟跳幾步才是最優呢？

其實跳幾步無所謂，關鍵在於可跳的覆蓋範圍！

不一定非要明確一次究竟跳幾步，每次取最大的跳躍步數，這個就是可以跳躍的覆蓋範圍。

這個範圍內，別管是怎麼跳的，反正一定可以跳過來。

那麼這個問題就轉化為跳躍覆蓋範圍究竟可不可以覆蓋到終點！

每次移動取最大跳躍步數（得到最大的覆蓋範圍），每移動一個單位，就更新最大覆蓋範圍。

貪心算法局部最優解：每次取最大跳躍步數（取最大覆蓋範圍），整體最優解：最後得到整體最大覆蓋範圍，看是否能到終點。

局部最優推出全局最優，找不出反例，試試貪心！

如圖：

i每次移動只能在cover的範圍內移動，每移動一個元素，cover得到該元素數值（新的覆蓋範圍）的補充，讓i繼續移動下去。

而cover每次只取 max(該元素數值補充後的範圍, cover本身範圍)。

如果cover大於等於了終點下標，直接return true就可以了。

Solution

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if ( nums.size() == 0 || nums.size() == 1 ) return true;
        int scope = 0;
        for ( int i = 0; i <= scope; i++ ) {
            scope = max( i + nums[i], scope );
            if ( scope >= nums.size() - 1 ) return true;
        }

        return false;
    }

};

45 - Jump Game II

#medium

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and
• i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:
Input: nums = [2,3,0,1,4]
Output: 2

// 每一步盡量往遠點跳，用最少的步數涵蓋最大的範圍。

class Solution {
public:
    int jump(vector<int>& nums) {
        if ( nums.size() == 1 ) return 0;
        int scope = 0;
        int next_scope = 0;
        int result = 0; // 跳幾步
        for  ( int i = 0; i < nums.size(); i++ ) {
             next_scope = max( i + nums[i], next_scope );
             // 到達終點
             if ( i == scope ) {
                 if ( scope != nums.size() - 1) {
                     result++;
                     scope = next_scope;
                     if ( scope >= nums.size() - 1 ) break;
                 }
                 else break;
             }
        }
  
        return result;
    }
};