第三十六天| 435. 无重叠区间、763.划分字母区间、56. 合并区间
Leetcode 435. 无重叠区间
题目链接:435 无重叠区间
题干:给定一个区间的集合
intervals,其中intervals[i] = [starti, endi]。返回 需要移除区间的最小数量,使剩余区间互不重叠 。
思考:贪心法。和452 用最少数量的箭引爆气球原理类似。按照左边界排序,从左向右记录多余交叉区间的个数。或者按照右边界排序,从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间的个数。

此图先按右边界排序,之后记录非交叉区间的个数还是有技巧的。取 区间1 和 区间2 右边界的最小值,因为这个最小值之前的部分一定是 区间1 和区间2 的重合部分,如果这个最小值也触达到区间3,那么说明 区间 1,2,3都是重合的。
代码一(按右边界排序):
class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b) {return a[1] < b[1]; //按右边界排序}int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.size() == 0) return 0;sort(intervals.begin(), intervals.end(), cmp); //排序int count = 1; //记录非重叠区间个数int end = intervals[0][1]; //记录当前重叠区间右边界for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] >= intervals[i - 1][1])count++;elseintervals[i][1] = min(intervals[i][1], intervals[i - 1][1]); //更新重叠区间右边界}return intervals.size() - count;}
};
代码二(按左边界排序):
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 = 0; //记录多余重叠区间个数for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] < intervals[i - 1][1]) { //存在重叠区间intervals[i][1] = min(intervals[i][1], intervals[i - 1][1]); //更新重叠区间右边界result++;}}return result;}
};
Leetcode 763.划分字母区间
题目链接:763 划分字母区间
题干:给你一个字符串
s。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是
s。返回一个表示每个字符串片段的长度的列表。
1 <= s.length <= 500s仅由小写英文字母组成
思考:贪心法。先寻找所有字母的最后出现的下标位置,和其首次出现的位置形成区间。接下来将重叠的区间合并起来,并记录每个不重叠区间的大小。由于按顺序遍历字符串因此在合并区间时只需要更新右边界,在不重叠时初始化新区间的边界。
代码:
class Solution {
public:vector<int> partitionLabels(string s) {int lastPresence[27] = { 0 }; //记录所有字母最后出现的下标位置for (int i = 0; i < s.size(); i++) lastPresence[s[i] - 'a'] = i;int left = 0; //记录区间的左边界int right = 0; //记录区间的右边界vector<int> result;for (int i = 0; i < s.size(); i++) {right = max(right, lastPresence[s[i] - 'a']); //更新当前区间右边界if (i == right) {result.push_back(right - left + 1);left = i + 1; //新区间左边界}}return result;}
};
Leetcode 56. 合并区间
题目链接:56 合并区间
题干:以数组
intervals表示若干个区间的集合,其中单个区间为intervals[i] = [starti, endi]。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
思考:贪心法。本题和435. 无重叠区间非常相似,都是先排序后再处理。区别:处理过程中如果记录区间和当前处理区间存在重叠,则更新记录区间的右边界,否则记录当前处理区间。
代码:
class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b) {return a[0] < b[0]; //按左区间排序}vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;if (intervals.size() == 0) return result;sort(intervals.begin(), intervals.end(), cmp);result.push_back(intervals[0]); //将首个区间放入结果集,后面出现重叠则修改右边界for (int i = 1; i < intervals.size(); i++) {if (result.back()[1] >= intervals[i][0])result.back()[1] = max(result.back()[1], intervals[i][1]); //更新重叠区间右边界elseresult.push_back(intervals[i]); //区间不重叠则加入新区间}return result;}
};
自我总结:
- 逐步理解贪心法处理区间问题,排序+特殊处理。
相关文章:
第三十六天| 435. 无重叠区间、763.划分字母区间、56. 合并区间
Leetcode 435. 无重叠区间 题目链接:435 无重叠区间 题干:给定一个区间的集合 intervals ,其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 。 思考:贪心法。和452 用最少数量的…...
React setState同步还是异步
React18 setState是同步还是异步?_react18 同步-CSDN博客 React18之前或者React18使用了ReactDOM.render,setState在React调度流程中是异步更新,在原生事件和setTimeout中是同步更新。React18使用ReactDOM.createRoot,那么默认都是…...
Docker安装和使用Redis
Docker安装和使用Redis 一、拉取 Redis 镜像二、根据镜像运行容器三、配置 Redis 密码1、进入 redis 容器内部2、使用 redis 命令行设置密码 一、拉取 Redis 镜像 docker pull redis二、根据镜像运行容器 docker run \ --name redis \-p 6379:6379 \-d \redis \redis-server …...
四分位距IQR_ interquartile range
四分位距IQR_ interquartile range 1 IQR(Interquartile Range)四分位距的含义2 如何计算IQR参考: 1 IQR(Interquartile Range)四分位距的含义 官方定义: 四分位距(interquartile range, IQR&a…...
Vision Transformer - VIT
文章目录 1. Embedding层2. Encoder层3. MLP Head层4. Hybrid混合模型 论文:An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale 网址:https://arxiv.org/abs/2010.11929 Hybrid - 传统CNN和Transformer混合模型 模型架构 输…...
HTTP与HTTPS:网络安全之门户
源码分享 https://docs.qq.com/sheet/DUHNQdlRUVUp5Vll2?tabBB08J2 在进行网页爬取和数据收集时,我们经常会与HTTP(超文本传输协议)和HTTPS(安全的超文本传输协议)打交道。这两种协议都用于互联网上的数据传…...
头歌:共享单车之数据分析
第1关 统计共享单车每天的平均使用时间 package com.educoder.bigData.sharedbicycle;import java.io.IOException; import java.text.ParseException; import java.util.Collection; import java.util.Date; import java.util.HashMap; import java.util.Locale; import java…...
MySQL的数据类型和细节
1.整型 数值类型字节描述TINYINT[UNSIGNED]1很小的整数,默认有符号 [-128,127]/[0,255]SMALLINT[UNSIGNED]2较小的整数,默认有符号 [-32768,32767]/[0,65535]MEDIUMINT[UNSIGNED]3中等的整数,默认有符号 [-8388608,8388607]/[0,16777215]…...
自建AWS S3存储服务
unsetunset前言unsetunset AWS S3(Amazon S3,全名为亚马逊简易存储服务),是亚马逊公司利用其亚马逊网络服务系统所提供的网络在线存储服务。我常用的很多SaaS服务中提供的文件存储功能,底层也都是AWS S3,比…...
『论文阅读|研究用于视障人士户外障碍物检测的 YOLO 模型』
研究用于视障人士户外障碍物检测的 YOLO 模型 摘要1 引言2 相关工作2.1 障碍物检测的相关工作2.2 物体检测和其他基于CNN的模型 3 问题的提出4 方法4.1 YOLO4.2 YOLOv54.3 YOLOv64.4 YOLOv74.5 YOLOv84.6 YOLO-NAS 5 实验和结果5.1 数据集和预处理5.2 训练和实现细节5.3 性能指…...
LeetCode--1445. 苹果和桔子
文章目录 1 题目描述2 测试用例3 解题思路 1 题目描述 表: Sales ------------------------ | Column Name | Type | ------------------------ | sale_date | date | | fruit | enum | | sold_num | int | ------------------------(sale…...
Java基础知识
一、标识符规范 标识符必须以字母(汉字)、下划线、美元符号开头,其他部分可以是字母、下划线、美元符号,数字的任意组合。谨记不能以数字开头。java使用unicode字符集,汉字也可以用该字符集表示。因此汉字也可以用作变量名。 关键字不能用作…...
并发编程-Synchronized
什么是Synchronized synchronized是Java提供的一个关键字,Synchronized可以保证并发程序的原子性,可见性,有序性。 我们会把synchronized称为重量级锁。主要原因,是因为JDK1.6之前,synchronized是一个重量级锁相比于J…...
C语言——从头开始——深入理解指针(1)
一.内存和地址 我们知道计算上CPU(中央处理器)在处理数据的时候,是通过地址总线把需要的数据从内存中读取的,后通过数据总线把处理后的数据放回内存中。如下图所示: 计算机把内存划分为⼀个个的内存单元,每…...
微信小程序-绑定数据并在后台获取它
如图 遍历列表的过程中需要绑定数据,点击时候需要绑定数据 这里是源代码 <block wx:for"{{productList}}" wx:key"productId"><view class"product-item" bindtap"handleProductClick" data-product-id"{{i…...
【删除数组用delete和Vue.delete有什么区别】
删除数组用delete和Vue.delete有什么区别? 在 JavaScript 中,delete 和 Vue.js 中的 Vue.delete 是两个完全不同的概念,它们在删除数组元素时的作用和效果也有所不同。 JavaScript 中的 delete 关键字: 在原生 JavaScript 中&a…...
【QT+QGIS跨平台编译】之四十二:【QWT+Qt跨平台编译】(一套代码、一套框架,跨平台编译)
文章目录 一、QWT介绍二、QWT下载三、文件分析四、pro文件五、编译实践5.1 Windows下编译4.2 Linux下编译5.3 MacOS下编译一、QWT介绍 QWT是一个基于Qt框架的开源C++库,用于创建交互式的图形用户界面。它提供了丰富的绘图和交互功能,可以用于快速开发图形化应用程序。 QWT包…...
yum方式快速安装mysql
问题描述 使用yum的方式简单安装了一下mysql,对过程进行简单记录。 步骤 ①安装wget和vim sudo yum -y install wget vim②下载mysql的rpm包 sudo wget https://dev.mysql.com/get/mysql80-community-release-el7-3.noarch.rpm③升级和更新rpm包 sudo rpm -Uv…...
基于Java的家政预约管理平台
功能介绍 平台采用B/S结构,后端采用主流的Springboot框架进行开发,前端采用主流的Vue.js进行开发。 整个平台包括前台和后台两个部分。 前台功能包括:首页、家政详情、家政入驻、用户中心模块。后台功能包括:家政管理、分类管理…...
C语言前世今生
C语言前世今生 C语言的发展历史 C语言于1972年11月问世,1978年美国电话电报公司(AT&T)贝尔实验室正式发布C语言,1983年由美国国家标准局(American National Standards Institute,简称ANSI)…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器
一、原理介绍 传统滑模观测器采用如下结构: 传统SMO中LPF会带来相位延迟和幅值衰减,并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF),可以去除高次谐波,并且不用相位补偿就可以获得一个误差较小的转子位…...
深入浅出Diffusion模型:从原理到实践的全方位教程
I. 引言:生成式AI的黎明 – Diffusion模型是什么? 近年来,生成式人工智能(Generative AI)领域取得了爆炸性的进展,模型能够根据简单的文本提示创作出逼真的图像、连贯的文本,乃至更多令人惊叹的…...
【Linux】Linux安装并配置RabbitMQ
目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的,需要先安…...
boost::filesystem::path文件路径使用详解和示例
boost::filesystem::path 是 Boost 库中用于跨平台操作文件路径的类,封装了路径的拼接、分割、提取、判断等常用功能。下面是对它的使用详解,包括常用接口与完整示例。 1. 引入头文件与命名空间 #include <boost/filesystem.hpp> namespace fs b…...
