Каков наиболее эффективный алгоритм для обращения к String в Java?

Question

Каков наиболее эффективный способ изменить строку на Java? Должен ли я использовать какой-то оператор xor? Легким способом было бы поместить все символы в стек и снова вернуть их в строку, но я сомневаюсь, что это очень эффективный способ сделать это.

И, пожалуйста, не говорите мне использовать встроенную функцию в Java. Мне интересно узнать, как сделать это, чтобы не использовать эффективную функцию, но не зная, почему она эффективна или как она создана.

Answer 1

Вы говорите, что вы хотите знать наиболее эффективный способ, и вы не хотите знать некоторые стандартные встроенный способ сделать это. Тогда я говорю вам: RTSL (читайте источник, luke):

Проверьте исходный код AbstractStringBuilder#reverse, который вызывается StringBuilder # reverse. Бьюсь об заклад, это некоторые вещи, которые вы бы не рассмотрели для надежной обратной операции.

Answer 2

Вы сказали, что вы не хотите, чтобы сделать это легкий путь, но для тех, кто погуглить вы должны использовать StringBuilder.reverse:

String reversed = new StringBuilder(s).reverse().toString(); 

Если вам нужно реализовать его самостоятельно, а затем перебрать символы в обратном порядке и добавьте их в StringBuilder. Вы должны быть осторожны, если есть (или могут быть) суррогатные пары, поскольку они не должны быть отменены. Вышеуказанный метод делает это автоматически, поэтому вы должны использовать его, если это возможно.

Answer 3

Следующие не имеют суррогатных пар UTF-16.

public static String reverse(String orig) 
{ 
    char[] s = orig.toCharArray(); 
    int n = s.length; 
    int halfLength = n/2; 
    for (int i=0; i<halfLength; i++) 
    { 
     char temp = s[i]; 
     s[i] = s[n-1-i]; 
     s[n-1-i] = temp; 
    } 
    return new String(s); 
} 

Answer 4

Самый быстрый способ будет использовать метод reverse() на StringBuilder или StringBuffer классов :)

Если вы хотите реализовать его самостоятельно, вы можете получить массив символов, выделить второй массив символов и переместить символы , в псевдокоде это будет примерно так:

String reverse(String 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); 
} 

Вы также можете запустить половину длины массива и поменять местами символы, проверки, связанные медленные вещи вниз, вероятно.

Answer 5

Если вы не хотите использовать какую-либо встроенную функцию, вам нужно вернуться со строкой к ее составным частям: массив символов.

Теперь вопрос становится тем, что является наиболее эффективным способом обращения вспять массива? Ответ на этот вопрос на практике также зависит от использования памяти (для очень больших строк), но теоретически эффективность в этих случаях измеряется в доступе к массиву.

Самый простой способ - создать новый массив и заполнить его значениями, которые вы встречаете, при обратном итерации по исходному массиву и возврату нового массива. (Хотя с временной переменной вы также можете сделать это без дополнительного массива, как в ответе Саймона Никерсона).

Таким образом вы получаете доступ к каждому элементу ровно один раз для массива с n элементами. Таким образом, получается эффективность O (n).

Answer 6

Я не совсем уверен, что вы имеете в виду, когда говорите, что вам нужен эффективный алгоритм.

Способы реверсирования строки, я могу думать, являются (все они уже упоминалось в других ответах):

1. использовать стек (ваша идея).

2. Создайте новую обратную строку, добавив символы поочередно в обратном порядке от исходной строки к пустой строке String/StringBuilder/char [].

3. Обмен всеми символами в первой половине строки со своей соответствующей позицией в последней половине (то есть i-й символ заменяется символом (длиной-i-1) -го символа).

Дело в том, что все они имеют один и тот же выполнения сложности: O (N). Таким образом, на самом деле нельзя утверждать, что любой из них значительно лучше других для очень больших значений N (т.е. очень больших строк).

У третьего метода есть что-то для этого, другие два требуют O (N) дополнительного пространства (для стека или новой строки), в то время как он может выполнять свопы на месте. Но Строки неизменны в Java, поэтому вам нужно выполнить свопы на вновь созданной StringBuilder/char [], и в итоге вам понадобится дополнительное пространство O (N).

Answer 7

public class ReverseInPlace { 

    static char[] str=null; 

