22##题目地址
33https://leetcode-cn.com/problems/reverse-words-in-a-string/
44
5- ## 思路
5+ > 综合考察字符串操作的好题。
66
7- 这道题目可以说是综合考察了字符串的多种操作。
7+ # 题目：151.翻转字符串里的单词
88
9- 那么问题来了，要不要使用split 和 reverse 等等库函数
9+ 给定一个字符串，逐个翻转字符串中的每个单词。
1010
11- 这道题目中很多同学使用库函数走捷径解题，其实这也无可厚非，如果这样做，一定要确保自己可以实现这些库函数的功能，别看 split 好像很简单，其实很多时候自己去实现的时候错漏百出的。
11+ 示例 1：
12+ 输入: "the sky is blue"
13+ 输出: "blue is sky the"
1214
13- 解题思路：
15+ 示例 2：
16+ 输入: " hello world! "
17+ 输出: "world! hello"
18+ 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
19+
20+ 示例 3：
21+ 输入: "a good example"
22+ 输出: "example good a"
23+ 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
24+
25+
26+ #思路
27+
28+ ** 这道题目可以说是综合考察了字符串的多种操作。**
29+
30+
31+ 一些同学会使用split库函数，分隔单词，然后定义一个新的string字符串，最后再把单词倒序相加，那么这道题题目就是一道水题了，失去了它的意义。
32+
33+ 所以这里我还是提高一下本题的难度：** 不要使用辅助空间，空间复杂度要求为O(1)。**
34+
35+ 不能使用辅助空间之后，那么只能在原字符串上下功夫了。
36+
37+ 想一下，我们将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒叙了，那么再把单词反转一下，单词不就正过来了。
38+
39+ 所以解题思路如下：
1440
1541* 移除多余空格
1642* 将整个字符串反转
@@ -22,7 +48,86 @@ https://leetcode-cn.com/problems/reverse-words-in-a-string/
2248
2349这样我们就完成了翻转字符串里的单词。
2450
25- ##代码
51+ 思路很明确了，我们说一说代码的实现细节，就拿移除多余空格来说，一些同学会上来写如下代码：
52+
53+ ```
54+ void removeExtraSpaces(string& s) {
55+ for (int i = s.size() - 1; i > 0; i--) {
56+ if (s[i] == s[i - 1] && s[i] == ' ') {
57+ s.erase(s.begin() + i);
58+ }
59+ }
60+ // 删除字符串最后面的空格
61+ if (s.size() > 0 && s[s.size() - 1] == ' ') {
62+ s.erase(s.begin() + s.size() - 1);
63+ }
64+ // 删除字符串最前面的空格
65+ if (s.size() > 0 && s[0] == ' ') {
66+ s.erase(s.begin());
67+ }
68+ }
69+ ```
70+
71+ 逻辑很简单，从前向后遍历，遇到空格了就erase。
72+
73+ 如果不仔细琢磨一下erase的时间复杂读，还以为以上的代码是O(n)的时间复杂度呢。
74+
75+ 想一下真正的时间复杂度是多少，一个erase本来就是O(n)的操作，erase实现原理题目：[ 数组：就移除个元素很难么？] ( https://mp.weixin.qq.com/s/wj0T-Xs88_FHJFwayElQlA ) ，最优的算法来移除元素也要O(n)。
76+
77+ erase操作上面还套了一个for循环，那么以上代码移除冗余空格的代码时间复杂度为O(n^2)。
78+
79+ 那么使用双指针法来去移除空格，最后resize（重新设置）一下字符串的大小，就可以做到O(n)的时间复杂度。
80+
81+ 如果对这个操作比较生疏了，可以再看一下这篇文章：[ 数组：就移除个元素很难么？] ( https://mp.weixin.qq.com/s/wj0T-Xs88_FHJFwayElQlA ) 是如何移除元素的。
82+
83+ 那么使用双指针来移除冗余空格代码如下： fastIndex走的快，slowIndex走的慢，最后slowIndex就标记着移除多余空格后新字符串的长度。
84+
85+ ```
86+ void removeExtraSpaces(string& s) {
87+ int slowIndex = 0, fastIndex = 0; // 定义快指针，慢指针
88+ // 去掉字符串前面的空格
89+ while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {
90+ fastIndex++;
91+ }
92+ for (; fastIndex < s.size(); fastIndex++) {
93+ // 去掉字符串中间部分的冗余空格
94+ if (fastIndex - 1 > 0
95+ && s[fastIndex - 1] == s[fastIndex]
96+ && s[fastIndex] == ' ') {
97+ continue;
98+ } else {
99+ s[slowIndex++] = s[fastIndex];
100+ }
101+ }
102+ if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格
103+ s.resize(slowIndex - 1);
104+ } else {
105+ s.resize(slowIndex); // 重新设置字符串大小
106+ }
107+ }
108+ ```
109+
110+ 有的同学可能发现用erase来移除空格，在leetcode上性能也还行。主要是以下几点；：
111+
112+ 1 . leetcode上的测试集里，字符串的长度不够长，如果足够长，性能差距会非常明显。
113+ 2 . leetcode的测程序耗时不是很准确的。
114+
115+ 此时我们已经实现了removeExtraSpaces函数来移除冗余空格。
116+
117+ 还做实现反转字符串的功能，支持反转字符串子区间，这个实现我们分别在[ 字符串：这道题目，使用库函数一行代码搞定] ( https://mp.weixin.qq.com/s/X02S61WCYiCEhaik6VUpFA ) 和[ 字符串：简单的反转还不够！] ( https://mp.weixin.qq.com/s/XGSk1GyPWhfqj2g7Cb1Vgw ) 里已经讲过了。
118+
119+ 代码如下：
120+
121+ ```
122+ // 反转字符串s中左闭又闭的区间[start, end]
123+ void reverse(string& s, int start, int end) {
124+ for (int i = start, j = end; i < j; i++, j--) {
125+ swap(s[i], s[j]);
126+ }
127+ }
128+ ```
129+
130+ ##本题C++整体代码
26131
27132效率：
28133
@@ -33,13 +138,12 @@ class Solution {
33138public:
34139 // 反转字符串s中左闭又闭的区间[start, end]
35140 void reverse(string& s, int start, int end) {
36- int offset = (end - start + 1) / 2;
37- for (int i = start, j = end; i < start + offset; i++, j--) {
141+ for (int i = start, j = end; i < j; i++, j--) {
38142 swap(s[i], s[j]);
39143 }
40144 }
41- // 字符串去掉冗余的空格
42- //使用快慢指针发
145+
146+ //移除冗余空格：使用双指针（快慢指针法）O(n)的算法
43147 void removeExtraSpaces(string& s) {
44148 int slowIndex = 0, fastIndex = 0; // 定义快指针，慢指针
45149 // 去掉字符串前面的空格
@@ -63,23 +167,6 @@ public:
63167 }
64168 }
65169
66- // 费时间的写法
67- void removeExtraSpaces1(string& s) {
68- for (int i = s.size() - 1; i > 0; i--) {
69- if (s[i] == s[i - 1] && s[i] == ' ') {
70- s.erase(s.begin() + i);
71- }
72- }
73- // 删除字符串最后面的空格
74- if (s.size() > 0 && s[s.size() - 1] == ' ') {
75- s.erase(s.begin() + s.size() - 1);
76- }
77- // 删除字符串最前面的空格
78- if (s.size() > 0 && s[0] == ' ') {
79- s.erase(s.begin());
80- }
81- }
82-
83170 string reverseWords(string s) {
84171 removeExtraSpaces(s); // 去掉冗余空格
85172 reverse(s, 0, s.size() - 1); // 将字符串全部反转