Last Stone Weight

Q: Wie hoch ist die Zeitkomplexität von Last Stone Weight?

Mit einem Max-Heap benötigen höchstens n-1 Runden mit jeweils zwei Entnahmen und einer Einfügung O(n log n) Zeit und O(n) Speicherplatz. Den gesamten Haufen in jeder Runde zu sortieren, benötigt O(n² log n) .

LeichtHeap

+10

Du hast einen Steinhaufen, und stones[i] ist das Gewicht des Steins i. Nimm in jeder Runde die beiden schwersten Steine und zerschlage sie miteinander. Wiegen sie gleich viel, werden beide zerstört. Andernfalls wird der leichtere zerstört und der schwerere auf die Differenz der beiden Gewichte verkleinert.

Schreibe lastStoneWeight, das so lange Runden spielt, bis höchstens ein Stein übrig ist, und dessen Gewicht zurückgibt, oder 0, wenn kein Stein übrig ist.

Funktion

lastStoneWeight(stones: integer-array) → integer

stonesinteger-array: die Gewichte der Steine im Haufen
Gibt zurückinteger: das Gewicht des letzten Steins oder 0, falls keiner übrig ist

Einschränkungen

1 ≤ stones.length ≤ 10⁴
1 ≤ stones[i] ≤ 1000

Beispiele

Eingabe: stones = [3, 9, 4, 6, 2]
Ausgabe: 0
Erklärung: 9 und 6 hinterlassen eine 3, dann hinterlassen 4 und 3 eine 1, dann hinterlassen 3 und 2 eine weitere 1. Die beiden 1-Steine zerstören sich gegenseitig, also ist die Antwort 0.

Eingabe: stones = [10, 4, 1]
Ausgabe: 5
Erklärung: 10 und 4 ergeben 6, und 6 und 1 ergeben 5. Ein Stein bleibt übrig und wiegt 5.

Eingabe: stones = [8]
Ausgabe: 8
Erklärung: Ein einzelner Stein hat nichts, womit er zerschmettert werden kann, daher ist sein Gewicht 8 die Antwort.

Weiterführende Frage

Die Gewichte betragen höchstens 1000. Kannst du diese Grenze nutzen, um die Aufgabe in O(n + W) Zeit abzuschließen, wobei W das größte Gewicht ist, und zwar ohne Heap?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Es gibt keine Formel, mit der du Runden überspringen kannst: Du spielst jede Runde. In jeder Runde brauchst du die beiden schwersten Steine aus einem Haufen, der sich ständig verändert, weil ein zerschlagener Stein leichter zurückkommen kann. Ein Max-Heap gibt den schwersten Stein aus und nimmt einen neuen in O(log n) auf.

Sortiere den Stapel in jeder Runde

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

Idee

Befolge die Regeln wörtlich: Sortiere den Steinhaufen, nimm die beiden schwersten Steine vom Ende und lege ihre Differenz zurück, wenn sie nicht null ist. Sortiere in jeder Runde erneut, denn die Differenz kann an beliebiger Stelle landen. Im ersten Beispiel bleiben aus 9 und 6 eine 3, die unter die 4 gehört.

In jeder Runde wird mindestens ein Stein entfernt, also gibt es bis zu n-1 Runden, in denen jeweils bis zu n Steine sortiert werden: O(n² log n). Für n = 10^4 sind das etwa 10^4 Sortiervorgänge mit jeweils bis zu 10^4 Zahlen.

Algorithmus

Kopiere die Steine in eine Liste namens pile.
Solange der Stapel mehr als einen Stein enthält, sortiere ihn in aufsteigender Reihenfolge.
Nimm die letzten beiden Steine heraus: heaviest und second.
Wenn sie unterschiedlich sind, füge heaviest - second wieder zum Stapel hinzu.
Gib den verbleibenden Stein zurück oder 0, wenn der Stapel leer ist.

