【刷题】代码随想录算法训练营第三十五天|435、无重叠区间,763、划分字母区间 ,56、合并区间

目录

    • 435、无重叠区间
    • 763、划分字母区间
    • 56、合并区间

435、无重叠区间

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

左边界和有边界排序,注意sort的排序规则函数编写。

class Solution {
public:
    // 按照区间左边界排序
    static bool cmp (const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0]; // 左边界排序
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) return 0;
        sort(intervals.begin(), intervals.end(), cmp);

        int result = 1; // points 不为空至少需要一支箭
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] >= intervals[i - 1][1]) {
                result++; // 需要一支箭
            }
            else {  // 气球i和气球i-1挨着
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]); // 更新重叠气球最小右边界
            }
        }
        return intervals.size() - 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

建立hash索引,找到分割点。

class Solution {
public:
    vector<int> partitionLabels(string s) {
    int hash[26] = {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) {
            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

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        if (intervals.size() == 0) return result; // 区间集合为空直接返回
        // 排序的参数使用了lambda表达式
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});

        // 第一个区间就可以放进结果集里,后面如果重叠,在result上直接合并
        result.push_back(intervals[0]); 

        for (int i = 1; i < intervals.size(); i++) {
            if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间
                // 合并区间,只更新右边界就好,因为result.back()的左边界一定是最小值,因为我们按照左边界排序的
                result.back()[1] = max(result.back()[1], intervals[i][1]); 
            } else {
                result.push_back(intervals[i]); // 区间不重叠 
            }
        }
        return result;
    }
};

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

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

相关文章

智能评估时代:SurveyKing开源问卷系统YYDS

最近有同事在设计问卷系统&#xff0c;我碰巧在 GitHub 上发现了一个开源的问卷/考试系统&#xff0c;觉得它非常不错&#xff0c;给他推荐了下。今天我打算和家人们分享一下这个发现。 项目介绍 官方网站&#xff1a;https://surveyking.cn/ github地址&#xff1a;https://…

springboot整合websocket,超简单入门

springBoot整合webSocket&#xff0c;超简单入门 webSocket简洁 WebSocket 是一种基于 TCP 协议的全双工通信协议&#xff0c;它允许客户端和服务器之间建立持久的、双向的通信连接。相比传统的 HTTP 请求 - 响应模式&#xff0c;WebSocket 提供了实时、低延迟的数据传输能力。…

数据库(MySQL)基础:约束

一、概述 1.概念&#xff1a;约束是作用于表中字段上的规则&#xff0c;用于限制存储在表中的数据。 2.目的&#xff1a;保证数据库中数据的正确、有效性和完整性。 3.分类 约束描述关键字非空约束限制该字段的数据不能为nullnot null唯一约束保证该字段的所有数据都是唯一…

QX---mini51单片机学习---(6)独立键盘

目录 1键盘简绍 2按键的工作原理 3键盘类型 4独立键盘与矩阵键盘的特点 5本节相关原理图 6按键特性 7实践 1键盘简绍 2按键的工作原理 内部使用轻触按键&#xff0c;常态按下按键触点才闭合 3键盘类型 编码键盘与非编码键盘 4独立键盘与矩阵键盘的特点 5本节相关原理…

硬性清空缓存的方法

前端发布代码后&#xff0c;我们是需要刷新页面再验证的。有时候仅仅f5 或者ctrlshiftdelete快捷键仍然有历史缓存&#xff0c;这时可以通过下面的方法硬性清空缓存。 以谷歌浏览器为例&#xff0c;打开f12&#xff0c;右键点击刷新按钮&#xff0c;选择【清空缓存并硬性加载】…

计算机网络5——运输层2TCP原理

文章目录 一、传输控制协议 TCP 概述1、TCP最主要的特点2、TCP的连接 二、可靠传输的工作原理1、停止等待协议1&#xff09;无差错情况2&#xff09;出现差错3&#xff09;确认丢失和确认迟到4&#xff09;信道利用率 2、连续 ARQ协议 三、TCP 报文段的首部格式 一、传输控制协…

代码审计-PHP模型开发篇动态调试反序列化变量覆盖TP框架原生POP链

知识点 1、PHP审计-动态调试-变量覆盖 2、PHP审计-动态调试-原生反序列化 3、PHP审计-动态调试-框架反序列化PHP常见漏洞关键字 SQL注入&#xff1a; select insert update delete mysql_query mysqli等 文件上传&#xff1a; $_FILES&#xff0c;type"file"&…

Kafka 执行命令超时异常: Timed out waiting for a node assignment

