C ++中的小行星碰撞

假设我们有一个整数小行星数组，它们连续代表小行星。现在，对于每个小行星，绝对值表示其大小，符号表示其方向，分别对于右侧和左侧可以为正或负。每个小行星以相同的速度移动。

在所有碰撞之后，我们必须找到小行星的状态。当两个小行星相遇时，较小的一个将爆炸。如果两者大小相同，则两者都会爆炸。朝同一方向移动的两个小行星将永远不会相遇。

因此，如果输入类似于[5，10，-5]，则输出将为[5，10]。这里10和-5在10中发生碰撞，那么5和10将永远不会发生碰撞。

为了解决这个问题，我们将遵循以下步骤-

• 使一个数组为ret，n：= arr的大小

• 对于i，范围为0至n – 1

• x：= ret的最后一个元素，从ret删除最后一个元素

• absX：= | x |，absY：= | arr [i] |

• 如果absX = absY，则将i加1

• 除此以外

• 如果absX> absY，则将x插入ret，将i增加1

• 将rr [i]插入ret，将i增加1

• 如果ret为空或ret的最后一个元素为正，而arr [i]为负，则

• 除此以外

• 返回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, ]