数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中用最少箭头射爆气球
假设在二维空间中散布着一些球形气球。对于每个气球，都有其水平直径的起始和结束坐标。起始坐标始终小于结束坐标。最多会有104个气球。一支箭可以从x轴上不同的点精确垂直向上射出。如果xstart ≤ x ≤ xend，则位于xstart到xend位置的气球会被射中x点的箭射爆。可以射出的箭的数量没有限制。假设射出的箭会无限向上飞行。我们必须找到射爆所有气球所需的最小箭头数量。例如，如果输入为[[10,16],[2,8], [1,6], [7,12]]，则输出为2。如果我们从x = 6射出一支箭，它会射爆[2,8]和[1,6]，然后从x = 11射出另一支箭来射爆其余的气球。
为了解决这个问题，我们将遵循以下步骤：
定义一个名为intersect()的方法来检查位置是否相交。
另一个方法manipulate()，在获取所有相交气球的范围后操作范围。
实际方法是将气球位置作为pos参数。
根据结束位置对pos数组进行排序。
n := 气球数量，如果n为0，则返回0。
currEnd := 排序后pos第一个元素的结束位置。
cnt := 1
对于i从1到n – 1的范围
如果currEnd < pos[i]的起始位置，则计数加1，并将currEnd := pos[i]的结束位置。
返回计数。
让我们看看下面的实现来更好地理解。
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool intersect(vector <int>& a, vector <int>& b){
return a[1] >= b[0];
}
static bool cmp(vector <int>& a, vector <int>& b){
return a[1] < b[1];
}
void manipulate(vector <int>& a, vector <int>& b){
a[0] = min(a[0], b[0]);
a[1] = max(a[1], b[1]);
}
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(), points.end(), cmp);
int n = points.size();
if(!n) return 0;
int currEnd = points[0][1];
int cnt = 1;
for(int i = 1; i < n; i++){
if(currEnd < points[i][0]){
cnt++;
currEnd = points[i][1];
}
}
return cnt;
}
};
main(){
vector<vector<int>> v = {{10,16},{2,8},{1,6},{7,12}};
Solution ob;
cout << (ob.findMinArrowShots(v));
}输入
[[10,16],[2,8],[1,6],[7,12]]
输出
2
更新于：2020年4月30日
221 次浏览
广告