March 19, 2019 · 数据结构与算法 本文字数: 365 阅读时长:1 min 全站字数:361.8k

反转字符串

  1. 反转字符串
  2. JDK1.8中的reverse实现

反转字符串

反转字符串, 给定一个字符数组,
假设字符都是ASCII字符, 必须是原地反转.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public void reverseString(char[] s) {
int lo = 0, hi = s.length - 1;
char c = 0;
while (lo < hi) {
c = s[lo];
s[lo] = s[hi];
s[hi] = c;
lo++;
hi--;
}
}
}

参考leetcode的讨论区的帖子
主要的优化是交换操作, 可以使用下面的位操作实现ab的两个字节的交换:

1
2
3
a = a ^ b;
b = a ^ b;
a = a ^ b;

如果给定输入是字符串类型, 还可以通过二分的方式解决, 代码如下:

1
2
3
4
5
6
7
8
9
public class Solution {
public String reverseString(String s) {
int length = s.length();
if (length <= 1) return s;
String leftStr = s.substring(0, length / 2);
String rightStr = s.substring(length / 2, length);
return reverseString(rightStr) + reverseString(leftStr);
}
}

时间复杂度是O(nlogn), 递推公式为T(n) = 2T(n/2) + O(n) (O(n)是字符串连接操作的 复杂度).

JDK1.8中的reverse实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//AbstractStringBuilder java.lang.AbstractStringBuilder.reverse()
public AbstractStringBuilder reverse() {
boolean hasSurrogates = false;
int n = count - 1;
// 使用移位操作优化除法操作
for (int j = (n-1) >> 1; j >= 0; j--) {
int k = n - j;
// 使用了两个char作为临时变量,做交换操作,由于需要判断surrogate pairs
char cj = value[j];
char ck = value[k];
value[j] = ck;
value[k] = cj;
if (Character.isSurrogate(cj) ||
Character.isSurrogate(ck)) {
hasSurrogates = true;
}
}
if (hasSurrogates) {
reverseAllValidSurrogatePairs();
}
return this;
}

JDK中的实现除了使用移位操作优化除法操作外, 还需要判断Unicode的surrogate pairs.