Quel est l’algorithme le plus efficace pour inverser une chaîne en Java?

Quel est le moyen le plus efficace d’inverser une chaîne en Java? Dois-je utiliser une sorte d’opérateur xor? Le moyen le plus simple serait de mettre tous les caractères dans une stack et de les replacer dans une chaîne, mais je doute que ce soit un moyen très efficace de le faire.

Et s’il vous plaît ne me dites pas d’utiliser une fonction intégrée en Java. Je suis intéressé à apprendre à le faire pour ne pas utiliser une fonction efficace, mais ne sachant pas pourquoi c’est efficace ou comment il est construit.

Vous dites que vous voulez connaître le moyen le plus efficace et que vous ne voulez pas connaître la manière standard de le faire. Alors je vous dis: RTSL (lisez la source, luke):

Consultez le code source de AbstractSsortingngBuilder # reverse , qui est appelé par SsortingngBuilder # reverse. Je parie que cela fait des choses que vous n’auriez pas considérées comme une opération inverse robuste.

Ce qui suit ne traite pas des paires de substitution UTF-16.

public static Ssortingng reverse(Ssortingng orig) { char[] s = orig.toCharArray(); int n = s.length; int halfLength = n / 2; for (int i=0; i 

Vous avez dit que vous ne voulez pas le faire facilement, mais pour ceux qui cherchent Google, vous devez utiliser SsortingngBuilder.reverse :

 Ssortingng reversed = new SsortingngBuilder(s).reverse().toSsortingng(); 

Si vous devez l’implémenter vous-même, parcourez les caractères dans l’ordre inverse et ajoutez-les à un SsortingngBuilder. Vous devez faire attention s’il y a (ou peut être) des paires de substitution, car elles ne devraient pas être inversées. La méthode indiquée ci-dessus le fait automatiquement pour vous, c’est pourquoi vous devriez l’utiliser si possible.

Un vieux post et une question, mais toujours pas vu les réponses concernant la récursion. Méthode récursive inverse la chaîne donnée s, sans relayer sur les fonctions jdk intégrées

  public static Ssortingng reverse(Ssortingng s) { if (s.length() <= 1) { return s; } return reverse(s.substring(1)) + s.charAt(0); } 

`

Le moyen le plus rapide consiste à utiliser la méthode reverse() sur les classes SsortingngBuilder ou SsortingngBuffer 🙂

Si vous souhaitez l’implémenter vous-même, vous pouvez obtenir le tableau de caractères, allouer un second tableau de caractères et déplacer les caractères. Dans le pseudo-code, cela ressemblerait à ceci:

 Ssortingng reverse(Ssortingng str) { char[] c = str.getCharArray char[] r = new char[c.length]; int end = c.length - 1 for (int n = 0; n <= end; n++) { r[n] = c[end - n]; } return new String(r); } 

Vous pouvez également exécuter la moitié de la longueur du tableau et échanger les caractères, les vérifications impliquées ralentissant probablement les choses.

Je ne suis pas vraiment sûr de ce que vous voulez dire quand vous dites que vous avez besoin d’un algorithme efficace .

Les manières d’inverser une chaîne à laquelle je peux penser sont (elles sont toutes déjà mentionnées dans d’autres réponses):

  1. Utilisez une stack (votre idée).

  2. Créez une nouvelle chaîne inversée en ajoutant des caractères un par un dans l’ordre inverse de la chaîne d’origine à une chaîne vide Ssortingng / SsortingngBuilder / char [].

  3. Échangez tous les caractères dans la première moitié de la chaîne avec la position correspondante dans la dernière moitié (c.-à-d. Que le ieme caractère est échangé avec le (longueur-i-1) ème caractère).

Le fait est qu’ils ont tous la même complexité d’exécution : O (N). Ainsi, on ne peut pas vraiment affirmer que quiconque est significativement meilleur que les autres pour de très grandes valeurs de N (c’est-à-dire de très grandes chaînes).

La troisième méthode a une chose pour elle, les deux autres nécessitent O (N) un espace supplémentaire (pour la stack ou la nouvelle chaîne), alors qu’elle peut effectuer des échanges sur place. Mais les chaînes de caractères sont immuables en Java, vous devez donc effectuer des permutations sur un object SsortingngBuilder / char [] nouvellement créé et avoir donc besoin d’un espace supplémentaire O (N).

 public class ReverseInPlace { static char[] str=null; public static void main(Ssortingng s[]) { if(s.length==0) System.exit(-1); str=s[0].toCharArray(); int begin=0; int end=str.length-1; System.out.print("Original ssortingng="); for(int i=0; i
		      	

Je pense que si vous n’avez VRAIMENT pas de problème de performance, vous devriez simplement choisir la solution la plus lisible qui soit:

 SsortingngUtils.reverse("Hello World"); 

Si vous ne voulez utiliser aucune fonction intégrée, vous devez revenir à la chaîne avec ses composants: un tableau de caractères.

Maintenant, la question est de savoir quel est le moyen le plus efficace d’inverser un tableau. Dans la pratique, la réponse à cette question dépend également de l’utilisation de la mémoire (pour les très grandes chaînes), mais en théorie, l’efficacité est mesurée dans les cas d’access aux tableaux.

Le moyen le plus simple consiste à créer un nouveau tableau et à le remplir avec les valeurs que vous rencontrez lors de l’itération inverse sur le tableau d’origine et de renvoyer le nouveau tableau. (Bien qu’avec une variable temporaire, vous pouvez également le faire sans tableau supplémentaire, comme dans la réponse de Simon Nickersons).

De cette façon, vous accédez à chaque élément exactement une fois pour un tableau avec n éléments. Donnant ainsi une efficacité de O (n).

 char* rev(char* str) { int end= strlen(str)-1; int start = 0; while( start 

=========================

Vous vous demandez comment ça marche?

Première opération:

 x1 = x1 XOR x2 x1: 1 0 0 x2: 1 1 1 New x1: 0 1 1 

Deuxième opération

 x2 = x2 XOR x1 x1: 0 1 1 x2: 1 1 1 New x2: 1 0 0 //Notice that X2 has become X1 now 

Troisième opération:

 x1 = x1 XOR x2 x1: 0 1 1 x2: 1 0 0 New x1: 1 1 1 //Notice that X1 became X2 
 private static Ssortingng reverse(Ssortingng str) { int i = 0; int j = str.length()-1; char []c = str.toCharArray(); while(i <= j){ char t = str.charAt(i); c[i] = str.charAt(j); c[j]=t; i++; j--; } return new String(c); } 

Je le ferais simplement de cette façon sans utiliser une seule fonction util. Juste la classe Ssortingng est suffisante.

 public class MySsortingngUtil { public static void main(Ssortingng[] args) { Ssortingng reversedSsortingng = reverse("SsortingngToReverse"); System.out.println("Reversed Ssortingng : " + reversedSsortingng); } /** * Reverses the given ssortingng and returns reversed ssortingng * * @param s Input Ssortingng * @returns reversed ssortingng */ private static Ssortingng reverse(Ssortingng s) { char[] charArray = s.toCharArray(); // Returns the Ssortingng's internal character array copy int j = charArray.length - 1; for (int i = 0; charArray.length > 0 && i < j; i++, j--) { char ch = charArray[i]; charArray[i] = charArray[j]; charArray[j] = ch; } return charArray.toString(); } } 

Vérifie ça. À votre santé!!

Utiliser une chaîne:

 Ssortingng abc = "abcd"; int a= abc.length(); Ssortingng reverse=""; for (int i=a-1;i>=0 ;i--) { reverse= reverse + abc.charAt(i); } System.out.println("Reverse of Ssortingng abcd using invert array is :"+reverse); 

Utilisation de SsortingngBuilder:

  Ssortingng abc = "abcd"; int a= abc.length(); SsortingngBuilder sb1 = new SsortingngBuilder(); for (int i=a-1;i>=0 ;i--) { sb1= sb1.append(abc.charAt(i)); } System.out.println("Reverse of Ssortingng abcd using SsortingngBuilder is :"+sb1); 

Une variante peut consister à échanger les éléments.

 int n = length - 1; char []strArray = str.toCharArray(); for (int j = 0; j < n; j++) { char temp = strArray[j]; char temp2 = strArray[n]; strArray[j] = temp2; strArray[n] = temp; n--; } 
 public static void main(Ssortingng[] args){ Ssortingng ssortingng ="abcdefghijklmnopqrstuvwxyz"; SsortingngBuilder sb = new SsortingngBuilder(ssortingng); sb.reverse(); System.out.println(sb); } 
 public static Ssortingng Reverse(Ssortingng word){ Ssortingng temp = ""; char[] arr = word.toCharArray(); for(int i = arr.length-1;i>=0;i--){ temp = temp+arr[i]; } return temp; } 
 public static ssortingng getReverse(ssortingng str) { char[] ch = str.ToCharArray(); ssortingng reverse = ""; for (int i = str.Length - 1; i > -1; i--) { reverse += ch[i]; } return reverse; } //using in-built method reverse of Array public static ssortingng getReverseUsingBulidingFunction(ssortingng str) { char[] s = str.ToCharArray(); Array.Reverse(s); return new ssortingng(s); } public static void Main(ssortingng[] args) { ssortingng str = "123"; Console.WriteLine("The reverse ssortingng of '{0}' is: {1}",str,getReverse(str)); Console.WriteLine("The reverse ssortingng of '{0}' is: {1}", str, getReverseUsingBulidingFunction(str)); Console.ReadLine(); } 

Utiliser plusieurs threads pour échanger les éléments:

  final char[] strArray = str.toCharArray(); IntStream.range(0, str.length() / 2).parallel().forEach(e -> { final char tmp = strArray[e]; strArray[e] = strArray[str.length() - e - 1]; strArray[str.length() - e - 1] = tmp; }); return new Ssortingng(strArray); 
 public static Ssortingng reverseSsortingng(Ssortingng str) { SsortingngBuilder sb = new SsortingngBuilder(); for (int i = str.length() - 1; i >= 0; i--) { sb.append(str[i]); } return sb.toSsortingng(); }