Question

java 实现字符串反转，要求时间和空间复杂度最优

比如”abcdef“反转后为“fedcba”，最重要的是时间和空间复杂度的优化。
我的想法是，设置循环，从0开始，到字符串长度的一半，遍历，将第一个和第length-i-1个互换，交换的方法采用不引入第三方的方法，但是整形数据可以采用（a,b,a=a+b,b=a-b,a=a-b),但是字符的话就不会了，求解。

Answer 1

不知为何你有这种想法，如果有好的算法可以和我讨论下，下面我写了2个代码希望能帮到你。

package app;
public class TransDemo {
//abcdef“反转后为“fedcba
public static void main(String[] args){
String str = "abcdef";
char[] ary = str.toCharArray();

for(int i = 0; i< str.length()/2; i++){
int temp = ary[ary.length-i-1]-ary[i];
ary[i] += temp;
ary[ary.length-i-1] -=temp;
}
str = new String(ary);
System.out.println(str);

}
}

package app;
public class TransDemo {
//abcdef“反转后为“fedcba
public static void main(String[] args){
String str = "abcdef";
char[] ary = str.toCharArray();

for(int i = 0; i< str.length()/2; i++){
char c = ary[i];
ary[i] = ary[str.length()-1-i];
ary[str.length()-1-i] = c;
}
str = new String(ary);
System.out.println(str);

}
}

追问

你这两个算是差不多一样吧，而且互换位置引入了第三方变量，如果不引入第三方变量不是也可以实现互换位置吗，这样空间复杂度不是可以得到优化吗？

追答

看一个算好坏主要看时间复杂度。假设字符串足够大了，就忽略了空间复杂度，而主要看时间复杂度，判断你的程序算法好坏也是从时间复杂度来计算了。
如果感兴趣请看数据结构和算法设计.
时间复杂度呢，可能你的想法空间复杂度是小的，可是时间复杂度却多了。，且现在的程序主要是看时间复杂度。引入第三方是我学过算法设计中的实现反转的最好的办法.

追问

题目要求是要结合时间复杂度和空间复杂度，你应该再看看题目

Answer 2

StringBuffer和StringBuilder都自带反转的方法reverse（），再toString（）即可。

追问

要求自己写一个，主要是考察算法的。

追答

public String reverse(String s){

StringBuilder sb=new StringBuilder();

for(int i=0;i<s.length();i++){

sb.append(s.charAt(s.length()-i-1));

}

return sb.toString();

}

Answer 3

char c1='a';
char c2='b';
c1=c1+=c2;
c2=(char)(c1-c2);
c1=c1-=c2;

追问

你有没有试过，这样写，编译不能通过

追答

编译是绝对可以通过的.
char类型是可以直接进行加减运算的

追问

public static String swap(String s){

char[] ch=s.toCharArray();
for(int i=0;i<ch.length/2;i++){
char c1=ch[i];
char c2=ch[ch.length-i-1];
c1=(char) (c1+c2);
c2=(char) (c1-c2);
c1=(char) (c1-c2);
}
return new String(ch);
}
public static void main(String[] args) {
String str="abcdefgh";
str=swap(str);
System.out.println(str);
}
请问我这个哪错了？

追答

你这个中间有问题啊.你只是把c1跟c2换过来了,但是ch[i]跟ch[ch.length-i-1]并没有换啊.

Answer 4

char 就是 int。无所谓文字还是数字

追问

你这样说太笼统了

Answer 5

这道题考的是字符串的算法 洗牌算法
思路大概是：令A = " ab " B = " cdef " C = " abcdef "

则 A' = " (ab)' " = " ba " B' = " (cdef)' " = " fedc "
故 由线代里矩阵转置的定理可得：
C' = (AB)' = B'A' = fedcba
算法不用多说了吧，Java里由反转的方法，可以直接引用。重点是了解一下洗牌算法最简单的一个例子。