def lastStoneWeight(stones):
    pile = list(stones)
    while len(pile) > 1:
        pile.sort()  # the two heaviest stones move to the end
        heaviest = pile.pop()
        second = pile.pop()
        if heaviest != second:
            pile.append(heaviest - second)
    return pile[0] if pile else 0

Max-Heap

Idee

Ein Max-Heap hält den größten Wert ganz oben. Das Entfernen des obersten Werts oder das Hinzufügen eines Werts kostet O(log n). Lege jeden Stein hinein. Entferne in jeder Runde zweimal den jeweils schwersten Stein und füge die Differenz wieder hinzu, sofern sie nicht null ist; der Heap bringt sie an die richtige Stelle. Bei [10, 4, 1] entfernst du 10 und 4 und fügst 6 hinzu, dann entfernst du 6 und 1 und fügst 5 hinzu.

Es gibt höchstens n-1 Runden mit jeweils zwei Entfernungen und einem Hinzufügen. Daher beträgt die Laufzeit O(n log n) und der Speicherbedarf O(n). In Sprachen ohne eingebauten Heap verwaltet die Lösung einen Heap in einem Array; der Elternknoten des Indexes i befindet sich bei (i-1)/2.

Algorithmus

Lege jeden Stein in einen Max-Heap.
Solange der Heap mehr als einen Stein enthält, entferne den schwersten und anschließend den zweitschwersten.
Wenn sie unterschiedlich sind, füge heaviest - second hinzu.
Gib das oberste Element des Heaps zurück oder 0, wenn er leer ist.

import heapq


def lastStoneWeight(stones):
    # heapq is a min-heap, so store negated weights: the smallest entry is the heaviest stone.
    heap = [-w for w in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        heaviest = -heapq.heappop(heap)
        second = -heapq.heappop(heap)
        if heaviest != second:
            heapq.heappush(heap, -(heaviest - second))
    return -heap[0] if heap else 0

Stolperfallen und Grenzfälle

Das oberste Element eines leeren Haufens zurückgeben. Wenn die beiden letzten Steine gleich viel wiegen, wie im ersten Beispiel, bleibt nichts übrig und die Antwort ist 0.
Aus Versehen einen Min-Heap verwenden. Pythons heapq und Javas standardmäßige PriorityQueue geben den kleinsten Wert zurück; negiere die Gewichte oder übergib einen umgekehrten Komparator.
Bei negierten Gewichten das Vorzeichen vergessen. Beide entnommenen Werte sind negativ, daher lautet der Wert, der eingefügt werden soll, -(heaviest - second).
Die Liste nur zu Beginn sortieren und dann durchgehen. Die Differenz kann kleiner sein als Steine, die du noch nicht angefasst hast, daher ist die Reihenfolge nach der ersten Runde veraltet.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Last Stone Weight?

Mit einem Max-Heap benötigen höchstens n-1 Runden mit jeweils zwei Entnahmen und einer Einfügung O(n log n) Zeit und O(n) Speicherplatz. Den gesamten Haufen in jeder Runde zu sortieren, benötigt O(n² log n).

Warum einen Heap für LastStoneWeight statt einer sortierten Liste verwenden?

Eine sortierte Liste liefert sofort die beiden schwersten Steine, aber das Wiedereinordnen der Differenz verschiebt bis zu n Einträge, insgesamt O(n²) über alle Runden. Ein Heap beantwortet nur die Frage „Was ist das größte Element?“ und nimmt einen neuen Wert an, beides in O(log n) – genau das, was die Simulation verlangt.

Ändert die Reihenfolge, in der Steine mit gleichem Gewicht zerschlagen werden, das Ergebnis?

Nein. Wenn mehrere Steine das höchste Gewicht haben, wiegen die beiden, die du auswählst, in jedem Fall gleich viel, sodass der Steinhaufen nach der Runde dieselben Gewichte aufweist. Die Antwort hängt nur von den Gewichten ab.

def lastStoneWeight(stones):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

stones = [3, 9, 4, 6, 2]

Erwartete Ausgabe