图片站手机网站怎么做/中国搜索引擎有哪些
一遍过。首先把区间按左端点排序,然后右端点有两种情况。
假设是a区间,b区间。。。这样排列的顺序,那么
假设a[1]>b[0],如果a[1]>b[1],就应该以b[1]为准,否则以a[1]为准。
class Solution {
public:static bool cmp(vector<int>& a ,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 res=0;for(int i=1;i<intervals.size();i++){if(intervals[i][0]<intervals[i-1][1]){res++;intervals[i][1]=min(intervals[i][1],intervals[i-1][1]);}}return res;}
};
题解方法:
我来按照右边界排序,从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了
就是取 区间1 和 区间2 右边界的最小值,因为这个最小值之前的部分一定是 区间1 和区间2 的重合部分,如果这个最小值也触达到区间3,那么说明 区间 1,2,3都是重合的。
接下来就是找大于区间1结束位置的区间,是从区间4开始。那有同学问了为什么不从区间5开始?别忘了已经是按照右边界排序的了。
区间4结束之后,再找到区间6,所以一共记录非交叉区间的个数是三个。
总共区间个数为6,减去非交叉区间的个数3。移除区间的最小数量就是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 (end <= intervals[i][0]) {end = intervals[i][1];count++;}}return intervals.size() - count;}
};
看了题解。
在遍历的过程中相当于是要找每一个字母的边界,如果找到之前遍历过的所有字母的最远边界,说明这个边界就是分割点了。此时前面出现过所有字母,最远也就到这个边界了。
可以分为如下两步:
- 统计每一个字符最后出现的位置
- 从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点
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> res;int left=0;int right=0;for(int i=0;i<s.size();i++){right=max(right,hash[s[i]-'a']);if(right==i){res.push_back(right-left+1);left=i+1;}// else{// }}return res;}
};
一遍过。将区间按左端点从小到大排序。假设是排序后是a,b,。。。
假设b区间左端点b[0]小于等于a区间右端点a[1],有两种情况:1、a[1]<b[1],那么合并区间选择b[1]。2、a[1]>b[1],就选a[1],而合并区间左端点始终选择a[0];
假设b[0]>a[1],那么就可以把上次融合后的区间加入结果。
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>> res;sort(intervals.begin(),intervals.end(),cmp);for(int i=1;i<intervals.size();i++){if(intervals[i][0]<=intervals[i-1][1]){intervals[i][1]=max(intervals[i][1],intervals[i-1][1]);intervals[i][0]=intervals[i-1][0];}else{res.push_back(intervals[i-1]);}}res.push_back(intervals[intervals.size()-1]);return res;}
};
题解写法:
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;}
};
相关文章:

