LeetCode Jump Game

LeetCode解題之Jump Game

原題

數組中的每個值表示在當前位置最多能向前面跳幾步，判斷給出的數組是否否存在一種跳法跳到最後。

注意點：

例子：

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

輸出: True

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

輸出: False

解題思路

先想一下什麼時候不能夠完成跳躍，在當前位置之前（包括當前位置）能夠跳躍到的最遠距離就是當前位置，且這時候還沒有到終點；什麼樣的情況就能保證可以跳到終點呢，只要當前最遠距離超過終點即可。只要當前的位置沒有超過能跳到的最遠距離，就可以不斷的刷新最遠距離來繼續前進。

AC源碼

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if not nums:
            return False
        length = len(nums)
        index = 0
        longest = nums[0]
        while index <= longest:
            if longest >= length - 1:
                return True
            longest = max(longest, index + nums[index])
            index += 1
        return False


if __name__ == "__main__":
    assert Solution().canJump([2, 3, 1, 1, 4]) == True
    assert Solution().canJump([3, 2, 1, 0, 4]) == False