Asteroid Collision

Q: Wie hoch ist die Zeitkomplexität der Asteroidenkollision?

O(n) Laufzeit und O(n) Speicherplatz mit einem Stapel der Überlebenden, da jeder Asteroid höchstens einmal auf den Stapel gelegt und wieder entfernt wird. Das erneute Durchlaufen der Zeile nach jedem Zusammenstoß kostet O(n²) .

Q: Warum ist ein Stack die richtige Datenstruktur für Asteroid Collision?

Ein neuer Asteroid kann nur die Überlebenden erreichen, die ihm am nächsten sind, und trifft sie vom neuesten bis zum ältesten. Das ist „Last in, first out“. Was sich am Ende auf dem Stapel befindet, kann nicht mehr kollidieren und bildet daher die letzte Zeile.

Q: Kann die Asteroidenkollision mit O(1) zusätzlichem Speicherplatz gelöst werden?

Ja, wenn du die Eingabe überschreiben darfst. Verwende den Anfang des Arrays als Stack: Behalte einen Schreibindex top bei, vergleiche mit asteroids[top-1] und gib die ersten top Einträge zurück.

MittelStack

+10

Eine Reihe von Asteroiden fliegt mit derselben Geschwindigkeit entlang einer Linie. Jeder Wert in asteroids beschreibt einen Asteroiden: Sein Absolutwert gibt seine Größe an, sein Vorzeichen seine Richtung, positiv für rechts und negativ für links.

Wenn ein Asteroid, der sich nach rechts bewegt, auf einen trifft, der sich nach links bewegt, stoßen sie zusammen. Der kleinere explodiert; sind sie gleich groß, explodieren beide. Asteroiden, die sich in dieselbe Richtung bewegen, treffen niemals aufeinander. Gib die Asteroiden zurück, die nach allen Zusammenstößen übrig bleiben, in ihrer ursprünglichen Reihenfolge. Das Ergebnis kann leer sein.

Funktion

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

asteroidsinteger-array: die Asteroiden von links nach rechts, Vorzeichen für die Richtung, Absolutwert für die Größe
Gibt zurückinteger-array: die verbliebenen Asteroiden von links nach rechts, möglicherweise keine

Einschränkungen

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

Beispiele

Eingabe: asteroids = [4, 9, -6, 2, -3]
Ausgabe: [4, 9]
Erklärung: 9 trifft auf -6 und gewinnt. 2 trifft auf -3 und explodiert, und dann fliegt -3 weiter auf 9 zu und explodiert ebenfalls. Nichts anderes bewegt sich auf etwas zu, also bleiben 4 und 9 übrig.

Weiterführende Frage

Der Stack liefert die Antwort darauf, welche Asteroiden überleben. Wie könntest du außerdem für jeden Asteroiden, der explodiert, den Index des Asteroiden angeben, der ihn zerstört hat?

Lösung

Ein Asteroid, der sich nach links bewegt, kann eine lange Reihe von Asteroiden zerstören, die sich nach rechts bewegen, und jeder Zusammenstoß kann ein neues Paar freilegen, das als Nächstes zusammenstößt. Ein neuer Asteroid trifft immer zuerst auf den zuletzt überlebenden Asteroiden, daher lässt sich mit einem Stapel der Überlebenden jeder Zusammenstoß in einem Durchgang auflösen.

Behebe jeweils einen Absturz auf einmal

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Zwei Asteroiden stoßen genau dann zusammen, wenn ein Rechtsbewegender direkt links von einem Linksbewegenden steht. Finde das erste solche Paar, löse den Zusammenstoß auf und durchsuche die Reihe erneut von links. Wenn kein Paar mehr übrig ist, wird nichts mehr zusammenstoßen und die Reihe ist die Antwort.

Die Reihenfolge der Auflösung spielt keine Rolle: Zwei benachbarte, aufeinander zu bewegende Asteroiden treffen aufeinander, bevor einer von ihnen auf etwas anderes treffen kann.

Jeder Zusammenstoß erfordert einen neuen Suchlauf und das Entfernen eines Elements aus der Mitte der Reihe. Bei 9,999 kleinen Rechtsbewegenden, gefolgt von -1000, durchläuft jeder Suchlauf die Reihe, um einen Rechtsbewegenden zu zerstören: etwa 5 × 10^7 Schritte.