    public static void main(String s[]) { 
     if(s.length==0) 
     System.exit(-1); 

     str=s[0].toCharArray(); 

     int begin=0; 
     int end=str.length-1; 

     System.out.print("Original string="); 
     for(int i=0; i<str.length; i++){ 
     System.out.print(str[i]); 
     } 

     while(begin<end){ 
      str[begin]= (char) (str[begin]^str[end]); 
      str[end]= (char) (str[begin]^str[end]); 
      str[begin]= (char) (str[end]^str[begin]); 

      begin++; 
      end--;  
     } 

     System.out.print("\n" + "Reversed string="); 
     for(int i=0; i<str.length; i++){ 
     System.out.print(str[i]); 
     } 

    } 
} 

Answer 8

старый пост & вопрос, однако до сих пор не видел ответы, относящиеся к рекурсии. Рекурсивный метод обратной заданной строки с, без ретрансляции на встроенных функций JDK

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

`

Answer 9

Использование Строка:

String abc = "abcd"; 
int a= abc.length(); 

String reverse=""; 

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

Использование StringBuilder:

String abc = "abcd"; 
    int a= abc.length(); 
    StringBuilder sb1 = new StringBuilder(); 

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

Answer 10

Один из вариантов может быть , заменяя элементы.

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

Answer 11

public static void main(String[] args){ 
    String string ="abcdefghijklmnopqrstuvwxyz"; 
    StringBuilder sb = new StringBuilder(string); 
    sb.reverse(); 

    System.out.println(sb); 
} 

Answer 12

public static String Reverse(String word){ 
     String temp = ""; 
     char[] arr = word.toCharArray(); 
     for(int i = arr.length-1;i>=0;i--){ 
      temp = temp+arr[i]; 
     } 
     return temp; 
    } 

Answer 13

Я думаю, что если вы действительно не имеете проблем с производительностью, вы должны просто идти с наиболее читаемым раствором, который является:

StringUtils.reverse("Hello World"); 

Answer 14

Я бы просто сделать это таким без использования какой-либо одной функции утилиты. Достаточно класс String.

public class MyStringUtil { 

    public static void main(String[] args) { 
     String reversedString = reverse("StringToReverse"); 
     System.out.println("Reversed String : " + reversedString); 
    } 

    /** 
    * Reverses the given string and returns reversed string 
    * 
    * @param s Input String 
    * @returns reversed string 
    */ 
    private static String reverse(String s) { 
     char[] charArray = s.toCharArray(); // Returns the String'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(); 
    } 
} 

Проверьте его. Ура !!

Answer 15

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

    while(start<end) 
    { 
    str[start] ^= str[end]; 
    str[end] ^= str[start]; 
    str[start]^= str[end]; 

    ++start; 
    --end; 
    } 

    return str; 
} 

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

Хотите знать, как это работает?

Первая операция:

x1 = x1 XOR x2 

x1: 1 0 0 
x2: 1 1 1 
New x1: 0 1 1 

Вторая операция

x2 = x2 XOR x1 

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

Третья операция:

x1 = x1 XOR x2 
x1: 0 1 1 
x2: 1 0 0 
New x1: 1 1 1 
//Notice that X1 became X2 

Answer 16

public static string getReverse(string str) 
{ 
    char[] ch = str.ToCharArray(); 
    string reverse = ""; 
    for (int i = str.Length - 1; i > -1; i--) 
    { 
     reverse += ch[i]; 
    } 
    return reverse; 
} 

//using in-built method reverse of Array 
public static string getReverseUsingBulidingFunction(string str) 
{ 
    char[] s = str.ToCharArray(); 
    Array.Reverse(s); 
    return new string(s); 
} 


public static void Main(string[] args) 
{ 
    string str = "123"; 
    Console.WriteLine("The reverse string of '{0}' is: {1}",str,getReverse(str)); 
    Console.WriteLine("The reverse string of '{0}' is: {1}", str, getReverseUsingBulidingFunction(str)); 
    Console.ReadLine(); 
} 

Answer 17

public static String reverseString(String str) 
{ 
    StringBuilder sb = new StringBuilder(); 

    for (int i = str.length() - 1; i >= 0; i--) 
    { 
     sb.append(str[i]); 
    } 

    return sb.toString(); 
} 

Answer 18

private static String reverse(String 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); 
} 

Answer 19

Использование нескольких потоков для замены элементов:

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 String(strArray);