题目：
难度中等758收藏分享切换为英文接收动态反馈
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例 1：
1
2
| 输入：s = "the sky is blue"
输出："blue is sky the"
|
示例 2：
1
2
3
| 输入：s = " hello world "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。
|
思路
本题如果我们按照之前固有的思路来解的话那就是用split来分割， 然后再进行反转就可以了，但是这样题目就失去了本身的意义。所以我们这里不借助String的本身的工具，而是自定义实现删除空格
操作虽然只有三步，但是每一步需要思考的东西有很多。所以这道题需要我们仔细的去琢磨
分三步进行操作 :
- 删除多余的空格
- 反转所有的字符串
- 反转字符串中的单词
删除多余空格
对于我们java选手来说，不需要去重定义String数组的大小，只需要用StringBuilder 或者StringBuffer就可以完成拼接
所以只需要考虑在什么时候拼接最为合适即可
所以我们就不需要双指针了，一个指针就可以完成，当然双指针仍然是最优解。
- 删除字符串前面的空格
删除前面的空格也不需要我们做什么操作，如果发现有空格那么我们就直接跳过就行了。指针向后移即可。
- 删除字符串中间的空格
当前面的空格移除完毕之后，剩下的就该中间的了。此时，执政就会指向字母所在的地方。我们需要做的就是删除中间多余的空格(需要留一个)。如何删除呢 ？
1
2
3
4
5
| 首先之前已经删除完字符串前面的空格了，所以之后的指针指向的第一个一定是字母，所以就会拼接上去
之后。指针就指向第二个，此时index - 1 是一定大于 0 的
同时指针一直向后移动。当index 指向' '时让他继续拼接 ，但是
当index 和index - 1同时都为' '时 ，这是我们就需要跳过一次循环，让他停止拼接一次。
这样就实现了删除中间多余的' '的操作了
|
- 删除字符串后面的空格
最后只可能出现唯一一种情况就是多了一个空格，因为我们之前在这一步
if(fast - 1 > 0 && s.charAt(fast-1) == s.charAt(fast) && s.charAt(fast) == ' ')
如果最后两个都是空格，那么他只会删除一个，所以有可能会出现多余空格。我们只需要在其有的可能下删除一个即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public StringBuilder delete(String s){
int fast = 0,slow = 0;
StringBuilder str = new StringBuilder();
while(s.length() > 0 && fast < s.length() && s.charAt(fast) ==' '){
fast++;
}
for(;fast <s.length() ;fast++){
if(fast - 1 > 0 && s.charAt(fast-1) == s.charAt(fast) && s.charAt(fast) == ' '){
continue;
}else{
str.append(s.charAt(fast));
}
}
if(str.charAt(str.length()-1) == ' '){
str.deleteCharAt(str.length()-1);
}
return str;
}
|
实现
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
59
60
61
62
63
| class Solution {
public String reverseWords(String s) {
StringBuilder res = delete(s);
reverseString(res,0,res.length() - 1);
int start =0,end = 0;
boolean flag = false;
for(int i = 0 ; i < res.length();i++){
if(!flag || (res.charAt(i)!=' ' && res.charAt(i-1)==' ')){
start = i;
flag = true;
}
if(flag && res.charAt(i) ==' ' ){
end = i-1;
reverseString(res,start,end);
flag = false;
}
if(flag && (i==(res.length()-1)) && res.charAt(i) != ' '){
end = i;
reverseString(res,start,end);
flag = false;
}
}
return res.toString();
}
public StringBuilder delete(String s){
int fast = 0,slow = 0;
StringBuilder str = new StringBuilder();
while(s.length() > 0 && fast < s.length() && s.charAt(fast) ==' '){
fast++;
}
for(;fast <s.length() ;fast++){
if(fast - 1 > 0 && s.charAt(fast-1) == s.charAt(fast) && s.charAt(fast) == ' '){
continue;
}else{
str.append(s.charAt(fast));
}
}
if(str.charAt(str.length()-1) == ' '){
str.deleteCharAt(str.length()-1);
}
return str;
}
public void reverseString(StringBuilder sb, int start, int end) {
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
}
|
