Asteroid Collision

Q: ¿Cuál es la complejidad temporal de la colisión de asteroides?

Tiempo O(n) y espacio O(n) con una pila de asteroides supervivientes, ya que cada asteroide se apila y desapila como máximo una vez. Volver a recorrer la fila después de cada choque cuesta O(n²) .

Q: ¿Por qué una pila es la estructura de datos adecuada para Asteroid Collision?

Un nuevo asteroide solo puede alcanzar a los supervivientes más cercanos a él, y se encuentra con ellos del más reciente al más antiguo. Es decir, el último en entrar es el primero en salir. Lo que quede en la pila al final ya no puede chocar, así que es la fila final.

Q: ¿Se puede resolver la colisión de asteroides en O(1) espacio adicional?

Sí, si puedes sobrescribir la entrada. Usa el principio del arreglo como pila: mantén un índice de escritura top , compara con asteroids[top-1] y devuelve las primeras top entradas.

MedioPila

+10

Una fila de asteroides avanza a lo largo de una línea, todos a la misma velocidad. Cada valor de asteroids describe un asteroide: su valor absoluto es su tamaño y su signo indica su dirección: positivo para la derecha y negativo para la izquierda.

Cuando un asteroide que se mueve hacia la derecha se encuentra con uno que se mueve hacia la izquierda, chocan. El más pequeño explota; si tienen el mismo tamaño, ambos explotan. Los asteroides que se mueven en la misma dirección nunca se encuentran. Devuelve los asteroides que quedan después de cada choque, en su orden original. El resultado puede estar vacío.

Función

asteroidCollision(asteroids: integer-array) → integer-array

asteroidsinteger-array: los asteroides de izquierda a derecha, el signo indica la dirección y el valor absoluto, el tamaño
Devuelveinteger-array: los asteroides supervivientes de izquierda a derecha, posiblemente ninguno

Restricciones

1 ≤ asteroids.length ≤ 10⁴
-1000 ≤ asteroids[i] ≤ 1000
asteroids[i] ≠ 0

Ejemplos

Entrada: asteroids = [4, 9, -6, 2, -3]
Salida: [4, 9]
Explicación: 9 se encuentra con -6 y gana. 2 se encuentra con -3 y explota, y después -3 sigue volando hasta 9 y también explota. Nada más se mueve hacia nada, así que quedan 4 y 9.

Para ir más allá

La pila indica qué asteroides sobreviven. ¿Cómo podrías informar también, por cada asteroide que explota, el índice del asteroide que lo destruyó?

Solución

Un asteroide que se mueve a la izquierda puede destruir una larga secuencia de asteroides que se mueven a la derecha, y cada choque puede exponer un nuevo par que chocará después. Un asteroide nuevo siempre se encuentra primero con el superviviente más reciente, así que una pila de supervivientes resuelve cada choque en una sola pasada.

Resuelve un fallo a la vez

Correcto, pero no termina con las pruebas más grandes

Intuición

Dos asteroides chocan exactamente cuando un astroide que se mueve hacia la derecha está justo a la izquierda de uno que se mueve hacia la izquierda. Encuentra el primer par de este tipo, resuélvelo y vuelve a recorrer la fila desde la izquierda. Cuando ya no quede ningún par, nada volverá a chocar y la fila será la respuesta.

El orden en que se resuelven los choques no importa: dos asteroides adyacentes que se mueven uno hacia el otro se encuentran antes de que cualquiera de ellos pueda encontrarse con otro.

Cada choque requiere un nuevo recorrido y una eliminación del medio de la fila. Con 9,999 asteroides pequeños que se mueven hacia la derecha, seguidos de -1000, cada recorrido avanza por la fila para destruir un asteroide que se mueve hacia la derecha: unos 5 × 10^7 pasos.

Algoritmo

Copia la fila para poder eliminar asteroides de ella.
Busca desde la izquierda el primer índice i donde row[i] > 0 y row[i+1] < 0.
Si no hay ninguno, devuelve la fila.
De lo contrario, elimina el menor de los dos, o ambos si sus tamaños son iguales, y vuelve a buscar.

