Asteroid Collision

Q: Quelle est la complexité temporelle de la collision d’astéroïdes ?

Temps O(n) et espace O(n) avec une pile d’astéroïdes survivants, puisque chaque astéroïde est empilé et dépilé au plus une fois. Reparcourir la ligne après chaque collision coûte O(n²) .

Q: Pourquoi une pile est-elle la structure de données adaptée à la collision d’astéroïdes ?

Un nouvel astéroïde ne peut atteindre que les survivants les plus proches de lui, et il les rencontre du plus récent au plus ancien. C’est le dernier entré, premier sorti. Tout ce qui se trouve sur la pile à la fin ne peut plus entrer en collision : c’est donc la rangée finale.

Q: Peut-on résoudre Asteroid Collision avec un espace supplémentaire en O(1) ?

Oui, si tu peux écraser l’entrée. Utilise le début du tableau comme pile : conserve un indice d’écriture top , compare avec asteroids[top-1] , et renvoie les top premières entrées.

MoyenPile

+10

Une rangée d’astéroïdes se déplace le long d’une ligne, tous à la même vitesse. Chaque valeur de asteroids décrit un astéroïde : sa valeur absolue correspond à sa taille, et son signe indique sa direction, positive vers la droite et négative vers la gauche.

Lorsqu’un astéroïde se déplaçant vers la droite en rencontre un autre qui se déplace vers la gauche, ils entrent en collision. Le plus petit explose ; s’ils ont la même taille, ils explosent tous les deux. Les astéroïdes qui se déplacent dans la même direction ne se rencontrent jamais. Renvoie les astéroïdes restants après toutes les collisions, dans leur ordre d’origine. Le résultat peut être vide.

Fonction

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

asteroidsinteger-array: les astéroïdes de gauche à droite, le signe pour la direction, la valeur absolue pour la taille
Renvoieinteger-array: les astéroïdes restants de gauche à droite, éventuellement aucun

Contraintes

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

Exemples

Entrée: asteroids = [4, 9, -6, 2, -3]
Sortie: [4, 9]
Explication: 9 rencontre -6 et gagne. 2 rencontre -3 et explose, puis -3 fonce vers 9 et explose aussi. Rien d’autre ne se dirige vers quoi que ce soit, donc 4 et 9 restent.

Pour aller plus loin

La pile indique quels astéroïdes survivent. Comment pourriez-vous également indiquer, pour chaque astéroïde qui explose, l’indice de l’astéroïde qui l’a détruit ?

Solution

Un astéroïde se déplaçant vers la gauche peut détruire une longue série d’astéroïdes se déplaçant vers la droite, et chaque collision peut révéler une nouvelle paire qui entrera ensuite en collision. Un nouvel astéroïde rencontre toujours d’abord le survivant le plus récent, donc une pile de survivants permet de résoudre toutes les collisions en un seul passage.

Résolvez un plantage à la fois

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Deux astéroïdes entrent en collision exactement lorsqu’un astéroïde se déplaçant vers la droite se trouve juste à gauche d’un astéroïde se déplaçant vers la gauche. Trouve la première paire de ce type, résous la collision, puis recommence le balayage depuis la gauche. Lorsqu’il ne reste aucune paire, plus rien ne pourra entrer en collision et la rangée est la réponse.

L’ordre de résolution n’a pas d’importance : deux astéroïdes adjacents qui se font face se rencontrent avant que l’un ou l’autre puisse en rencontrer un autre.

Chaque collision nécessite un nouveau balayage et une suppression au milieu de la rangée. Avec 9 999 petits astéroïdes se déplaçant vers la droite, suivis de -1000, chaque balayage parcourt la rangée pour détruire un astéroïde se déplaçant vers la droite : environ 5 × 10^7 étapes.

Algorithme

Copie la ligne pour pouvoir en retirer les astéroïdes.
Parcours la ligne de gauche à droite pour trouver le premier indice i tel que row[i] > 0 et row[i+1] < 0.
S’il n’y en a aucun, retourne la ligne.
Sinon, retire le plus petit des deux, ou les deux si leurs tailles sont égales, puis recommence le parcours.

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]

Pile de survivants

Intuition

Garde les survivants jusqu’ici dans une pile. Elle ne contient jamais un astéroïde allant vers la droite suivi d’un autre allant vers la gauche, car cette paire serait déjà entrée en collision ; elle contient donc des astéroïdes allant vers la gauche qui se sont échappés, suivis d’astéroïdes allant vers la droite.

Un nouvel astéroïde allant vers la droite s’éloigne de tout ce qui se trouve dans la pile, alors tu l’empiles. Un nouvel astéroïde allant vers la gauche fonce vers les astéroïdes allant vers la droite au sommet et rencontre d’abord le plus récent ; le sommet est donc le seul astéroïde qu’il peut percuter ensuite. Dans le premier exemple, -3 dépile 2, puis explose contre 9, et la pile [4, 9] est la réponse dans son ordre d’origine.

Chaque astéroïde est empilé au plus une fois et dépilé au plus une fois, donc le parcours est en O(n), même lorsqu’un astéroïde allant vers la gauche en élimine une longue série.

Algorithme

Commencez avec une pile de survivants vide.
Pour chaque astéroïde, s’il se déplace vers la droite, empilez-le et continuez.
S’il se déplace vers la gauche, dépilez les astéroïdes se déplaçant vers la droite au sommet tant qu’ils sont plus petits que lui.
Si le sommet est maintenant un astéroïde se déplaçant vers la droite de même taille, dépilez-le et éliminez le nouvel astéroïde. Si le sommet est un astéroïde plus gros se déplaçant vers la droite, éliminez le nouvel astéroïde. Sinon, empilez-le.
Renvoie la pile du bas vers le haut.

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

Pièges et cas limites

Traiter un objet se déplaçant vers la gauche suivi d’un objet se déplaçant vers la droite comme une collision. Dans [-2, -7, 3, 8], les groupes s’éloignent l’un de l’autre et les quatre survivent.
Utiliser if au lieu de while pour les dépilements. Dans [1, 2, 3, 4, 5, -15], l’objet se déplaçant vers la gauche détruit les cinq objets se déplaçant vers la droite et survit.
Oublier le cas d’égalité. [6, -6] doit dépiler 6 et supprimer -6, ce qui laisse un résultat vide.
Empiler un objet se déplaçant vers la gauche qui a perdu. Dans [9, -6], -6 explose et ne doit pas être ajouté à la pile ; garde un indicateur pour savoir s’il est encore en vie.

Questions fréquentes3

Quelle est la complexité temporelle de la collision d’astéroïdes ?

Temps O(n) et espace O(n) avec une pile d’astéroïdes survivants, puisque chaque astéroïde est empilé et dépilé au plus une fois. Reparcourir la ligne après chaque collision coûte O(n²).

Pourquoi une pile est-elle la structure de données adaptée à la collision d’astéroïdes ?

Un nouvel astéroïde ne peut atteindre que les survivants les plus proches de lui, et il les rencontre du plus récent au plus ancien. C’est le dernier entré, premier sorti. Tout ce qui se trouve sur la pile à la fin ne peut plus entrer en collision : c’est donc la rangée finale.

Peut-on résoudre Asteroid Collision avec un espace supplémentaire en O(1) ?

Oui, si tu peux écraser l’entrée. Utilise le début du tableau comme pile : conserve un indice d’écriture top, compare avec asteroids[top-1], et renvoie les top premières entrées.

def asteroidCollision(asteroids):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

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

Résultat attendu

[4, 9]