app与网站的区别是什么,福田公司怎么样,网站建设公司易下拉软件,树莓派可以用wordpress文章目录 55.跳跃游戏思路参考#xff1a;56.合并区间 55.跳跃游戏
55.跳跃游戏
灵神思路 思路分析#xff1a; 两种思路#xff0c;思路1是我们可以直接维护当前到达i的时候所能到达的最右的边界mr#xff0c;如果imr就说明无法到达i,否则就是可以到达#xff1b;… 文章目录 55.跳跃游戏思路参考56.合并区间 55.跳跃游戏
55.跳跃游戏
灵神思路 思路分析 两种思路思路1是我们可以直接维护当前到达i的时候所能到达的最右的边界mr如果imr就说明无法到达i,否则就是可以到达思路2是可以将每一个nums[i] 转换为 [i,inums[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,ic)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,inums[i]]n len(nums)start,end 0,0nums[0]for i in range(1,n):# 当当前的坐标也就是区间的开始小于前面的区间的结尾说明可以合并然后就更新endif i end:end max(inums[i],end)if endn-1:return Trueelse:return False
