算法之 跳跃游戏

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 = 0
        for i,c in enumerate(nums):
            # 如果当前所需到达的坐标大于先前可以到达的最右边的距离，那么就直接返回false
            if i > mr :
                return False
            mr = 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):
            # 当当前的坐标，也就是区间的开始小于前面的区间的结尾，说明可以合并，然后就更新end
            if i <= end:
                end = max(i+nums[i],end)
        if end>=n-1:
            return True
        else:
            return False