这是一个全面检查字符串操作的好问题。
主题：151.翻转字符串中的短语
给定一个字符串，逐个翻转字符串中的每个短语。
示例1：
输入：“天空是蓝色的”
输出：“蓝色是天空”
示例2：
输入：“你好世界！”
输出：“世界！你好”
说明：输入字符串可以在其上方或前面包含额外的空格，但反转的字符不能。
示例3：
输入：“一个很好的例子”
输出：“例子很好”
说明：如果两个单词之间有多余的空格，请将反转短语之间的空格减少到只有一个。
思路
“这道题可以说是对字符串各种操作的综合考察。”
有的同学会用split库函数将词组分开jquery去掉前后空格，然后定义一个新的字符串，最后将词组逆序相乘，那么这道题就是水题，失去了意义。
所以这里我还是增加了这个问题的难度：“不要使用辅助空间，空间复杂度要求是O(1)”。
当辅助空间无法使用后，唯一能做的就是对原始字符串进行处理。
想一想，如果我们将整个字符串反转，那么以反转的顺序指定短语的顺序，但是短语本身也被插入，然后再次反转短语，单词就会反转。
所以问题的解决方法如下：
正如动画中所示：
这样，我们就完成了字符串中短语的翻转。
这个想法非常明确。 下面说一下代码的实现细节。 我们以删除多余空格为例。 有的同学会上来写出下面的代码：
void removeExtraSpaces(string& s) { for (int i = s.size() - 1; i > 0; i--) { if (s[i] == s[i - 1] && s[i] == ' ') { s.erase(s.begin() + i); } } // 删除字符串最后面的空格 if (s.size() > 0 && s[s.size() - 1] == ' ') { s.erase(s.begin() + s.size() - 1); } // 删除字符串最前面的空格 if (s.size() > 0 && s[0] == ' ') { s.erase(s.begin()); }}逻辑很简单，从前往后遍历，遇到空格就擦除。
如果你不仔细考虑erase的时间复杂度，你会认为上面的代码是O(n)时间复杂度。
考虑实时复杂性。 擦除最初是一个 O(n) 操作。 擦除实现原理 题目：数组：只删除一个元素很难吗？ ，删除元素的最优算法也是 O(n)。
擦除操作中还有一个for循环，因此上述代码去除冗余空格的代码时间复杂度为O(n^2)。
然后使用双指针的方法去掉空格，最后resize（重置）字符串的大小，就可以实现O(n)的时间复杂度。
如果你对这个操作不熟悉，可以再看一下这篇文章：数组：只删除一个元素很难吗？ 如何删除元素。
然后用双针去除多余的空间。 代码如下：fastIndex 移动得快，slowIndex 移动得慢，最后slowIndex 标记去掉多余空格后的新字符串的粗细。
void removeExtraSpaces(string& s) { int slowIndex = 0, fastIndex = 0; // 定义快指针，慢指针 // 去掉字符串前面的空格 while (s.size() > 0 && fastIndex 0 && s[fastIndex - 1] == s[fastIndex] && s[fastIndex] == ' ') { continue; } else { s[slowIndex++] = s[fastIndex]; } } if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格 s.resize(slowIndex - 1); } else { s.resize(slowIndex); // 重新设置字符串大小 }}有的朋友可能会发现，在leetcode上使用erase去除空格有很好的性能。 主要有以下几点：
在leetcode上的测试集中，字符串的宽度不够长。 如果足够长，性能差异会特别显着。 leetcode测量的程序时长不是很准确。
至此我们已经实现了removeExtraSpaces函数来删除多余的空格。
它还实现了字符串反转的功能jquery去掉前后空格，支持字符串子范围的反转。 对于这个实现，我们将使用库函数用一行代码和字符串来解决这个问题：简单的反转是不够的！ 已经说过了。
代码如下所示：
// 反转字符串s中左闭又闭的区间[start, end]void reverse(string& s, int start, int end) { for (int i = start, j = end; i 本题C++整体代码
class Solution {public: // 反转字符串s中左闭又闭的区间[start, end] void reverse(string& s, int start, int end) { for (int i = start, j = end; i 0 && fastIndex 0 && s[fastIndex - 1] == s[fastIndex] && s[fastIndex] == ' ') { continue; } else { s[slowIndex++] = s[fastIndex]; } } if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格 s.resize(slowIndex - 1); } else { s.resize(slowIndex); // 重新设置字符串大小 } } string reverseWords(string s) { removeExtraSpaces(s); // 去掉冗余空格 reverse(s, 0, s.size() - 1); // 将字符串全部反转 int start = 0; // 反转的单词在字符串里起始位置 int end = 0; // 反转的单词在字符串里终止位置 bool entry = false; // 标记枚举字符串的过程中是否已经进入了单词区间 for (int i = 0; i 在留言区留下你的想法吧！
发表评论