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

ให้อาร์เรย์ asteroids ค่าสัมบูรณ์ = ขนาด, เครื่องหมาย = ทิศทาง (+ = ขวา, - = ซ้าย) ทุกดาวเคลื่อนที่ความเร็วเท่ากัน เมื่อชนกัน ตัวเล็กจะระเบิด เท่ากันทั้งคู่ระเบิด ทิศทางเดียวกันไม่ชน

ตัวอย่าง: [5,10,-5] → [5,10] (10 กับ -5 ชน 10 ชนะ, 5 กับ 10 ไม่ชน)

ขั้นตอนการแก้ปัญหา (Stack)

1. สร้างสแต็ก ret
2. วนแต่ละดาว a:
   • ถ้า ret ว่าง หรือบนสุดเคลื่อนขวา (>=0) และ a เคลื่อนซ้าย (<0) → ไม่ชน ใส่ a เข้า stack
   • มิฉะนั้น (บนสุดเคลื่อนขวา, a เคลื่อนซ้าย = จะชน):
     • ดึงบนสุด x ออก
     • ถ้า |x| == |a| → ทั้งคู่ระเบิด (ไม่ใส่กลับ, ข้าม a)
     • ถ้า |x| > |a| → x ชนะ ใส่ x กลับ, ข้าม a
     • ถ้า |x| < |a| → a ชนะ ลองชนกับตัวถัดไปใน stack (วนลูป)
3. คืน stack ที่เหลือ

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v) {
    cout << "[";
    for (int x : v) cout << x << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& arr) {
        vector<int> st;
        for (int a : arr) {
            bool alive = true;
            while (alive && !st.empty() && st.back() > 0 && a < 0) {
                int x = st.back(); st.pop_back();
                if (abs(x) == abs(a)) { alive = false; }
                else if (abs(x) > abs(a)) { st.push_back(x); alive = false; }
            }
            if (alive) st.push_back(a);
        }
        return st;
    }
};

int main() {
    vector<int> v = {5, 10, -4};
    Solution ob;
    print_vector(ob.asteroidCollision(v));
}

Input

[5,10,-4]

Output

[5, 10, ]