首页 > 编程语言 >36天【代码随想录算法训练营34期】第八章 贪心算法 part05( ● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间 )

36天【代码随想录算法训练营34期】第八章 贪心算法 part05( ● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间 )

时间:2024-04-25 18:24:35浏览次数:32  
标签:end int 随想录 List len 算法 intervals result 区间

435. 无重叠区间

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        count = 0
        intervals.sort(key=lambda x: x[0])

        for i in range(1, len(intervals)):
            if intervals[i][0] < intervals[i-1][1]:
                intervals[i][1] = min(intervals[i][1], intervals[i-1][1])
                count += 1
        return count

763.划分字母区间

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        table = {}
        start = 0
        end = 0
        result = []

        for i in range(len(s)):
            table[s[i]] = i

        for i in range(len(s)):
            end = max(end, table[s[i]])
            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]]:
        if len(intervals) == 0:
            return intervals
        intervals.sort(key=lambda x: x[0])
        result = [intervals[0]]

        for i in range(1, len(intervals)):
            if result[-1][1] >= intervals[i][0]:
                result[-1][1] = max(intervals[i][1], result[-1][1])
            else:
                result.append(intervals[i])

        return result

标签:end,int,随想录,List,len,算法,intervals,result,区间
From: https://www.cnblogs.com/miramira/p/18158317

相关文章

  • 使用 Redis 实现限流——滑动窗口算法
    用Go语言实现滑动窗口限流算法,并利用Redis作为存储后端,可以按照以下步骤进行设计和编码。滑动窗口限流的核心思想是维护一个固定时间窗口,并在窗口内记录请求次数,当窗口滑动时,旧的请求计数被移除,新的请求计数被添加。这里以Redis的有序集合(SortedSet,简称ZSet)作为数据结构,因......
  • 56. 合并区间(leetcode)
    https://leetcode.cn/problems/merge-intervals/?envType=study-plan-v2&envId=top-100-liked合并区间练习题typedefpair<int,int>PII;vector<PII>segs;classSolution{public:vector<vector<int>>merge(vector<vector<int>>......
  • 输入‘(’和‘)’判断字符串有效的函数算法
    ``//设置一个函数,通过输入键盘中的‘(’和‘)’判断字符串是否有效//顺序表中的元素数据类型是char类型typedefcharDataType_t;//创建顺序栈SequenceStack各项数据(栈底地址栈容量栈顶元素下标)的结构体typedefstructSequenceStack{DataType_t*Bottom;//记录栈......
  • [算法学习笔记] 并查集
    提示:本文并非并查集模板讲解,是在模板基础上的进一步理解以及拓展。Review并查集可以用来维护集合问题。例如,已知\(a,b\)同属一个集合,\(b,c\)同属一个集合。那么\(a,b,c\)都属一个集合。并查集分为合并,查询操作。定义\(fa_i\)表示点\(i\)的父亲。为了降低复杂度,在fi......
  • 导数: 如何理解$f(x)$在某一区间内可导
    设函数\(y=|x|\),其函数图像如下所示:可见\(x=0\)时,\(y=0\)。其函数图像于\(x=0\)处存在1个“棱角”。这意味着\(y\)在\(x=0\)处是不可导的,因为\(y\)呈现的函数图像是有棱角的,“非光滑的”,即不是曲线。反之,若已知另一个函数\(f(x)\)在例如开区间\((a,b)\)内是可导的,则\(f(x)\)......
  • 用一个尽可能高效的算法,查找单向链表(有头结点)中倒数第k个位置上的结点
    思路  定义两个指向链表首结点的指针变量,第一个指针变量向后移动k个位置后,第二个指针变量也开始跟着一起向后移动,直到第一个指针变量指向尾结点为止,第二个指针变量指向的位置结点就是倒数第k个结点。实现步骤及参考代码(C语言)intLList_FindLK(LList_t*Head,DataType_tda......
  • 某数5代--算法版分析
    提示:本文章仅供学习交流,严禁用于非法用途,如有不当可联系本人删除!文章于2024-4-24发布  网站:aHR0cDovL3d3dy5uaGMuZ292LmNuL3dqdy9nZnh3amovbGlzdC5zaHRtbA==  r5方法与r4流程基本一致,区别在于两点:1、rs5没有假cookie。2、rs5需要动态获取20位数组值,不同于rs4的是需要调用动......
  • 为什么自动驾驶领域发论文都是用强化学习算法,但是实际公司里却没有一家使用强化学习算
    为什么自动驾驶领域发论文都是用强化学习算法,但是实际公司里却没有一家使用强化学习算法?——(特斯拉今年年初宣布推出实际上第一款纯端到端的自动驾驶系统,全部使用强化算法,替换掉原有的30万行C++的rule-based代码)给出一个自己比较认可的答案:https://www.zhihu.com/question/54......
  • 汽车诊断仪算法保护芯片——LKT4305-GM
    各类车载设备在车辆上的广泛应用,为分析道路交通事故原因和真相、界定道路交通事故性质和厘清事故责任提供基础数据,汽车诊断仪内的数据安全通过特定功能的安全芯片来建立,这里推荐款芯片——LKT4305-GM。LKT4305-GM是以32位安全处理器为基础的具有高性能高安全性的加密产品。芯片满......
  • 算法小笔记0424
    1在C++中,multiset是一种容器适配器,它允许存储多个具有相同键的元素。它是set的一个变体,与set不同的是,multiset允许重复的元素。multiset中的元素按照特定的排序标准自动排序,这个排序标准是在容器创建时指定的。下面是一个使用multiset的简单示例:#include<iostream>......