LeetCode Jump Game II

LeetCode解題之Jump Game II

原題

數組中的每個值表示在當前位置最多能向前面跳幾步，判斷至少跳幾步能夠跳到最後。

注意點：

例子：

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

輸出: 2

解題思路

這是在 Jump Game 之上給出的問題，題目已經保證能夠跳到最後。遍歷數組，起始到當前坐標所有跳躍方式能夠到達的最遠距離是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 counter


if __name__ == "__main__":
    assert Solution().jump([2, 3, 1, 1, 4]) == 2

歡迎查看我的Github來獲得相關源碼。