Coliziunea de asteroizi și logica din spatele unui algoritm elegant în C++
În lumea programării algoritmice, există probleme care par simple la prima vedere, dar ascund o logică fascinantă. Una dintre acestea este LeetCode 735 – Asteroid Collision, o provocare care combină gândirea analitică, structurile de date și imaginația. În esență, problema ne cere să simulăm o serie de coliziuni între asteroizi ce se deplasează în spațiu — iar scopul este să determinăm care dintre ei supraviețuiește.
🪐 Enunțul problemei
Ni se oferă un vector de numere întregi care reprezintă asteroizi în mișcare:
- semnul pozitiv (+) indică faptul că asteroidul se deplasează spre dreapta;
- semnul negativ (−) înseamnă că merge spre stânga;
- valoarea absolută indică dimensiunea și masa acestuia.
Atunci când doi asteroizi se întâlnesc, are loc o coliziune. Regula este simplă:
- dacă unul este mai mare, cel mic dispare;
- dacă sunt egali, amândoi sunt distruși;
- iar dacă se deplasează în aceeași direcție, nu se ciocnesc.
Scopul final este să returnăm configurația sistemului după toate coliziunile.
⚙️ Cum abordăm problema
Cea mai intuitivă soluție ar fi să simulăm fiecare ciocnire pas cu pas, dar asta ar fi ineficient. Aici intervine una dintre cele mai elegante structuri de date: stiva (stack).
Logica este următoarea:
- Parcurgem vectorul de asteroizi de la stânga la dreapta.
- Pentru fiecare asteroid, analizăm dacă el se poate ciocni cu cel aflat în vârful stivei.
- Dacă există o coliziune (un asteroid merge la dreapta, altul la stânga), verificăm:
- care are valoarea absolută mai mare;
- pe cine păstrăm în stivă;
- dacă sunt egali, eliminăm amândoi.
- Continuăm până nu mai pot apărea coliziuni, apoi returnăm stiva ca rezultat final.
Prin această metodă, simulăm fizica problemei cu complexitate O(n), o îmbunătățire semnificativă față de o abordare naivă.
De ce merită să o înveți
Problema Asteroid Collision nu este doar un exercițiu tehnic; ea te învață cum să gândești în termeni de simulare logică și cum să aplici o structură de date simplă pentru a modela fenomene complexe.
Aceeași idee se aplică în:
- simulări fizice,
- sisteme de procesare în timp real,
- sau chiar analiza tranzacțiilor și a fluxurilor de date.
🌟 Vrei să vezi explicația completă în acțiune?
Pe canalul nostru YouTube – LAN Academy, am publicat videoclipul
👉 Asteroid Collision in C++ | LeetCode 735 Explained Clearly
Acolo vei găsi explicația vizuală, pas cu pas, cu cod clar și exemple animate.
Fie că te pregătești pentru interviuri tehnice sau vrei să înțelegi mai profund cum gândesc profesioniștii în algoritmică, acest clip este punctul perfect de pornire.
🧭 Despre LAN Academy
LAN Academy este un proiect educațional dedicat învățării logice și clare a programării, matematicii și algoritmicii.
Scopul nostru este simplu: să facem din învățare o experiență inteligentă, modernă și accesibilă.