LeetCode: Asteroid collision

En este post te voy a explicar como resolver el problema: Asteroid Collision de la plataforma LeetCode.

¿Cómo se resuelve el ejercicio?.

Este ejercicio: Asteroid collision, lo resolví con una pila.  En el problema vas a recibir un arreglo con una serie de números enteros. El valor del entero, representa el tamaño, y el signo su dirección.

Dado el siguiente arreglo [10,-5], el número diez se moverá a la derecha (→10) y el menos cinco a la izquierda -5←, esto generará una colisión, donde el diez al ser más grande sobrevivirá. De la combinación de signos y valores obtienes los siguientes escenarios:

  1. [→10, -5←]  = [10]
  2. [-10←, →5]  = [-10, 5]
  3. [-10←,-5←] = [-10, -5]
  4. [→10,→5].    = [10, 5]
  5. [→5,-10←]   = [-10]
  6. [→10,-10←] = []

Para recorrer el arreglo puedes usar una pila, en ella acumulas los valores que no causan colisión, cada asteroide nuevo puede generar una reacción en cadena o no afectar en nada. Por ejemplo:

Dado el siguiente arreglo: [1,2,3,-5]

  1. Stack: [1],       Array [2,3,-5]
  2. Stack: [1,2],    Array [3,-5]
  3. Stack: [1,2,3], Array [-5]
  4. Stack: [1,2],    Array [-5]
  5. Stack: [1],       Array [-5]
  6. Stack: [-5],    Array []

Solución:

 

Gustavo Sánchez