跳跃游戏

一、题目

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。题目保证可以跳到结尾

leetcode题目

能否跳到最后一个下标：https://leetcode.cn/problems/jump-game/

最小跳跃次数：https://leetcode.cn/problems/jump-game-ii/

二、思路

先来看最小跳跃次数，题目保证了给出的用例可以跳到结尾。

我们使用三个变量，jump 表示跳的次数，cur 表示跳 jump 步，最远可以到达的位置，next 表示多跳一步，最远能够到达的位置。next 每一步都会更新。然后我们遍历这个数组。

如果 cur >= i，表示当前跳 jump 步，可以到达 i 位置，因此什么都不用做
如果 cur < i，表示跳 jump 步，不能到达 i 位置，此时需要将 jump++，并且将 next 赋给 cur。也就是说，获取到了在跳一步，可以达到的最远位置。
在遍历的过程中，每次都需要更新 next，获取到跳 jump 可以达到的位置。

再来看是否可以跳到最后一个下标问题

这个问题比较简单，我们只需要依次遍历数组，并且在遍历的过程中，判断 i 位置和 jump 的大小。如果 jump 无法支持跳到 i 位置，那就直接返回 false。然后再更新 jump ，也就是加上当前节点，看最远能跳到哪里。

三、代码

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

class Solution {
public:
    // 无法处理不能跳到的情况
    int jump(const std::vector<int>& nums) {
        size_t jump = 0, cur = 0, next = 0;
        for (size_t i = 0; i < nums.size(); ++i) {
            if (cur < i) {
                jump++;
                cur = next;
            }
            next = std::max(next, i+nums[i]);
        }
        return jump;
    }

    bool canJump(const std::vector<int>& nums) {
        size_t jump = 0;
        for (size_t i = 0; i < nums.size(); ++i) {
            if (i > jump) return false;
            jump = std::max(jump, i+nums[i]);
        }
        return true;
    }
};

int main() {
    Solution s;
    int res = s.jump({3, 2, 1, 0, 4});
    std::cout << res << std::endl;
    return 0;
}