自己做网站需要买哪些,网易163企业邮箱官网,wordpress加分页,百度网盘在线观看资源刷题记录 452. 用最少数量的箭引爆气球思路一思路二 435. 无重叠区间763. 划分字母区间 452. 用最少数量的箭引爆气球
leetcode题目地址
思路一
先按起始坐标从小到大排序。排序后找交集并将交集存入一个数组中#xff0c;遍历气球数组从交集数组中找交集#xff0c;找到与… 刷题记录 452. 用最少数量的箭引爆气球思路一思路二 435. 无重叠区间763. 划分字母区间 452. 用最少数量的箭引爆气球
leetcode题目地址
思路一
先按起始坐标从小到大排序。排序后找交集并将交集存入一个数组中遍历气球数组从交集数组中找交集找到与当前集合相交的集合后将该集合的范围更新为两集合的交集即左右区间取最小最后返回交集数组的长度。
时间复杂度 O ( n 2 ) O(n^2) O(n2) 空间复杂度 O ( n ) O(n) O(n)
// c
class Solution {
public: static bool cmp(const vectorint a, const vectorint b){if(a[0] b[0]) return a[1]b[1];return a[0] b[0];}int findMinArrowShots(vectorvectorint points) {vectorvectorint arrows;sort(points.begin(), points.end(), cmp);for(int i0; ipoints.size(); i){bool flag true;for(int j0; jarrows.size(); j){if(points[i][0]arrows[j][0] points[i][0] arrows[j][1]){arrows[j][0] min(arrows[j][0], points[i][0]);arrows[j][1] min(arrows[j][1], points[i][1]);flag false;break;}}if(flag){arrows.emplace_back(points[i]);}}return arrows.size();}
};思路二
和思路一本质上是一样的只是不再借助额外空间也不再需要双层循环。排序后只查看当前气球的起始坐标小于上一个气球的结束坐标是则说明有重叠则缩小当前节点的结束坐标为交集的结束位置反之没有重叠则箭数量1。
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) 空间复杂度 O ( 1 ) O(1) O(1)
class Solution {
public:static bool cmp(const vectorint a, const vectorint b){if(a[0] b[0]) return a[1]b[1];return a[0] b[0];}int findMinArrowShots(vectorvectorint points) {if(points.size()0) return 0;sort(points.begin(), points.end());int result 1;for(int i1; ipoints.size(); i){if(points[i][0] points[i-1][1]){result;}else{points[i][1] min(points[i-1][1], points[i][1]);}}return result;}
};435. 无重叠区间
leetcode题目地址
本题可以说是和上一题换汤不换药只不过上一题是统计不重叠的区间个数本题是统计重叠区间。尽可能少的移除区间来保持剩余区间互不重叠那每次出现重叠移除区间最大的那个即可。
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) 空间复杂度 O ( 1 ) O(1) O(1)
// c
class Solution {
public:static bool cmp(const vectorinta, const vectorintb){if(a[0] b[0]) return a[1]b[1];return a[0]b[0];}int eraseOverlapIntervals(vectorvectorint intervals) {int result 0;sort(intervals.begin(), intervals.end(), cmp);for(int i1; iintervals.size(); i){if(intervals[i][0] intervals[i-1][1]){// 把最大的区间移除intervals[i][1] min(intervals[i-1][1], intervals[i][1]);result;}}return result;}
};763. 划分字母区间
leetcode题目地址
记录每个字符出现的最远位置子串截取到子串中出现的字符的最远位置。
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
// c
class Solution {
public:vectorint partitionLabels(string s) {cin.tie(nullptr)-sync_with_stdio(false);int hash[26] {0};for(int i0; is.size(); i){hash[s[i]-a] i;}int left 0;int right 0;vectorint result;for(int i0; is.size(); i){right max(right, hash[s[i]-a]);if(iright){result.emplace_back(right-left1);left i1;}}return result;}
};
