Leetcode 55. Jump Game -

Jump Game :

給一個非負整數的陣列，陣列元素的數值代表「最大」可以走的步數，問這條陣列能不能走完(預設出發點從index 0開始)

Python

方法 : Greedy 解

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        if n <= 1:
            return True

        lastPoint = n - 1
        for i in range(n - 1, -1, -1):
            if i + nums[i] >= lastPoint:    #當前的數加步數大於最後一值
                lastPoint = i               #lastpoint 給定當前位置

        return lastPoint == 0

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        reach = 0
        for i, n in enumerate(nums):
            if i > reach:                
                return False
            reach = max(reach, i + n)    
        return True

Python

相關