刷题记录
- 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 vector<int> & a, const vector<int> & b){
if(a[0] == b[0]) return a[1]>b[1];
return a[0] < b[0];
}
int findMinArrowShots(vector<vector<int>>& points) {
vector<vector<int>> arrows;
sort(points.begin(), points.end(), cmp);
for(int i=0; i<points.size(); i++){
bool flag = true;
for(int j=0; j<arrows.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 vector<int> & a, const vector<int> & b){
if(a[0] == b[0]) return a[1]>b[1];
return a[0] < b[0];
}
int findMinArrowShots(vector<vector<int>>& points) {
if(points.size()==0) return 0;
sort(points.begin(), points.end());
int result = 1;
for(int i=1; i<points.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 vector<int>&a, const vector<int>&b){
if(a[0] == b[0]) return a[1]>b[1];
return a[0]<b[0];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
int result = 0;
sort(intervals.begin(), intervals.end(), cmp);
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]);
result++;
}
}
return result;
}
};
763. 划分字母区间
leetcode题目地址
记录每个字符出现的最远位置,子串截取到子串中出现的字符的最远位置。
时间复杂度:
O
(
n
)
O(n)
O(n)
空间复杂度:
O
(
1
)
O(1)
O(1)
// c++
class Solution {
public:
vector<int> partitionLabels(string s) {
cin.tie(nullptr)->sync_with_stdio(false);
int hash[26] = {0};
for(int i=0; i<s.size(); i++){
hash[s[i]-'a'] = i;
}
int left = 0;
int right = 0;
vector<int> result;
for(int i=0; i<s.size(); i++){
right = max(right, hash[s[i]-'a']);
if(i==right){
result.emplace_back(right-left+1);
left = i+1;
}
}
return result;
}
};