Leecode刷题C语言之跳跃游戏②

执行结果:通过

执行用时和内存消耗如下：

int jump(int* nums, int numsSize) {
    int position = numsSize - 1;
    int steps = 0;
    while (position > 0) {
        for (int i = 0; i < position; i++) {
            if (i + nums[i] >= position) {
                position = i;
                steps++;
                break;
            }
        }
    }
    return steps;
}

解题思路：

这段代码是用来解决“跳跃游戏 II”（Jump Game II）的问题，目标是最小化跳跃次数，从数组的起始位置跳到最后一个位置。代码的思路可以分解为以下几个步骤：

1. 初始化变量：
   • position：设置为数组的最后一个位置（numsSize - 1），表示当前需要到达的目标位置。
   • steps：设置为0，用来记录跳跃的次数。
2. 逆向思维：
   • 代码采用了逆向思维，从数组的最后一个位置开始向前推算，直到到达数组的第一个位置。这种方法相较于正向推算，可以减少不必要的比较，因为从后向前更容易确定哪些位置可以一步跳到当前的目标位置。
3. 寻找能够跳到目标位置的最远起点：
   • 使用一个while循环，条件是position > 0，意味着只要目标位置不是数组的起始位置，就继续寻找。
   • 在while循环内部，使用一个for循环遍历当前目标位置之前的所有位置（从0到position - 1）。
   • 在for循环内部，检查每个位置i是否能通过一次跳跃到达或超过当前的目标位置position（即i + nums[i] >= position）。
   • 一旦找到这样的位置i，更新目标位置position为i（即新的目标位置变为当前能够跳到之前目标位置的最远起点），跳跃次数steps增加1，然后跳出for循环。
4. 返回结果：
   • 当while循环结束时，说明已经从最后一个位置逆向推算到了第一个位置，此时steps记录的就是最小跳跃次数。
   • 返回steps作为结果。

总结来说，这段代码通过逆向遍历数组，从后向前寻找每个目标位置的最远可达起点，从而计算出从数组起始位置跳到最后一个位置所需的最小跳跃次数。