Reverse Nodes in k-Group

Q: Wie hoch sind die Zeit- und Speicherkomplexität beim Umkehren von Knoten in k-Gruppen?

Für eine Liste mit L Knoten läuft es in O(L)-Zeit: Jeder Knoten wird einmal gezählt und einmal umgedreht. Die In-place-Version benötigt O(1) zusätzlichen Speicher; das Kopieren der Werte in ein Array benötigt O(L).

Q: Was passiert mit der letzten Gruppe, wenn sie weniger als k Knoten enthält?

Die ursprüngliche Reihenfolge bleibt erhalten. Zähle k Knoten, bevor du jede Gruppe umdrehst; wenn du zuerst das Ende der Liste erreichst, lass den Rest unverändert.

SchwerVerkettete Liste

+10

Eine einfach verkettete Liste wird in zwei Arrays gleicher Länge gespeichert. Knoten i enthält values[i] und ist mit Knoten next[i] verknüpft; -1 beendet die Liste, und der Kopf ist Knoten 0. Die Knoten können in beliebiger Reihenfolge gespeichert sein. Folge daher den Verknüpfungen und nicht der Reihenfolge im Array.

Kehre die Liste in Gruppen von k Knoten um: Die ersten k Knoten werden umgekehrt, dann die nächsten k und so weiter. Eine letzte Gruppe mit weniger als k Knoten behält ihre Reihenfolge bei. Gib die Werte in der Reihenfolge der neuen Liste zurück.

Funktion

reverseKGroup(next: integer-array, values: integer-array, k: integer) → integer-array

nextinteger-array: den Index des Knotens, auf den jeder Knoten verweist, oder -1 für den letzten Knoten
valuesinteger-array: der von jedem Knoten gehaltene Wert
kinteger: die Anzahl der Knoten in jeder Gruppe, die umgekehrt werden soll
Gibt zurückinteger-array: die Werte in der Reihenfolge der neuen Liste

Einschränkungen

1 ≤ L ≤ 5000, wobei L die Länge von next und von values ist.
-1000 ≤ values[i] ≤ 1000
1 ≤ k ≤ L
Jedes next[i] ist -1 oder ein Knotenindex von 0 bis L-1.
Beginnend bei Knoten 0, besucht die Liste jeden Knoten genau einmal und erreicht dann -1. Es gibt keinen Zyklus.

Beispiele

Eingabe: next = [2, 3, 4, -1, 1]values = [1, 4, 2, 5, 3]k = 2
Ausgabe: [2, 1, 4, 3, 5]
Erklärung: Die Liste lautet 1, 2, 3, 4, 5 (Knoten 0, 2, 4, 1, 3). Die Paare 1, 2 und 3, 4 sind umgekehrt, und nur 5 ist kürzer als k = 2, daher bleibt es am Ende.

Eingabe: next = [5, 3, 6, -1, 7, 2, 4, 1]values = [10, 70, 30, 80, 50, 20, 40, 60]k = 3
Ausgabe: [30, 20, 10, 60, 50, 40, 70, 80]
Erklärung: Die Liste lautet 10, 20, ..., 80. Die Gruppen 10, 20, 30 und 40, 50, 60 sind umgekehrt. 70, 80 ist kürzer als k = 3, daher behält es seine Reihenfolge bei.

Eingabe: next = [2, -1, 1]values = [7, 9, 3]k = 3
Ausgabe: [9, 3, 7]
Erklärung: Das Array lautet 7, 9, 3, aber die Liste lautet 7, 3, 9. Wenn k der Länge entspricht, bildet die ganze Liste eine Gruppe und wird umgekehrt ausgegeben: 9, 3, 7.

Weiterführende Frage

Können Sie es rekursiv schreiben, indem Sie eine Gruppe umkehren und für den Rest der Liste rekursiv vorgehen? Wie viel zusätzlichen Speicher benötigt das?

Tipps

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

0 von 3 geöffnet

Lösung

Eine ganze Liste umzukehren, erfordert einen Durchlauf mit Verknüpfungsumkehrungen. Hier werden die Verknüpfungen alle k Knoten umgedreht, und jede umgekehrte Gruppe muss mit dem Teil davor und den Knoten danach verbunden werden. Du kannst die Werte in ein Array kopieren und Blöcke umkehren oder jede Gruppe direkt an Ort und Stelle mit O(1) zusätzlichem Speicher neu verknüpfen.

Kopiere die Werte und kehre jeden Block um

Idee

Gehe von Knoten 0 aus mit node = next[node] weiter und kopiere die Werte in Listenreihenfolge in ein Array. Die Gruppen sind jetzt die Indexblöcke 0 bis k-1, k bis 2k-1 und so weiter: Kehre jeden vollständigen Block um und lass einen kürzeren letzten Block unverändert. Das benötigt O(L) Zeit und O(L) zusätzlichen Speicher und verändert niemals eine Verknüpfung.

Algorithmus

Gehe von Knoten 0 bis -1 und füge values[node] zu einem Array hinzu.
Für start = 0, k, 2k, ..., solange start + k ≤ L gilt: Kehre den Block von Index start bis start+k-1 um.
Lass einen kürzeren Block am Ende unverändert.
Gib das Array zurück.

def reverseKGroup(next, values, k):
    # Read the values in list order.
    order = []
    node = 0
    while node != -1:
        order.append(values[node])
        node = next[node]
    # Reverse every full block of k; a shorter last block stays as it is.
    for start in range(0, len(order) - k + 1, k):
        order[start:start + k] = order[start:start + k][::-1]
    return order

