Last Stone Weight

LeichtHeap

+10

Du hast einen Haufen Steine, und stones[i] ist das Gewicht des Steins i. Nimm in jeder Runde die beiden schwersten Steine und schlage sie gegeneinander. Wenn sie gleich schwer sind, werden beide zerstört. Andernfalls wird der leichtere zerstört und der schwerere auf die Differenz der beiden Gewichte reduziert.

Schreibe eine Funktion namens lastStoneWeight, die so lange Runden spielt, bis höchstens ein Stein übrig ist, und das Gewicht dieses Steins 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, wenn 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 ergeben eine 3, dann ergeben 4 und 3 eine 1, dann ergeben 3 und 2 eine weitere 1. Die beiden Steine mit dem Gewicht 1 zerstören sich gegenseitig, sodass nichts übrig bleibt und die Antwort 0 lautet.

Eingabe: stones = [10, 4, 1]
Ausgabe: 5
Erklärung: 10 und 4 ergeben eine 6, und 6 und 1 ergeben eine 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.

+13 versteckte Tests beim Einreichen

Weiterführende Frage

Die Gewichte betragen höchstens 1000. Kannst du diese Obergrenze 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

Die Regeln sind eine Simulation: Es gibt keine Formel, mit der du Runden überspringen kannst, also spielst du jede Runde. Für jede Runde werden die beiden schwersten Steine eines Haufens benötigt, der sich ständig verändert, denn ein zerschmetterter Stein kann leichter zurückkommen. Wenn du in jeder Runde erneut sortierst, findest du sie, aber das kostet O(n log n) pro Runde. Ein Max-Heap gibt den schwersten Stein aus und nimmt in O(log n) einen neuen zurück.

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 so, dass die beiden schwersten Steine am Ende liegen, nimm sie heraus und lege bei unterschiedlichem Gewicht die Differenz zurück. Wiederhole das, bis der Haufen einen oder keinen Stein mehr enthält.

Die Differenz kann an beliebiger Stelle in der Reihenfolge landen. Im ersten Beispiel ergeben 9 und 6 eine 3, die unter die 4 gehört. Deshalb sortierst du vor der nächsten Runde erneut, um die nun beiden schwersten Steine zu finden.

In jeder Runde wird mindestens ein Stein entfernt, also gibt es bis zu n-1 Runden, die jeweils eine Sortierung von bis zu n Steinen umfassen: O(n² log n). Bei n = 10^4 sind das etwa 10^4 Sortierungen von jeweils bis zu 10^4 Zahlen, also mindestens 5 × 10^7 Schritte, selbst wenn die Sortierung erkennt, dass die Liste fast sortiert ist, und ein Mehrfaches davon, wenn sie das nicht tut. Das ist für die größten Tests zu langsam, während der untenstehende Heap nur einige Hunderttausend Schritte benötigt.

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 beiden letzten Steine heraus: heaviest und second.
Wenn sie unterschiedlich sind, lege heaviest - second zurück auf den Stapel.
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

In jeder Runde brauchst du nur die größten Steine, niemals die vollständige Reihenfolge. Dafür wird ein Max-Heap verwendet: Er hält den größten Wert an der Spitze, und das Entfernen des obersten Elements oder das Hinzufügen eines Werts kostet O(log n).

Lege jeden Stein in den Heap. Entferne in jeder Runde zweimal das oberste Element, um die beiden schwersten Steine zu erhalten. Sind sie unterschiedlich, lege die Differenz zurück; der Heap bringt sie selbst an die richtige Stelle. Bei [10, 4, 1] entfernst du 10 und 4 und legst 6 hinein, dann entfernst du 6 und 1 und legst 5 hinein, sodass der Heap nur noch 5 enthält.

Es gibt höchstens n-1 Runden, jede mit zwei Entfernungen und höchstens einem Einfügen. Daher beträgt die Laufzeit O(n log n), und der Heap benötigt O(n) Speicherplatz. Einige Sprachen bieten einen Heap: Python's heapq ist ein Min-Heap und speichert daher negierte Gewichte; Java hat PriorityQueue, C++ priority_queue, Go container/heap, Rust BinaryHeap und PHP SplMaxHeap. In den anderen Sprachen implementiert die Lösung ihren eigenen Heap in einem Array: Der Elternknoten von Index i befindet sich bei (i-1)/2, und ein neuer Wert steigt auf, solange er größer als sein Elternknoten ist.

Algorithmus

Lege jeden Stein in einen Max-Heap.
Solange der Heap mehr als einen Stein enthält, entnimm den schwersten und dann 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

Die Simulation ist kurz, daher verstecken sich die Fehler an den Enden und im Heap selbst.

Das oberste Element eines leeren Stapels zurückgeben. Wenn die letzten beiden Steine gleich schwer sind, bleibt nichts übrig und die Antwort ist 0.
Aus Versehen einen Min-Heap verwenden. Pythons heapq und Javas Standard-PriorityQueue geben den kleinsten Wert zurück; negiere die Gewichte oder übergib einen umgekehrten Comparator.
Vergessen, zurückzunegieren. Bei heapq sind beide entnommenen Werte negativ, also ist die Differenz, die du einfügst, -(heaviest - second).
Einmal am Anfang sortieren und die Liste durchlaufen. Die Differenz zweier Steine kann leichter sein als Steine, die du noch nicht angefasst hast, sodass eine feste Reihenfolge schon nach der ersten Runde nicht mehr aktuell ist.

Häufige Fragen4

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

Mit einem Max-Heap benötigen der Aufbau des Heaps und das Spielen von höchstens n-1 Runden mit jeweils zwei Entnahmen und einem Einfügen O(n log n) Zeit und O(n) Speicherplatz. Den gesamten Steinhaufen stattdessen in jeder Runde zu sortieren, benötigt O(n² log n).

Warum einen Heap für Last Stone Weight verwenden?

In jeder Runde werden die zwei größten Werte einer Sammlung benötigt, die sich nach jeder Runde ändert. Ein Heap beantwortet die Frage „Was ist der größte Wert?“ und nimmt einen neuen Wert in O(log n) auf, ohne die gesamte Sammlung sortiert zu halten. Genau diese Arbeit wiederholt die Simulation.

Kann Last Stone Weight ohne einen Heap gelöst werden?

Ja, denn die Gewichte sind klein. Zähle, wie viele Steine jedes Gewicht von 1 bis 1000 haben, und gehe vom schwersten Gewicht abwärts. Gleich schwere Steine heben sich paarweise auf, und ein neuer Stein ist immer leichter als der schwerste Stein, aus dem er gebildet wurde. Daher geht es nur abwärts. Das benötigt für das größte Gewicht W eine Laufzeit von O(n + W).

Ändert sich das Ergebnis, wenn man gleich schwere Steine in einer anderen Reihenfolge zerschlägt?

Nein. Wenn mehrere Steine das höchste Gewicht haben, wiegen die beiden, die du auswählst, in jedem Fall gleich viel, sodass der Haufen nach der Runde dieselben Gewichte enthält. Die Antwort hängt nur von den Gewichten ab. Deshalb gibt jede korrekte Lösung dieselbe Zahl zurück.

Python

def lastStoneWeight(stones):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet