Reverse Nodes in k-Group

Q: Jaka jest złożoność czasowa i pamięciowa odwracania węzłów w grupach po k?

Działa w czasie O(L) dla listy składającej się z L węzłów: każdy węzeł jest zliczany raz i odwracany raz. Wersja działająca w miejscu wykorzystuje O(1) dodatkowej pamięci; skopiowanie wartości do tablicy wymaga O(L).

Q: Co się stanie z ostatnią grupą, jeśli ma mniej niż k węzłów?

Zachowuje pierwotną kolejność. Policz k węzłów przed odwróceniem każdej grupy; jeśli najpierw dotrzesz do końca listy, pozostaw resztę bez zmian.

TrudneLista wiązana

+10

Jednokierunkowa lista wiązana jest przechowywana w dwóch tablicach o tej samej długości. Węzeł i przechowuje values[i] i wskazuje na węzeł next[i]; -1 oznacza koniec listy, a głową jest węzeł 0. Węzły mogą być przechowywane w dowolnej kolejności, dlatego podążaj za wskaźnikami, a nie za kolejnością w tablicy.

Odwróć listę w grupach po k węzłów: pierwsze k węzłów mają zostać odwrócone, potem następne k i tak dalej. Ostatnia grupa licząca mniej niż k węzłów zachowuje swoją kolejność. Zwróć wartości w nowej kolejności listy.

Funkcja

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

nextinteger-array: indeks węzła, do którego prowadzi każdy węzeł, lub -1 dla ostatniego węzła
valuesinteger-array: wartość przechowywana przez każdy węzeł
kinteger: liczba węzłów w każdej grupie do odwrócenia
Zwracainteger-array: wartości w nowej kolejności listy

Ograniczenia

1 ≤ L ≤ 5000, gdzie L jest długością next i values.
-1000 ≤ values[i] ≤ 1000
1 ≤ k ≤ L
Każde next[i] to -1 lub indeks węzła od 0 do L-1.
Rozpoczynając od węzła 0, lista odwiedza każdy węzeł dokładnie raz, a następnie dociera do -1. Nie ma cyklu.

Przykłady

Wejście: next = [2, 3, 4, -1, 1]values = [1, 4, 2, 5, 3]k = 2
Wyjście: [2, 1, 4, 3, 5]
Wyjaśnienie: Lista odczytuje 1, 2, 3, 4, 5 (węzły 0, 2, 4, 1, 3). Pary 1, 2 i 3, 4 są odwrócone, a samo 5 jest krótsze niż k = 2, więc pozostaje na końcu.

Wejście: next = [5, 3, 6, -1, 7, 2, 4, 1]values = [10, 70, 30, 80, 50, 20, 40, 60]k = 3
Wyjście: [30, 20, 10, 60, 50, 40, 70, 80]
Wyjaśnienie: Lista zawiera 10, 20, ..., 80. Grupy 10, 20, 30 i 40, 50, 60 są odwrócone. 70, 80 jest krótsza niż k = 3, więc zachowuje swoją kolejność.

Wejście: next = [2, -1, 1]values = [7, 9, 3]k = 3
Wyjście: [9, 3, 7]
Wyjaśnienie: Tablica zawiera 7, 9, 3, ale lista zawiera 7, 3, 9. Gdy k jest równe długości, cała lista stanowi jedną grupę i zostaje odwrócona: 9, 3, 7.

Pytanie dodatkowe

Czy potrafisz zapisać to rekurencyjnie, odwracając jedną grupę i wywołując rekurencję dla reszty listy? Ile dodatkowej pamięci to wymaga?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Odwrócenie całej listy wymaga jednego przejścia, podczas którego zmieniasz kierunek łączy. Tutaj zmiana kierunku łączy następuje co każde k węzłów, a każdą odwróconą grupę trzeba połączyć z poprzedzającą ją częścią i następującymi po niej węzłami. Możesz skopiować wartości do tablicy i odwrócić bloki albo ponownie połączyć każdą grupę na miejscu, używając O(1) dodatkowej pamięci.

Skopiuj wartości i odwróć kolejność w każdym bloku

Intuicja

Przejdź od węzła 0, używając node = next[node], i skopiuj wartości do tablicy w kolejności listy. Grupy to teraz bloki indeksów 0–k-1, k–2k-1 i tak dalej: odwróć każdy pełny blok, a krótszy ostatni blok pozostaw bez zmian. Zajmuje to O(L) czasu i O(L) dodatkowej pamięci i nie modyfikuje żadnego łącza.