day 36 贪心算法 part05● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间
一遍过。首先把区间按左端点排序,然后右端点有两种情况。 假设是a区间,b区间。。。这样排列的顺序,那么 假设a[1]>b[0],如果a[1]>b[1],就应该以b[1]为准,否则以a[1]为准。 class Solution { public:static bo…...

【数据结构与算法】快速排序(详解:快排的Hoare原版,挖坑法和双指针法|避免快排最坏时间复杂度的两种解决方案|小区间优化|非递归的快排)
引言 快速排序作为交换排序的一种,在排序界的影响力毋庸置疑,我们C语言中用的qsort,C中用的sort,底层的排序方式都是快速排序。相比于同为交换排序的冒泡,其效率和性能就要差的多了,本篇博客就是要重点介绍…...

三位数组合-第12届蓝桥杯选拔赛Python真题精选
[导读]:超平老师的Scratch蓝桥杯真题解读系列在推出之后,受到了广大老师和家长的好评,非常感谢各位的认可和厚爱。作为回馈,超平老师计划推出《Python蓝桥杯真题解析100讲》,这是解读系列的第42讲。 三位数组合&#…...

Mongodb入门到入土,安装到实战,外包半年学习的成果
这是我参与「第四届青训营 」笔记创作活动的的第27天,今天主要记录前端进阶必须掌握内容Mongodb数据库,从搭建环境到运行数据库,然后使用MongodB; 一、文章内容 数据库基础知识关系型数据库和非关系型数据库为什么学习Mongodb数据库环境搭建及运行MongodbMongodb命…...

【C++初阶】之类和对象(下)
【C初阶】之类和对象(下) ✍ 再谈构造函数🏄 初始化列表的引入💘 初始化列表的语法💘 初始化列表初始化元素的顺序 🏄 explicit关键字 ✍ Static成员🏄 C语言中的静态变量🏄 C中的静…...

Spring Boot 3 极速搭建OAuth2认证框架
本篇环境 Java 17Spring Boot 3.2.3Spring Authorization Server 1.2.3开发工具 SpringToolSuite4Spring Boot 3.2.3 需要JDK 17及之上的版本。 项目初始化 项目可以使用Spring的初始化器生成, 也可以创建一个Maven类型的项目。 项目创建后的目录结构如下: 项目配置 使用 …...

大数据开发(离线实时音乐数仓)
大数据开发(离线实时音乐数仓) 一、数据库与ER建模1、数据库三范式2、ER实体关系模型 二、数据仓库与维度建模1、数据仓库(Data Warehouse、DW、DWH)1、关系型数据库很难将这些数据转换成企业真正需要的决策信息,原因如…...

Python读取csv文件入Oracle数据库
在Python中,使用pandas库的read_sql_query函数可以直接从SQL查询中读取数据到DataFrame。而pd.set_option函数用于设置pandas的显示选项。具体来说,display.unicode.ambiguous_as_wide选项用于控制当字符宽度不明确时,pandas是否将这些字符显…...

Linux_进程概念_冯诺依曼_进程概念_查看进程_获取进程pid_创建进程_进程状态_进程优先级_环境变量_获取环境变量三种方式_3
文章目录 一、硬件-冯诺依曼体系结构二、软件-操作系统-进程概念0.操作系统做什么的1.什么叫做进程2.查看进程3.系统接口 获取进程pid- getpid4.系统接口 获取父进程pid - getppid5.系统接口 创建子进程 - fork1、手册2、返回值3、fork做了什么4、基本用法 6.进程的状态1、进程…...

Set A Light 3D Studio中文--- 打造专业级3D照明效果
Set A Light 3D Studio是一款专业的灯光模拟软件,专为摄影师和电影制片人打造。它允许用户在计算机上模拟并预览各种布光效果,助力拍摄出真实、精准且具有艺术感的作品。软件提供了丰富的灯光和场景模型,用户可以灵活调整光源参数,…...

【深度学习】基于机器学习的无机钙钛矿材料形成能预测,预测形成能,神经网络,回归问题
文章目录 任务分析数据处理处理离散数值处理缺失值处理不同范围的数据其他注意事项 我们的数据处理模型训练网页web代码、指导 任务分析 简单来说,就是一行就是一个样本,要用绿色的9个数值,预测出红色的那1个数值。 数据处理 在进行深度数…...

20240321-2-Adaboost 算法介绍
Adaboost 算法介绍 1. 集成学习 集成学习(ensemble learning)通过构建并结合多个学习器(learner)来完成学习任务,通常可获得比单一学习器更良好的泛化性能(特别是在集成弱学习器(weak learner…...

python第三方库的安装,卸载和更新,以及在cmd下pip install安装的包在pycharm不可用问题的解决
目录 第三方库pip安装,卸载更新 1.安装: 2.卸载 3.更新 一、第三方库pip安装,卸载更新 1.安装 pip install 模块名 加镜像下载:pip install -i 镜像网址模块名 常用的是加清华镜像,如 pip install -i https://pyp…...

Python第三次作业
周六 1. 求一个十进制的数值的二进制的0、1的个数 def er(x):a bin(x)b str(a).count("1")c str(a).count("0") - 1print(f"{a},count 1:{b},count 0:{c}")x int(input("enter a number:")) er(x) 2. 实现一个用户管理系统&…...

ai写作软件选哪个?这5款风靡全球的工具不容错过!
从去年到现在,ai 人工智能的发展一直是许多人关注的重点,每隔一段时间新诞生的 ai 工具软件,总会成为人们茶余饭后谈论的焦点。不过在种类繁多的 ai 工具软件中,ai 写作软件是最常被使用的 ai 工具类别,它的使用门槛较…...

信号处理与分析——matlab记录
一、绘制信号分析频谱 1.代码 % 生成测试信号 Fs 3000; % 采样频率 t 0:1/Fs:1-1/Fs; % 时间向量 x1 1*sin(2*pi*50*t) 1*sin(2*pi*60*t); % 信号1 x2 1*sin(2*pi*150*t)1*sin(2*pi*270*t); % 信号2% 绘制信号图 subplot(2,2,1); plot(t,x1); title(信号x1 1*sin(…...

Android Databinding 使用教程
Android Databinding 使用教程 一、介绍 Android Databinding 是 Android Jetpack 的一部分,它允许你直接在 XML 布局文件中绑定 UI 组件到数据源。通过这种方式,你可以更简洁、更直观地更新 UI,而无需编写大量的 findViewById 和 setText/…...

【每日跟读】常用英语500句(200~300)
【每日跟读】常用英语500句 Home sweet home. 到家了 show it to me. 给我看看 Come on sit. 过来坐 That should do nicely. 这样就很好了 Get dressed now. 现在就穿衣服 If I were you. 我要是你 Close your eyes. 闭上眼睛 I don’t remember. 我忘了 I’m not su…...

【Java开发过程中的流程图】
流程图由一系列的图形符号和箭头组成,每个符号代表一个特定的操作或决策。下面是一些常见的流程图符号及其含义: 开始/结束符号(圆形):表示程序的开始和结束点。 过程/操作符号(矩形)ÿ…...

蓝桥杯刷题-day5-动态规划
文章目录 使用最小花费爬楼梯解码方法 使用最小花费爬楼梯 【题目描述】 给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶…...

新概念英语1:Lesson7内容详解
新概念英语1:Lesson7内容详解 如何询问人的个人信息 本课里有两个关于个人信息的问句,一个是问国籍,一个是问工作,句型如下: what nationality are you?询问国籍 回复一般就是我是哪国人,I’m Chinese…...

FASTAPI系列 14-使用JSONResponse 返回JSON内容
FASTAPI系列 14-使用JSONResponse 返回JSON内容 文章目录 FASTAPI系列 14-使用JSONResponse 返回JSON内容前言一、默认返回的JSON格式二、JSONResponse 自定义返回三、自定义返回 headers 和 media_type总结 前言 当你创建一个 FastAPI 接口时,可以正常返回以下任意…...

【版本控制】git使用指南
Git 是一个免费、开源的分布式版本控制系统,最初由 Linus Torvalds 于2005年创建。它旨在管理项目的源代码,并提供了跟踪更改、协作开发、版本控制、分支管理等功能。 一、版本控制概念 版本控制系统(Version Control System,VC…...

Flask 与小程序 的图片数据交互 过程及探讨研究学习
今天不知道怎么的,之前拿编程浪子地作品抄过来粘上用好好的,昨天开始照片突的就不显示了。 今天不妨再耐味地细细探究一下微信小程序wxml 和flask服务器端是怎么jpg图片数据交互的。 mina/pages/food/index.wxml <!--index.wxml--> <!--1px …...

【JavaEE】初识线程,线程与进程的区别
文章目录 ✍线程是什么?✍线程和进程的区别✍线程的创建1.继承 Thread 类2.实现Runnable接口3.匿名内部类4.匿名内部类创建 Runnable ⼦类对象5.lambda 表达式创建 Runnable ⼦类对象 ✍线程是什么? ⼀个线程就是⼀个 “执行流”. 每个线程之间都可以按…...

Kafka高级面试题-2024
Kafka中的Topic和Partition有什么关系? 在Kafka中,Topic和Partition是两个密切相关的概念。 Topic是Kafka中消息的逻辑分类,可以看作是一个消息的存储类别。它是按照不同的主题对消息进行分类,并且可以用于区分和筛选数据。每个…...

Qt——Qt文本读写之QFile与QTextStream的使用总结(打开文本文件,修改内容后保存至该文件中)
【系列专栏】:博主结合工作实践输出的,解决实际问题的专栏,朋友们看过来! 《项目案例分享》 《极客DIY开源分享》 《嵌入式通用开发实战》 《C++语言开发基础总结》 《从0到1学习嵌入式Linux开发》 《QT开发实战》 《Android开发实战》...

掌握Java中的super关键字
super 是 Java 中的一个关键字,它在继承的上下文中特别有用。super 引用了当前对象的直接父类,它可以用来访问父类中的属性、方法和构造函数。以下是 super 的几个主要用途: 1. 调用父类的构造函数 在子类的构造函数中,你可以使…...

STM32之HAL开发——系统定时器(SysTick)
系统定时器(SysTick)介绍 SysTick—系统定时器是属于 CM3 内核中的一个外设,内嵌在 NVIC 中。系统定时器是一个 24bit的向下递减的计数器,计数器每计数一次的时间为 1/SYSCLK,一般我们设置系统时钟 SYSCLK等于 72M。当…...

Redis 不再“开源”:中国面临的挑战与策略应对
Redis 不再“开源”,使用双许可证 3 月 20 号,Redis 的 CEO Rowan Trollope 在官网上宣布了《Redis 采用双源许可证》的消息。他表示,今后 Redis 的所有新版本都将使用开源代码可用的许可证,不再使用 BSD 协议,而是采用…...