Jak znaleźć wszystkie niezrównoważone pareny w ciągu w czasie liniowym ze stałą pamięcią?

Podczas wywiadu dostałem następujący problem:

Daje ciąg znaków, który zawiera pewną mieszankę parenów (nie nawiasów klamrowych ani nawiasów klamrowych - tylko pareny) z innymi znakami alfanumerycznymi, zidentyfikuj wszystkie pareny, które nie mają pasujących paren.

Na przykład w ciągu „) (ab))” indeksy 0 i 5 zawierają pareny, które nie mają pasujących paren.

Przedstawiam działające rozwiązanie O (n) przy użyciu pamięci O (n), używając stosu i przechodząc przez ciąg po dodaniu parens do stosu i usunięciu ich ze stosu, ilekroć napotkałem zamykający paren i górną część stosu paren otwierający.

Następnie ankieter zauważył, że problem można rozwiązać w czasie liniowym ze stałą pamięcią (jak w, bez dodatkowego użycia pamięci poza tym, co jest pobierane przez dane wejściowe).

Zapytałem, jak i powiedziała coś o przejściu sznurka raz z lewej strony, identyfikując wszystkie otwarte pareny, a potem drugi raz z prawej, identyfikując wszystkie bliskie pareny ... a może było na odwrót. Naprawdę nie rozumiałem i nie chciałem prosić, żeby mnie za to trzymała.

Czy ktoś może wyjaśnić zaproponowane przez nią rozwiązanie?

$O(1)$$\Theta(\log(n))$$n$

Możesz zachować podstawową zasadę zastosowanego algorytmu. Straciłeś okazję do optymalizacji pamięci.

używając stosu i przechodząc przez ciąg po dodaniu parens do stosu i usuwając je ze stosu, ilekroć napotkałem zamykający paren, a góra stosu zawierała otwierający paren

Co zawiera ten stos? Nigdy nie będzie zawierać ()(nawias otwierający, a następnie nawias zamykający), ponieważ za każdym razem, gdy )pojawia się napis, (zamiast naciskać ). Tak więc stos ma zawsze formę )…)(…(- kilka nawiasów zamykających, a następnie kilka nawiasów otwierających.

Nie potrzebujesz stosu, aby to przedstawić. Zapamiętaj tylko liczbę nawiasów zamykających i liczbę nawiasów otwierających.

Jeśli przetwarzasz ciąg znaków od lewej do prawej, używając tych dwóch liczników, na końcu masz liczbę niedopasowanych nawiasów zamykających i liczbę niedopasowanych nawiasów otwierających.

$\Theta(n)$

Podsumowując: przetwarzaj ciąg znaków od lewej do prawej. Zachowaj licznik niedopasowanych nawiasów otwierających. Jeśli widzisz otwierający nawias, zwiększ licznik. Jeśli widzisz zamykający nawias, a licznik jest niezerowy, zmniejsz licznik. Jeśli widzisz nawias zamykający, a licznik jest równy zero, wypisz bieżący indeks jako niedopasowany nawias zamykający.

Ostateczna wartość licznika to liczba niedopasowanych nawiasów otwierających, ale to nie określa ich pozycji. Zauważ, że problem jest symetryczny. Aby wyświetlić pozycje niedopasowanych nawiasów otwierających, po prostu uruchom algorytm w przeciwnym kierunku.

Ćwiczenie 1: zapisz to w formalnej notacji (matematyka, pseudokod lub twój ulubiony język programowania).

Ćwiczenie 2: przekonaj się, że jest to ten sam algorytm, co Apass.Jack , po prostu wyjaśniono inaczej.

Ponieważ możemy po prostu zignorować wszystkie znaki alfanumeryczne, założymy, że odtąd ciąg zawiera tylko nawiasy. Podobnie jak w pytaniu, istnieje tylko jeden rodzaj nawiasu, „()”.

Jeśli będziemy kontynuować usuwanie zrównoważonych nawiasów, dopóki nie będzie można usunąć więcej zrównoważonych nawiasów, wszystkie pozostałe nawiasy muszą wyglądać jak „))…) ((… (”, które są niezbalansowanymi nawiasami. Ta obserwacja sugeruje, że powinniśmy najpierw znaleźć ten punkt zwrotny) , przed którymi mamy tylko niezrównoważone nawiasy zamykające, a po których mamy niezrównoważone tylko nawiasy otwierające.

Oto algorytm. Krótko mówiąc, najpierw oblicza punkt zwrotny. Następnie generuje dodatkowy nawias zamykający, skanując ciąg od początku do prawej do punktu zwrotnego. Symetrycznie generuje dodatkowy nawias otwierający, skanując od końca do lewej do punktu zwrotnego.

Pozwolić str$n$

Zainicjuj turning_point=0, maximum_count=0, count=0. Dla każdego iz 0aby n-1wykonać następujące czynności.

1. Jeśli str[i] = ')'dodaj 1 do count; w przeciwnym razie odejmij 1.
2. Jeśli count > maximum_count , ustaw turning_point=ii maximum_count=count.

Teraz turning_pointjest indeks punktu zwrotnego.

Zresetować maximum_count=0, count=0. Dla każdegoi z 0aby turning_pointwykonać następujące czynności.

1. Jeśli str[i] = ')'dodaj 1 do count; w przeciwnym razie odejmij 1.
2. Jeśli count > maximum_count, ustawmaximum_count = count . Dane wyjściowe ijako indeks niezrównoważonego nawiasu zamykającego.

Zresetować maximum_count=0, count=0. Dla każdego izn-1 do turning_point+1dołu wykonaj następujące czynności.

1. Jeśli str[j] = '('dodaj 1 do count; w przeciwnym razie odejmij 1.
2. Jeśli count > maximum_count, ustaw maximum_count = count. Wyniki jako indeks niezrównoważonego nawiasu otwierającego.

$O(n)$$O(1)$$O(u)$$u$

Jeśli przeanalizujemy powyższy algorytm, zobaczymy, że tak naprawdę wcale nie musimy znajdować punktu zwrotnego i korzystać z niego. Ładna obserwacja, że ​​wszystkie niezrównoważone nawiasy zamykające mają miejsce, zanim wszystkie niezrównoważone nawiasy otwierające mogą zostać zignorowane, chociaż interesujące.

Oto kod w Pythonie .

Wystarczy nacisnąć „Uruchom”, aby zobaczyć kilka wyników testu.

Ćwiczenie 1. Pokaż, że powyższy algorytm wyświetli zestaw nawiasów o najmniejszej liczności, tak aby pozostałe nawiasy były zrównoważone.

Problem 1. Czy możemy uogólnić algorytm na przypadek, gdy ciąg zawiera dwa rodzaje nawiasów, takie jak „() []”? Musimy ustalić, jak rozpoznać i potraktować nową sytuację, przypadek przeplatania, „([)]”.