Algorytm

Przejdź od węzła 0 aż do -1 i dołącz values[node] do tablicy.
Dla start = 0, k, 2k, ..., dopóki start + k ≤ L: odwróć blok od indeksu start do start+k-1.
Krótszy blok na końcu pozostaw bez zmian.
Zwróć tablicę.

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

Odwróć każdą grupę na miejscu, ponownie łącząc węzły

Intuicja

Aby odwrócić całą listę, przechodzisz przez nią, używając prev i node, i ustawiasz next[node] = prev. Grupa to ta sama pętla wykonana k razy, przy czym prev początkowo wskazuje after, czyli węzeł bezpośrednio za grupą. Pierwszy węzeł grupy staje się jej ostatnim i wskazuje na after, dzięki czemu reszta listy pozostaje dołączona.

Policz k węzłów przed ich odwróceniem: jeśli najpierw dotrzesz do -1, pozostała część jest krótką grupą i zostaje bez zmian. Po odwróceniu prev wskazuje nowy pierwszy węzeł grupy. Połącz z nim ostatni węzeł poprzedniej grupy albo ustaw go jako głowę, jeśli jest to pierwsza grupa. Pierwszy węzeł grupy przed odwróceniem jest teraz ostatnim węzłem gotowej części.

Każdy węzeł jest odwiedzany dwa razy: raz podczas liczenia i raz podczas odwracania: czas O(L) i kilka liczb całkowitych pamięci (O(L) w R, które kopiuje wektor łączy przy jego pierwszej zmianie).

Algorytm

Zacznij od head = 0, prevTail = -1, groupStart = 0.
Przejdź k kroków od groupStart do after; jeśli wcześniej dotrzesz do -1, przejdź do kroku 5.
Ustaw prev = after i node = groupStart, a następnie powtórz k razy: zapisz next[node], ustaw next[node] = prev i przesuń oba wskaźniki dalej.
Jeśli prevTail ma wartość -1, ustaw head = prev; w przeciwnym razie ustaw next[prevTail] = prev. Ustaw prevTail = groupStart, groupStart = after; przejdź do kroku 2.
Zbierz wartości, zaczynając od 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

Pułapki i przypadki brzegowe

Odwracanie krótkiej ostatniej grupy. Policz węzły k przed odwróceniem; odwróconego połączenia nie da się cofnąć bez kolejnego przejścia.
Rozpoczynanie odwracania od prev = -1, jak przy pełnym odwróceniu. Krótki koniec listy wtedy odpada: pierwszy przykład zwraca 2, 1, 4, 3.
Niełączenie ostatniego węzła poprzedniej grupy z nowym pierwszym węzłem. Nadal wskazuje on na stary pierwszy węzeł, więc k-1 węzłów znika.
Odczytywanie odpowiedzi od węzła 0 lub odczytywanie values od lewej do prawej. Po odwróceniu grupy o rozmiarze k ≥ 2 węzeł 0 nie jest głową listy, a kolejność tablicy nigdy nie była kolejnością listy.
Indeksowanie od 0 w Lua i R, których tablice zaczynają się od 1. Zachowaj indeksy węzłów liczone od 0 i odczytuj next[node + 1].

Najczęstsze pytania3

Jaka jest złożoność czasowa i pamięciowa odwracania węzłów w grupach po k?

Działa w czasie O(L) dla listy składającej się z L węzłów: każdy węzeł jest zliczany raz i odwracany raz. Wersja działająca w miejscu wykorzystuje O(1) dodatkowej pamięci; skopiowanie wartości do tablicy wymaga O(L).

Co się stanie z ostatnią grupą, jeśli ma mniej niż k węzłów?

Zachowuje pierwotną kolejność. Policz k węzłów przed odwróceniem każdej grupy; jeśli najpierw dotrzesz do końca listy, pozostaw resztę bez zmian.

Dlaczego rozwiązania tego problemu używają węzła wartowniczego?

W przypadku obiektów węzłów fikcyjny węzeł przed głową sprawia, że pierwsza grupa ma przed sobą węzeł, dzięki czemu jedna linia łączy każdą grupę z ukończoną częścią. W przypadku tablicy linków prevTail, które pozostaje równe -1 do ukończenia pierwszej grupy, spełnia tę samą funkcję.

def reverseKGroup(next, values, k):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

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

Oczekiwany wynik

[2, 1, 4, 3, 5]