Palindrome Linked List
Otrzymujesz jednokierunkową listę połączoną zapisaną w dwóch tablicach o tej samej długości. Węzeł i przechowuje wartość values[i] i wskazuje na węzeł next[i], -1 oznacza koniec listy, a głową jest węzeł 0. Węzły nie są zapisane w kolejności listy, więc podążaj za odnośnikami.
Zwróć true, jeśli wartości odczytane od głowy do końca są takie same jak odczytane od końca do głowy, a w przeciwnym razie false.
Funkcja
- nextinteger-array
- indeks węzła, do którego prowadzi połączenie z każdego węzła, lub -1 dla ostatniego węzła
- valuesinteger-array
- wartość przechowywana w każdym węźle
- Zwracaboolean
- true, jeśli listę odczytuje się tak samo w obu kierunkach
Ograniczenia
1 ≤ L ≤ 5000, gdzieLjest długościąnextivalues.-100 ≤ values[i] ≤ 100- Każde
next[i]ma wartość-1lub indeks węzła od0doL-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 = [4, 3, -1, 2, 1]values = [3, 4, 3, 1, 1]
- Wyjście
- true
- Wyjaśnienie
- Łącza odwiedzają węzły
0, 4, 1, 3, 2, więc lista ma postać3, 1, 4, 1, 3. Obie trójki pasują do siebie, obie jedynki pasują do siebie, a4pośrodku nie ma pary do sprawdzenia.
- Wejście
- next = [2, -1, 3, 1]values = [4, 4, 9, 9]
- Wyjście
- true
- Wyjaśnienie
- Lista odwiedza węzły
0, 2, 3, 1i odczytuje4, 9, 9, 4, tak samo w obu kierunkach.
- Wejście
- next = [2, -1, 1]values = [1, 2, 1]
- Wyjście
- false
- Wyjaśnienie
- Tablica
valuesma wartość[1, 2, 1], ale lista odwiedza węzły0, 2, 1i odczytuje1, 1, 2. Od tyłu to2, 1, 1, więc odpowiedź tofalse.
Pytanie dodatkowe
Czy potrafisz zrobić to w czasie O(L) i przy użyciu O(1) dodatkowej pamięci?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Sprawdzenie, czy ciąg jest palindromem, polega na porównaniu pierwszej wartości z ostatnią, drugiej z przedostatnią i tak dalej. W jednokierunkowej liście łączonej możesz poruszać się tylko do przodu. Co umożliwiłoby dotarcie do końca?
Kopiowanie wartości do tablicy w kolejności z listy działa, ale kosztuje
O(L)pamięci. Bez kopiowania trzeba przejść drugą połowę wstecz. Zmiana jej połączeń może to umożliwić.Znajdź środek za pomocą dwóch wskaźników:
fastprzesuwa się o dwa łącza za każdym razem, gdyslowprzesuwa się o jedno. Gdyfastnie może już się przesunąć,slowwyznacza koniec pierwszej połowy. Odwróć łącza zaslow, a następnie jednocześnie przechodź od głowy i od dawnego ostatniego węzła, porównując je.
Rozwiązanie
Sprawdzanie palindromu polega na parowaniu każdej wartości z jej lustrzanym odpowiednikiem z drugiego końca. Lista jednokierunkowa pozwala poruszać się tylko do przodu, więc trudność polega na odczytaniu drugiej połowy w odwrotnej kolejności. Kopia tablicy wymaga O(L) pamięci, gdzie L to liczba węzłów; odwrócenie połączeń w drugiej połowie wymaga O(1).
Skopiuj wartości do tablicy
Intuicja
Wskaźnik to tutaj indeks węzła, a przejście do przodu odbywa się przez node = next[node]. Przejdź raz przez listę i skopiuj każdą wartość do tablicy, którą możesz odczytywać z obu końców. Porównaj pierwszą i ostatnią wartość, przesuń oba indeksy w stronę środka i zwróć false przy każdej niezgodności. Przy nieparzystej długości środkowa wartość jest swoją własną parą.
Trzeba odczytać każdą wartość, więc czas O(L) jest najlepszy z możliwych. Kosztem jest użycie L dodatkowych liczb całkowitych.
Algorytm
- Przejdź od węzła
0do-1i dodaj każdą wartośćvalues[node]do tablicy. - Ustaw
i = 0, ajustaw na ostatnim indeksie. - Gdy
i < j, zwróćfalse, jeśli wartości są różne, w przeciwnym razie zwiększii zmniejszj. - Zwróć
true.
def isPalindrome(next, values):
# Write the values out in list order.
seq = []
node = 0
while node != -1:
seq.append(values[node])
node = next[node]
# Compare from both ends toward the middle.
i = 0
j = len(seq) - 1
while i < j:
if seq[i] != seq[j]:
return False
i += 1
j -= 1
return TrueOdwróć drugą połowę na miejscu
Intuicja
Odwróć łącza drugiej połowy zamiast jej kopiować: przejście od dawnego ostatniego węzła prowadzi wtedy ku środkowi. Aby znaleźć środek, przesuwaj fast o dwa łącza na każde łącze, o które przesuwa się slow, dopóki fast ma przed sobą dwa łącza. slow zatrzymuje się na ostatnim węźle pierwszej połowy, czyli na środkowym węźle, gdy L jest nieparzyste. W pierwszym przykładzie slow przechodzi przez 0 → 4 → 1, a fast przez 0 → 1 → 2, więc slow zatrzymuje się na 4.
Odwróć węzły za slow, a następnie przejdź jednocześnie left od głowy i right od odwróconej połowy: 3 z 3, a potem 1 z 1. Odwrócona połowa nigdy nie jest dłuższa niż pierwsza połowa, więc zatrzymanie się, gdy skończy się right, porównuje dokładnie te pary, które mają znaczenie. Każda faza przechodzi przez co najwyżej L węzłów i przechowuje kilka liczb całkowitych. W R zmiana next_ kopiuje wektor jeden raz, więc R używa pamięci O(L).
Algorytm
- Ustaw
slow = fast = 0. Dopóki zarównonext[fast], jak inext[next[fast]]są różne od-1, przesuwajslowo jedno ogniwo, afasto dwa. - Odwróć listę zaczynającą się od
next[slow]: dla każdego węzła zapisz jego odnośnik, skieruj go naprev, a następnie przesuńprevi węzeł do przodu. - Ustaw
left = 0iright = prev, głowę odwróconej połowy. - Dopóki
right != -1, w przypadku niezgodności zwróćfalse, w przeciwnym razie przesuń oba wskaźniki o jedno ogniwo. - Zwróć
true.
def isPalindrome(next, values):
# Find the middle: fast moves two links for every one link slow moves.
slow = 0
fast = 0
while next[fast] != -1 and next[next[fast]] != -1:
slow = next[slow]
fast = next[next[fast]]
# slow is the last node of the first half (the middle node when the length is odd).
# Reverse the links of the second half.
prev = -1
node = next[slow]
while node != -1:
after = next[node]
next[node] = prev
prev = node
node = after
# prev is the old last node, now the head of the reversed half.
left = 0
right = prev
while right != -1:
if values[left] != values[right]:
return False
left = next[left]
right = next[right]
return True
Pułapki i przypadki brzegowe
- Sprawdzanie tablic zamiast listy. W trzecim przykładzie
valuesma wartość[1, 2, 1], ale lista zawiera1, 1, 2. - Testowanie tylko
next[fast] != -1.fastmoże wtedy przeskoczyć do-1i odczytaćnext[-1], co w większości języków wykracza poza zakres, a w Pythonie i Ruby po cichu odwołuje się do ostatniego elementu. - Porównywanie, dopóki nie skończy się
left, zamiastright. Środkowy węzeł nadal łączy się ze starą drugą połową, więc przejście od głowy jest dłuższe. - Nadpisanie
next[node]podczas odwracania listy, zanim zostanie zapisany, co powoduje utratę reszty listy. - W Lua i R, gdzie tablice zaczynają się od 1, odczytywanie
next[node]dla identyfikatora węzła o indeksie 0. Odczytajnext[node + 1].
Najczęstsze pytania3
Jaka jest złożoność czasowa sprawdzania, czy lista połączona jest palindromem?
Każde podejście ma złożoność O(L) dla listy zawierającej L węzłów, ponieważ trzeba porównać każdą wartość. Skopiowanie wartości do tablicy lub na stos wymaga dodatkowej pamięci O(L); odwrócenie drugiej połowy w miejscu wymaga O(1).
Jak szybki i wolny wskaźnik znajdują środek listy połączonej?
Oba zaczynają na początku listy, a szybki wskaźnik wykonuje dwa kroki na każdy krok wolnego wskaźnika. Gdy szybki wskaźnik dotrze do końca, pokona całą listę, a wolny wskaźnik — połowę.
Czy odwrócenie połowy listy niszczy dane wejściowe?
Tak, zmienia linki w drugiej połowie, a w większości języków ta tablica należy do wywołującego. Jeśli lista będzie jeszcze potrzebna, dokończ porównanie bez przedwczesnego zwracania wyniku, a następnie ponownie odwróć tę połowę. Środkowy węzeł nadal wskazuje na pierwszy węzeł tej połowy, więc lista znów jest cała, przy użyciu dodatkowej pamięci O(1).
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def isPalindrome(next, values):
# Wpisz tutaj kodTest #1
Test #2
Test #3
Argumenty
next = [4, 3, -1, 2, 1] values = [3, 4, 3, 1, 1]
Oczekiwany wynik
true