惠州建设网站,江阴招聘网站建设学徒,建网站卖阀门,创艺装饰公司官网文章目录 435.无重叠区间按右边界排序CPP代码 按左边界排序如何判断相邻区间是否重叠如何判断一下一个区间与当前相邻区间是否重叠总结CPP代码 763.划分字母区间思路伪代码实现CPP代码 56. 合并区间思路CPP代码 435.无重叠区间 力扣题目链接 文章链接#xff1a;435.无重叠区间… 文章目录 435.无重叠区间按右边界排序CPP代码 按左边界排序如何判断相邻区间是否重叠如何判断一下一个区间与当前相邻区间是否重叠总结CPP代码 763.划分字母区间思路伪代码实现CPP代码 56. 合并区间思路CPP代码 435.无重叠区间 力扣题目链接 文章链接435.无重叠区间 视频链接贪心算法依然是判断重叠区间 | LeetCode435.无重叠区间 状态排序顺序很重要决定了我们如何处理后续逻辑。对于按右边界排序我们只要抓住分割线即可每次更新分割线说明就有非交叉区间 想都不用想本题首先要求的肯定就是进行排序让为了让我们后续更好进行操作。
并且可以很直观得推导出我们的贪心策略
局部最优——当前区间与相邻两个区间是否重叠这里是非常有技巧的具体可以看下面的思路
全局最优——找出所有的重叠区间
按右边界排序
我们先按右边界进行排序然后从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
在记录非交叉区间的个数也是很需要技巧的 总之一句话最重要的点就在于找到区间的分割线每次遇到分割线我们就记录一次非交叉区间个数。比如上文中更新了两次分割线所以非交叉区间是3。所以在代码表现上也是比较直观的。 基于以上代码的一个重要前提就是区间是按照右边界来排序的
CPP代码
class Solution {
public:// 按照区间右边界排序static bool cmp (const vectorint a, const vectorint b) {return a[1] b[1];}int eraseOverlapIntervals(vectorvectorint 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;}
};按左边界排序
对于左边界排序这里拿 intervals [[1,100],[11,22],[1,11],[2,12]]举例
排序后intervals [[1,100],[1,11],[2,12],[11,22]]。如果我们按照右边界排序的处理还能行吗。简单推导一下这样会导致我们的最终结果是3因为end永远都无法更新程序认为只有一条分割线也就是count 1。
那么如果按照左边界来排序应该怎么写呢 如何判断相邻区间是否重叠
如果当前区间的左边界[1, 11]大于等于上一个区间的右边界[1, 100]。说明相邻区间不重叠如果不满足该情况那肯定说明区间重叠。 这里的count表示的是重叠区间的个数。 end在此处仍然表示的是区间分割点。
if (intervals[i-1][0] intervals[i][1]) end intervals[i][1];
else {count; //记录我们重叠了多少个区间
}如何判断一下一个区间与当前相邻区间是否重叠
要首先计算出之前我们判断的相邻区间的最小边界左边界的最小值和我们下一个区间的左边界是否重叠。
else {count;end min(end, intervals[i][1])
}这里num[i][1]min(nums[i-1][1], nums[i][1])等到i遍历到下一个区间应该和之前两个相邻区间的最小右边界比较如果当前i区间的左边界要大的话那么说明不是重叠区间。
总结
左边界的思想一句话就是如果发现了重叠区间我们就进行更新新的分割点并且count
CPP代码
class Solution {
public:static bool cmp (const vectorint a, const vectorint b) {return a[0] b[0]; // 改为左边界排序}int eraseOverlapIntervals(vectorvectorint intervals) {if (intervals.size() 0) return 0;sort(intervals.begin(), intervals.end(), cmp);int count 0; // 注意这里从0开始因为是记录重叠区间int end intervals[0][1]; // 记录区间分割点for (int i 1; i intervals.size(); i) { if (intervals[i][0] end) end intervals[i][1]; // 无重叠的情况else { // 重叠情况 end min(end, intervals[i][1]);count;}}return count;}
};# 精简版
class Solution {
public:static bool cmp (const vectorint a, const vectorint b) {return a[0] b[0]; // 改为左边界排序}int eraseOverlapIntervals(vectorvectorint intervals) {if (intervals.size() 0) return 0;sort(intervals.begin(), intervals.end(), cmp);int count 0; // 注意这里从0开始因为是记录重叠区间for (int i 1; i intervals.size(); i) {if (intervals[i][0] intervals[i - 1][1]) { //重叠情况intervals[i][1] min(intervals[i - 1][1], intervals[i][1]);count;}}return count;}
};763.划分字母区间 力扣题目链接 文章链接763.划分字母区间 视频链接贪心算法寻找最远的出现位置 LeetCode763.划分字母区间 状态 本题其实就是一句话“面多了加水水多了加面直到刚刚好”。
这里完全不是贪心的思路就是全局的一个模拟主要它也属于重叠区间的问题。
思路
思路上还是很难想到的。
我们在遍历过程中相当于找到每一个字母出现的边界如果找到之前遍历过的所有字母的最远边界说明这个边界就是分割点了。
所以分为如下两步
统计每个字符最后出现的位置从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点
我们需要记录每个字符出现的最后位置如图 伪代码实现
统计每一个字符最后出现的位置
int hash[27] {0}; //i为字符hash[i]为字符出现的最后位置
for (int i 0; i S.size(); i) {hash[S[i] - a] i;
}定义变量
vectorint result;
int left 0;
int right 0;字符出现的最远边界的更新和结果存储
for (int i 0; i S.size(); i) {right max(right, hash[S[i] - a]); // 找到字符出现的最远边界if (i right) {result.push_back(right - left 1);left i 1;}
}CPP代码
class Solution {
public:vectorint partitionLabels(string S) {int hash[27] {0}; // i为字符hash[i]为字符出现的最后位置for (int i 0; i S.size(); i) { // 统计每一个字符最后出现的位置hash[S[i] - a] i;}vectorint result;int left 0;int right 0;for (int i 0; i S.size(); i) {right max(right, hash[S[i] - a]); // 找到字符出现的最远边界if (i right) {result.push_back(right - left 1);left i 1;}}return result;}
};56. 合并区间 力扣题目链接 文章链接56. 合并区间 视频链接贪心算法合并区间有细节LeetCode56.合并区间 状态 思路
本题同样也是重叠区间的问题。
区别在于判断区间重叠后的逻辑本题是将重叠区间进行合并。
先排序如果intervals[i][0] intervals[i - 1][1]就有重叠所以进行合并 合并的逻辑也比较简单
用合并区间后左边界和右边界作为一个新的区间加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。
CPP代码
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {vectorvectorint result;if (intervals.size() 0) return result; // 区间集合为空直接返回// 排序的参数使用了lambda表达式sort(intervals.begin(), intervals.end(), [](const vectorint a, const vectorint 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;}
};
