Reverse a String

Odwrócony zapis s zaczyna się od ostatniego znaku s, zawiera następnie przedostatni znak, a kończy się pierwszym. Przechodź więc po indeksach od n-1 w dół do 0 i dopisuj każdy napotkany znak do wyniku. Dla Coddy2026 dopisujesz 6, 2, 0, 2, y i tak dalej, co daje 6202yddoC.

Każdy znak jest odczytywany raz i zapisywany raz, więc złożoność czasowa wynosi O(n). Wynik to drugi ciąg znaków o długości n, co oznacza dodatkową złożoność pamięciową O(n).

Sposób dopisywania ma znaczenie. Dodawanie jednego znaku do niemutowalnego ciągu za pomocą + za każdym razem kopiuje cały ciąg, a dla n = 10^4 oznacza to około 5 × 10^7 kopiowanych znaków. Zbieraj znaki na liście lub w obiekcie do budowania ciągu, a następnie połącz je raz na końcu.

Odwracanie zamienia pary znaków, zaczynając od zewnętrznych i przesuwając się do środka. Pierwszy i ostatni znak zamieniają się miejscami, następnie drugi i przedostatni i tak dalej w kierunku środka. Umieść wskaźnik left na indeksie 0, a wskaźnik right na indeksie n-1, zamień miejscami oba znaki i przesuń oba wskaźniki o jeden krok do środka.

Zatrzymaj się, gdy wskaźniki się spotkają lub miną. W noon wskaźniki zaczynają na indeksach 0 i 3, następnie przesuwają się na 1 i 2, po czym się mijają — po dwóch zamianach. W przypadku nieparzystej długości, takiej jak xYz, spotykają się na środkowym znaku, który już znajduje się na swoim docelowym miejscu, więc nigdy nie zostaje dotknięty. Każda zamiana umieszcza dwa znaki na ich docelowych pozycjach, więc n / 2 zamian wystarczy, by zakończyć zadanie.

Same zamiany wymagają tylko jednej zmiennej tymczasowej, czyli dodatkowej pamięci O(1). Większość języków nie pozwala modyfikować ciągu znaków w miejscu, dlatego najpierw kopiujesz go do tablicy znaków, co wymaga O(n) pamięci. Podczas rozmowy kwalifikacyjnej, gdy dane wejściowe są już tablicą znaków, to podejście odwraca ją bez użycia dodatkowej pamięci.