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

今天的三道题都是区间问题

435. 无重叠区间

讲解链接:https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html

思路分析在代码注释

class Solution {
public:
    static bool cmp(const vector<int>&a, const vector<int>& b) {
        if(a[0]==b[0])
            return a[1]<b[1];
        return a[0]<b[0];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),cmp);
        int result = 0;
        //和上一篇中的思想一样,需要一个变量来存储目前这个区间的右边界
        //初始为第一个区间的右边界
        int right_bound = intervals[0][1];
        //还是从第二个元素开始(若只有一个元素也没关系)
        for(int i=1;i<intervals.size();i++) {
            //合理的情况:(无交集)第二个区间的左边界 要大于等于第一个区间的右边界
            if(intervals[i][0] >= right_bound) {
                //更新右边界
                right_bound = intervals[i][1];
            }
            else {
                result++;
                //这里也需要对边界进行一个更新;
                right_bound = min(right_bound,intervals[i][1]);
                continue;
            }
        }
        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 {
public:
    vector<int> partitionLabels(string s) {
        //记录每一个字符的最后一个出现位置
        int hash[27] = {0};
        for(int i=0;i<s.size();i++) {
            hash[s[i]-'a'] = i;
        }
        vector<int> result;
        int left = 0;
        int right = 0;
        for(int i=0;i<s.size();i++) {
            //更新最远边界
            right = max(right,hash[s[i]-'a']);
            //集合划分条件: 下标与最远边界相同
            if(i==right) {
                //记录集合中的元素个数:利用right-left+1
                result.push_back(right-left+1);
                //同时更新下一个左界
                left = i+1;
            }
            
        }
        return result;
    }
};

56. 合并区间

讲解链接:https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html

新学了一招
result.back()[1] 表示 result 向量中最后一个区间的结束时间。result.back() 返回 result 向量中的最后一个元素,这是一个区间(向量)。然后 [1] 表示这个区间的结束时间。以下是一个详细解释:

result.back() 返回 result 的最后一个元素,它是一个 vector,代表一个区间。
result.back()[1] 返回这个区间的第二个元素,即区间的结束时间

class Solution {
public:
    static bool cmp(const vector<int>&a, const vector<int>& b){
        if(a[0]==b[0])
            return a[1]<b[1];
        return a[0]<b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size()<=1)
            return intervals;
        vector<vector<int>> result;
        sort(intervals.begin(),intervals.end(),cmp);
        
