55.Jump Game

Tags: Medium Greedy

Links: https://leetcode.com/problems/jump-game/

---

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 1:

Input: [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: [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.

---

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return true;

        vector<int> d(n, 1);
        for (int i = 0; i < n - 1; ++i){
            if (i > 0 && d[i] == 1) return false;
            for (int j = 1; j <= nums[i]; ++j){
                if (i + j < n)
                    ++d[i + j];
                else break;
            }
        }
        if (d[n - 1] > 1) return true;
        return false;
    }
};

这种方法是用一个额外数组来记录当前位置是否可以被前面的节点访问到，只要可以被访问到，那么数值一定大于1，最后只需要判断末尾数值是否大于1即可判断是否可以从前面的位置跳过来。但是这种方法速度太慢。

Runtime: 1124 ms, faster than 5.01% of C++ online submissions for Jump Game.
Memory Usage: 10.2 MB, less than 34.21% of C++ online submissions for Jump Game.

方法二：

我们只关心最远能到达的地点，中间有哪些点能到到我们并不关心。

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

        return reach >= n;
    }
};

这里reach表示前i个节点最远能到达的位置，我们从1开始计数。那么这种计数显然i不能大于等于reach。因为到了某个i，它实际的位置是i+1，也就是说前i-1个节点最远也到不了i+1.如果相等，显然此位置速度明显加快。

Runtime: 8 ms, faster than 96.99% of C++ online submissions for Jump Game.
Memory Usage: 9.9 MB, less than 96.05% of C++ online submissions for Jump Game.