跳跃游戏 II python_python跳跃游戏

题目链接：

45. 跳跃游戏 II - 力扣（LeetCode）

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

与跳跃游戏 I 不同的是，他这次不是要求是否可以到达，要求的是在可以到达的前提下，最小的跳跃次数

只是要求判断是否可以到达最后，只要不断更新最远位置就行了

如果要知道最小的跳跃次数，还要注意，你还需要记录步数，在确定了下一跳目的地之前，跳数还没变，没有真正的跳出去

class Solution:
    def jump(self, nums:list) -> int:
        last_reach = 0 # 上一跳位置
        reach_farest = 0 # 上一跳可以到达的最大位置，下一跳的位置就在这之间
        jump = 0
        n =len(nums)
        target = len(nums)-1
        for i in range(n-1):
            reach_farest = max(reach_farest, i + nums[i])
            if i == last_reach:
                jump += 1
                # 确定了下一跳目的地之后才真正的跳出
                last_reach = reach_farest
                # 确定下下跳的区间 
        return jump