leetcode45：跳跃游戏II

题目链接

leetcode

题目描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处满足：0 <= j <= nums[i], i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

/*
    状态定义：
        f[i] 表示到达 i 最小的跳跃次数。
    状态计算：
        f[i] = f[last] + 1

    时间复杂度：O(n)
        数组中每个元素最多被遍历两次。
        最坏情况下，数组中每个元素遍历一次。
    空间复杂度：O(n)
        数组的空间是 O(n)。
*/
class Solution_0 {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        // 初始化
        f[0] = 0;
        int last = 0; // 上一跳的位置
        
        // 状态计算
        for (int i = 1; i < n; i++) {
            // 更新 last
            while (i > last + nums[last]) {
                last++;
            }
            // 更新 f[i]
            f[i] = f[last] + 1;
        }
        
        return f[n-1];
    }
};

/*
    移动下标到了当前覆盖的最远距离下标时，步数加一，增加覆盖距离。
    最后的步数，就是最小的跳跃次数。
    特殊情况：移动下标到了当前覆盖的最远距离下标，步数不用加一，不能再向后走。

    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int step = 0; // 当前步数
        int cur = 0;  // 当前可以到达的最远位置
        int last = 0; // 上一跳的最远位置

        for (int i = 0; i < n-1; i++) {
            // 更新当前可以到达的最远位置
            cur = max(cur, nums[i] + i);
            // 如果到达了上一跳的最远位置，则更新
            if (i == last) {
                last = cur;
                step++;
            }
        }

        return step;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> nums_cases = {
        {2,3,1,1,4},
        {2,3,0,1,4}
    };

    for (auto& nums : nums_cases) {
        cout << "Input: nums = ";
        printArray(nums);
        cout << endl;

        int result = solution.jump(nums);
        cout << "Output: " << result << endl;
    }

    return 0;