算法通关村第十七关：黄金挑战-跳跃游戏问题

黄金挑战-跳跃游戏问题

1. 跳跃游戏

LeetCode 55
https://leetcode.cn/problems/jump-game/

思路分析

关键是判断能否到达终点，不用管每一步跳跃到哪里，而是尽可能的跳跃到最远的位置
看最多能覆盖到哪里，只要不断更新能覆盖的距离，最后能覆盖到末尾就行了

具体执行：

1. 定义一个cover表示能最远达到的方位，i每次移动只能在其 cover 范围内移动
2. 每移动一次，根据该元素值重新更新cover，cover = max(该元素补充后范围，cover本身范围)
3. 如果cover大于等于终点下标，返回ture

代码实现

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        cover = 0
        n = len(nums)
        for i in range(n):
            # 判断是能能够到达 i 的位置
            if cover < i:
                return False
            cover = max(i + nums[i], cover)
            if cover >= n - 1:
                return True
        return False

1
2
3
4
5
6
7
8
9
10
11
12
13

2. 最短跳跃游戏

LeetCode 45
https://leetcode.cn/problems/jump-game-ii/

思路分析

贪心+双指针

设置四个变量

• left 一步步遍历数组
• steps 记录到达当前位置的最少步数
• right 表示当前步数能够覆盖到的最大范围
• left到达right时，更新right，step+1

代码实现

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        steps = 0
        max_position = 0
        right = 0

        for left in range(n-1):
            max_position = max(max_position, nums[left] + left)
            if left == right:
                right = max_position
                steps += 1

        return steps
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16