Odwracanie ciągów w Javie: nauka odwracania ciągów na różne sposoby

Czy można zostać dobrym programistą nie znając algorytmów? Bardzo, bardzo kontrowersyjne. Tak, w naszych firmach outsourcingowych można znaleźć pracę, ponieważ podczas rozmów kwalifikacyjnych zadają pytania głównie o technologię. Ale czy będziesz dobrym specjalistą, jeśli swoje decyzje będziesz opierać o kulach? Jeśli chcesz przenieść się do poważniejszej firmy zagranicznej, spotkasz się z rozmowami kwalifikacyjnymi, które skupiają się przede wszystkim na algorytmach. Tak czy inaczej warto zastosować najbardziej podstawowe algorytmy, bo algorytm jest przyjacielem programisty . Dzisiaj poruszymy jeden z tych tematów i omówimy sposoby odwrócenia ciągu znaków. Tutaj wszystko jest proste. Odwrócenie ciągu oznacza cofnięcie ciągu. Na przykład: JavaRush na zawsze ->reverof hsuRavaJ Jak więc odwrócić ciąg znaków w Javie?

1. Konstruktor String/Bufor String

Najpopularniejszym i najprostszym sposobem jest użycie StringBuilder/StringBuffer :

public static String reverseString(String str) {
  return new StringBuilder(str).reverse().toString();
}

Najlepsze rozwiązanie = najprostsze. Na pytanie, jak odwrócić ciąg znaków w Javie, jest to pierwsza rzecz, która powinna przyjść na myśl. Ale o algorytmach rozmawialiśmy wcześniej, prawda? Przyjrzyjmy się rozwiązaniom, które nie są gotowe do użycia.

2. Rozwiązanie tablicowe

public static String reverseString(String str) {
  char[] array = str.toCharArray();
  String result = "";
  for (int i = array.length - 1; i >= 0; i--) {
     result = result + array[i];
  }
  return result;
}

Nasz ciąg znaków konwertujemy na tablicę za pomocą metody toCharArray . Uruchommy pętlę for przez tę tablicę od jej końca, dodając po drodze znaki do wynikowego ciągu.

3. Rozwiązanie z charAt

public static String reverseString(String str) {
  String result = "";
  for (int i = 0; i < str.length(); i++) {
     result = str.charAt(i) + result;
  }
  return result;
}

W tym przypadku nie musimy nawet dzielić ciągu znaków na tablicę, ponieważ każdy znak wyodrębniamy za pomocą metody klasy String - charAt (pętla for ponownie działa odwrotnie, co pozwala nam sekwencyjnie przenosić znaki wstecz).

4. Rozwiązanie ze stosem

Klasa Stack nie jest używana od dłuższego czasu i uważa się ją za przestarzałą, niemniej jednak dla odniesienia warto przyjrzeć się rozwiązaniu z jej wykorzystaniem:

public static String reverseString(String str) {
  Stack<Character> stack = new Stack<>();
  String result = "";
  for (Character character : str.toCharArray()) {
     stack.add(character);
  }
  while (!stack.isEmpty()) {
     result = result + stack.pop();
  }
  return result;
}

Tutaj ponownie używamy toCharArray , aby podzielić ciąg na tablicę i umieścić wszystko na naszym stosie za pomocą ogólnego typu Character . Następnie zaczynamy pobierać elementy ze szczytu stosu. Ze względu na charakter stosu jako struktury LIFO - Last In First Out (pierwsze weszło , ostatnie wyszło ), elementy zostaną przeniesione wstecz, a wynik zostanie zapisany w wynikowym wierszu.

5. Rozwiązanie metodą rekurencji

Prawie każdy problem algorytmiczny można rozwiązać za pomocą rekurencji. I tutaj również nie możemy się bez niej obejść. Albo nawet bez nich. W końcu dzisiaj rozważymy nie tylko jedną metodę rozwiązania rekurencji, ale kilka.

• metoda pierwsza

  public static String reverseString(String str) {
    String rightStr;
    String leftStr;
    int length = str.length();
  
    if (length <= 1) {
       return str;
    }
  
    leftStr = str.substring(0, length / 2);
    rightStr = str.substring(length / 2, length);
  
    return reverseString(rightStr) + reverseString(leftStr);
  }

  Używamy zmiennych RightStr i leftStr , aby podzielić przychodzący ciąg na dwie równe części. Następnie, korzystając z tego podziału, dzielimy ciąg na najmniejsze, podzielne części (1 znak). Następnie rekursja zaczyna się załamywać, zwracając znaki w odwrotnej kolejności (te, które były po prawej stronie, zostały umieszczone po lewej stronie, te, które były po lewej stronie, zostały umieszczone po prawej stronie)

  Nie wolno nam zapominać, że każda rekurencja to wielokrotne wywołanie metody, a co za tym idzie, znaczny wydatek zasobów. Cóż, jeśli mówimy o rekurencji z nieosiągalnym warunkiem wyjścia, to jest to ścieżka do nieskończoności i do StackOverflowError.

