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