Inverser la chaîne en Java : apprendre à inverser les chaînes de différentes manières

Est-il possible de devenir un bon programmeur sans connaître les algorithmes ? Très, très controversé. Oui, vous pouvez trouver un emploi dans nos sociétés d'externalisation, car lors des entretiens, elles posent principalement des questions sur la technologie. Mais serez-vous un bon spécialiste si vos décisions se font avec des béquilles ? Si vous souhaitez évoluer vers une entreprise étrangère plus sérieuse, vous rencontrerez des entretiens essentiellement axés sur les algorithmes. D’une manière ou d’une autre, cela vaut la peine d’adopter les algorithmes les plus élémentaires, car un algorithme est l’ami du programmeur . Aujourd'hui, nous aborderons l'un de ces sujets et discuterons des moyens d'inverser une chaîne. Tout est simple ici. Inverser une chaîne revient à faire reculer la chaîne. Par exemple : JavaRush Forever ->reverof hsuRavaJ Alors, comment inverser une chaîne en Java ?

1. StringBuilder/StringBuffer

La manière la plus courante et la plus simple consiste à utiliser StringBuilder/StringBuffer :

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

Meilleure solution = la plus simple. Lorsqu'on lui demande comment inverser une chaîne en Java, c'est la première chose qui devrait nous venir à l'esprit. Mais nous avons parlé d’algorithmes plus tôt, n’est-ce pas ? Jetons un coup d'œil aux solutions qui ne sortent pas des sentiers battus.

2. Solution matricielle

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

Nous convertissons notre chaîne en tableau en utilisant la méthode toCharArray . Exécutons une boucle for dans ce tableau à partir de sa fin, en ajoutant des caractères à la chaîne résultante en cours de route.

3. Solution avec charAt

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

Dans ce cas, nous n'avons même pas besoin de diviser la chaîne en un tableau, puisque nous extrayons chaque caractère à l'aide de la méthode de classe String - charAt (la boucle for, encore une fois, est inversée, ce qui nous permet de prendre les caractères séquentiellement en arrière).

4. Solution avec Stack

Personne n'utilise la classe Stack depuis longtemps, et elle est considérée comme obsolète, mais néanmoins, pour référence, il sera utile de regarder une solution l'utilisant :

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

Ici encore, nous utilisons toCharArray pour diviser la chaîne en un tableau et mettre le tout dans notre Stack avec un type générique Character . Ensuite, nous commençons à prendre les éléments du haut de la pile. En raison de la nature de la pile en tant que structure LIFO - L ast I n F irst Out (premier entré, dernier sorti), les éléments seront repris à l'envers et le résultat sera stocké dans la ligne résultante.

5. Solution par récursion

Presque tous les problèmes d’algorithme peuvent être résolus par récursivité. Et ici aussi, nous ne pouvons pas nous passer d'elle. Ou même sans eux. Après tout, nous examinerons aujourd'hui non pas une seule méthode de résolution de la récursivité, mais plusieurs.

• première méthode

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

  Nous utilisons les variables rightStr et leftStr pour diviser la chaîne entrante en deux parties égales. Ensuite, en utilisant cette division, nous divisons la chaîne en plus petites parties divisibles (1 caractère). Ensuite, la récursion commence à s'effondrer, renvoyant les caractères dans l'ordre inverse (ceux qui étaient à droite ont été placés à gauche ; ceux qui étaient à gauche ont été placés à droite)

  Il ne faut pas oublier que chaque récursion est un appel multiple à une méthode, et par conséquent une dépense de ressources considérable. Eh bien, si nous parlons de récursivité avec une condition de sortie inaccessible, alors c'est le chemin vers l'infini et vers StackOverflowError.

• deuxième méthode

  Ici, nous avons besoin d'un argument supplémentaire dans la méthode - index.

  Lorsque cette méthode est exécutée, une longueur de chaîne de -1 lui est attribuée :

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

  Et la méthode elle-même :

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

  Notre index sert d'indicateur pour savoir quel élément de ligne nous utiliserons maintenant (et nous utiliserons les éléments de la fin).

  Par conséquent, nous définissons des conditions de sortie lorsque l'index atteint le premier élément.

Nous ajoutons les valeurs obtenues à l'aide de l' index des lettres avec le résultat de l'exécution précédente de la méthode et renvoyons le résultat.

• méthode trois

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

  Cette méthode est essentiellement la plus simple des méthodes récursives. Et comme on s’en souvient, simple = meilleur.

  Lors de chaque exécution, nous spécifions la même chaîne, mais sans le premier élément. Lorsque la condition de sortie est atteinte (quand il nous reste un caractère), la récursion commence à s'effondrer et le caractère inutilisé précédent sera ajouté à chaque résultat suivant.

6. Utiliser XOR

XOR est une opération logique au niveau du bit. Dans le cas de deux variables, le résultat d’une opération est vrai si et seulement si l’un des arguments est vrai et l’autre est faux. Vous pouvez en savoir plus sur les opérations au niveau du bit dans cet article . La prochaine solution reposera sur le fait que :

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

À quoi ressemblera la méthode :

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

Voyons ce qui se passe ici. Nous créons un tableau à partir de la chaîne entrante. Nous créons deux variables, low et high , qui stockent les index pour parcourir le tableau. En conséquence, l'un se déplacera du début à la fin - nous lui donnons la valeur 0, le second - de la fin au début, nous le définissons arr.length - 1 . Nous entrons dans une boucle qui jouera tant que l'indice high sera supérieur à low . C'est là que les choses amusantes commencent à se produire : l'utilisation du OU exclusif. Prenons l'exemple de x et y . Supposons que arr[high] = 'x'; Son code binaire sera 1 1 1 1 0 0 0 A ce moment arr[high] = 'n'; Code binaire - 1 1 0 1 1 1 0 Ce que nous aurons dans les opérations XOR en boucle :

1. arr[faible] = (char) (arr[faible] ^ arr[élevé]);

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

   
   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[faible] = (char) (arr[faible] ^ arr[élevé]);

   
   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

En conséquence, grâce à ces opérations, nous avons échangé les valeurs de deux cellules du tableau. arr[high] contient autant d'éléments de la fin du tableau que arr[low] du début. Par conséquent, nous échangeons simplement les éléments avec ces indices. Par exemple, lors de la première exécution de la phrase « JavaRush Forever », J et r seront échangés, lors de la seconde - a et e , etc. Si nous avons un nombre impair de caractères, alors lorsque nous atteignons l'élément qui se trouve dans le milieu, nous serons expulsés de la boucle (c'est-à-dire qu'il n'est pas nécessaire de changer l'élément du milieu). Si c’est égal, nous serons expulsés après avoir traité tous les éléments. Eh bien, après cela, nous entrons dans une boucle régulière et construisons une chaîne à partir des éléments du tableau.