55. 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.

---

给定一个数组，每个数字A[i]表示站在i位置最多能跳的步数，初始时站在数组左边，问能否跳到数组右边。
使用贪心策略，维护一个当前能跳到的最远位置maxpos。从左往右遍历数组，如果位置i>maxpos，说明根据之前的数字，没办法跳到位置i，直接break；否则更新maxpos为max(maxpos,A[i]+i)。最后检查maxpos>=n-1。完整代码如下：

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

本代码提交AC，用时12MS。

二刷。是LeetCode Jump Game II的简化版，依然将问题转化为BFS，如果在BFS某一层时，最远距离没有更新，则表示没法再往前跳了。最后看看最远距离能否到达末尾即可。完整代码如下：

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

本代码提交AC，用时4MS。

三刷。在每个位置，我们可以算到该位置能跳到的最远位置maxindex，如果当前位置i在maxindex范围内，说明可以到达i，且能从i进行新的起跳，所以可更新maxindex。如果i超过maxindex，说明无法到达i，也就无法在i的基础上进行新的起跳了。最后看看maxindex能否到达末尾即可。

完整代码如下：

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

本代码提交AC，用时8MS。