想要精通算法和SQL的成长之路 - 跳跃游戏系列

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 跳跃游戏

原题链接
给定一个非负整数数组 nums ，你最初位于数组的第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

• 输入：nums = [2,3,1,1,4]
• 输出：true
• 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

思路：

• 我们遍历数组，假设每次遍历到的那个位置为起点。
• 求得以每个下标作为起点时，能够跳到的最大覆盖范围 Math.max(maxRight, i + nums[i])。
• 同时我们要注意，每次遍历的循环范围是不同的，右边界maxRight可能会改变。最后看覆盖范围是否包括终点即可maxRight >= nums.length - 1 。

伪代码就是：

public boolean canJump(int[] nums) {
	// 右边界
    int maxRight = 0;
    // 数组长度为1的时候，就相当于已经在终点了
    if (nums.length == 1) {
        return true;
    }
    for (int i = 0; i <= maxRight; i++) {
    	// 更新右边界，取覆盖范围最右侧的边界值
        maxRight = Math.max(maxRight, i + nums[i]);
        // 如果右边界超过了终点（数组长度-1）说明可到达终点
        if (maxRight >= nums.length - 1) {
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二. 跳跃游戏II

原题链接
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。

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

这题和第一题有什么不同呢？

• 第一题：在[0,maxRight]这个范围内的元素都会遍历。用的是穷举，因为只需要判断是否可到达终点。
• 第二题：因为最少跳跃次数的限制，需要考虑何时才应该去跳跃。

局部最优：每次跳的距离尽可能的远，如果还没有到达终点，就再跳一次（跳跃次数+1）
整体最优：跳到终点 / 跳跃次数最小。

那么第二题的思路如下：（以第一步和第二步为例）

1. 求得第一步可以到达的范围是：[0, one]。
2. 在[0, one]这一区间进行遍历，求得这一区间内，第二次跳跃时可以到达的最远距离two。
3. 一旦你确定了第二次可到达的最远距离，在计算跳跃次数的时候，对于程序而言，你怎么跳的已经无所谓了。因为你不可避免的需要跳两次。
4. 也就是说，你遍历到one这个下标的时候，次数就应该加1了，跳到第二个最远距离two的时候，次数同样应该加1。

public int canJump(int[] nums) {
    int step = 0;
    int curMaxEnd = 0;// 当前能够跳的最远距离
    int nextMaxEnd = 0;// 下一次跳跃的最远距离
    for (int i = 0; i < nums.length - 1; i++) {
        // 更新本次跳跃范围内，不断更新可以到达的最远距离
        nextMaxEnd = Math.max(nextMaxEnd, i + nums[i]);
        // 跳到本次最远的地方之后，步数+1，开始计算下一次的最远跳跃下标,
        if (i == curMaxEnd) {
            // 下一次跳跃，更新当前可跳跃的最远距离，步数+1
            curMaxEnd = nextMaxEnd;
            step++;
        }
    }
    return step;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

结合上面的流程图来看，我们知道

1. 第二次跳跃的时候，可以到达的最远距离就是4了。也就是终点下标。那么整个步骤需要2次跳跃。
2. 我们记i == curMaxEnd为一次跳跃。也就是我们遍历到下标为2的位置的时候，跳跃次数就是2次了。已经能够跳跃到终点了。

试想一下，如果我们的for循环写i < nums.length，会发生什么？

1. 第二次满足i == curMaxEnd（第二次跳跃）的时候，curMaxEnd的值被赋值为nextMaxEnd，也就是4。处于数组下标区间内。
2. 那么当第三次 i == curMaxEnd的时候，步数还会+1。就多余了。
3. 因此我们记得是：本次跳跃能够到达的最远距离，当你第二次已经能够到达的时候，就不应该继续往后计数了。因此for循环写的是i < nums.length - 1

（可能有点绕，但是可以仔细想一下-1的意义）