如何做网站活动,国外设计作品,免费网站免费网站平台,新区网站建设435. 无重叠区间
https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html
考点 贪心算法重叠区间 我的思路 先按照区间左坐标进行排序#xff0c;方便后续处理进行for循环#xff0c;循环范围是0到倒数第二个元素如果当前区间和下一区间重叠…435. 无重叠区间
https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html
考点 贪心算法重叠区间 我的思路 先按照区间左坐标进行排序方便后续处理进行for循环循环范围是0到倒数第二个元素如果当前区间和下一区间重叠结果计数加1同时令下一区间的右坐标等于两个区间右坐标中的较小者这里体现出了贪心的思路因为取较小者即令区间尽可能小也就降低了其与其它区间重叠的可能计数完毕后返回即可 视频讲解关键点总结 和我的思路类似 我的思路的问题 无 代码书写问题 无 可执行代码
class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) - int:intervals.sort(keylambda x: x[0])result 0for i in range(len(intervals) - 1):if intervals[i 1][0] intervals[i][1]:result 1intervals[i 1][1] min(intervals[i][1], intervals[i 1][1])return result*763.划分字母区间
https://programmercarl.com/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.html
考点 本题不是贪心但思路近似于重叠区间因此放到这里如何记录字母最后出现的位置有了字母最后位置如何让整个区间的字母均满足要求 我的思路 无思路 视频讲解关键点总结 本题两个关键点写在了考点里一先遍历一遍字符串记录每个字符出现的最后位置的索引二在循环遍历字符串的过程中用一个变量记录遍历过的字符所对应的索引最大值当当前索引和最大值吻合时记录一次结果 我的思路的问题 无思路 代码书写问题 无 可执行代码
class Solution:def partitionLabels(self, s: str) - List[int]:last_position [0] * 26for i in range(len(s)):last_position[ord(s[i]) - ord(a)] iresult []start_index 0end_index 0for i in range(len(s)):end_index max(end_index, last_position[ord(s[i]) - ord(a)])if i end_index:result.append(i - start_index 1)start_index end_index 1end_index 0return result*56. 合并区间
https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html
考点 贪心算法重叠区间 我的思路 如果区间有重叠将区间合并知道当前区间和下一区间不重叠将当前区间加入结果 视频讲解关键点总结 先将第一个区间加入结果列表中之后判断原列表的当前区间与结果列表的最后一个区间是否重叠如果重叠更新结果列表的最后一个区间如果不重叠直接把当前区间加入结果列表 我的思路的问题 会遗漏最后一个区间 代码书写问题 无 可执行代码
class Solution:def merge(self, intervals: List[List[int]]) - List[List[int]]:intervals.sort(keylambda x: x[0])result [intervals[0]]for i in range(1, len(intervals)):if result[-1][1] intervals[i][0]:result[-1][0] min(intervals[i][0], result[-1][0])result[-1][1] max(intervals[i][1], result[-1][1])else:result.append(intervals[i])return result