        //初始化这个左界
        //不可以这样赋值 : result[k][0] = intervals[0][0];
        result.push_back(intervals[0]);
        for(int i=1;i<intervals.size();i++) {
            //新学了一招
            //.back()是最后一个向量,.back()[0]左边界,[1]右边界
            if(intervals[i][0]<=result.back()[1]) {
                result.back()[1] = max(intervals[i][1],result.back()[1]);
            }
            else {
                result.push_back(intervals[i]);
            }
        }
        return result;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/673538.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

AI智能体|基于已有的扣子Coze Bot进行插件化改造

大家好&#xff0c;我是无界生长&#xff0c;国内最大AI付费社群“AI破局俱乐部”初创合伙人。 AI智能体&#xff5c;基于已有的扣子Coze Bot进行插件化改造本文通过案例演示的方式&#xff0c;介绍了如何将扣子Coze平台创建的Bot改造成插件并发布到插件商店供第三方使用。如果…

Python的文件管理

读取文件 首先我们可以先创建一个工程项目&#xff0c;如图所示&#xff1a; 打开我们名为1.读取文件.py的python文件&#xff0c;然后我们可以写下读取Python文件的代码&#xff0c;代码如下&#xff1a; f open("1.txt", "r") print(f.read()) f.clos…

burp插件new_xp_capcha识别验证码的简易安装

1.new_xp_capcha 插件是大佬开发的可以正常白嫖&#xff0c;感谢大佬&#xff0c;我找了个不需要任何高级操作就可以做的安装手法&#xff0c;因为我在网上搜了一下就发现这个的安装过程攻略都还蛮复杂&#xff0c;我这里用了个简单的手法 2.安装 下载地址&#xff1a;smxia…

[C][可变参数列表]详细讲解

目录 1.宏含义及使用2.宏原理分析1.原理2.宏理解 1.宏含义及使用 依赖库stdarg.hva_list 其实就是char*类型&#xff0c;方便后续按照字节进行指针移动 va_start(arg, num) 使arg指向可变参数部分(num后面) va_arg(arg, int) 先让arg指向下个元素&#xff0c;然后使用相对位置…

Wireshark 如何查找包含特定数据的数据帧

1、查找包含特定 string 的数据帧 使用如下指令&#xff1a; 双引号中所要查找的字符串 frame contains "xxx" 查找字符串 “heartbeat” 示例&#xff1a; 2、查找包含特定16进制的数据帧 使用如下指令&#xff1a; TCP&#xff1a;在TCP流中查找 tcp contai…

MySQL中:cmd下输入命令mysql -uroot -p 连接数据库错误

目录 问题cmd下输入命令mysql -uroot -p错误 待续、更新中 问题 cmd下输入命令mysql -uroot -p错误 解决 配置环境变量&#xff1a;高级系统设置——环境变量——系统变量——path编辑——新建——MySQL.exe文件路径&#xff08;如下图所示&#xff09; phpstudy2018软件下&am…

C语言 | Leetcode C语言题解之第127题单词接龙

题目&#xff1a; 题解&#xff1a; struct Trie {int ch[27];int val; } trie[50001];int size, nodeNum;void insert(char* s, int num) {int sSize strlen(s), add 0;for (int i 0; i < sSize; i) {int x s[i] - ;if (trie[add].ch[x] 0) {trie[add].ch[x] size;m…

Web安全:软件开发的安全问题与解决方案

「作者简介」&#xff1a;2022年北京冬奥会网络安全中国代表队&#xff0c;CSDN Top100&#xff0c;就职奇安信多年&#xff0c;以实战工作为基础对安全知识体系进行总结与归纳&#xff0c;著作适用于快速入门的 《网络安全自学教程》&#xff0c;内容涵盖系统安全、信息收集等…

C++类和对象下篇

&#x1f407; &#x1f525;博客主页&#xff1a; 云曦 &#x1f4cb;系列专栏&#xff1a;[C] &#x1f4a8;路漫漫其修远兮 吾将而求索 &#x1f49b; 感谢大家&#x1f44d;点赞 &#x1f60b;关注&#x1f4dd;评论 文章目录 &#x1f4d4;1、再谈构造函数&#x1f4f0;…

链表算法题(OJ刷题超详细讲解)

1.返回倒数第K个节点&#xff0c; OJ链接&#xff1a;返回倒数第K个节点 本题有很多种解法&#xff0c;例如创建数组&#xff0c;或者将原链表反转等等&#xff0c;这里们使用快慢指针&#xff0c;只需要遍历一遍链表&#xff0c;并且空间复杂度为O(1)&#xff0c;时间复杂度为…

【C++杂货铺】unordered系列容器

目录 &#x1f308; 前言&#x1f308; &#x1f4c1; unordered系列关联式容器 &#x1f4c1; 底层结构 &#x1f4c2; 哈希概念 &#x1f4c2; 哈希冲突 &#x1f4c2; 哈希函数 &#x1f4c2; 哈希冲突解决 &#x1f4c1; 模拟实现 &#x1f4c1; 总结 &#x1f308; 前…

Tailwindcss Layout布局相关样式及实战案例,5万字长文,附完整源码和效果截图

aspect 相关样式类 基础样式 ClassPropertiesaspect-autoaspect-ratio: auto;aspect-squareaspect-ratio: 1 / 1;aspect-videoaspect-ratio: 16 / 9; 案例&#xff1a;引入B站视频 Use the aspect-* utilities to set the desired aspect ratio of an element. 使用’ asp…

k8s学习--ConfigMap详细解释与应用

文章目录 一 什么是configmapConfigMap 的好处ConfigMap 的限制 二.创建ConfigMap的4种方式1.在命令行指定参数创建2.在命令行通过多个文件创建3.在命令行通过文件提供多个键值对创建4.YAML资源清单文件创建 三 configmap的两种使用方法1.通过环境变量的方式传递给pod2.通过vol…

Java(十二)---认识异常

文章目录 前言1. 异常的概念与体系结构1.1.异常的概念1.异常的体系1.3 异常的分类 2. 异常的处理2.1 防御式编程2.2 异常的抛出2.3 异常的捕获2.3.1 异常声明throws2.3.2 try-catch捕获并处理2.3.3 finally 2.4 异常的处理流程 3. 自定义异常类 前言 这一篇就是咱们学习JavaSE…

学习笔记——网络参考模型——TCP/IP模型(传输层)

四、TCP/IP模型-传输层 一、TCP 1、TCP定义 TCP(Transmission Control Protocol&#xff0c;传输控制协议)∶为应用程序提供可靠的面向连接的通信服务。目前&#xff0c;许多流行的应用程序都使用TCP。 连接&#xff1a;正式发送数据之前&#xff0c;提前建立好一种虚拟的&…

String常用操作

String常用方法 构造字符串 常用的构造字符串有3种&#xff1a; 1.直接赋值String s "abcd"; 2.实例化调用构造方法String s new String("abcd"); 3.实例化传字符数组 char[] ch {a,b,c,d}; String s new String(ch);字符串比较 比较 比较的是两个…

40.8K开源交流社区平台:Discourse

Discourse&#xff1a; 开放源代码&#xff0c;打造社区讨论的自由家园- 精选真开源&#xff0c;释放新价值。 概览 Discourse是一个完全开源的社区平台&#xff0c;为那些希望完全控制自己网站运行方式和地点的组织和个人提供服务。经过十多年的实战考验&#xff0c;Discours…

索引 ---- mysql

目录 1. 索引 1.1 概念 1.2 作用 1.3 使用场景 1.4 使用 1.4.1查看索引 1.4.2 创建索引 1.4.3 删除索引 1.5 注意事项 1.6 索引底层的数据结构 (面试经典问题) 1. 索引 1.1 概念 索引是一种特殊的文件&#xff0c;包含着对数据表里所有记录的引用指针。可以对表中的…

数据库(18)——DCL权限控制

MySQL常用权限 权限说明ALL,ALL PRIVILEGES所有权限SELECT查询数据INSERT插入数据UPDATE修改数据DELETE删除数据ALTER修改表DROP删除数据库/表/视图CREATE创建数据库/表 DCL语法 查询权限 SHOW GRANTS FOR 用户名主机名; 查询hello的权限 SHOW GRANTS FOR hellolocalhost; 授…

方法重写

自学python如何成为大佬(目录):https://blog.csdn.net/weixin_67859959/article/details/139049996?spm1001.2014.3001.5501 基类的成员都会被派生类继承&#xff0c;当基类中的某个方法不完全适用于派生类时&#xff0c;就需要在派生类中重写父类的这个方法&#xff0c;这和…