Каков наиболее эффективный способ изменить строку на Java? Должен ли я использовать какой-то оператор xor? Легким способом было бы положить все символы в стек и снова вернуть их в строку, но я сомневаюсь, что это очень эффективный способ сделать это.
И, пожалуйста, не говорите мне использовать какую-либо встроенную функцию в Java. Мне интересно узнать, как сделать это, чтобы не использовать эффективную функцию, но не зная, почему она эффективна или как она создана.
Вы говорите, что хотите узнать наиболее эффективный способ, и вы не хотите знать какой-то стандартный встроенный способ сделать это. Тогда я говорю вам: RTSL (читайте источник, luke):
Проверьте исходный код AbstractStringBuilder # reverse, который вызывается StringBuilder # reverse. Бьюсь об заклад, это делает некоторые вещи, которые вы бы не рассмотрели для надежной обратной операции.
Ниже не рассматриваются суррогатные пары 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);
}
Вы сказали, что не хотите делать это легко, но для тех, кто использует Google, вы должны использовать StringBuilder.reverse:
String reversed = new StringBuilder(s).reverse().toString();
Если вам нужно реализовать его самостоятельно, перейдите по символам в обратном порядке и добавьте их в StringBuilder. Вы должны быть осторожны, если есть (или могут быть) суррогатные пары, поскольку они не должны быть отменены. Вышеуказанный метод делает это автоматически, поэтому вы должны использовать его, если это возможно.
Старый пост и вопрос, однако, не видели ответов, относящихся к рекурсии. Рекурсивный метод реверсирует данную строку s, не передавая встроенные функции jdk
public static String reverse(String s) {
if (s.length() <= 1) {
return s;
}
return reverse(s.substring(1)) + s.charAt(0);
}
`
Самый быстрый способ - использовать метод 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);
}
Вы также можете запустить половину длины массива и поменять символы, проверки, вероятно, замедляют работу.
Я не совсем уверен, что вы имеете в виду, когда говорите, что вам нужен эффективный алгоритм.
Способы изменения строки, о которой я могу думать (все они уже упоминаются в других ответах):
Используйте стек (ваша идея).
Создайте новую переменную String, добавив символы по порядку в обратном порядке от исходной строки к пустой строке String/StringBuilder/ char [].
Обменивать все символы в первой половине строки с ее соответствующей позицией в последней половине (т.е. i-й символ обменивается с (длиной-i-1) -им символом).
Дело в том, что все они имеют одинаковую сложность выполнения: O (N). Таким образом, на самом деле нельзя утверждать, что любой из них значительно лучше других для очень больших значений N (т.е. очень больших строк).
У третьего метода есть что-то для этого, другие два требуют O (N) дополнительного пространства (для стека или новой строки), тогда как он может выполнять свопы. Но Строки неизменны в Java, поэтому вам нужно выполнить свопы на вновь созданной StringBuilder/ char [], и, таким образом, вам нужно дополнительное пространство O (N).
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]);
}
}
}
Я думаю, что если у вас ДЕЙСТВИТЕЛЬНО нет проблем с производительностью, вы должны просто пойти с самым читаемым решением, которое:
StringUtils.reverse("Hello World");
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);
}
Если вы не хотите использовать какую-либо встроенную функцию, вам нужно вернуться со строкой к ее составным частям: массив символов.
Теперь вопрос становится наиболее эффективным способом обращения к массиву? Ответ на этот вопрос на практике также зависит от использования памяти (для очень больших строк), но теоретически эффективность в этих случаях измеряется в доступе к массиву.
Самый простой способ - создать новый массив и заполнить его значениями, которые вы встречаете при обратном итерации по исходному массиву, и возврату нового массива. (Хотя с временной переменной вы также можете сделать это без дополнительного массива, как в ответе Саймона Никерсона).
Таким образом вы получаете доступ к каждому элементу ровно один раз для массива с n элементами. Таким образом, получается эффективность O (n).
Я бы просто сделал это без использования какой-либо одной функции утилиты. Достаточно класс 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 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();
}
}
Проверьте это. Ура!!
Использование строки:
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);
Один вариант может быть, заменяя элементы.
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(String[] args){
String string ="abcdefghijklmnopqrstuvwxyz";
StringBuilder sb = new StringBuilder(string);
sb.reverse();
System.out.println(sb);
}
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;
}
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
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();
}
Использование нескольких потоков для замены элементов:
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);
Конечно это самый эффективный способ:
String reversed = new StringBuilder(str).reverse().toString();
Но если вам не нравится это, я рекомендую это:
public String reverseString(String str)
{
String output = "";
int len = str.length();
for(int k = 1; k <= str.length(); k++, len--)
{
output += str.substring(len-1,len);
}
return output;
}
static String ReverseString(String input) {
var len = input.Length - 1;
int i = 0;
char[] revString = new char[len+1];
while (len >= 0) {
revString[i] = input[len];
len--;
i++;
}
return new string(revString);
}
почему мы не можем придерживаться простейшего цикла и почитать с чтением символов и продолжать добавлять в массив символов, я наткнулся на интервью с доской, где интервьюер установил ограничения на то, чтобы не использовать StringBuilder и встроенные функции.
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();
}