def asteroidCollision(asteroids):
    row = list(asteroids)
    while True:
        # A crash happens where a right-mover is directly followed by a left-mover.
        hit = -1
        for i in range(len(row) - 1):
            if row[i] > 0 and row[i + 1] < 0:
                hit = i
                break
        if hit == -1:
            return row
        right, left = row[hit], -row[hit + 1]
        if right > left:
            del row[hit + 1]
        elif right < left:
            del row[hit]
        else:
            del row[hit:hit + 2]

Pila de supervivientes

Intuición

Mantén a los supervivientes hasta el momento en una pila. Nunca contiene un asteroide que se mueve hacia la derecha seguido de uno que se mueve hacia la izquierda, ya que esa pareja ya habría chocado; por lo tanto, contiene algunos asteroides que se mueven hacia la izquierda y han escapado, seguidos de asteroides que se mueven hacia la derecha.

Un nuevo asteroide que se mueve hacia la derecha se aleja de todo lo que hay en la pila, así que lo apilas. Un nuevo asteroide que se mueve hacia la izquierda vuela hacia los asteroides que se mueven hacia la derecha en la parte superior y se encuentra primero con el más reciente, así que el de la cima es el único asteroide con el que puede chocar a continuación. En el primer ejemplo, -3 saca 2 de la pila y luego explota al chocar contra 9; la pila [4, 9] es la respuesta en su orden original.

Cada asteroide se apila como máximo una vez y se saca de la pila como máximo una vez, por lo que el recorrido es O(n), incluso cuando un asteroide que se mueve hacia la izquierda despeja una larga secuencia.

Algoritmo

Empieza con una pila vacía de asteroides supervivientes.
Para cada asteroide, si se mueve hacia la derecha, apílalo y continúa.
Si se mueve hacia la izquierda, desapila los asteroides que se mueven hacia la derecha desde la cima mientras sean más pequeños que él.
Si ahora el de la cima se mueve hacia la derecha y tiene el mismo tamaño, desapílalo y descarta el asteroide nuevo. Si el de la cima es un asteroide más grande que se mueve hacia la derecha, descarta el asteroide nuevo. De lo contrario, apílalo.
Devuelve la pila desde la base hasta la cima.

def asteroidCollision(asteroids):
    survivors = []  # the row so far, after every crash it caused
    for rock in asteroids:
        alive = True
        # Only a left-mover can hit something: a right-mover on top of the stack.
        while alive and rock < 0 and survivors and survivors[-1] > 0:
            top = survivors[-1]
            if top < -rock:
                survivors.pop()        # the right-mover is smaller and explodes
            elif top == -rock:
                survivors.pop()        # same size: both explode
                alive = False
            else:
                alive = False          # the right-mover is bigger: the new one explodes
        if alive:
            survivors.append(rock)
    return survivors

Errores comunes y casos límite

Tratar un objeto que se mueve hacia la izquierda seguido de uno que se mueve hacia la derecha como una colisión. En [-2, -7, 3, 8], los grupos se alejan y los cuatro sobreviven.
Usar if en lugar de while para las extracciones. En [1, 2, 3, 4, 5, -15], el objeto que se mueve hacia la izquierda destruye a los cinco objetos que se mueven hacia la derecha y sobrevive.
Pasar por alto el caso de igualdad. [6, -6] debe extraer 6 y descartar -6, dejando un resultado vacío.
Apilar un objeto que se mueve hacia la izquierda y que perdió. En [9, -6], -6 explota y no debe quedar en la pila; mantén una bandera que indique si aún está vivo.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de la colisión de asteroides?

Tiempo O(n) y espacio O(n) con una pila de asteroides supervivientes, ya que cada asteroide se apila y desapila como máximo una vez. Volver a recorrer la fila después de cada choque cuesta O(n²).

¿Por qué una pila es la estructura de datos adecuada para Asteroid Collision?

Un nuevo asteroide solo puede alcanzar a los supervivientes más cercanos a él, y se encuentra con ellos del más reciente al más antiguo. Es decir, el último en entrar es el primero en salir. Lo que quede en la pila al final ya no puede chocar, así que es la fila final.

¿Se puede resolver la colisión de asteroides en O(1) espacio adicional?

Sí, si puedes sobrescribir la entrada. Usa el principio del arreglo como pila: mantén un índice de escritura top, compara con asteroids[top-1] y devuelve las primeras top entradas.

def asteroidCollision(asteroids):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

asteroids = [4, 9, -6, 2, -3]

Salida Esperada

[4, 9]