LeetCode:(Python)(Array) Jump Game

題目連結: https://leetcode.com/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150

題意說明

• nums 內的數字，代表在該位置上能夠往下走的最大步伐數
• 如果數字是3，代表可以走1，2，3的步伐，不一定要走3
• 如果能夠走到 nums的最後一格，代表能走完全程，True，反之 False

實作程式碼

1. 一開始的步伐數是0
2. 每往前推進一步，就要扣一步
3. 每往前推進一步就確認，目前殘餘的步伐數，和現在位置的步伐數，哪一個大
4. 遇到0，代表這格不會獲得任何步伐數，要看手上的步伐數能不能跳過0

# 這個有錯誤，不能用
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_step = 0
        
        for n in nums:
            if n > max_step: #每往前推進一步就確認，目前殘餘的步伐數，和現在位置的步伐數，哪一個大
                max_step = n

            if n == 0 and max_step == 0: #遇到0，代表這格不會獲得任何步伐數，要看手上的步伐數能不能跳過0
                return False

            max_step = max_step - 1 #每往前推進一步，就要扣一步
        
        return True

但上述程式碼會遇到一個問題

例如 nums = [3, 0, 0, 0]

走到最後一格時其實已經走到終點，但 n == 0 且 手上剩餘步伐樹也是0，會導致誤判。

我覺得最好的處理方式是，不要管 nums的最後一格，不管他是數字多少，只要能走到這一格，就一定是 True。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_step = 0
        
        for n in nums[:(len(nums)-1)]:
            if n > max_step:
                max_step = n

            if n == 0 and max_step == 0:
                return False

            max_step = max_step - 1
            
        return True