数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++小行星碰撞
假设我们有一个整数数组asteroids，表示一排中的小行星。每个小行星的绝对值表示其大小，符号表示其方向，正数表示向右，负数表示向左。每颗小行星以相同的速度移动。
我们需要找到所有碰撞后小行星的状态。当两颗小行星相遇时，较小的小行星会爆炸。如果两颗小行星大小相同，则都会爆炸。两个朝相同方向移动的小行星永远不会相遇。
例如，如果输入为[5, 10, -5]，则输出为[5, 10]。这里10和-5在10处碰撞，然后5和10将不会碰撞。
为了解决这个问题，我们将遵循以下步骤：
创建一个数组ret，n := arr的大小
对于i从0到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
返回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, ]
更新于：2020年5月2日
863 次浏览
广告