55 Jump Game 跳躍游戲

Description:
Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example:

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.

Constraints:

1 <= nums.length <= 3 * 10^4
0 <= nums[i][j] <= 10^5

題目描述:
給定一個非負整數(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 ， 所以你永遠不可能到達最后一個位置。

思路:

貪心法
參考LeetCode #45 Jump Game II 跳躍游戲 II
每次更新 i + nums[i]表示最遠能跳到到位置
只要不能跳到當前位置, 立即返回 false
時間復(fù)雜度O(n), 空間復(fù)雜度O(1)

代碼:
C++:

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

Java:

class Solution {
    public boolean canJump(int[] nums) {
        int reach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (reach < i) return false;
            reach = Math.max(reach, nums[i] + i);
        }
        return true;
    }
}

Python:

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        reach = 0
        for i in range(len(nums)):
            if i > reach:
                return False
            reach = max(i + nums[i], reach)
        return True