Minimum Cost of Ropes

Q: Wie hoch ist die Zeitkomplexität der minimalen Kosten für Seile?

O(n log n) Zeit und O(n) Speicherplatz mit einem Min-Heap: n-1 Verknüpfungen, jeweils drei Heap-Operationen mit O(log n) . Wird stattdessen der ganze Haufen nach den beiden kürzesten Seilen durchsucht, ergibt sich O(n²) .

LeichtHeap Greedy

+10

Du hast einige Seile, und ropes[i] ist die Länge des Seils i. Du kannst beliebige zwei Seile zu einem Seil verbinden, dessen Länge der Summe der beiden entspricht; diese Verbindung kostet ebenfalls so viel. Du verbindest die Seile so lange, bis nur noch ein Seil übrig ist.

Schreibe eine Funktion namens minCostRopes, die die geringsten Gesamtkosten für das Verbinden aller Seile zu einem Seil zurückgibt, oder 0, wenn es von Anfang an nur ein Seil gibt.

Funktion

minCostRopes(ropes: integer-array) → integer

ropesinteger-array: die Länge jedes Seils
Gibt zurückinteger: die geringsten Gesamtkosten, um alle Seile zu einem einzigen zu verbinden

Einschränkungen

1 ≤ ropes.length ≤ 10⁴
1 ≤ ropes[i] ≤ 100
Die Antwort passt in eine vorzeichenbehaftete 32-Bit-Ganzzahl.

Beispiele

Eingabe: ropes = [5, 2, 8, 3]
Ausgabe: 33
Erklärung: Verbinde 2 und 3 zu 5, die beiden Seile der Länge 5 zu 10, dann 8 und 10 zu 18. Die Gesamtsumme ist 5 + 10 + 18 = 33.

Eingabe: ropes = [1, 1, 1, 1]
Ausgabe: 8
Erklärung: Fasse die 1er paarweise für jeweils 2 zusammen, dann die beiden Seile der Länge 2 für 4: insgesamt 8. Jedes 1 zu einem wachsenden Seil hinzuzufügen, würde 2 + 3 + 4 = 9 kosten.

Weiterführende Frage

Angenommen, eine Verbindung kann bis zu drei Seile zusammenfügen und kostet so viel wie ihre Gesamtlänge. Wie ändert sich die Greedy-Regel, wenn die Anzahl der Seile nicht ohne Rest aufgeht?

Lösung

Bei jeder Verbindung wird die gesamte Länge beider Stücke berechnet, daher wird ein früh verbundenes Seil bei jeder späteren Verbindung, an der es beteiligt ist, erneut berechnet. Halte lange Seile aus den frühen Verbindungen heraus: Verbinde in jeder Runde die beiden kürzesten Seile. Ein Min-Heap findet diese beiden in O(log n).

Durchsuche jede Runde nach den zwei kürzesten

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

Idee

Scanne in jeder Runde den Haufen nach dem kürzesten Seil und nimm es heraus, scanne erneut nach dem nächstkürzesten und lege ihre Verbindung zurück.

Warum die zwei kürzesten: Zeichne die Verbindungen als Baum, mit den Seilen als Blättern. Die Länge eines Seils wird für jede Verbindung darüber einmal bezahlt, also entsprechend seiner Tiefe. Die tiefste Ebene hat zwei Blätter nebeneinander, und wenn man die zwei kürzesten Seile dorthin verschiebt, steigen die Kosten nie. Daher verbindet irgendein optimaler Plan zuerst die zwei kürzesten, und das Argument wiederholt sich mit dem kleineren Haufen.

Es gibt n-1 Runden mit jeweils zwei vollständigen Durchläufen: O(n²), etwa 10^8 Vergleiche für 10^4 Seile.

Algorithmus

Kopiere die Seile in eine Arbeitsliste, pile, und setze total auf 0.
Wiederhole, bis ein Seil übrig ist: Finde das kürzeste Seil und entferne es, indem du das letzte Seil an seine Stelle verschiebst.
Führe dasselbe erneut aus, um das nächstkürzeste Seil zu erhalten.
Addiere die Summe der beiden zu total und füge der Liste ein Seil dieser Länge hinzu.
Gib total zurück.

