題目出處

55. Jump Game

難度

Medium

個人範例程式碼

一開始建了一個新的答案的 list

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

        max_can_reach_idx = [0 for _ in range(len(nums))]
        for i, num in enumerate(nums):
            if i == 0:
                max_can_reach_idx[0] = num+i
            if i > 0 and max_can_reach_idx[i-1] >= i:
                max_can_reach_idx[i] = max(max_can_reach_idx[i-1], num+i)

        return max_can_reach_idx[-1] > 0

後來發現可以簡化至單一個 max_idx 即可，並當發現不行時，提早 early return

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_idx = 0
        for i, num in enumerate(nums):
            if i > max_idx: # can not reach, first 0 > 0 
                return False
            max_idx = max(num+i, max_idx)

        return max_idx >= len(nums)-1 # 4 >= 5-1

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

透過建立一個新的 list，我們紀錄

1. 前一個 idx 最大可抵達的位置
2. 相比前一個 idx 最大可抵達位置，看下一個位置是否能抵達，同時取 max(此位置能抵達的最遠, 上一個位置能抵達的最遠)

input handling

如果 input len <= 1，return True

Boundary conditions

後來優化的版本中，其實當發現 max_idx 已經到不了的時候，就已經可以 early return 了
第一個版本是一定會算完

Reference

• 1-6 lines, O(n) time, O(1) space