55.跳躍游戲

55.跳躍游戲

靈神思路

思路分析： 兩種思路，思路1是我們可以直接維護當前到達i的時候所能到達的最右的邊界mr，如果i>mr就說明無法到達i,否則就是可以到達；思路2是可以將每一個nums[i] 轉換為 [i,i+nums[i]]的這樣的一個區間，這樣我們只需通過合并每一個區間，如果合并之后的區間包含完整的區間，那么就說明可以可以到達的

思路1：

class Solution:def canJump(self, nums: List[int]) -> bool:# 維護最右可以到達的位置mr = 0for i,c in enumerate(nums):# 如果當前所需到達的坐標大于先前可以到達的最右邊的距離，那么就直接返回falseif i > mr :return Falsemr = max(mr,i+c)return True

思路2：區間合并

思路參考：56.合并區間

56.合并區間

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:# 直接合并就好了，start,end 記錄當前區間的開始與結尾# 然后遍歷后面一個區間，判斷 start1是否大于end,如果大于就將當前區間加入，并更新新的start和end# 否則就合并# 先進行排序,先按照開始時間進行升序intervals.sort(key = lambda x :x[0] )n = len(intervals)ans = []start = intervals[0][0]end = intervals[0][1]for i in range(1,n):if intervals[i][0] <= end:# 當后面一個活動的開始時間在前面的一個結束時間之前，合并的時候結束時間取它們的較大值end = max(end,intervals[i][1])else:ans.append([start,end])start,end = intervals[i][0],intervals[i][1]# 最后一個還需要加入ans.append([start,end])return ans

參照這個區間合并的思路，寫出對應的題解

class Solution:def canJump(self, nums: List[int]) -> bool:# 使用區間合并的算法進行求解# nums[i] 轉換為 [i,i+nums[i]]n = len(nums)start,end = 0,0+nums[0]for i in range(1,n):# 當當前的坐標，也就是區間的開始小于前面的區間的結尾，說明可以合并，然后就更新endif i <= end:end = max(i+nums[i],end)if end>=n-1:return Trueelse:return False