def minCostRopes(ropes):
    pile = list(ropes)

    def take_shortest():
        k = 0
        for i in range(1, len(pile)):
            if pile[i] < pile[k]:
                k = i
        pile[k], pile[-1] = pile[-1], pile[k]  # move it to the end, then remove it
        return pile.pop()

    total = 0
    while len(pile) > 1:
        joined = take_shortest() + take_shortest()
        total += joined
        pile.append(joined)
    return total

Min-Heap

Idee

Ein Min-Heap hält das kürzeste Seil an seiner Wurzel. Das Entfernen der Wurzel oder das Einfügen eines Seils kostet O(log n). Eine Runde besteht aus zwei Entnahmen, bei denen du die beiden kürzesten Seile erhältst, und dem Einfügen des zusammengefügten Seils.

n Seile benötigen n-1 Zusammenfügungen mit jeweils drei Heap-Operationen, also beträgt die Laufzeit O(n log n): etwa 4 × 10^5 Schritte für 10^4 Seile. Der Heap enthält nie mehr als n Seile.

Algorithmus

Lege jede Seillänge in einen Min-Heap und setze total = 0.
Wiederhole den Vorgang, bis ein Seil übrig ist: Entnimm die beiden kürzesten.
Addiere ihre Summe zu total und lege die Summe zurück in den Heap.
Gib total zurück; bei nur einem Seil bleibt der Wert 0.

import heapq


def minCostRopes(ropes):
    heap = list(ropes)
    heapq.heapify(heap)  # a min-heap: heap[0] is the shortest rope
    total = 0
    while len(heap) > 1:
        joined = heapq.heappop(heap) + heapq.heappop(heap)
        total += joined
        heapq.heappush(heap, joined)
    return total

Stolperfallen und Grenzfälle

Einmal sortieren und jedes Seil zu einem einzigen fortlaufenden Seil hinzufügen. Das fortlaufende Seil kann länger werden als Seile, die du noch nicht verwendet hast: Für [2, 3, 4, 4] kostet es 5 + 9 + 13 = 27, während das Verbinden der beiden kürzesten Seile 5 + 8 + 13 = 26 kostet.
Das verbundene Seil weglassen. Seine Länge kommt zurück in den Haufen und wird bei einem späteren Verbinden erneut berechnet.
Die Länge des endgültigen Seils zurückgeben. Für [5, 2, 8, 3] ist das letzte Seil 18 lang, aber die Kosten betragen 33.
Aus Versehen einen Max-Heap verwenden. C++ priority_queue und Rusts BinaryHeap geben den größten Wert aus, sofern du die Reihenfolge nicht umkehrst.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität der minimalen Kosten für Seile?

O(n log n) Zeit und O(n) Speicherplatz mit einem Min-Heap: n-1 Verknüpfungen, jeweils drei Heap-Operationen mit O(log n). Wird stattdessen der ganze Haufen nach den beiden kürzesten Seilen durchsucht, ergibt sich O(n²).

Ist Minimum Cost of Ropes dasselbe wie Huffman-Codierung?

Ja, es ist derselbe Algorithmus. Die Huffman-Codierung erstellt einen Präfixcode, indem sie immer wieder die zwei am seltensten vorkommenden Symbole zusammenführt. Dabei minimiert sie die Summe aus jeder Häufigkeit multipliziert mit ihrer Tiefe im Baum. Hier entsprechen die Seile den Symbolen und ihre Längen den Häufigkeiten, sodass die Gesamtkosten dieselbe Summe ergeben.

Kann man Minimum Cost of Ropes ohne einen Heap lösen?

Ja, mit zwei Warteschlangen. Sortiere die Seile in einer Warteschlange und füge jedes verbundene Seil hinten in eine zweite ein. Verbundene Seile kommen in nicht absteigender Reihenfolge heraus, sodass das kürzeste verbleibende Seil vorne in einer der Warteschlangen liegt. Jede Runde dauert dann O(1), und bei Längen bis zu 100 sorgt eine Zählsortierung dafür, dass die Laufzeit O(n) beträgt.

def minCostRopes(ropes):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

ropes = [5, 2, 8, 3]

Erwartete Ausgabe