Algorithmus

Kopiere die Zeile, damit du Asteroiden daraus entfernen kannst.
Durchsuche sie von links nach dem ersten Index i, für den row[i] > 0 und row[i+1] < 0 gilt.
Wenn es keinen gibt, gib die Zeile zurück.
Entferne andernfalls den kleineren der beiden Asteroiden oder beide, wenn sie gleich groß sind, und durchsuche die Zeile erneut.

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]

Stapel der Überlebenden

Idee

Behalte die bisher überlebenden Asteroiden auf einem Stapel. Darauf folgt nie ein nach links fliegender Asteroid auf einen nach rechts fliegenden, denn dieses Paar wäre bereits zusammengestoßen. Es sind also einige entkommene, nach links fliegende Asteroiden, gefolgt von nach rechts fliegenden.

Ein neuer, nach rechts fliegender Asteroid fliegt von allen Asteroiden auf dem Stapel weg, also legst du ihn darauf. Ein neuer, nach links fliegender Asteroid fliegt auf die oben liegenden, nach rechts fliegenden Asteroiden zu und trifft zuerst auf den neuesten. Daher ist der oberste Asteroid der einzige, den er als Nächstes treffen kann. Im ersten Beispiel entfernt -3 die 2 vom Stapel und explodiert dann mit der 9. Der Stapel [4, 9] ist die Antwort in seiner ursprünglichen Reihenfolge.

Jeder Asteroid wird höchstens einmal auf den Stapel gelegt und höchstens einmal davon entfernt. Daher läuft der Durchlauf in O(n), selbst wenn ein nach links fliegender Asteroid eine lange Reihe abräumt.

Algorithmus

Beginne mit einem leeren Stapel der überlebenden Asteroiden.
Bewegt sich ein Asteroid nach rechts, lege ihn auf den Stapel und fahre fort.
Bewegt er sich nach links, entferne von oben nach rechts bewegte Asteroiden, solange sie kleiner sind als er.
Bewegt sich das oberste Element nun nach rechts und ist gleich groß, entferne es und verwerfe den neuen Asteroiden. Ist das oberste Element ein größerer, nach rechts bewegter Asteroid, verwerfe den neuen Asteroiden. Andernfalls lege ihn auf den Stapel.
Gib den Stapel von unten nach oben zurück.

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

Stolperfallen und Grenzfälle

Einen nach links bewegten Wert, auf den ein nach rechts bewegter folgt, als Zusammenstoß behandeln. In [-2, -7, 3, 8] bewegen sich die Gruppen voneinander weg, und alle vier überleben.
Für die Pop-Operationen if statt while verwenden. In [1, 2, 3, 4, 5, -15] zerstört der nach links bewegte Wert alle fünf nach rechts bewegten Werte und überlebt.
Den Gleichheitsfall übersehen. [6, -6] muss 6 entfernen und -6 verwerfen, sodass das Ergebnis leer bleibt.
Einen nach links bewegten Wert auf den Stack legen, der verloren hat. In [9, -6] explodiert -6 und darf nicht auf dem Stack landen; verwende ein Flag, um festzuhalten, ob er noch lebt.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität der Asteroidenkollision?

O(n) Laufzeit und O(n) Speicherplatz mit einem Stapel der Überlebenden, da jeder Asteroid höchstens einmal auf den Stapel gelegt und wieder entfernt wird. Das erneute Durchlaufen der Zeile nach jedem Zusammenstoß kostet O(n²).

Warum ist ein Stack die richtige Datenstruktur für Asteroid Collision?

Ein neuer Asteroid kann nur die Überlebenden erreichen, die ihm am nächsten sind, und trifft sie vom neuesten bis zum ältesten. Das ist „Last in, first out“. Was sich am Ende auf dem Stapel befindet, kann nicht mehr kollidieren und bildet daher die letzte Zeile.

Kann die Asteroidenkollision mit O(1) zusätzlichem Speicherplatz gelöst werden?

Ja, wenn du die Eingabe überschreiben darfst. Verwende den Anfang des Arrays als Stack: Behalte einen Schreibindex top bei, vergleiche mit asteroids[top-1] und gib die ersten top Einträge zurück.

def asteroidCollision(asteroids):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

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

Erwartete Ausgabe

[4, 9]