西安公司建设网站,企业网站推广的重要性,汽车行业做网站,广州市网站设计以下四个题都是重叠区间问题
452. 用最少数量的箭引爆气球
为了让气球尽可能重叠#xff0c;先按照气球起始位置由大到小排序tips#xff1a;sort默认就可以实现以上排序#xff0c;不需要写cmp重点#xff1a;当下一个气球的左边界不小于上一个气球的右边界时(即有重叠的…以下四个题都是重叠区间问题
452. 用最少数量的箭引爆气球
为了让气球尽可能重叠先按照气球起始位置由大到小排序tipssort默认就可以实现以上排序不需要写cmp重点当下一个气球的左边界不小于上一个气球的右边界时(即有重叠的情况)为了判断再下一个气球能否和这两个有重叠就需要将右边界 point[i][1] 置成小的那个右边界 min(point[i-1][1] , point[i][1])
class Solution {
public:int findMinArrowShots(vectorvectorint points) {sort(points.begin(), points.end());int ret 1;for (int i 1; i points.size(); i) {if (points[i][0] points[i - 1][1]) ret;else points[i][1] min(points[i - 1][1], points[i][1]);}return ret;}
};
435. 无重叠区间
与上一个题极其相似首先按照左边界排序当重叠的时候舍弃重叠的右边长的那个区间(即将右边界定为小的那个)ret记录重叠区间个数。
class Solution {
public:int eraseOverlapIntervals(vectorvectorint intervals) {sort(intervals.begin(), intervals.end());int ret 0;for (int i 1; i intervals.size(); i) {if (intervals[i][0] intervals[i - 1][1]) {ret;intervals[i][1] min(intervals[i][1], intervals[i - 1][1]);}}return ret;}
};763. 划分字母区间
统计每一个字符最后出现的位置从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点
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 ret;int left 0, right 0;for (int i 0; i s.size(); i) {right max(hash[s[i] - a], right);if (right i) {ret.push_back(right - left 1);left i 1;}}return ret;}
};56. 合并区间
和上面的435差不多先按照左边界排序好将第一组数据添加到ret中之后如果满足后一个的左边界小于等于这个的右边界时候更新ret中的这个(ret.back()[1]更新成大的右边界)不满足就把下一个添加进来for循环是从i1开始
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {sort(intervals.begin(), intervals.end());if (intervals.size() 1)return intervals;vectorvectorint ret;ret.push_back(intervals[0]);for (int i 1; i intervals.size(); i) {if (intervals[i][0] ret.back()[1]) {ret.back()[1] max(ret.back()[1], intervals[i][1]);} elseret.push_back(intervals[i]);}return ret;}
};
