C++ 中的小行星碰撞
c++server side programmingprogramming更新于 2024/9/1 6:36:00
假设我们有一个由整数组成的数组 asteroids，表示一行中的小行星。现在对于每颗小行星，绝对值表示其大小，符号表示其方向，分别为右和左的正或负。每颗小行星以相同的速度移动。
我们必须找到所有碰撞后小行星的状态。当两颗小行星相遇时，较小的那颗会爆炸。如果两颗小行星大小相同，则两颗都会爆炸。两颗朝同一方向移动的小行星永远不会相遇。
因此，如果输入为 [5, 10, -5]，则输出为 [5, 10]。这里 10 和 -5 在 10 中发生碰撞，那么 5 和 10 永远不会发生碰撞。
为了解决这个问题，我们将遵循以下步骤 −
创建一个数组 ret, n := size of arr
for i in range 0 to n – 1
如果 ret 为空或 ret 的最后一个元素为正数且 arr[i] 为负数，则
将 arr[i] 插入到 ret 中，将 i 增加 1
否则
x := ret 的最后一个元素，从 ret 中删除最后一个元素
absX := |x|, absY := |arr[i]|
如果 absX = absY，则将 i 增加 1
否则
如果 absX > absY，则将 x 插入到 ret 中，将 i 增加 1
return ret
示例 (C++)
让我们看下面的实现，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
bool isNeg(int x){
return x < 0;
}
vector<int> asteroidCollision(vector<int>& arr) {
vector <int> ret;
int n = arr.size();
for(int i = 0; i< n; ){
if(ret.empty() || !(!isNeg(ret[ret.size() - 1]) && isNeg(arr[i]))){
ret.push_back(arr[i]);
i++;
} else {
int x = ret[ret.size() - 1];
ret.pop_back();
int absX = abs(x);
int absY = abs(arr[i]);
if(absX == absY){
i++;
} else {
if(absX > absY){
ret.push_back(x);
i++;
}
}
}
}
return ret;
}
};
main(){
vector<int> v = {5, 10, -4};
Solution ob;
print_vector(ob.asteroidCollision(v));
}
输入
[5,10,-4]
输出
[5, 10, ]
