技术标签: 算法 c++ 贪心算法 leetcode 刷题记录
给定一个区间的集合 intervals
,其中 intervals[i] = [starti, endi]
。返回 需要移除区间的最小数量,使剩余区间互不重叠 。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后,剩下的区间没有重叠。
示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间,因为它们已经是无重叠的了。
提示:
intervals.length
<= 10^5intervals[i].length
== 2starti < endi
<= 5 * 10^4本题和上一题的引爆气球有点像,也是重叠区间的问题。本题是判断删掉多少个区间,能够得到不重合的区间组合。如下图:
第一步仍然是按照左边界排序,让所有区间按照大小顺序排在一起。
判断相邻两个区间不重叠,也就是i区间左边界>=i-1区间的右边界。
if(i>0&&nums[i][0]>nums[i-1][1]){
continue;//不重叠直接继续遍历
}
判断区间如果重叠,那么计数+1(重叠的一定要删掉),和气球题目类似,依旧取最小右边界,看看下一个区间是否重叠
else{
result++;
//修改右边界
nums[i][1]=min(nums[i][1],nums[i-1][1]);//修改后继续遍历即可
}
class Solution {
public:
static bool cmp(vector<int>&a,vector<int>&b){
if(a[0]<b[0]) return true;//左边界升序排序
return false;
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if(intervals.size()==0) return 0;
sort(intervals.begin(),intervals.end(),cmp);
int count=0;
for(int i=1;i<intervals.size();i++){
if(intervals[i][0]>=intervals[i-1][1]) continue;
//如果重叠,更新最小右边界
else{
count++;
intervals[i][1]=min(intervals[i][1],intervals[i-1][1]);
}
}
return count;
}
};
在我们自己画图模拟重叠区间的时候,一定要注意,更新最小右边界之后,实际上重叠的区间相当于已经被修改了!也就是说,当前重叠区间的右边界,已经成为最小右边界了。
重叠区间原有右边界需要及时在图里删掉,否则容易出现看图看错逻辑的情况。模拟图如下图所示。
这种情况遍历到7的时候,实际上7前面和8重合的部分,8已经被删掉了,所以并不会出现i=3的重合。
class Solution {
public:
static bool cmp(vector<int>&a,vector<int>&b){
if(a[1]<b[1]) return true;//右边界升序排序
return false;
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if(intervals.size()==0) return 0;
sort(intervals.begin(),intervals.end(),cmp);
int count=0;
for(int i=1;i<intervals.size();i++){
if(intervals[i][0]>=intervals[i-1][1]) continue;
//如果重叠,更新最小右边界
else{
count++;
intervals[i][1]=min(intervals[i][1],intervals[i-1][1]);
}
}
return count;
}
};
给你一个字符串 s
。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。
注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s
。
返回一个表示每个字符串片段的长度的列表。
示例 1:
输入:s = "ababcbacadefegdehijhklij"
输出:[9,7,8]
解释:
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的,因为划分的片段数较少。
示例 2:
输入:s = "eccbbbbdec"
输出:[10]
提示:
s.length
<= 500s
仅由小写英文字母组成本题首先要理解题意。题目中说同一字母最多出现在一个片段中,也就是说,对字母a来说,划分出来的片段应该包括所有的a。同时还要保证划分出来的片段数目是最多的。
也就是说,一旦包含a,就要包含所有的a,一旦包含b就要包含所有的b。
因此,本题的策略是找到每个元素的最远位置,然后看区间之间的包含关系。如下图所示:
a的最远位置包含了b和c的最远位置。因此第一个区间的分界线就在a的最远位置处。d的最远位置没有包含e,因此我们最后的区间是de最远位置的最大值。
class Solution {
public:
vector<int> partitionLabels(string s) {
vector<int>result;
//次数数组
int hash[27]={
0};
//先统计每个元素的最远位置
for(int i=0;i<s.size();i++){
hash[s[i]-'a']=i;//下标i不断更新,最后hash里面的i就是最远位置的i
}
int left=0,right=0;
int length=0;
//用right记录目前为止所有遍历元素的最大下标
for(int i=0;i<s.size();i++){
right = max(right,hash[s[i]-'a']);
//如果已经到了最大下标
if(i==right){
cout<<right<<endl;
cout<<left<<endl;
length=right-left+1;
result.push_back(length);
left=right+1;//重置左区间起始点,注意这里一定要left+1,区间不能重合
length=0;//重置长度
}
}
return result;
}
};
如下图所示,本题主要是利用max来记录目前为止遍历过的所有元素里,最远距离最大的那一个。
当right遍历到了max,也就是说,right目前在的位置,是目前遍历过的所有元素里,最远距离最大的元素!此时right的位置,就是区间的分界线!
第一次提交出现了很奇怪的结果,因为left没赋初值,所以每一次运行,left的值都不一样。修改left=0后问题解决。
这道题目leetcode标记为贪心算法,其实没有太体现贪心策略,找不出局部最优推出全局最优的过程。
本质上还是重叠区间的问题,就是用最远出现距离模拟了圈字符的行为。最远出现距离,相当于重叠区间中包含所有区间的最大区间。
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi]
。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
示例 1:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示:
intervals.length
<= 10^4intervals[i].length
== 2starti
<= endi
<= 10^4本题是重叠区间经典题目,和 452.最少弓箭引爆气球 435.无重叠区间 的思路非常类似。
但是也有不同的地方,这道题如果完全按照无重叠区间思路来做,会有逻辑问题,本题因为是result数组收集合并后的区间,因此我们需要更新的是result的最后一个元素,而不是直接在原数组上修改,遇到重叠区间取最值加入result。
class Solution {
public:
//原数组上直接合并的写法
static bool cmp(vector<int>&a,vector<int>&b){
if(a[0]<b[0]) return true;//左边界升序排序
return false;
}
vector<vector<int>>result;
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end(),cmp);
for(int i=1;i<intervals.size();i++){
//完全不重叠
if(intervals[i][0]>intervals[i-1][1]){
//cout<<intervals[i-1][1]<<" "<<intervals[i][0]<<endl;
//把i-1放进去,而不是i
result.push_back(intervals[i-1]);
continue;
}
//<=都算重叠
if(intervals[i][0]<=intervals[i-1][1]){
//左边界已经排好序了不用管了
//intervals[i-1][0]=min(intervals[i-1][0],intervals[i][0]);
//更新i-1右边界
intervals[i-1][1]=max(intervals[i-1][1],intervals[i][1]);
result.push_back(intervals[i-1]);
}
//最后一个单独判断,如果不重叠加入自身
if(i==intervals.size()-1&&intervals[i][0]>intervals[i-1][1])
result.push_back(intervals[i]);
}
return result;
}
};
这种写法出现了逻辑错误,因为我们从i=1开始遍历,i=1时更新了i-1为新数组,但是遍历到i=2的时候,并没有接收到新数组的信息,而是依然在和i对比!
class Solution {
public:
//原数组上直接合并的写法
static bool cmp(vector<int>&a,vector<int>&b){
if(a[0]<b[0]) return true;//左边界升序排序
return false;
}
vector<vector<int>>result;
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end(),cmp);
for(int i=1;i<intervals.size();i++){
//完全不重叠
if(intervals[i][0]>intervals[i-1][1]){
//cout<<intervals[i-1][1]<<" "<<intervals[i][0]<<endl;
//把i-1放进去,而不是i
result.push_back(intervals[i-1]);
continue;
}
//<=都算重叠
if(intervals[i][0]<=intervals[i-1][1]){
//更新i而不是i-1
intervals[i][0]=min(intervals[i-1][0],intervals[i][0]);
//更新i右边界
intervals[i][1]=max(intervals[i-1][1],intervals[i][1]);
//更新之后直接遍历下一个即可,下一个发现不重叠会直接加入结果集
}
}
//所有都结束之后再push_back
result.push_back(intervals[intervals.size()-1]);
return result;
}
};
class Solution {
public:
static bool cmp(vector<int>&a,vector<int>&b){
if(a[0]<b[0]) return true;//左边界升序排序
return false;
}
vector<vector<int>>result;
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end(),cmp);
//先把第一个元素加进去
result.push_back(intervals[0]);
//开始遍历
for(int i=1;i<intervals.size();i++){
//完全不重叠,直接和.back()比较
if(result.back()[1]<intervals[i][0]){
result.push_back(intervals[i]);
}
else{
//更新上个元素的右边界,左边界已经排好序了
//这里需要取最大值,和他本身作比较
result.back()[1]=max(intervals[i][1],result.back()[1]);
}
}
return result;
}
};
std::sort
的平均时间复杂度为O(N log N),其中N是intervals
的长度。其余的操作,包括遍历和比较,时间复杂度为O(N)。因此,总的时间复杂度是O(N log N + N),但是在大O表示法中,我们通常只关心最高阶项,所以我们可以忽略掉O(N)部分,所以总的时间复杂度是O(N log N)。result
的大小。在最坏的情况下,如果所有的区间都不重叠,那么result
的大小和输入的intervals
大小相同,即N。除此之外,sort
操作使用的是原地排序,不需要额外的存储空间。所以总的空间复杂度是O(N)。关于重叠区间类型的题目,其实主要就是靠画图模拟。
重叠区间题目需要注意元素初值的问题,包括计数变量的初值,以及有时候需要考虑数组i=0时候的初值(因为重叠判断大都是i=1开始的)。
比如本题,是结果收集而不是记录重叠个数,此时就需要考虑数组初值也要被加入结果数组的情况!
文章浏览阅读5.8k次。在大数据的发展当中,大数据技术生态的组件,也在不断地拓展开来,而其中的Hive组件,作为Hadoop的数据仓库工具,可以实现对Hadoop集群当中的大规模数据进行相应的数据处理。今天我们的大数据入门分享,就主要来讲讲,Hive应用场景。关于Hive,首先需要明确的一点就是,Hive并非数据库,Hive所提供的数据存储、查询和分析功能,本质上来说,并非传统数据库所提供的存储、查询、分析功能。Hive..._hive应用场景
文章浏览阅读496次。Zblog是由Zblog开发团队开发的一款小巧而强大的基于Asp和PHP平台的开源程序,但是插件市场上的Zblog采集插件,没有一款能打的,要么就是没有SEO文章内容处理,要么就是功能单一。很少有适合SEO站长的Zblog采集。人们都知道Zblog采集接口都是对Zblog采集不熟悉的人做的,很多人采取模拟登陆的方法进行发布文章,也有很多人直接操作数据库发布文章,然而这些都或多或少的产生各种问题,发布速度慢、文章内容未经严格过滤,导致安全性问题、不能发Tag、不能自动创建分类等。但是使用Zblog采._zblog 网页采集插件
文章浏览阅读2.4k次,点赞2次,收藏2次。restUI页面提交1.1 添加上传jar包1.2 提交任务job1.3 查看提交的任务2. 命令行提交./flink-1.9.3/bin/flink run -c com.qu.wc.StreamWordCount -p 2 FlinkTutorial-1.0-SNAPSHOT.jar3. 命令行查看正在运行的job./flink-1.9.3/bin/flink list4. 命令行查看所有job./flink-1.9.3/bin/flink list --all._flink定时运行job
文章浏览阅读1k次,点赞2次,收藏6次。这个项目是基于STM32的LED闪烁项目,主要目的是让学习者熟悉STM32的基本操作和编程方法。在这个项目中,我们将使用STM32作为控制器,通过对GPIO口的控制实现LED灯的闪烁。这个STM32 LED闪烁的项目是一个非常简单的入门项目,但它可以帮助学习者熟悉STM32的编程方法和GPIO口的使用。在这个项目中,我们通过对GPIO口的控制实现了LED灯的闪烁。LED闪烁是STM32入门课程的基础操作之一,它旨在教学生如何使用STM32开发板控制LED灯的闪烁。_嵌入式stm32闪烁led实验总结
文章浏览阅读63次。本文介绍了安装和部署Debezium的详细步骤,并演示了如何将Debezium服务托管到systemctl以进行方便的管理。本文将详细介绍如何安装和部署Debezium,并将其服务托管到systemctl。解压缩后,将得到一个名为"debezium"的目录,其中包含Debezium的二进制文件和其他必要的资源。注意替换"ExecStart"中的"/path/to/debezium"为实际的Debezium目录路径。接下来,需要下载Debezium的压缩包,并将其解压到所需的目录。
文章浏览阅读4.4k次。需求:在诗词曲文项目中,诗词整篇朗读的时候,文章没有读完会因为屏幕熄灭停止朗读。要求:在文章没有朗读完毕之前屏幕常亮,读完以后屏幕常亮关闭;1.权限配置:设置电源管理的权限。
文章浏览阅读2.3k次。目标检测简介、评估标准、经典算法_目标检测
文章浏览阅读6.3k次,点赞4次,收藏9次。实训时需要安装SQL server2008 R所以我上网上找了一个.exe 的安装包链接:https://pan.baidu.com/s/1_FkhB8XJy3Js_rFADhdtmA提取码:ztki注:解压后1.04G安装时Microsoft需下载.NET,更新安装后会自动安装如下:点击第一个傻瓜式安装,唯一注意的是在修改路径的时候如下不可修改:到安装实例的时候就可以修改啦数据..._sqlserver 127 0 01 无法连接
文章浏览阅读7.4k次。1. Object.keys(item); 获取到了key之后就可以遍历的时候直接使用这个进行遍历所有的key跟valuevar infoItem={ name:'xiaowu', age:'18',}//的出来的keys就是[name,age]var keys=Object.keys(infoItem);2. 通常用于以下实力中 <div *ngFor="let item of keys"> <div>{{item}}.._js 遍历对象的key
文章浏览阅读2.2w次,点赞51次,收藏310次。粒子群算法求解路径规划路径规划问题描述 给定环境信息,如果该环境内有障碍物,寻求起始点到目标点的最短路径, 并且路径不能与障碍物相交,如图 1.1.1 所示。1.2 粒子群算法求解1.2.1 求解思路 粒子群优化算法(PSO),粒子群中的每一个粒子都代表一个问题的可能解, 通过粒子个体的简单行为,群体内的信息交互实现问题求解的智能性。 在路径规划中,我们将每一条路径规划为一个粒子,每个粒子群群有 n 个粒 子,即有 n 条路径,同时,每个粒子又有 m 个染色体,即中间过渡点的_粒子群算法路径规划
文章浏览阅读353次。所谓稳健的评估指标,是指在评估的过程中数据的轻微变化并不会显著的影响一个统计指标。而不稳健的评估指标则相反,在对交易系统进行回测时,参数值的轻微变化会带来不稳健指标的大幅变化。对于不稳健的评估指标,任何对数据有影响的因素都会对测试结果产生过大的影响,这很容易导致数据过拟合。_rar 海龟
文章浏览阅读607次,点赞2次,收藏7次。–基于STM32F103ZET6的UART通讯实现一、什么是IAP,为什么要IAPIAP即为In Application Programming(在应用中编程),一般情况下,以STM32F10x系列芯片为主控制器的设备在出厂时就已经使用J-Link仿真器将应用代码烧录了,如果在设备使用过程中需要进行应用代码的更换、升级等操作的话,则可能需要将设备返回原厂并拆解出来再使用J-Link重新烧录代码,这就增加了很多不必要的麻烦。站在用户的角度来说,就是能让用户自己来更换设备里边的代码程序而厂家这边只需要提供给_value line devices connectivity line devices