55. Jump Game-蒲公英云

55. Jump Game

心已赠人 2022-03-21 09:28 348阅读 0赞

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.
题意：一个数组存储了**非负整型数据**，数组中的第i个元素nums\[i\]，代表了可以从数组第i个位置**最多**向前跳跃nums\[i\]步。已知数组**各元素**的情况下，求是否可以从数组的**第0个**位置跳跃到数组的**最后一个元素**的位置。
分析：从第i个位置，最远可跳 i + nums\[i\] 的位置。用数组index记录每一个位置**最远**可跳到的位置。如果从第0个位置**最远**可以跳至第i个位置，则从第0位置**也一定**可以跳至1,2......i-1, i 的位置。到底选择哪一个呢？应该选择其中可以跳到最远的那一个（**贪心**）。
class Solution {
public:
    bool canJump(vector<int>& nums) {
     vector<int> index;
    int max_index = 0;
    for (int i = 0; i < nums.size(); i++)
    {
        index.push_back(i+nums[i]);
    }
    int pos = 0;
    while (pos <= max_index && pos < nums.size())
    {
        if (index[pos] > max_index)
            max_index = index[pos];
        pos++;
    }
    return pos >= nums.size();   
    }
};