การชนกันของดาวเคราะห์น้อยใน C++

สมมติว่าเรามีดาวเคราะห์น้อยอาร์เรย์เป็นจำนวนเต็มแทนดาวเคราะห์น้อยในแถว สำหรับดาวเคราะห์น้อยแต่ละดวง ค่าสัมบูรณ์แสดงถึงขนาดของมัน และเครื่องหมายแสดงถึงทิศทางที่สามารถเป็นบวกหรือลบสำหรับด้านขวาและด้านซ้ายตามลำดับ ดาวเคราะห์น้อยแต่ละดวงเคลื่อนที่ด้วยความเร็วเท่ากัน

เราต้องหาสถานะของดาวเคราะห์น้อยหลังจากการชนกันทั้งหมด เมื่อดาวเคราะห์น้อยสองดวงมาบรรจบกัน ดาวเคราะห์น้อยดวงนั้นก็จะระเบิด ถ้าทั้งคู่มีขนาดเท่ากันทั้งคู่จะระเบิด ดาวเคราะห์น้อยสองดวงที่เคลื่อนที่ไปในทิศทางเดียวกันจะไม่มีวันมาบรรจบกัน

ดังนั้นหากอินพุตเป็น [5, 10, -5] เอาต์พุตจะเป็น [5, 10] ที่นี่ 10 และ -5 ชนกันใน 10 จากนั้น 5 และ 10 จะไม่ชนกัน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างหนึ่งอาร์เรย์ ret, n :=ขนาดของ arr

• สำหรับฉันอยู่ในช่วง 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

• รีเทิร์น

ตัวอย่าง (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, ]