当前位置: 首页 > news >正文

第三十六天| 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 <= 500
  • s 仅由小写英文字母组成

思考:贪心法。先寻找所有字母的最后出现的下标位置,和其首次出现的位置形成区间。接下来将重叠的区间合并起来,并记录每个不重叠区间的大小。由于按顺序遍历字符串因此在合并区间时只需要更新右边界,在不重叠时初始化新区间的边界。

代码:

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. 无重叠区间 题目链接&#xff1a;435 无重叠区间 题干&#xff1a;给定一个区间的集合 intervals &#xff0c;其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量&#xff0c;使剩余区间互不重叠 。 思考&#xff1a;贪心法。和452 用最少数量的…...

React setState同步还是异步

React18 setState是同步还是异步&#xff1f;_react18 同步-CSDN博客 React18之前或者React18使用了ReactDOM.render&#xff0c;setState在React调度流程中是异步更新&#xff0c;在原生事件和setTimeout中是同步更新。React18使用ReactDOM.createRoot&#xff0c;那么默认都是…...

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&#xff08;Interquartile Range&#xff09;四分位距的含义2 如何计算IQR参考&#xff1a; 1 IQR&#xff08;Interquartile Range&#xff09;四分位距的含义 官方定义&#xff1a; 四分位距&#xff08;interquartile range, IQR&a…...

Vision Transformer - VIT

文章目录 1. Embedding层2. Encoder层3. MLP Head层4. Hybrid混合模型 论文&#xff1a;An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale 网址&#xff1a;https://arxiv.org/abs/2010.11929 Hybrid - 传统CNN和Transformer混合模型 模型架构 输…...

HTTP与HTTPS:网络安全之门户

源码分享 ​​https://docs.qq.com/sheet/DUHNQdlRUVUp5Vll2?tabBB08J2​​ 在进行网页爬取和数据收集时&#xff0c;我们经常会与HTTP&#xff08;超文本传输协议&#xff09;和HTTPS&#xff08;安全的超文本传输协议&#xff09;打交道。这两种协议都用于互联网上的数据传…...

头歌:共享单车之数据分析

第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很小的整数&#xff0c;默认有符号 [-128,127]/[0,255]SMALLINT[UNSIGNED]2较小的整数&#xff0c;默认有符号 [-32768,32767]/[0,65535]MEDIUMINT[UNSIGNED]3中等的整数&#xff0c;默认有符号 [-8388608,8388607]/[0,16777215]…...

自建AWS S3存储服务

unsetunset前言unsetunset AWS S3&#xff08;Amazon S3&#xff0c;全名为亚马逊简易存储服务&#xff09;&#xff0c;是亚马逊公司利用其亚马逊网络服务系统所提供的网络在线存储服务。我常用的很多SaaS服务中提供的文件存储功能&#xff0c;底层也都是AWS S3&#xff0c;比…...

『论文阅读|研究用于视障人士户外障碍物检测的 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基础知识

一、标识符规范 标识符必须以字母(汉字)、下划线、美元符号开头&#xff0c;其他部分可以是字母、下划线、美元符号&#xff0c;数字的任意组合。谨记不能以数字开头。java使用unicode字符集&#xff0c;汉字也可以用该字符集表示。因此汉字也可以用作变量名。 关键字不能用作…...

并发编程-Synchronized

什么是Synchronized synchronized是Java提供的一个关键字&#xff0c;Synchronized可以保证并发程序的原子性&#xff0c;可见性&#xff0c;有序性。 我们会把synchronized称为重量级锁。主要原因&#xff0c;是因为JDK1.6之前&#xff0c;synchronized是一个重量级锁相比于J…...

C语言——从头开始——深入理解指针(1)

一.内存和地址 我们知道计算上CPU&#xff08;中央处理器&#xff09;在处理数据的时候&#xff0c;是通过地址总线把需要的数据从内存中读取的&#xff0c;后通过数据总线把处理后的数据放回内存中。如下图所示&#xff1a; 计算机把内存划分为⼀个个的内存单元&#xff0c;每…...

微信小程序-绑定数据并在后台获取它

如图 遍历列表的过程中需要绑定数据&#xff0c;点击时候需要绑定数据 这里是源代码 <block wx:for"{{productList}}" wx:key"productId"><view class"product-item" bindtap"handleProductClick" data-product-id"{{i…...

【删除数组用delete和Vue.delete有什么区别】

删除数组用delete和Vue.delete有什么区别&#xff1f; 在 JavaScript 中&#xff0c;delete 和 Vue.js 中的 Vue.delete 是两个完全不同的概念&#xff0c;它们在删除数组元素时的作用和效果也有所不同。 JavaScript 中的 delete 关键字&#xff1a; 在原生 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&#xff0c;对过程进行简单记录。 步骤 ①安装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结构&#xff0c;后端采用主流的Springboot框架进行开发&#xff0c;前端采用主流的Vue.js进行开发。 整个平台包括前台和后台两个部分。 前台功能包括&#xff1a;首页、家政详情、家政入驻、用户中心模块。后台功能包括&#xff1a;家政管理、分类管理…...

C语言前世今生

C语言前世今生 C语言的发展历史 C语言于1972年11月问世&#xff0c;1978年美国电话电报公司&#xff08;AT&T&#xff09;贝尔实验室正式发布C语言&#xff0c;1983年由美国国家标准局&#xff08;American National Standards Institute&#xff0c;简称ANSI&#xff09…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

什么是VR全景技术

VR全景技术&#xff0c;全称为虚拟现实全景技术&#xff0c;是通过计算机图像模拟生成三维空间中的虚拟世界&#xff0c;使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验&#xff0c;结合图文、3D、音视频等多媒体元素…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...

基于鸿蒙(HarmonyOS5)的打车小程序

1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...