LeetCode 筆記 - 55. Jump Game

Posted on 標籤
跳跳遊戲系列首題，判定是否能抵達數列終點。本文警告讀者避免落入動態規劃的複雜度陷阱，改採只需紀錄「最遠可抵達位置」的貪婪思維。這種線性掃描法能以極高的效率完成判定，是學習貪婪策略與範圍判斷的優質案例。
⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 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

也許你也會想看看