C++での小惑星の衝突

すべての衝突の後、小惑星の状態を見つける必要があります。 2つの小惑星が出会うと、小さい方の小惑星が爆発します。両方が同じサイズの場合、両方が爆発します。同じ方向に移動する2つの小惑星が出会うことはありません。

したがって、入力が[5、10、-5]の場合、出力は[5、10]になります。ここでは、10と-5が10で衝突し、5と10が衝突することはありません。

これを解決するには、次の手順に従います-

• 1つの配列をretにします。n：=arrのサイズ

• 0からn–1の範囲のiの場合

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