Leetcode

Posted on Word count in article: 1.3k Reading time ≈ 5 mins.

241201 – 贪心 – 跳跃游戏

题目描述

给你一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

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

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

1 <= nums.length <= $10^{4}$
0 <= nums[i] <= $10^{5}$

题解思路

  1. 初始化：

    • 定义一个变量 MaxReach，用来记录当前能够到达的最远位置。初始时，这个位置是0，因为你还没有开始跳跃。

  2. 遍历数组：

    • 从数组的第一个元素开始，遍历到最后一个元素，防止出现开始即结束的情况的误判。

  3. 检查是否能够到达当前位置：

    • 在每次迭代中，首先检查当前位置 i 是否已经超过了 MaxReach。如果是，意味着你无法从上一个可达位置跳到当前位置，因此返回 False。

  4. 更新最远可达位置：

    • 如果当前位置可以到达，接下来需要更新 MaxReach。这里使用了一个三元运算符来实现贪心选择：如果当前位置加上该位置可跳的最大长度 nums[i] 大于 MaxReach，则更新 MaxReach 为 i + nums[i]，否则保持 MaxReach 不变。

  5. 判断是否到达终点：

    • 遍历完成后，检查 MaxReach 是否至少等于数组长度减去1（即最后一个元素的索引）。如果是，意味着你能够到达数组的最后一个位置，返回 True；否则返回 False。

算法的贪心之处

这个算法的贪心之处在于，在每一步都尽可能地更新 MaxReach 到最远可达的位置，而不是选择一个保守的跳跃距离。通过这种方式，算法能够在遍历一次数组的过程中，高效地判断是否能够到达终点。

具体展示

假设数组 nums = [2, 3, 1, 1, 4] 以及 nums = [3, 2, 1, 0, 4]，我们将通过这两个数组来展示每一步的跳跃和MaxReach的更新过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
初始状态:
数值: 2  3  1  1  4
位置: 0  1  2  3  4
可跳: 2  3  1  1  4
MaxReach: 0

开始遍历：

i = 0
数值: 2  3  1  1  4
位置: 0  1  2  3  4
可跳: 2  3  1  1  4
MaxReach: 2 (0 + nums[0])

i = 1
数值: 2  3  1  1  4
位置: 0  1  2  3  4
可跳: 2  3  1  1  4
MaxReach: 4 (1 + nums[1], 因为4 > 2)

i = 2
数值: 2  3  1  1  4
位置: 0  1  2  3  4
可跳: 2  3  1  1  4
MaxReach: 4 (不变，因为2 + nums[2] = 3 < MaxReach)

i = 3
数值: 2  3  1  1  4
位置: 0  1  2  3  4
可跳: 2  3  1  1  4
MaxReach: 4 (不变，因为3 + nums[3] = 4 = MaxReach)

i = 4
数值: 2  3  1  1  4
位置: 0  1  2  3  4
可跳: 2  3  1  1  4
MaxReach: 8 (4 + nums[4]，但是这个值不影响结果，
因为能更新说明能达到该点，而该点即为终点。)

最终判断:
MaxReach (8) >= len(nums) - 1 (4)
返回 True，可以跳到最后一个位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
初始状态:
数值: 3  2  1  0  4
位置: 0  1  2  3  4
可跳: 3  2  1  0  4
MaxReach: 0

开始遍历：

i = 0
数值: 3  2  1  0  4
位置: 0  1  2  3  4
可跳: 3  2  1  0  4
MaxReach: 3 (0 + nums[0])

i = 1
数值: 3  2  1  0  4
位置: 0  1  2  3  4
可跳: 3  2  1  0  4
MaxReach: 3 (不变，因为1 + nums[1] = 3 <= MaxReach)

i = 2
数值: 3  2  1  0  4
位置: 0  1  2  3  4
可跳: 3  2  1  0  4
MaxReach: 3 (不变，因为2 + nums[2] = 3 <= MaxReach)

i = 3
数值: 3  2  1  0  4
位置: 0  1  2  3  4
可跳: 3  2  1  0  4
MaxReach: 3 (不变，因为3 + nums[3] = 3 <= MaxReach)

i = 4
i (4) > MaxReach (3)
无法到达索引 i，返回 False，不更新 MaxReach

说明：

  • 位置：表示数组中的索引位置。
  • 可跳：表示在该位置可以跳跃的最大长度。
  • MaxReach：表示当前能够到达的最远位置。

我们可以看到每一步如何根据当前位置和可跳长度更新MaxReach，并最终判断是否能够到达数组的最后一个位置。这个过程体现了贪心算法的思想：在每一步选择当前最优的选项（即尽可能跳得更远），以期望达到全局的最优解。

代码展示 – python

1
2
3
4
5
6
7
class Solution:
def canJump(self, nums: List[int]) -> bool:
    MaxReach = 0
    for i in range(len(nums)):
        if i > MaxReach: return False
        MaxReach = MaxReach if MaxReach >= i + nums[i] else i + nums[i]
    return MaxReach >= len(nums) - 1

注意

这里遍历是遍历到结束的，是因为可能存在开始便结束的情况，若修改遍历的值为len(nums) - 1，则会导致数组长度为1的无法判断。
这时应该返回 True。

不用管 i = index(end) 那一步对应的值为多少，因为当其能够更新的情况，那么终点已经能够够到了，这是前一个 if 判断的。