LeetCode 筆記 - 55. Jump Game

Posted on

題目在此 55. Jump Game

給一個數列，從 index 0 開始，數列裡面代表 i 可以跳幾步
請問是否可以跳到最後？

解題思維

歡迎來跳跳遊戲系列的第一題 ☺️

這題很直覺的就想要用 Dynamic programming 開始看過去的結果
這是惡魔的陷阱，千萬不要就這樣跳下去了同學

這題就單純記錄一下，最遠可以到達的 index 即可

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        
        if (size := len(nums)) == 1:
            return True
        
        max_index = 0
        for i in range(size):
            max_index = max(max_index, i + nums[i])
            
            if max_index >= size - 1:
                return True
            if max_index == i:
                return False
            
        return True

相關文章