Stringa inversa in Java: imparare a invertire le stringhe in diversi modi

È possibile diventare un buon programmatore senza conoscere gli algoritmi? Molto, molto controverso. Sì, puoi trovare lavoro nelle nostre società di outsourcing, perché durante i colloqui fanno domande soprattutto sulla tecnologia. Ma sarai un buon specialista se le tue decisioni saranno piene di stampelle? Se vuoi trasferirti in un’azienda straniera più seria, incontrerai colloqui incentrati principalmente sugli algoritmi. In un modo o nell’altro, vale la pena adottare gli algoritmi più elementari, perché un algoritmo è amico del programmatore . Oggi toccheremo uno di questi argomenti e discuteremo i modi per invertire una stringa. Tutto è semplice qui. Invertire una stringa significa riportare la stringa al contrario. Ad esempio: JavaRush Forever ->reverof hsuRavaJ Quindi, come puoi invertire una stringa in Java?

1. StringBuilder/StringBuffer

Il modo più comune e semplice è utilizzare StringBuilder/StringBuffer :

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

Soluzione migliore = più semplice. Quando ti viene chiesto come invertire una stringa in Java, questa è la prima cosa che dovrebbe venire in mente. Ma prima abbiamo parlato di algoritmi, no? Diamo un'occhiata alle soluzioni che non sono fuori dagli schemi.

2. Soluzione di matrice

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

Convertiamo la nostra stringa in un array utilizzando il metodo toCharArray . Eseguiamo un ciclo for attraverso questo array dalla sua fine, aggiungendo caratteri alla stringa risultante lungo il percorso.

3. Soluzione con 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 questo caso, non dobbiamo nemmeno dividere la stringa in un array, poiché estraiamo ogni carattere utilizzando il metodo della classe String - charAt (il ciclo for, ancora una volta, è inverso, il che ci consente di portare i caratteri in sequenza all'indietro).

4. Soluzione con Stack

La classe Stack non viene utilizzata da molto tempo ed è considerata obsoleta, ma sarà comunque utile, come riferimento, cercare una soluzione che la utilizzi:

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

Anche in questo caso utilizziamo toCharArray per dividere la stringa in un array e inserirla tutta nel nostro Stack con un tipo generico Character . Successivamente, iniziamo a prendere gli elementi dalla cima dello stack. A causa della natura dello stack come struttura LIFO - L ast I n F irst Out (first in, last out), gli elementi verranno ripresi all'indietro e il risultato verrà memorizzato nella riga risultante.

5. Soluzione per ricorsione

Quasi tutti i problemi algoritmici possono essere risolti utilizzando la ricorsione. E anche qui non possiamo fare a meno di lei. O anche senza di loro. Dopotutto, oggi considereremo non solo un metodo per risolvere la ricorsione, ma diversi.

• metodo uno

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

  Usiamo le variabili rightStr e leftStr per dividere la stringa in arrivo in due parti uguali. Successivamente, utilizzando questa suddivisione, dividiamo la stringa nelle parti divisibili più piccole (1 carattere). Successivamente la ricorsione comincia a collassare, restituendo i caratteri nell'ordine inverso (quelli che erano a destra venivano posti a sinistra; quelli che erano a sinistra venivano posti a destra)

  Non dobbiamo dimenticare che ogni ricorsione è una chiamata multipla a un metodo e, di conseguenza, un notevole dispendio di risorse. Bene, se parliamo di ricorsione con una condizione di uscita irraggiungibile, allora questo è il percorso verso l'infinito e verso StackOverflowError.

• metodo due

  Qui abbiamo bisogno di un argomento aggiuntivo nel metodo: indice.

  Quando viene eseguito questo metodo, gli viene assegnata una lunghezza di stringa pari a -1:

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

  E il metodo stesso:

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

  Il nostro indice serve come indicatore di quale elemento di riga utilizzeremo ora (e utilizzeremo gli elementi dalla fine).

  Pertanto, impostiamo le condizioni di uscita quando l'indice raggiunge il primo elemento.

Sommiamo i valori ottenuti utilizzando l' indice delle lettere con il risultato della precedente esecuzione del metodo e restituiamo il risultato.

• metodo tre

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

  Questo metodo è essenzialmente il più semplice tra quelli ricorsivi. E come ricordiamo, semplice = migliore.

  Durante ogni esecuzione specifichiamo la stessa stringa, ma senza il primo elemento. Quando viene raggiunta la condizione di uscita (quando ci rimane un carattere), la ricorsione inizia a collassare e il precedente carattere inutilizzato verrà aggiunto a ogni risultato successivo.

6. Utilizzo di XOR

XOR è un'operazione logica bit a bit. Nel caso di due variabili, il risultato di un'operazione è vero se e solo se uno degli argomenti è vero e l'altro è falso. Puoi leggere ulteriori informazioni sulle operazioni bit a bit in questo articolo . La prossima soluzione si baserà sul fatto che:

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

Come sarà il metodo:

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

Scopriamo cosa sta succedendo qui. Creiamo un array dalla stringa in arrivo. Creiamo due variabili, low e high , che memorizzano gli indici per attraversare l'array. Di conseguenza, uno si sposterà dall'inizio alla fine - gli diamo il valore 0, il secondo - dalla fine all'inizio, lo impostiamo arr.length - 1 . Entriamo in un loop che verrà riprodotto finché l'indice alto sarà maggiore del basso . È qui che iniziano ad accadere le cose divertenti: l'uso della sala operatoria esclusiva. Consideriamo xey come esempio . Supponiamo che arr[high] = 'x'; Il suo codice binario sarà 1 1 1 1 0 0 0 In questo momento arr[high] = 'n'; Codice binario - 1 1 0 1 1 1 0 Cosa avremo nelle operazioni XOR in un ciclo:

1. arr[basso] = (char) (arr[basso] ^ arr[alto]);

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

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

   
   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

Di conseguenza, grazie a queste operazioni, abbiamo scambiato i valori di due celle dell'array. arr[high] contiene tanti elementi dalla fine dell'array quanti sono arr[low] dall'inizio. Pertanto, scambiamo semplicemente gli elementi con questi indici. Ad esempio, alla prima esecuzione nella frase "JavaRush Forever" J e r verranno scambiati, alla seconda - a ed e , ecc. Se abbiamo un numero dispari di caratteri, quando raggiungiamo l'elemento che si trova nella middle, verremo espulsi dal ciclo (ovvero non è necessario modificare l'elemento centrale). Se è pari, verremo espulsi dopo aver elaborato tutti gli elementi. Bene, dopodiché entriamo in un ciclo regolare e creiamo una stringa dagli elementi dell'array.