代码随想录算法训练营第三十六天丨435. 无重叠区间、763. 划分字母区间、56. 合并区间

本文主要是介绍代码随想录算法训练营第三十六天丨435. 无重叠区间、763. 划分字母区间、56. 合并区间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

435. 无重叠区间

我的思路：

跟昨天的第三题很像，按照右边界排序，记录当前非重叠区间的右边界用于检测下个区间起点，由于区间按照右边界有序，非重叠区域右界必定是判断过的最小值；迭代结束即可得到结果。

class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:intervals.sort(key=lambda x: x[1])start = intervals[0][1]res = 0for interval in intervals[1:]:if interval[0] < start:res += 1else:start = interval[1]return res

优化思路：

可以只判断一次，记录非重叠区域数量。

class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:intervals.sort(key=lambda x: x[1])start = intervals[0][1]count = 1for interval in intervals[1:]:if interval[0] >= start:count +=1start = interval[1]return len(intervals) - count

763. 划分字母区间

我的思路：

遍历一次字符串，记录每个字符最后一次出现的位置。遍历字符串，对于每个字符，更新当前片段的结束位置 end 为当前字符的最后出现位置。如果当前位置达到了 end，说明当前片段结束，记录当前片段的长度，并将 start 更新为 end，表示开始下一个片段。

class Solution:def partitionLabels(self, s: str) -> List[int]:n = len(s)last_pos = collections.defaultdict()for i, char in enumerate(s):last_pos[char] = ires = []i = 0start = 0while i < n:end = last_pos[s[i]] + 1while i < end:if last_pos[s[i]] + 1 > end:end = last_pos[s[i]] + 1i += 1res.append(end - start)start = endreturn res

优化：

代码量有点大，其实可以直接写for循环。

import collectionsclass Solution:def partitionLabels(self, s: str) -> List[int]:n = len(s)last_pos = collections.defaultdict(int)for i, char in enumerate(s):last_pos[char] = ires = []start = 0end = 0for i in range(n):end = max(end, last_pos[s[i]])if i == end:res.append(end - start + 1)start = i + 1return res

可以用数组做哈希，这里不再改写了...

56. 合并区间

我的思路：

ac了，但是思路有点问题，我一开始想的是对右边界排序；改成左边界直接AC了，并没有能想明白。

初始化左边界和右边界为第一个interval。遍历剩下的interval，如果遇到不相交的，把当前的左右边界作为结果记录；如果相交，更新左右边界。

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort()cur_left,cur_right = intervals[0][0], intervals[0][1]res = []for interval in intervals[1:]:if interval[0] > cur_right:res.append([cur_left, cur_right])cur_left, cur_right = interval[0], interval[1]else:cur_left = min(cur_left, interval[0])cur_right = max(cur_right, interval[1])res.append([cur_left, cur_right])return res

仔细研究了一下，还是没能正确理解排序的作用，其实左边界已经有序了，左边界直接加入结果，如果有重叠直接更新右边界就可以了。

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort()res = []for interval in intervals:if not res or interval[0] > res[-1][1]:res.append(interval)else:res[-1][1] = max(res[-1][1], interval[1])return res

这个就是题解方法了！

如果对右边界排序，则需要从后向前遍历，因为右边界有序，从后遍历右边界一定是更大的。

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort(key=lambda x: x[1])  # 按照右边界排序res = []while intervals:cur_left, cur_right = intervals.pop()while intervals and intervals[-1][1] >= cur_left:cur_left = min(cur_left, intervals[-1][0])intervals.pop()res.append([cur_left, cur_right])return res

这篇关于代码随想录算法训练营第三十六天丨435. 无重叠区间、763. 划分字母区间、56. 合并区间的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---