solution.md

# 跳跃游戏 II
<p>给定一个非负整数数组，你最初位于数组的第一个位置。</p>
<p>数组中的每个元素代表你在该位置可以跳跃的最大长度。</p>
<p>你的目标是使用最少的跳跃次数到达数组的最后一个位置。</p>
<p><strong>示例:</strong></p>
<pre><strong>输入:</strong> [2,3,1,1,4]<strong><br />输出:</strong> 2<strong><br />解释:</strong> 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳&nbsp;1&nbsp;步，然后跳&nbsp;3&nbsp;步到达数组的最后一个位置。</pre>
<p><strong>说明:</strong></p>
<p>假设你总是可以到达数组的最后一个位置。</p>
<p><p>给定一个非负整数数组，你最初位于数组的第一个位置。</p>
<p>数组中的每个元素代表你在该位置可以跳跃的最大长度。</p>
<p>你的目标是使用最少的跳跃次数到达数组的最后一个位置。</p>
<p><strong>示例:</strong></p>
<pre><strong>输入:</strong> [2,3,1,1,4]<strong><br />输出:</strong> 2<strong><br />解释:</strong> 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳&nbsp;1&nbsp;步，然后跳&nbsp;3&nbsp;步到达数组的最后一个位置。</pre>
<p><strong>说明:</strong></p>
<p>假设你总是可以到达数组的最后一个位置。</p>
<p>以下错误的选项是？</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};
    int res;

    res = sol.jump(nums);

    cout << res;
    return 0;
}
```

## 答案
```cpp
class Solution
{
public:
    int jump(vector<int> &nums)
    {
        int res_min = 0;
        int end = 0;
        int longest_distance = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            longest_distance = max(longest_distance, nums[i]);

            if (i == end)
            {
                if (end != nums.size() - 1)
                {
                    ++res_min;
                    end = longest_distance;
                    if (longest_distance >= nums.size() - 1)
                        break;
                }
                else
                    break;
            }
        }
        return res_min;
    }
};
```
## 选项

### A
```cpp
class Solution
{
public:
    int jump(vector<int> &nums)
    {
        int steps = 0;
        int lo = 0, hi = 0;
        while (hi < nums.size() - 1)
        {
            int right = 0;
            for (int i = lo; i <= hi; i++)
            {
                right = max(i + nums[i], right);
            }
            lo = hi + 1;
            hi = right;
            steps++;
        }
        return steps;
    }
};
```

### B
```cpp
class Solution
{
public:
    int jump(vector<int> &nums)
    {
        if (nums.size() == 1)
            return 0;
        int steps = 0, oldIdx = 0;
        int nextJump = oldIdx + nums[oldIdx];
        if (nextJump >= nums.size() - 1)
            return steps + 1;

        while (oldIdx < nums.size())
        {
            int maxJump = 0, newIdx = oldIdx;
            for (int j = oldIdx; j <= oldIdx + nums[oldIdx]; j++)
            {
                int nextJump = j + nums[j];
                if (nextJump >= nums.size() - 1)
                    return steps + 2;
                if (j + nums[j] > maxJump)
                {
                    maxJump = j + nums[j];
                    newIdx = j;
                }
            }

            oldIdx = newIdx;
            steps++;
        }
    }
};
```

### C
```cpp
class Solution
{
public:
    int jump(vector<int> &nums)
    {
        int i, j, n = nums.size();
        if (n == 1)
            return 0;
        int ans = 0;
        for (i = 0; i < n;)
        {
            if (i == n - 1)
                break;
            if (i + nums[i] >= n - 1)
            {
                ans++;
                break;
            }
            else
            {
                int max = i + 1;
                for (j = 2; j <= nums[i]; j++)
                {
                    if (nums[max] + max <= nums[i + j] + i + j)
                        max = i + j;
                }
                ans++;
                i = max;
            }
        }
        return ans;
    }
};
```