我新建的个人博客，欢迎访问：hmilzy.github.io
344. 反转字符串
题目链接: 反转字符串
没什么好说的，左右指针往中间走就行了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public void reverseString(char[] s) {
int left = 0;
int right = s.length - 1;
while(left <= right){
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
}
|
541. 反转字符串 II
题目链接: 反转字符串 II
自定义一个函数reverse，实现对字符数组任意区间的字符进行反转。
主函数中for循环 i += 2*k ，判断剩余长度大小，执行不同区间的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
| class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
for(int i = 0; i < ch.length; i += (2 * k)) {
if(i + k <= ch.length) {
reverse(ch,i,i + k - 1);
}else{
reverse(ch,i,ch.length - 1);
}
}
return new String(ch);
}
public static void reverse(char[] ch,int begin,int end){
int left = begin;
int right = end;
while(left <= right){
char temp = ch[left];
ch[left] = ch[right];
ch[right] = temp;
left++;
right--;
}
}
}
|
剑指Offer 05.替换空格
题目链接: 替换空格
用StringBuilder更改字符串，append添加。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public String replaceSpace(String s) {
StringBuilder result = new StringBuilder();
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) == ' '){
result.append("%20");
}else{
result.append(s.charAt(i));
}
}
return result.toString();
}
}
|
151. 反转字符串中的单词
题目链接: 反转字符串中的单词
这道题我想的思路是
1.用trim去掉头尾空格。
2.用split(“ “)将字符串分为字符串数组。
3.反转字符串数组。
4.中间加空格。
但是这里有个问题是，如果字符串s中间有两个空格，应该怎么办。
这种情况可以用split(“\s+”)。但是空间复杂度可能比较高喔，没有达到原地反转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public String reverseWords(String s) {
String[] str = s.trim().split("\\s+");
int left = 0;
int right = str.length - 1;
while(left <= right) {
String temp = str[left];
str[left] = str[right];
str[right] = temp;
left++;
right--;
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < str.length; i++) {
if(i == str.length - 1){
sb.append(str[i]);
}else{
sb.append(str[i] + " ");
}
}
return sb.toString();
}
}
|
第二种方法：原地反转
1.移除首尾和中间的多余空格
2.反转整个字符串
3.将每个单词自己反转
见如下代码：需要仔细看！比较巧妙
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| class Solution {
public String reverseWords(String s) {
StringBuilder sb = removeSpace(s);
reverseString(sb,0,sb.length() - 1);
reverseEachWord(sb);
return sb.toString();
}
public StringBuilder removeSpace(String s){
int start = 0;
int end = s.length()-1;
while(s.charAt(start) == ' '){
start++;
}
while(s.charAt(end) == ' '){
end--;
}
StringBuilder sb = new StringBuilder();
while(start <= end){
char c = s.charAt(start);
if(s.charAt(start) != ' ' || sb.charAt(sb.length() - 1) != ' '){
sb.append(c);
}
start++;
}
return sb;
}
private void reverseString(StringBuilder sb,int start,int end){
char temp;
while(start < end){
temp = sb.charAt(start);
sb.setCharAt(start,sb.charAt(end));
sb.setCharAt(end,temp);
start++;
end--;
}
}
private void reverseEachWord(StringBuilder sb){
int start = 0;
int end = 1;
while(start < sb.length()){
while(end < sb.length() && sb.charAt(end) != ' '){
end++;
}
reverseString(sb,start,end - 1);
start = end + 1;
end = start + 1;
}
}
}
|
剑指 Offer 58 - II. 左旋转字符串
题目链接: 左旋转字符串
先将后面的字符加入。再将前面的字符加入。但是好像复杂度不太行，需要改进。
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder result = new StringBuilder();
for(int i = n; i < s.length(); i++){
result.append(s.charAt(i));
}
for(int i = 0; i < n; i++){
result.append(s.charAt(i));
}
return result.toString();
}
}
|
