資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告