洛阳做公司网站,微信小程序公众号开发,网站雪花代码,盐城网站建设渠道合作452. 用最少数量的箭引爆气球 - 力扣#xff08;LeetCode#xff09;
思路#xff1a;先按照左边界排序#xff0c;当前的左边界大于前一个的右边界的时候#xff0c;表示没有覆盖所以需要一根箭#xff0c;反之则要更新为最小的右边界
重点#xff1a;是区间覆盖问题…452. 用最少数量的箭引爆气球 - 力扣LeetCode
思路先按照左边界排序当前的左边界大于前一个的右边界的时候表示没有覆盖所以需要一根箭反之则要更新为最小的右边界
重点是区间覆盖问题判断好边界 class Solution {
public:static bool cmp(const vectorint a,const vectorint b){return a[0]b[0];}int findMinArrowShots(vectorvectorint points) {sort(points.begin(),points.end(),cmp);int ans1;for(int i1;ipoints.size();i){if(points[i][0]points[i-1][1]){ans;}else{points[i][1]min(points[i][1],points[i-1][1]);}}return ans;}
};
435. 无重叠区间 - 力扣LeetCode
思路统计覆盖的区间个数区间覆盖问题判断好边界
class Solution {
public:static bool cmp(const vectorint a,const vectorint b){return a[0]b[0];}int eraseOverlapIntervals(vectorvectorint intervals) {sort(intervals.begin(),intervals.end(),cmp);int ans0;for(int i1;iintervals.size();i){if(intervals[i][0]intervals[i-1][1]){ans;intervals[i][1]min(intervals[i][1],intervals[i-1][1]);//更新有边界}}return ans;}
};
763. 划分字母区间 - 力扣LeetCode
思路抽象、为区间覆盖、问题统计最字母最远下标位置更新右边界到达有边界的时候表示可以划分为一个区间然后再更新左边界
class Solution {
public:vectorint partitionLabels(string s) {int hash[26]{0};for(int i0;is.length();i){hash[s[i]-a]i;}vectorintans;int left0,right0;for(int i0;is.length();i){rightmax(right,hash[s[i]-a]);if(righti){ans.push_back(right-left1);leftright1;}}return ans;}
};
总结
区间覆盖问题先排序判断好边界。
