编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
//输入一个字符串，输出它的倒序字符串
input: Hello
output: olleH
反转字符串，确实没什么难度，但是我无意间搜索了一下，才发现这么一个看似简单的反转算法实现起来真可谓花样繁多。这里我们尽可能分别总结介绍一下。
1. 使用字符数组倒序输出
最常规的解法，也是最容易想到的一种方法就是使用字符数组倒序输出。
具体思路是：倒序遍历字符串字符循环给char数组赋值
public static String strReverseWithArray(String string) {
if (string == null || string.length() == 0) return string;
char[] array = new char[string.length()];
for (int i = 0; i < string.length(); i++) {
array[i] = string.charAt(string.length() - i - 1);
}
return new String(array);
}
优化：
分析上面这种解法，循环遍历时，我们其实不需要循环这么多次。每次循环的时候，我们应该直接给前、后位置（第一个和最后一个，第二个和倒数第二个）交换。也就是说我们不必对这个字符数组进行完全遍历，通常情况下我们会只遍历一半同时交换中轴前后两个元素就可以了。
public static String strReverseWithArray(String string) {
if (string == null || string.length() == 0) return string;
char[] array = string.toCharArray();
//注意这里中间的位置计算
for (int i = 0; i < Math.ceil(string.length() / 2.0f); i++) {
int j = string.length() - i - 1;
if (i != j) { //交换元素
char temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
return new String(array);
}
2. 使用StringBuilder
StringBuilder可以帮助我们创建字符串，所以也可以使用 StringBuilder替代字符数组存储，具体思路是:
逆序遍历字符串中的字符，并将它依次添加到StringBuilder中
public static String strReverseWithStringBuilder(String string) {
if (string == null || string.length() == 0) return string;
StringBuilder sb = new StringBuilder();
for (int i = string.length() - 1; i >= 0; i--) {
sb.append(string.charAt(i));
}
return sb.toString();
}
以上这几种方法按算法角度来说，其实可以归结为一类。然而下面的几种算法就完全不是同一类型的了。
比如使用栈、使用异或运算。
3. 使用StringBuilder.reverse()方法
new StringBuilder(hi).reverse().toString()
StringBuilder中提供了 reverse()方法来实现字符串反转，我们可以直接调用
public static String strReverseWithRecursive(String string) {
if (string == null || string.length() == 0) return string;
return new StringBuilder(string).reverse().toString();
}
Or, for versions earlier than JDK 1.5, use
java.util.StringBufferinstead ofStringBuilder— they have the same API. Thanks commentators for pointing out that StringBuilder is preferred nowadays.
对于JDK 1.5之前的版本可以使用 StringBuffer替代 StringBuilder，这两个的API都一样。
4. 使用栈
我们都知道，栈有”后进先出(LIFO)”的特点。这一特点刚好用于反转字符串。具体思路是:
- 将字符串转换为char数组
- 将char数组中的字符依次压入栈中
- 将栈中的字符依次弹出赋值给char数组
public static String strReverseWithStack(String string) {
if (string == null || string.length() == 0) return string;
char[] array = string.toCharArray();
Stack stack = new Stack();
for (Character c : array) {
stack.push(c); //压栈
}
for (int i = 0; i < string.length(); i++) {
array[i] = stack.pop();
}
return new String(array); //出栈
}
两次循环和栈的开销无疑使这种方法成为目前为止开销最大的方法。但使用栈这个数据结构的想法还是非常有价值的。
5. 使用异或运算
计算机的数据流本质上都是0，1二进制数据。字符串也是一样。而二进制数据的处理往往是通过位运算来实现的。位操作有： 与，或，非，异或 。
对位运算有过了解的应该知道，使用 异或操作 能实现交换两个变量的值而不引入第三个变量。
实现原理:
- 首先介绍异或操作
异或操作: 当两两数值相同为否，而数值不同为真。写作A^B
A B A^B
0 0 0
0 1 1
1 0 1
0 1 0
- 使用异或操作交换数值
两个数异或的结果再与其中一个数异或的结果是另外一个数
这涉及到了离散数学中的异或的性质:
1.交换律:A^B=B^A
2.结合律: A^(B^C)=(A^B)^C
3.恒等律:X^0=0
4.归零律:X^X=0
5.自反：A^B^B = A^0=A
根据以上性质:
A=A^B
B=A^B
A=A^B
通过以上三步，能实现在程序中交换两个变量的数值的目标。
- 使用异或操作交换字符值
before:"Hello"
after: "olleH"
index: 0 1 2 3 4
char : H e l l o
ASCII: 72 101 108 108 111
以第0个字符和第4个字符交换为例:
交换前:
array[0]=1001000
array[4]=1101111
交换:
array[0]=array[0]^array[4]=0100111
array[4]=array[4]^array[0]=1001000
array[0]=array[0]^array[4]=1101111
交换后:
array[0]=1101111--->111-->o
array[4]=1001000--->72--->H
使用这种交换方法，每次循环的时候，我们直接给中轴前、后位置元素（第一个和最后一个，第二个和倒数第二个）交换。这样我们也只遍历一半就可以了。
public static String strReverseWithArray(String string) {
if (string == null || string.length() == 0) return string;
char[] array = string.toCharArray();
for (int i = 0, j = string.length() - 1; i < j; i++, j--) {
//异或运算交换元素
array[i] ^= array[j];
array[j] ^= array[i];
array[i] ^= array[j];
}
return new String(array);
}
6. 使用递归
当我们反转字符串的时候，脑海里想的就是从首尾两端依次交换直到到达中间位置。当我们在反转某个字符时，剩下的字符串也是一个反转字符串的过程。这样，我们就能用递归的方法来实现反转字符串的目的。
具体思路是:
- 找出递归结束的临界条件
- 对针对于临界条件的不同的值做出不同的处理
编码实现：
public static String reverse(String string) {
if (string == null || string.length()
反转一个字符串有这么多方法，那么如何把一个字符串反转，而单词不翻转呢？
题目：写一个函数，将字符串反转，反转方式如下：
//输入一个字符串，输出它的倒序字符串，单词不翻转
input: "I am a student"
output: "student a am I"
我们可以仿照上面的字符串完全反转方法。
比如使用栈，可以把单词入栈，而不是字符，然后出栈，就是想要的效果了。或者也使用StringBuilder倒序存储，如下：
public static String reverse(String word) {
String[] arr = word.split("\\W+");
StringBuffer sb = new StringBuffer();
int len = arr.length;
for (int i = len - 1; i >= 0; i--) {
sb.append(arr[i]).append(" ");
}
return sb.toString();
}
还有一种思路是： 先把整个字符串完全反转，再将字符串分割为单词，每个单词再单独反转回来。这种办法也没什么问题，大家可以参考一下。
Original: https://www.cnblogs.com/ciel717/p/16190675.html
Author: 夏尔_717
Title: LeetCode344.反转字符串
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/712326/
转载文章受原作者版权保护。转载请注明原作者出处！