2024-01-03 无重叠区间

发布时间:2024年01月10日

435. 无重叠区间

思路:和最少数量引爆气球的箭的思路基本都是一致了!贪心就是比较左边的值是否大于下一个右边的值

img

class Solution:
    def eraseOverlapIntervals(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x: (x[0], x[1]))
        # 比较边界
        res = points[0][1]
        count = 0
        for i in range(1, len(points)):
            if points[i][0] < res:
                res = min(res, points[i][1])
                count += 1
            else:
                res = points[i][1]
        return count

763. 划分字母区间

贪心思路:第一个字母最后出现的位置的过程中其他字母也出现的最后位置的最大值,就是一次划分区域了!

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

763.划分字母区间

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        # 字母出现次数?
        # 每一次字母最后出现的位置以及
        mm = {}
        for i in range(len(s)):
            mm[s[i]] = i
        start = 0
        max_temp = mm[s[0]]
        res = []
        for i in range(len(s)):
            if max_temp == i:
                res.append(max_temp - start + 1)
                start = i + 1
                if i + 1 < len(s):
                    max_temp = mm[s[i + 1]]
            elif mm[s[i]] > max_temp:
                max_temp = mm[s[i]]
        return res
    
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last_occurrence = {}  # 存储每个字符最后出现的位置
        for i, ch in enumerate(s):
            last_occurrence[ch] = i

        result = []
        start = 0
        end = 0
        for i, ch in enumerate(s):
            end = max(end, last_occurrence[ch])  # 找到当前字符出现的最远位置
            if i == end:  # 如果当前位置是最远位置,表示可以分割出一个区间
                result.append(end - start + 1)
                start = i + 1

        return result

56. 合并区间

思路:就是如果区间的重叠的哇,就去重叠区间之间的最小值和最大值!关键还是拆分排序

在这里插入图片描述

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        res = []
        intervals.sort(key=lambda x :(x[0], x[1]))
        index = 0
        max_broad = intervals[0][1]
        for i in range(1, len(intervals)):
            if intervals[i][0] <= max_broad:
                intervals[index][0] = min(intervals[index][0], intervals[i][0])
                intervals[index][1] = max(intervals[index][1], intervals[i][1])
                max_broad = intervals[index][1]
            else:
                res.append(intervals[index])
                index = i
                max_broad = intervals[i][1]
        if intervals[index] not in res:
            res.append(intervals[index])
        return res

文章来源:https://blog.csdn.net/niuzai_/article/details/135514353
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。