LeetCode解题之Jump Game II

---

原题

数组中的每一个值表示在当前位置最多能向前面跳几步，推断至少跳几步可以跳到最后。

注意点：

• 全部的数字都是正数
• 跳的步数可以比当前的值小
• 保证全部的測试用例都可以跳到最后

样例：

输入: nums = [2, 3, 1, 1, 4]

输出: 2

解题思路

这是在 之上给出的问题。题目已经保证可以跳到最后。

遍历数组。起始到当前坐标全部跳跃方式可以到达的最远距离是reach，我们跳n步能到达的最远距离用longest表示，假设longest不能到达当前坐标，说明就要多跳一步了，直接跳到当前坐标之前的点可以跳到的最远位置。

AC源代码

class Solution(object):    def jump(self, nums):        """        :type nums: List[int]        :rtype: int        """        length = len(nums)        counter = 0        longest = 0        reach = 0        for i in range(length):            if longest < i:                counter += 1                longest = reach            reach = max(reach, nums[i] + i)        return counterif __name__ == "__main__":    assert Solution().jump([2, 3, 1, 1, 4]) == 2

欢迎查看我的 () 来获得相关源代码。