技术标签: 算法
目录
首先还是按照区间的左端点进行排序,然后判断当前区间的左端点与上一个区间的右端点的大小来判断是否重叠。如果重叠,计数加一,并且更新当前区间的右端点为两个区间右端点的最小值。更新是为了比较下一个区间与上一个区间是否有重叠。(当前区间的前后两个区间)
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 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][1], intervals[i][1]);
}
}
return 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;
}
int left = 0; // 左端点
int right = 0; // 右端点
vector<int> result; // 结果数组
for (int i = 0; i < s.size(); i++) {
// 更新right
right = max(right, hash[s[i] - 'a']);
// 遍历到了最大下标,说明已经包含所有字母
if (right == i) {
// 存结果
result.push_back(right - left + 1);
// 更新左端点
left = i + 1;
}
}
return result;
}
};
做的第四道重叠区间的题了,思路大体相同。不重叠时向后遍历,重叠时做处理。这道题的处理稍微有点区别,就是要合并重叠的区间,左端点选最小,右端点选最大,然后继续向后遍历即可。在原数组上修改有些麻烦,直接定义一个新数组存放结果,重叠时pop出来,合并区间后再push进去。
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) {
// 只有一个区间时,直接返回
if (intervals.size() == 1)
return intervals;
sort(intervals.begin(), intervals.end(), cmp); // 排序
vector<vector<int>> result; // 用来存结果
result.push_back(intervals[0]); // 先把第一个区间存进去
for (int i = 1; i < intervals.size(); i++) {
// 如果不重叠,直接存
if (intervals[i][0] > intervals[i - 1][1]) {
result.push_back(intervals[i]);
} else {
// 重叠时先把上一个放进去的区间拿出来
result.pop_back();
// 合并区间
intervals[i][0] = min(intervals[i - 1][0], intervals[i][0]);
intervals[i][1] = max(intervals[i - 1][1], intervals[i][1]);
// 将合并后的区间存到结果数组
result.push_back(intervals[i]);
}
}
return result;
}
};
①重叠区间,一般都要对数组排序,要熟悉sort函数的第三个参数以及排列规则
②区间的重叠定义细节要注意,有时两个区间右端点与左端点相等不算重叠,有时算,具体看题目
文章浏览阅读2.9k次。ifort 编译器的安装ifort 编译器可以在 intel 官网上下载。打开https://software.intel.com/content/www/us/en/develop/tools/oneapi/components/fortran-compiler.html#gs.7iqrsm点击网页中下方处的 Download, 选择 Intel Fortran Compiler Classic and Intel Fortran Compiler(Beta) 下方对应的版本。我选择的是 l_在linux系统的用户目录下安装ifort和mkl库并配置
文章浏览阅读689次,点赞7次,收藏8次。些项目时需要一个生成图片的方法,我在网上找到比较方便且适合我去设置一些样式的生成方式之一就是使用Freemarker,在对应位置上先写好一个html格式的ftl文件,在对应位置用${参数名}填写上。还记得当时为了解决图片大小设置不上,搜索了好久资料,不记得是在哪看到的需要在里面使用width与height直接设置,而我当时用style去设置,怎么都不对。找不到,自己测试链接,准备将所有含有中文的图片链接复制一份,在服务器上存储一份不带中文的文件。突然发现就算无中文,有的链接也是打不开的。_ftl格式pdf的样式调整
文章浏览阅读1.5k次,点赞6次,收藏12次。拉取librealsense。_opt/ros/noetic/lib/nodelet/nodelet: symbol lookup error: /home/admin07/reals
文章浏览阅读1w次。本文介绍了UOS系统安装(全盘安装)的过程,如果没有特殊要求,推荐安装UOS系统都采用全盘安装_统信uos系统专业版
文章浏览阅读116次。这种专利有意思吗 有意义吗 有创新吗?和别人都是右手写字,我申请左手写字的专利 ,,有什么区别
文章浏览阅读514次。jmeter接口测试自动获取cookie有时候我们接口地址和方式都对,就是报错,查看接口文档,其实需要加上消息头cookie,添加完cookie,不需要配置获取什么的,只要加一个访问网站的首页地址(HTTP请求),他会自动获取到cookie值添加cookie管理器加完cookie管理器,登录里就获取到了cookie值Jmeter请求参数3种形..._jmeter request body获取cookie
文章浏览阅读2.4k次。PADS中常见问题解决方案1、走线很细,不是设定值。解答:有时将预拉线布好线后,所布的线变成了一根很细的线而不是我们所设定的线宽,但是查看它的属性也还是一样的,最小线宽显示值的设定大于route线宽。setup→preferences→global→minimum display或者使用R X这个快捷命令,X表示需要设定的值。走线宽度无法修改,提示wrong widthvalue,关于线宽的rul..._pads设置灌铜进不去
文章浏览阅读438次。原标题:OPPO Reno可尝鲜Android Q:教程如下5月8日凌晨,Android Q在谷歌I/O开发者大会上正式亮相。在I/O大会现场,谷歌公布了首批Android Q升级名单,其中OPPO Reno成为首批可适配Android Q的国产手机。官方介绍,OPPO Reno从今天起就可以体验到Android Q Beta版。OPPO Reno如何尝鲜Android Q?备份1、确认你的机型为..._android oppo 申请定位权限
文章浏览阅读99次。14.2选词控件的渲染这个控件由于使用了三个子窗口来实现功能,所以它的渲染窗口实现非常简单,只是负责描绘背景。代码如下。void FalgardIMEShowWindow::render(){ IMEShowWindow* w = (IMEShowWindow*)d_window; const WidgetLookFeel&am..._gui-guider生成的输入框组件没法输入中文应该怎么解决
文章浏览阅读1.5k次。windowns以及linux下的内存泄露方法实现_clion 内存泄漏
文章浏览阅读3.1k次。练习内容:给出上图拓扑图,配置两个交换机后,使得pc14可直接ping通pc17 ,给定各pc的ip和掩码如下pc14: 192.168.0.1 255.255.255.0 pc15: 192.168.0.2 255.255.255.0pc16: 192.168.0.3 255.255.255.0 pc17: 192.168.0.4 255.255.25..._适合练习用的华为交换机
文章浏览阅读640次,点赞8次,收藏11次。java.lang.ClassNotFoundException: org.springframework.web.context.ContextLoa解决方案_java.lang.classnotfoundexception: org.springframework.web.context.contextloa