leetcode45.跳跃游戏 II

Posted on | In |
Words count in article: 599 | Reading time ≈ 2

给定一个长度为 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]。

示例：

1
2
3
4
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

分析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
通过枚举单纯的动态规划我们可以知道，f[N]数组里面是单调递增的
大概就是0,1,1,2,2,2,....
所以f[i]是一个单调递增的数组
又从动态规划的状态转移方程可知
f[i] = f[j] + 1
我们要枚举i之前的能跳到i的所有j，然后每次找到一个符合条件的j之后就f[i] = f[j]+1
因为初始的时候f[j]都为0，所以不管找到多少个j，都只会使得f[i]在0的基础上加1

找到第一个能跳到i的j的时候更新了一次f[i]，之后无论再找到多少个j都只能使得f[i] = 0+1 = 1
也就是说除了第一个点之外，后面找到的点都是进行的重复的操作

所以我们只用找到第一个能跳到i的点j，然后用j去更新i的状态即f[i] = f[j] + 1

后面更新更多的点同理，只用找到能跳到的第一个点即可

动态规划时瓶颈就在于更新每个点的最小值时需要遍历所有能跳到i的点，而有了单调性以后就可以用第一个能跳到i的点更新了

因为找到第一个点和遍历所有的点都只遍历了一次，所以时间复杂度会降到O(n)

代码

  • C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int f[n + 1];
        f[0] = 0;

        for (int i = 1, j = 0;i < n;i ++) {
            while (j + nums[j] < i) j ++;
            f[i] = f[j] + 1;
        }

        return f[n - 1];
    }
};

[原题链接](45. 跳跃游戏 II - 力扣（Leetcode）)

0%