Jede Gruppe durch erneutes Verknüpfen direkt umkehren

Idee

Um eine ganze Liste umzukehren, durchläufst du sie mit prev und node und setzt next[node] = prev. Eine Gruppe entsteht durch dieselbe Schleife, die k Mal ausgeführt wird, wobei prev mit after beginnt, dem Knoten direkt nach der Gruppe. Der erste Knoten der Gruppe wird zu ihrem letzten und zeigt auf after, sodass der Rest der Liste verbunden bleibt.

Zähle k Knoten, bevor du sie umdrehst: Wenn du zuerst -1 erreichst, ist der Rest eine kurze Gruppe und bleibt unverändert. Nach dem Umdrehen ist prev der neue erste Knoten der Gruppe. Verknüpfe den letzten Knoten der vorherigen Gruppe mit ihm oder mache ihn zur Listenwurzel, wenn es die erste Gruppe ist. Der ursprünglich erste Knoten der Gruppe ist jetzt der letzte Knoten des fertig bearbeiteten Teils.

Jeder Knoten wird zweimal besucht, einmal zum Zählen und einmal zum Umdrehen: O(L) Zeit und einige Ganzzahlen an Speicher (O(L) in R, das den Linkvektor bei seiner ersten Änderung kopiert).

Algorithmus

Beginne mit head = 0, prevTail = -1, groupStart = 0.
Gehe von groupStart aus k Schritte bis after; wenn du zuerst -1 erreichst, fahre mit Schritt 5 fort.
Wiederhole mit prev = after und node = groupStart k Mal: Speichere next[node], setze next[node] = prev und gehe bei beiden einen Schritt weiter.
Wenn prevTail gleich -1 ist, setze head = prev; andernfalls setze next[prevTail] = prev. Setze prevTail = groupStart, groupStart = after; fahre mit Schritt 2 fort.
Sammle die Werte ab head.

def reverseKGroup(next, values, k):
    head = 0           # the list's head; changes after the first group
    prev_tail = -1     # last node of the groups already reversed
    group_start = 0
    while True:
        # Find the node right after this group, or stop if fewer than k remain.
        after, count = group_start, 0
        while after != -1 and count < k:
            after = next[after]
            count += 1
        if count < k:
            break
        # Turn the group's k links around. Its first node ends up last
        # and links to the node after the group.
        prev, node = after, group_start
        for _ in range(k):
            following = next[node]
            next[node] = prev
            prev, node = node, following
        # prev is the group's new first node: hang it after the previous group.
        if prev_tail == -1:
            head = prev
        else:
            next[prev_tail] = prev
        prev_tail = group_start
        group_start = after
    # Walk the relinked list from its head.
    result = []
    node = head
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Stolperfallen und Grenzfälle

Die kurze letzte Gruppe umkehren. Zähle k Knoten, bevor du sie umdrehst; eine umgedrehte Verknüpfung lässt sich ohne einen weiteren Durchlauf nicht rückgängig machen.
Die Umkehrung mit prev = -1 beginnen, wie bei einer vollständigen Umkehrung. Ein kurzer Rest fällt dann ab: Das erste Beispiel gibt 2, 1, 4, 3 zurück.
Den letzten Knoten der vorherigen Gruppe nicht mit dem neuen ersten Knoten verknüpfen. Er zeigt weiterhin auf den alten ersten Knoten, sodass k-1 Knoten verschwinden.
Die Antwort ab Knoten 0 ablesen oder values von links nach rechts lesen. Sobald eine Gruppe mit k ≥ 2 umgedreht wird, ist Knoten 0 nicht mehr der Kopf, und die Array-Reihenfolge entsprach nie der Listenreihenfolge.
In Lua und R ab 0 indizieren, deren Arrays bei 1 beginnen. Behalte die Knotenindizes bei 0 und lies next[node + 1].

Häufige Fragen3

Wie hoch sind die Zeit- und Speicherkomplexität beim Umkehren von Knoten in k-Gruppen?

Für eine Liste mit L Knoten läuft es in O(L)-Zeit: Jeder Knoten wird einmal gezählt und einmal umgedreht. Die In-place-Version benötigt O(1) zusätzlichen Speicher; das Kopieren der Werte in ein Array benötigt O(L).

Was passiert mit der letzten Gruppe, wenn sie weniger als k Knoten enthält?

Die ursprüngliche Reihenfolge bleibt erhalten. Zähle k Knoten, bevor du jede Gruppe umdrehst; wenn du zuerst das Ende der Liste erreichst, lass den Rest unverändert.

Warum verwenden Lösungen für dieses Problem einen Dummy-Knoten?

Bei Knotenobjekten sorgt ein Dummy-Knoten vor dem Kopf dafür, dass die erste Gruppe einen Knoten vor sich hat, sodass eine einzige Zeile jede Gruppe mit dem fertigen Teil verbindet. Bei einem Array von Verknüpfungen erfüllt ein prevTail, das bis zum Abschluss der ersten Gruppe -1 bleibt, denselben Zweck.

def reverseKGroup(next, values, k):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

next = [2, 3, 4, -1, 1]
values = [1, 4, 2, 5, 3]
k = 2

Erwartete Ausgabe

[2, 1, 4, 3, 5]