关于设计图的网站,怎么自己编码做网站,网站优化北京,网络运营推广是干嘛的435. 无重叠区间
思路#xff1a;
按照左边排序#xff0c;按照452引爆气球的思路即可#xff0c;统计重叠区间个数就是最小删除个数#xff0c; 直接改点就好。
代码#xff1a;
//手搓
class Solution {
private:static bool cmp(const vectorint a, c…435. 无重叠区间
思路
按照左边排序按照452引爆气球的思路即可统计重叠区间个数就是最小删除个数 直接改点就好。
代码
//手搓
class Solution {
private:static bool cmp(const vectorint a, const vectorint b){return a[0]b[0];}
public:int eraseOverlapIntervals(vectorvectorint intervals) {if(intervals.size() 0) return 0;sort(intervals.begin(),intervals.end(),cmp);int result 0;for(int i 1; iintervals.size();i){if(intervals[i][0]intervals[i-1][1]){result; intervals[i][1] min(intervals[i-1][1],intervals[i][1]); }}return result;}
};//卡哥代码
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;}
};
时间复杂度O(nlog n) 有一个快排空间复杂度O(n)有一个快排最差情况(倒序)时需要n次递归调用。因此确实需要O(n)的栈空间
763.划分字母区间
思路
如果找到之前遍历过的所有字母的最远边界说明这个边界就是分割点了。此时前面出现过所有字母最远也就到这个边界了。
可以分为如下两步
统计每一个字符最后出现的位置从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点
如图 代码
//手撕
class Solution {
private:
vectorint result;
int left0,right0;
int hash[27]{0};
public:vectorint partitionLabels(string s) {for(int i 0; is.size();i){hash[s[i]-a] i;}for(int i 0; is.size();i){right max(right,hash[s[i]-a]);if(iright){result.push_back(right-left1);left i1;}}return result;}
};//卡哥代码
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;}
};
时间复杂度O(n)空间复杂度O(1)使用的hash数组是固定大小
56. 合并区间
思路
和讲过的452. 用最少数量的箭引爆气球 (opens new window)和 435. 无重叠区间 (opens new window)都是一个套路。
这几道题都是判断区间重叠区别就是判断区间重叠后的逻辑本题是判断区间重贴后要进行区间合并。
所以一样的套路先排序让所有的相邻区间尽可能的重叠在一起按左边界或者右边界排序都可以处理逻辑稍有不同。
按照左边界从小到大排序之后如果 intervals[i][0] intervals[i - 1][1] 即intervals[i]的左边界 intervals[i - 1]的右边界则一定有重叠。本题相邻区间也算重贴所以是,本题技巧在于直接修改区间不用删除再添加
这么说有点抽象看图注意图中区间都是按照左边界排序之后了 代码
//手搓
class Solution {
private:vectorvectorint result;static bool cmp(vectorinta,vectorintb){return a[0]b[0];}
public:vectorvectorint merge(vectorvectorint intervals) {sort(intervals.begin(),intervals.end(),cmp);result.push_back(intervals[0]);for(int i 1; i intervals.size(); i){if(intervals[i][0]result.back()[1]){result.back()[1]max(intervals[i][1],result.back()[1]);}else result.push_back(intervals[i]);}return result;}
};//卡哥代码
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;}
};
时间复杂度: O(nlogn)空间复杂度: O(logn)排序需要的空间开销
