String in Java umkehren: Lernen, Strings auf unterschiedliche Weise umzukehren

Ist es möglich, ein guter Programmierer zu werden, ohne Algorithmen zu kennen? Sehr, sehr kontrovers. Ja, Sie können einen Job in unseren Outsourcing-Unternehmen finden, da in Vorstellungsgesprächen hauptsächlich Fragen zur Technologie gestellt werden. Aber werden Sie ein guter Spezialist sein, wenn Ihre Entscheidungen voller Krücken sind? Wenn Sie zu einem seriöseren ausländischen Unternehmen wechseln möchten, werden Sie auf Vorstellungsgespräche stoßen, in denen es vor allem um Algorithmen geht. Auf die eine oder andere Weise lohnt es sich, die grundlegendsten Algorithmen zu übernehmen, denn ein Algorithmus ist der Freund eines Programmierers . Heute werden wir eines dieser Themen ansprechen und Möglichkeiten diskutieren, eine Zeichenfolge umzukehren. Hier ist alles einfach. Das Umkehren einer Zeichenfolge bedeutet, dass die Zeichenfolge rückwärts verschoben wird. Zum Beispiel: JavaRush Forever ->reverof hsuRavaJ Wie kann man also einen String in Java umkehren?

1. StringBuilder/StringBuffer

Der gebräuchlichste und einfachste Weg ist die Verwendung von StringBuilder/StringBuffer :

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

Beste Lösung = einfachste. Wenn man gefragt wird, wie man einen String in Java umkehrt, kommt einem als Erstes folgendes in den Sinn. Aber wir haben vorhin über Algorithmen gesprochen, nicht wahr? Werfen wir einen Blick auf Lösungen, die nicht sofort einsatzbereit sind.

2. Array-Lösung

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;
}

Wir konvertieren unseren String mit der toCharArray -Methode in ein Array . Lassen Sie uns eine for- Schleife vom Ende dieses Arrays durchlaufen und dabei der resultierenden Zeichenfolge Zeichen hinzufügen.

3. Lösung mit charAt

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

In diesem Fall müssen wir den String nicht einmal in ein Array aufteilen, da wir jedes Zeichen mit der String- Klassenmethode – charAt – extrahieren (die for-Schleife ist wiederum umgekehrt, was es uns ermöglicht, Zeichen sequentiell rückwärts zu nehmen).

4. Lösung mit Stack

Die Stack- Klasse wurde schon lange nicht mehr verwendet und sie gilt als veraltet. Dennoch ist es als Referenz hilfreich, sich eine Lösung anzusehen, die sie verwendet:

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;
}

Auch hier verwenden wir toCharArray, um die Zeichenfolge in ein Array aufzuteilen und alles mit einem generischen Typ Character in unserem Stack abzulegen . Als Nächstes beginnen wir damit, Elemente von der Oberseite des Stapels zu übernehmen. Aufgrund der Beschaffenheit des Stapels als LIFO- Struktur – Last In First Out (First In , Last Out) werden Elemente rückwärts genommen und das Ergebnis in der resultierenden Zeile gespeichert .

5. Lösung durch Rekursion

Fast jedes Algorithmusproblem kann durch Rekursion gelöst werden. Und auch hier können wir nicht ohne sie auskommen. Oder auch ohne sie. Schließlich werden wir heute nicht nur eine Methode zur Lösung der Rekursion betrachten, sondern mehrere.

• Methode eins

  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);
  }

  Wir verwenden die Variablen rightStr und leftStr , um die eingehende Zeichenfolge in zwei gleiche Teile aufzuteilen. Als nächstes teilen wir mit dieser Aufteilung die Zeichenfolge in die kleinsten teilbaren Teile (1 Zeichen) auf. Danach beginnt die Rekursion zusammenzubrechen und die Zeichen werden in umgekehrter Reihenfolge zurückgegeben (die Zeichen, die rechts waren, wurden links platziert; die Zeichen, die links waren, wurden rechts platziert).

  Wir dürfen nicht vergessen, dass jede Rekursion ein mehrfacher Aufruf einer Methode und damit ein erheblicher Ressourcenaufwand ist. Nun, wenn es sich um eine Rekursion mit einer unerreichbaren Exit-Bedingung handelt, dann ist dies der Weg ins Unendliche und zum StackOverflowError.