Kafka 执行命令超时异常&#xff1a; Timed out waiting for a node assignment 问题描述&#xff1a; 搭建了一个kafka集群环境&#xff0c;在使用命令行查看已有topic时&#xff0c;报错如下&#xff1a; [rootlocalhost bin]# kafka-topics.sh --list --bootstrap-server…

Vue自定义封装音频播放组件(带拖拽进度条)

Vue自定义封装音频播放组件&#xff08;带拖拽进度条&#xff09; 描述 该款自定义组件可作为音频、视频播放的进度条&#xff0c;用于控制音频、视频的播放进度、暂停开始、拖拽进度条拓展性极高。 实现效果 具体效果可以根据自定义内容进行位置调整 项目需求 有播放暂停…

51单片机软件环境安装

keli5的安装 把CID放到破解程序中 破解程序会给一串数字然后填到那个框中 驱动程序的安装 安装完了以后 设备管理器会出现这个 同时c盘会出现这个文件夹

巨量千川的投放技巧,一站式全自动千川投流工具(抖音玩家必备)

随着抖音平台的快速发展&#xff0c;越来越多的品牌和广告商意识到抖音的潜力&#xff0c;并希望能够通过投放广告来获取更多的曝光和用户参与。在这个过程中&#xff0c;巨量千川成为了抖音玩家必备的一站式全自动千川投流工具&#xff0c;为广告商提供了投放技巧&#xff0c;…

word-快速入门

1、熟悉word界面 2、word排版习惯 3、排版文本基本格式 1、word界面 选项卡 功能组 点击功能组右下角小三角可以开启完整功能组&#xff0c;获得启动器 软件右上角有功能显示折叠按钮 2、排版好习惯 &#xff08;1&#xff09;随时保存 &#xff08;2&#xff09;规范文件命…

408算法题专项-2015

题目&#xff1a; 分析&#xff1a;时间复杂度尽可能高效&#xff0c;提示可能存在一种空间换时间的算法 思路一&#xff1a;空间换时间 思考&#xff1a;开数组储存结点数据域&#xff0c;对于只出现一次或多次出现第一次的&#xff0c;保留&#xff0c;对于多次出现的&…

流程详解!2024年成都市发明专利申请流程及各阶段操作要点

一、受理阶段 时间期限&#xff1a; 电子申请2天内&#xff0c;纸质申请当天现场提交&#xff0c;邮寄约为半月。 申请人&#xff1a; 1. 委托专利代理机构&#xff0c;签订委托代理协议和保密协议等&#xff1b; 2. 提供原始技术资料和个人以及单位信息等&#xff1b; 3…

片冰机工作原理

片冰机工作原理 1、制冰用的水需要加盐(行话叫做加药)至于多少量。看制冰量多少调制泵(柱塞泵)自动调整。 2、制冰机主体分两腔体外腔体内盘的一定密度的铜管。专业术语叫(蒸发腔)就是俗话讲的制冷的东西。 3、外腔体内是一个很规则的圆不锈钢腔体&#xff0c;中心有一三叶刮…

基于Django图像识别系统毕业设计(付源码)

前言&#xff1a;Django是一个由Python编写的具有完整架站能力的开源Web框架&#xff0c;Django本身基于MVC模型&#xff0c;即Model&#xff08;模型&#xff09;View&#xff08;视图&#xff09; Controller&#xff08;控制器&#xff09;设计模式&#xff0c;因此天然具有…

零售数据分析之连带销售分析怎么做

连带销售是指顾客在购买某款产品后&#xff0c;通常会顺手也买上另一款产品。这种情况在超市零售中屡见不鲜&#xff0c;因此通常来说在做超市零售数据分析时&#xff0c;都需要做一个详尽的连带销售分析。那么做零售数据分析中的连带销售分析&#xff0c;要计算分析哪些指标&a…

MBR与GPT分区表

文章目录 MBR分区表MBR分区表结构MBR分区表项查看U盘的分区表信息查看系统中所有磁盘的分区类型获取分区表信息 GPT分区表保护性MBRGPT分区表头格式GPT分区表项格式分区类型分区属性分区表项内容 MBR分区表 CHS &#xff1a;磁头&#xff08;Heads&#xff09;、柱面(Cylinder…

AH8651-220V转3.3V低成本方案

本篇文章将介绍一种220V转3.3V低成本方案&#xff0c;该方案采用AH8651芯片&#xff0c;无需外接电感&#xff0c;具有高效率的智能控制、宽广的交流输入范围、内置过流保护、欠压保护和过热自动关断等功能。AH8651可以通过SEL引脚选择输出电压&#xff0c;启动时通过内部高压电…

【连连国际注册/登录安全分析报告】

连连国际注册/登录安全分析报告 前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨…
最新文章