免备案网站建设,建设网站公司,wordpress发布站点,wordpress 汉化版主题目录
LeeCode 435. 无重叠区间
LeeCode 763.划分字母区间
LeeCode 56. 合并区间 LeeCode 435. 无重叠区间
435. 无重叠区间 - 力扣#xff08;LeetCode#xff09;
思路1#xff1a;按照右边界排序#xff0c;从左向右记录非交叉区间的个数。最后用区间总数减去非交叉…目录
LeeCode 435. 无重叠区间
LeeCode 763.划分字母区间
LeeCode 56. 合并区间 LeeCode 435. 无重叠区间
435. 无重叠区间 - 力扣LeetCode
思路1按照右边界排序从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
时间复杂度On log n 空间复杂度On
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;}
};
思路2左边界排序直接求 重叠的区间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;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;}
}; LeeCode 763.划分字母区间
763. 划分字母区间 - 力扣LeetCode
思路1遍历的过程中找每一个字母的边界如果找到之前遍历过的所有字母的最远边界说明这个边界就是分割点。
class Solution {
public:vectorint partitionLabels(string s) {int hash[27] {0};for (int i 0; i s.size(); i) {hash[s[i] - a] i;}vectorint result;int left 0, 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;}
};
思路2统计字符串中所有字符的起始和结束位置记录这些区间将区间按左边界从小到大排序找到边界将区间划分成组互不重叠。找到的边界就是答案。
class Solution {
public:static bool cmp(vectorint a, vectorint b) {return a[0] b[0];}vectorvectorint countLabels(string s) {vectorvectorint hash(26, vectorint(2,INT_MIN));vectorvectorint hash_filter;for (int i 0; i s.size(); i) {if (hash[s[i] - a][0] INT_MIN) hash[s[i] - a][0] i;hash[s[i] - a][1] i;}for (int i 0; i hash.size(); i) {if (hash[i][0] ! INT_MIN) hash_filter.push_back(hash[i]);}return hash_filter;}vectorint partitionLabels(string s) {vectorint res;vectorvectorint hash countLabels(s);sort(hash.begin(), hash.end(), cmp);int rightBoard hash[0][1];int leftBoard 0;for (int i 1; i hash.size(); i) {if (hash[i][0] rightBoard) {res.push_back(rightBoard - leftBoard 1);leftBoard hash[i][0];}rightBoard max(rightBoard, hash[i][1]);} res.push_back(rightBoard - leftBoard 1);return res;}
}; LeeCode 56. 合并区间
56. 合并区间 - 力扣LeetCode
思路对区间排序后判断是否重合合并区间将合并后的左右边界作为一个新的区间加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。
时间复杂度On log n 空间复杂度Olog n
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {vectorvectorint result;if (intervals.size() 0) return result;sort(intervals.begin(), intervals.end(), [](const vectorint a, const vectorint b){return a[0] b[0];});result.push_back(intervals[0]);for (int i 1; i intervals.size(); i) {if (result.back()[1] intervals[i][0]) result.back()[1] max(result.back()[1], intervals[i][1]);else result.push_back(intervals[i]);}return result;}
};
