力扣:435. 无重叠区间(贪心)

题目:

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。

注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1:
输入:s = “ababcbacadefegdehijhklij”
输出:[9,7,8]
解释:
划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的,因为划分的片段数较少。
示例 2:

输入:s = “eccbbbbdec”
输出:[10]

提示:

1 <= s.length <= 500
s 仅由小写英文字母组成

思路:

本题跟 力扣:452用最少的箭引爆气球 思路类似,可以直接参照力扣:452. 用最少数量的箭引爆气球(贪心)这里就不做过多描述

完整代码:

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        # 按照区间起始点对intervals进行排序
        intervals.sort(key = lambda x : x[0])
        result = 0
        for i in range(1, len(intervals)):
            # 如果当前区间的起始点小于前一个区间的结束点,说明需要移除重叠的区间
            if intervals[i][0] < intervals[i - 1][1]:
                result += 1
                # 更新当前区间的结束点为两个区间结束点的最小值
                intervals[i][1] = min(intervals[i][1], intervals[i - 1][1])
        return result

相关推荐

  1. 435. 重叠区间贪心

    2023-12-29 23:06:04       55 阅读
  2. 【LeetCode-435重叠区间(贪心)

    2023-12-29 23:06:04       60 阅读
  3. -435.重叠空间

    2023-12-29 23:06:04       56 阅读
  4. 435. 重叠区间

    2023-12-29 23:06:04       42 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2023-12-29 23:06:04       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2023-12-29 23:06:04       101 阅读
  3. 在Django里面运行非项目文件

    2023-12-29 23:06:04       82 阅读
  4. Python语言-面向对象

    2023-12-29 23:06:04       91 阅读

热门阅读

  1. Leetcode的AC指南 —— 哈希法:454. 四数相加 II

    2023-12-29 23:06:04       71 阅读
  2. 配置LDAP 用户连接Oracle

    2023-12-29 23:06:04       62 阅读
  3. 算法笔记(模拟最大三数乘积问题)

    2023-12-29 23:06:04       59 阅读
  4. 三维点通用排序

    2023-12-29 23:06:04       63 阅读
  5. 算术整除——扩散型dp

    2023-12-29 23:06:04       49 阅读
  6. 二维数组调整

    2023-12-29 23:06:04       64 阅读
  7. 算法图解:第七章 狄克斯特拉算法 dijkstra

    2023-12-29 23:06:04       46 阅读
  8. FastAPI使用异步Redis

    2023-12-29 23:06:04       72 阅读
  9. Flink实时电商数仓(九)

    2023-12-29 23:06:04       52 阅读
  10. mysql(51) : 大数据导出为insert, 支持条件查询

    2023-12-29 23:06:04       65 阅读
  11. python3.x编码解码unicode字符串

    2023-12-29 23:06:04       58 阅读
  12. 【AI】人工智能爆发推进器之变分自动编码器

    2023-12-29 23:06:04       62 阅读