算法之 跳跃游戏

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