solution.md

# 跳跃游戏 II
以下错误的选项是？
## 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;
    }
};
```