leetcode55 Jump Game 解題概念
2022 年 5 月 17 日
![](https://i0.wp.com/lazyinwork.com/wp-content/uploads/2022/05/image-24.png?resize=678%2C726&ssl=1)
題目會給一組正整數數列,我們會從第一個數字開始,數字顯示我們最多可以行走的距離,我們要確定該數列是否有可能可以抵達最終一個數字。
倒推法
這邊我們將目標設定為最後一個位置,然後我們從最後一個數字往前找,只要有滿足『位置+行走距離』大於等於『目標』的情況時,我們就會更新該位置為新的『目標』
class Solution:
def canJump(self, nums: List[int]) -> bool:
goal = len(nums)-1
for idx in range(goal,-1,-1):
val = nums[idx]
if idx+val >= goal:
goal = idx
return True if goal == 0 else False
最遠距離
這個概念是我們盡可能地往遠處走,我們記錄每個點最遠可以行走的距離,只要還沒有超過當前的最遠距離時,我們就會持續往下一個位置移動,並且更新最遠行走距離。
class Solution:
def canJump(self, nums: List[int]) -> bool:
if len(nums) == 1:
return True
farthest = nums[0]
idx = 0
while idx < len(nums)-1:
if farthest >= len(nums)-1:
return True
idx +=1
if idx > farthest:
return False
if idx+nums[idx]>farthest:
farthest = idx+nums[idx]