• Methode zwei

  Hier benötigen wir ein zusätzliches Argument im Methodenindex.

  Wenn diese Methode ausgeführt wird, erhält sie eine Zeichenfolgenlänge von -1:

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

  Und die Methode selbst:

  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);
  }

  Unser Index dient als Indikator dafür, welches Zeilenelement wir jetzt verwenden werden (und wir werden die Elemente vom Ende verwenden).

  Daher legen wir Exit-Bedingungen fest, wenn der Index das erste Element erreicht.

Wir addieren die über den Buchstabenindex erhaltenen Werte mit dem Ergebnis der vorherigen Ausführung der Methode und geben das Ergebnis zurück.

• Methode drei

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

  Diese Methode ist im Wesentlichen die einfachste der rekursiven Methoden. Und wie wir uns erinnern: einfach = am besten.

  Bei jedem Lauf geben wir die gleiche Zeichenfolge an, jedoch ohne das erste Element. Wenn die Exit-Bedingung erreicht ist (wenn wir noch ein Zeichen übrig haben), beginnt die Rekursion zusammenzubrechen und das vorherige nicht verwendete Zeichen wird zu jedem nachfolgenden Ergebnis hinzugefügt.

6. Verwendung von XOR

XOR ist eine logische bitweise Operation. Bei zwei Variablen ist das Ergebnis einer Operation genau dann wahr, wenn eines der Argumente wahr und das andere falsch ist. Weitere Informationen zu bitweisen Operationen finden Sie in diesem Artikel . Die nächste Lösung basiert auf der Tatsache, dass:

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

So wird die Methode aussehen:

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;
}

Lassen Sie uns herausfinden, was hier vor sich geht. Wir erstellen ein Array aus der eingehenden Zeichenfolge. Wir erstellen zwei Variablen, low und high , die Indizes zum Durchlaufen des Arrays speichern. Dementsprechend bewegt sich einer vom Anfang zum Ende – wir geben ihm den Wert 0, der zweite – vom Ende zum Anfang, wir setzen ihn arr.length – 1 . Wir treten in eine Schleife ein, die so lange abgespielt wird, wie der Index hoch größer als niedrig ist . Hier beginnen die lustigen Dinge zu passieren – die Verwendung von Exklusiv-ODER. Schauen wir uns x und y als Beispiel an . Angenommen, arr[high] = 'x'; Sein Binärcode lautet 1 1 1 1 0 0 0 Zu diesem Zeitpunkt arr[high] = 'n'; Binärcode - 1 1 0 1 1 1 0 Was wir bei XOR-Operationen in einer Schleife haben werden:

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[high] = (char) (arr[low] ^ arr[high]);

   
   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

Als Ergebnis haben wir dank dieser Operationen die Werte zweier Array-Zellen vertauscht. arr[high] ist so viele Elemente vom Ende des Arrays wie arr[low] vom Anfang. Deshalb tauschen wir einfach die Elemente mit diesen Indizes aus. Zum Beispiel werden bei der ersten Ausführung im Satz „JavaRush für immer“ J und r vertauscht, bei der zweiten - a und e usw. Wenn wir eine ungerade Anzahl von Zeichen haben, dann, wenn wir das Element erreichen, das in der ist In der Mitte werden wir aus der Schleife geworfen (d. h. es besteht keine Notwendigkeit, das mittlere Element zu ändern). Wenn es gerade ist, werden wir nach der Verarbeitung aller Elemente rausgeworfen. Nun, danach gehen wir in eine reguläre Schleife und erstellen aus den Array-Elementen einen String.