前言
参考题解:用最少数量的箭引爆气球-代码随想录
提交代码
方法一:贪心
贪心:每次射尽可能多的气球。射尽可能多的气球的每一箭,都有个范围。只要这个范围,被共同包含在最多的气球范围内,即可。
class Solution {
public:
struct cmp{
bool operator() (vector<int>& v1, vector<int>& v2){
// start越小,越靠前;start相同,end越小,越靠前
if(v1[0]<v2[0])
return true;
else if(v1[0]==v2[0])
return v1[1]<v2[1];
else
return false;
}
};
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(),points.end(),cmp());
int count = 1; // 1 <= points.length <= 10^4
int start = points[0][0];
int end = points[0][1];
for(int i=1; i<points.size(); i++){
if(points[i][0]>=start && points[i][0]<=end){
// 当前气球,可以被上一个气球连带zhapo
// 同时缩小范围,范围为一针可以都扎破的范围
start = min(start,points[i][0]);
end = min(end,points[i][1]);
continue;
}
// 开启新的范围
count++;
start = points[i][0];
end = points[i][1];
}
return count;
}
};
方法二:贪心
贪心:每次射尽可能多的气球。将上面的代码简化。下面代码来自参考题解。
代码思路:找重复的气球,寻找重叠气球最小右边界
class Solution {
private:
static bool cmp(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.size() == 0) return 0;
sort(points.begin(), points.end(), cmp);
int result = 1; // points 不为空至少需要一支箭
for (int i = 1; i < points.size(); i++) {
// 因为排序,points[i][0]必然大于等于points[i - 1][0]
// 当开头,比上一个开头还大,完全不想交
if (points[i][0] > points[i - 1][1]) { // 气球i和气球i-1不挨着,注意这里不是>=
result++; // 需要一支箭
}
else { // 气球i和气球i-1挨着
// 因为排序的原因,范围的开头在不断向大处缩小
points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界
}
}
return result;
}
};
总的来说,虽然方法二简化了些,但是我写的方法一更容易懂~