solution.md

# 跳跃游戏

<p>给定一个非负整数数组 <code>nums</code> ，你最初位于数组的 <strong>第一个下标</strong> 。</p><p>数组中的每个元素代表你在该位置可以跳跃的最大长度。</p><p>判断你是否能够到达最后一个下标。</p><p> </p><p><strong>示例 1：</strong></p><pre><strong>输入：</strong>nums = [2,3,1,1,4]<strong><br />输出：</strong>true<strong><br />解释：</strong>可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>nums = [3,2,1,0,4]<strong><br />输出：</strong>false<strong><br />解释：</strong>无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>1 <= nums.length <= 3 * 10<sup>4</sup></code></li>	<li><code>0 <= nums[i] <= 10<sup>5</sup></code></li></ul>
<p>以下错误的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp
int main()
{
    Solution sol;
    vector<int> nums = {2, 3, 1, 1, 4};
    bool res;

    res = sol.canJump(nums);
    cout << res;
    return 0;
}
```

## 答案

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


### A

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

### B

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

### C

```cpp
class Solution
{
public:
    bool canJump(vector<int> &nums)
    {
        int i = 0, j = 1, n = nums.size();
        while (j < n)
        {
            int end = min(nums[i] + i + 1, n);
            if (nums[i] == 0)
                return false;
            while (j < end)
            {
                if (nums[j] + j >= nums[i] + i)
                    i = j;
                j++;
            }
            if (nums[i] + i > n)
                break;
        }
        return true;
    }
};
```