LeetCode 筆記 - 55. Jump Game

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

也許你也會想看看