Va chạm tiểu hành tinh trong C ++

Giả sử chúng ta có một mảng gồm các số nguyên đại diện cho các tiểu hành tinh liên tiếp. Bây giờ đối với mỗi tiểu hành tinh, giá trị tuyệt đối đại diện cho kích thước của nó và dấu hiệu đại diện cho hướng của nó có thể là dương hoặc âm đối với bên phải và bên trái tương ứng. Mỗi tiểu hành tinh di chuyển với tốc độ như nhau.

Chúng ta phải tìm ra trạng thái của các tiểu hành tinh sau tất cả các vụ va chạm. Khi hai tiểu hành tinh gặp nhau, tiểu hành tinh nhỏ hơn sẽ phát nổ. Nếu cả hai có cùng kích thước, cả hai sẽ phát nổ. Hai tiểu hành tinh chuyển động cùng chiều sẽ không bao giờ gặp nhau.

Vì vậy, nếu đầu vào là [5, 10, -5], thì đầu ra sẽ là [5, 10]. Ở đây 10 và -5 va chạm trong 10, sau đó 5 và 10 sẽ không bao giờ va chạm.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một mảng ret, n:=kích thước của arr

• cho tôi trong phạm vi từ 0 đến n - 1

  • nếu ret trống hoặc phần tử cuối cùng của ret là dương và arr [i] là âm thì

    • chèn arr [i] vào ret, tăng i lên 1

  • nếu không thì

    • x:=phần tử cuối cùng của ret, xóa phần tử cuối cùng khỏi ret

    • absX:=| x |, absY:=| arr [i] |

    • nếu absX =absY, sau đó tăng i lên 1

    • nếu không thì

      • nếu absX> absY, sau đó chèn x vào ret, tăng i lên 1

• trả lại ret

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

#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));
}

Đầu vào

[5,10,-4]

Đầu ra

[5, 10, ]