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