[Leetcode] 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.

For example:

A = 

[2,3,1,1,4]

, return 

true

.

A = 

[3,2,1,0,4]

, return 

false

.

思路：

贪心算法即可。我们维护一个变量right，表示当前可以到达的最右位置，然后遍历数组处理如下情况：1）发现当前可以到达的最右位置right小于当前位置，表示无法跳到该位置，直接返回false；2）更新right的值；3）如果更新后的right的值大于等于最后一个元素的索引，表示从当前位置就可以调到末尾，直接返回true。算法的时间复杂度O(n)，空间复杂度O(1)。

代码：

class Solution {
public:
    bool canJump(vector<int>& nums) 
    {
        int right = 0;      // the right most index we can jump to
        for(int i = 0; i < nums.size(); ++i)
        {
            if(right < i)
                return false;
            right = max(right, i + nums[i]);
            if(right >= nums.size() - 1)
                return true;
        }
        return true;
    }
};