Asteroid Collision
Una fila di asteroidi si muove lungo una linea, tutti alla stessa velocità. Ogni valore in asteroids descrive un asteroide: il suo valore assoluto ne indica la dimensione e il segno la direzione, positivo per destra e negativo per sinistra.
Quando un asteroide che si muove verso destra incontra uno che si muove verso sinistra, si scontrano. Quello più piccolo esplode; se hanno la stessa dimensione, esplodono entrambi. Gli asteroidi che si muovono nella stessa direzione non si incontrano mai. Restituisci gli asteroidi rimasti dopo ogni scontro, nel loro ordine originale. Il risultato potrebbe essere vuoto.
Funzione
- asteroidsinteger-array
- gli asteroidi da sinistra a destra, il segno indica la direzione, il valore assoluto la dimensione
- Restituisceinteger-array
- gli asteroidi sopravvissuti da sinistra a destra, eventualmente nessuno
Vincoli
1 ≤ asteroids.length ≤ 104-1000 ≤ asteroids[i] ≤ 1000asteroids[i] ≠ 0
Esempi
- Input
- asteroids = [4, 9, -6, 2, -3]
- Output
- [4, 9]
- Spiegazione
- 9 incontra -6 e vince. 2 incontra -3 ed esplode, poi -3 vola verso 9 ed esplode anche lui. Nient'altro si muove verso qualcos'altro, quindi restano 4 e 9.
- Input
- asteroids = [6, -6]
- Output
- []
- Spiegazione
- 6 e -6 si arrestano in modo anomalo con la stessa dimensione, quindi entrambi esplodono e il risultato è vuoto.
- Input
- asteroids = [-2, -7, 3, 8]
- Output
- [-2, -7, 3, 8]
- Spiegazione
- -2 e -7 volano a sinistra e 3 e 8 volano a destra, quindi i due gruppi si allontanano. Non si verifica mai alcuna collisione e tutti e quattro gli asteroidi sopravvivono.
Per approfondire
The stack risponde a quali asteroidi sopravvivono. Come potresti anche indicare, per ogni asteroide che esplode, l'indice dell'asteroide che l'ha distrutto?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Perché avvenga uno scontro, serve un asteroide che si muove verso destra a sinistra e uno che si muove verso sinistra a destra. Un asteroide che si muove verso sinistra, senza nulla che si muova verso destra prima di esso, è al sicuro per sempre. Percorri la fila da sinistra a destra: quali asteroidi precedenti può ancora colpire un nuovo asteroide che si muove verso sinistra?
Un nuovo elemento che si muove verso sinistra colpisce per primo l'elemento più vicino che si muove verso destra e che è sopravvissuto, poi il successivo e così via, finché non esplode o non esaurisce gli elementi che si muovono verso destra. I sopravvissuti fino a quel momento si comportano come una pila: solo il più recente può essere colpito per primo.
Tieni i sopravvissuti su uno stack. Inserisci ogni elemento che si muove verso destra. Per un elemento che si muove verso sinistra, finché quello in cima è un elemento più piccolo che si muove verso destra, rimuovilo. Se quello in cima è un elemento che si muove verso destra della stessa dimensione, rimuovilo e scarta quello nuovo. Se quello in cima è più grande, scarta quello nuovo. Altrimenti, inseriscilo.
Soluzione
Un elemento che si sposta a sinistra può distruggere una lunga sequenza di elementi che si spostano a destra, e ogni collisione può esporre una nuova coppia che collide subito dopo. Un nuovo asteroide incontra sempre per primo il sopravvissuto più recente, quindi una pila di sopravvissuti risolve ogni collisione in un solo passaggio.
Risolvi un arresto anomalo alla volta
Corretto, ma non termina sui test più grandi
Intuizione
Due asteroidi si scontrano esattamente quando un asteroide che si muove verso destra si trova subito a sinistra di uno che si muove verso sinistra. Trova la prima coppia di questo tipo, risolvi lo scontro e ripeti la scansione da sinistra. Quando non rimane nessuna coppia, non ci saranno più scontri e la riga è la risposta.
L’ordine in cui risolvi gli scontri non importa: due asteroidi adiacenti che si fronteggiano si scontrano tra loro prima che uno dei due possa scontrarsi con qualcos’altro.
Ogni scontro richiede una nuova scansione e la rimozione di un elemento dal centro della riga. Con 9,999 piccoli asteroidi che si muovono verso destra seguiti da -1000, ogni scansione attraversa la riga per distruggere un asteroide che si muove verso destra: circa 5 × 10^7 passaggi.
Algoritmo
- Copia la riga per poter rimuovere gli asteroidi da essa.
- Scorri da sinistra per trovare il primo indice
iper cuirow[i] > 0erow[i+1] < 0. - Se non ce n'è nessuno, restituisci la riga.
- Altrimenti rimuovi il più piccolo dei due, o entrambi se hanno la stessa dimensione, e ripeti la scansione.
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 di sopravvissuti
Intuizione
Finora, tieni gli asteroidi sopravvissuti su una pila. Non contiene mai un asteroide diretto a destra seguito da uno diretto a sinistra, perché quella coppia si sarebbe già scontrata; contiene quindi alcuni asteroidi sopravvissuti diretti a sinistra seguiti da asteroidi diretti a destra.
Un nuovo asteroide diretto a destra si allontana da tutti quelli sulla pila, quindi lo inserisci. Un nuovo asteroide diretto a sinistra si muove verso gli asteroidi diretti a destra in cima alla pila e incontra per primo quello più recente, quindi l’elemento in cima è l’unico asteroide che può colpire subito dopo. Nel primo esempio, -3 rimuove 2 dalla pila, poi esplode contro 9 e la pila [4, 9] è la risposta nel suo ordine originale.
Ogni asteroide viene inserito al massimo una volta e rimosso al massimo una volta, quindi la passata è O(n) anche quando un asteroide diretto a sinistra elimina una lunga sequenza.
Algoritmo
- Inizia con una pila vuota di asteroidi sopravvissuti.
- Per ogni asteroide, se si muove verso destra, inseriscilo nella pila e continua.
- Se si muove verso sinistra, estrai dalla cima gli asteroidi che si muovono verso destra finché sono più piccoli di esso.
- Se ora in cima c'è un asteroide che si muove verso destra ed è della stessa dimensione, estrailo e scarta il nuovo asteroide. Se in cima c'è un asteroide più grande che si muove verso destra, scarta il nuovo asteroide. Altrimenti inseriscilo nella pila.
- Restituisci la pila dal basso verso l'alto.
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
Trappole e casi limite
- Considerare uno che si muove verso sinistra seguito da uno che si muove verso destra come uno scontro. In
[-2, -7, 3, 8]i gruppi si allontanano e tutti e quattro sopravvivono. - Usare
ifinvece diwhileper le rimozioni. In[1, 2, 3, 4, 5, -15]quello che si muove verso sinistra distrugge tutti e cinque quelli che si muovono verso destra e sopravvive. - Non gestire il caso di uguaglianza.
[6, -6]deve rimuovere 6 ed eliminare -6, lasciando un risultato vuoto. - Aggiungere alla pila uno che si muove verso sinistra, ma che ha perso. In
[9, -6], -6 esplode e non deve finire sulla pila; mantieni un flag per indicare se è ancora vivo.
Domande frequenti3
Qual è la complessità temporale della collisione tra asteroidi?
Tempo O(n) e spazio O(n) con una pila di asteroidi sopravvissuti, poiché ogni asteroide viene inserito e rimosso dalla pila al massimo una volta. Riesaminare la fila dopo ogni collisione costa O(n²).
Perché una pila è la struttura dati giusta per Asteroid Collision?
Un nuovo asteroide può raggiungere solo i superstiti più vicini a esso, e li incontra dal più recente al più vecchio. Questo è «ultimo a entrare, primo a uscire». Qualunque cosa si trovi nello stack alla fine non può più schiantarsi, quindi è l’ultima fila.
Asteroid Collision può essere risolto con spazio aggiuntivo O(1)?
Sì, se puoi sovrascrivere l’input. Usa l’inizio dell’array come pila: mantieni un indice di scrittura top, confronta con asteroids[top-1] e restituisci le prime top voci.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def asteroidCollision(asteroids):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
asteroids = [4, 9, -6, 2, -3]
Output atteso
[4, 9]