导航
导航
文章目录
  1. 题目
  2. 翻译
    1. 方法一:char数组逆序
    2. 方法二:StringBuffer不断添加
    3. 方法三:库函数

LeetCode-344.Reverse String

题目

Write a function that takes a string as input and returns the string reversed.

Example:
Given s = “hello”, return “olleh”.

翻译

编写函数,将输入字符串反转并返回。
例如:给出s=”hello”,返回”olleh”。

方法一:char数组逆序

设立一个与s长度相同的char数组chars,和low、high指针分别指向s的头尾,不断调换位置填入chars,并逐渐向中间逼近:

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
public String reverseString(String s) {
if (s == null || s.length() <= 1) return s;
int low = 0, len = s.length(), high = len - 1;
char[] chars = new char[len];
while (low <= high) {
chars[low] = s.charAt(high);
chars[high--] = s.charAt(low++);
}
return new String(chars);
}
}

Run Time: 3ms
或逐个扫描:

1
2
3
4
5
6
7
8
9
public class Solution {
public String reverseString(String s) {
if (s == null) return s;
int len = s.length();
char[] chars = new char[len];
for (int i = 0; i < len; i++) chars[i] = s.charAt(len - i - 1);
return new String(chars);
}
}

Run time: 3ms

方法二:StringBuffer不断添加

设立指针从s尾部逐渐向头部扫描,逐个添加到StringBuffer中:

1
2
3
4
5
6
7
8
public class Solution {
public String reverseString(String s) {
if (s == null) return s;
StringBuffer sb = new StringBuffer();
for (int i = s.length() - 1; i >= 0; i--) sb.append(s.charAt(i));
return sb.toString();
}
}

Run Time: 7ms

方法三:库函数

利用StringBuffer()的reverse()方法:

1
2
3
4
5
public class Solution {
public String reverseString(String s) {
return new StringBuffer(s).reverse().toString();
}
}

查看JDK源码可得reverse()函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public AbstractStringBuilder reverse() {
boolean hasSurrogate = false;
int n = count - 1;
for (int j = (n-1) >> 1; j >= 0; --j) {
char temp = value[j];
char temp2 = value[n - j];
if (!hasSurrogate) {
hasSurrogate = (temp >= Character.MIN_SURROGATE && temp <= Character.MAX_SURROGATE)
|| (temp2 >= Character.MIN_SURROGATE && temp2 <= Character.MAX_SURROGATE);
}
value[j] = temp2;
value[n - j] = temp;
}
if (hasSurrogate) {
// Reverse back all valid surrogate pairs
for (int i = 0; i < count - 1; i++) {
char c2 = value[i];
if (Character.isLowSurrogate(c2)) {
char c1 = value[i + 1];
if (Character.isHighSurrogate(c1)) {
value[i++] = c1;
value[i] = c2;
}
}
}
}
return this;
}

Run Time: 4ms