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.

题解：

输入一个数组，数组中的元素 nums[i] 表示可以从第 i 个位置最多向前跳跃 nums[i] 步，问对于输入的数组nums，是否可以从数组的第0个位置跳跃到数组的最后一个位置。
例如：
A = [2,3,1,1,4], return true.
A[0] = 2; 表示可以从数组的第0个位置跳跃到第 （0+2） 个位置上；
A[1] = 3; 表示可以从数组的第1个位置跳跃到第 （1+3） 个位置上；
A[2] = 1; 表示可以从数组的第2个位置跳跃到第 （2+1） 个位置上；
A[3] = 1; 表示可以从数组的第3个位置跳跃到第 （3+1） 个位置上；
A[4] = 4; 表示可以从数组的第4个位置跳跃到第 （4+4） 个位置上；
可以看出，数组中各位置所能跳跃到的最远的位置为：[2,4,3,4,8]；
当我遍历数组A时，定义一个max_jump用来存储截止到当前位置之前所能跳跃的最大的步数，例如，截止到A[2]之前，我们所能跳跃到的最远的距离为 位置4 ；
当 max_jump < i 时，说明截止到位置 i 之前，我们所能到达的最远位置max_jump 小于 当前位置 i ，也就是说我们无法到达位置 i ，返回false；
反正，说明我们能够到达位置 i ，那么就将 max_jump 更新为截止到 i 时我们所能到达的最远的位置；
若遍历结束仍然没有触发 false ，说明我们成功的到达了数组A的最后一个位置，返回 true 。

My Solution （C/C++完整实现）：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

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

int main() {
    vector<int> nums;
    nums.push_back(2);
    nums.push_back(3);
    nums.push_back(1);
    nums.push_back(1);
    nums.push_back(4);
    Solution s;
    cout << s.canJump(nums);
    return 0;
}

结果：

1

My Solution（Python）：

class Solution:
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        max_jump = nums[0]
        for i in range(1, len(nums)):
            if i <= max_jump:
                max_jump = max(i+nums[i], max_jump)
            else:
                return False
        return True