• metoda druga

  Tutaj potrzebny jest dodatkowy argument w metodzie - indeks.

  Po uruchomieniu tej metody otrzymuje ona łańcuch o długości -1:

  String str = "JavaRush forever";
  System.out.println(reverseString(str, str.length()-1));

  I sama metoda:

  public static String reverseString(String str, int index) {
    if(index == 0){
       return str.charAt(0) + "";
    }
  
    char letter = str.charAt(index);
    return letter + reverseString(str, index-1);
  }

  Nasz indeks służy jako wskaźnik tego, którego elementu wiersza będziemy teraz używać (i będziemy używać elementów od końca).

  Dlatego ustalamy warunki wyjścia, gdy indeks osiągnie pierwszy element.

Wartości uzyskane za pomocą indeksu literowego dodajemy do wyniku poprzedniego wykonania metody i zwracamy wynik.

• metoda trzecia

  public static String reverseString(String str) {
    if (str.length() <= 1) {
       return str;
    }
    return reverseString(str.substring(1)) + str.charAt(0);
  }

  Ta metoda jest w zasadzie najprostszą z metod rekurencyjnych. A jak pamiętamy, proste = najlepsze.

  Podczas każdego uruchomienia podajemy ten sam ciąg znaków, ale bez pierwszego elementu. Kiedy warunek wyjścia zostanie osiągnięty (kiedy zostanie nam jeden znak), rekurencja zaczyna się załamywać, a do każdego kolejnego wyniku dodawany będzie poprzedni, nieużywany znak.

6. Korzystanie z XOR-a

XOR jest logiczną operacją bitową. W przypadku dwóch zmiennych wynik operacji jest prawdziwy wtedy i tylko wtedy, gdy jeden z argumentów jest prawdziwy, a drugi fałszywy. Więcej o operacjach bitowych możesz przeczytać w tym artykule . Kolejne rozwiązanie będzie polegało na tym, że:

(A XOR B) XOR B = A
(A XOR B) XOR A = B

Jak będzie wyglądać metoda:

public static String reverseString(String str) {
  char[] arr = str.toCharArray();
  int low = 0;
  int high = arr.length - 1;
  String result = "";
  while (low < high) {
     arr[low] = (char) (arr[low] ^ arr[high]);
     arr[high] = (char) (arr[low] ^ arr[high]);
     arr[low] = (char) (arr[low] ^ arr[high]);
     low++;
     high--;
  }
  for (int i = 0; i < arr.length; i++) {
     result = result + arr[i];
  }
  return result;
}

Zastanówmy się, co się tutaj dzieje. Tworzymy tablicę z przychodzącego ciągu. Tworzymy dwie zmienne, low i high , które przechowują indeksy umożliwiające poruszanie się po tablicy. Odpowiednio jeden będzie przechodził od początku do końca – nadajemy mu wartość 0, drugi – od końca do początku, ustawiamy arr.length – 1 . Wchodzimy w pętlę, która będzie odtwarzana tak długo, jak wysoki indeks będzie większy niż niski . Tutaj zaczynają się dziać najfajniejsze rzeczy — użycie wyłącznego OR. Spójrzmy na x i y jako przykład . Załóżmy, że arr[high] = 'x'; Jego kod binarny będzie wynosił 1 1 1 1 0 0 0 W tym momencie arr[high] = 'n'; Kod binarny - 1 1 0 1 1 1 0 Co będziemy mieli w operacjach XOR w pętli:

1. arr[low] = (char) (arr[low] ^ arr[high]);

   
   arr[low] = 1 1 0 1 1 1 0
   arr[high] =1 1 1 1 0 0 0
   arr[low] = 0 0 1 0 1 1 0

2. arr[wysoki] = (znak) (tablica[niska] ^ tablica[wysoka]);

   
   arr[low] =  0 0 1 0 1 1 0
   arr[high] = 1 1 1 1 0 0 0
   arr[high] = 1 1 0 1 1 1 0

3. arr[low] = (char) (arr[low] ^ arr[high]);

   
   arr[low] =  0 0 1 0 1 1 0
   arr[high] = 1 1 0 1 1 1 0
   arr[low] =  1 1 1 1 0 0 0

W efekcie dzięki tym operacjom zamieniliśmy wartościami dwóch komórek tablicy. arr[high] to tyle elementów od końca tablicy, ile arr[low] od początku. Dlatego po prostu zamieniamy elementy tymi indeksami. Przykładowo przy pierwszym wykonaniu w zdaniu „JavaRush Forever” zamienione zostaną J i r , przy drugim – a i e itd. Jeśli mamy nieparzystą liczbę znaków, to gdy dotrzemy do elementu znajdującego się w środkowy, zostaniemy wyrzuceni z pętli (tzn. nie ma potrzeby zmiany środkowego elementu). Jeśli będzie równo, to po przetworzeniu wszystkich elementów zostaniemy wyrzuceni. Cóż, potem wchodzimy w zwykłą pętlę i budujemy ciąg znaków z elementów tablicy.