344. 反转字符串

题目链接：344. 反转字符串
题目内容：

题目中重点强调了必须原地修改输入数组，即不能新建一个数组来完成字符串的反转。我们注意到：

• 原来下标为0的，反转后是size - 1【原来下标是size - 1的，反转后是0】；
• 原来下标是1的，反转后是size - 2【原来下标是size -2的，反转后是1】；
• ……原来下标是i的，反转后变成了size - 1 - i【原来下标是size - 1 - i的，反转后是i】

因此可以用双指针，front = 0，behind = size -1；front向后移动，behind向前移动；front和behind对应元素交换位置即完成字符串的反转。交换元素需要额外申请一个元素的空间，因此空间复杂度是O(1)的。
代码如下（C++）：

class Solution {
public:void reverseString(vector<char>& s) {int n = s.size();//双指针for(int front = 0, behind = n - 1; front < behind ; front++, behind--){//交换front、behind对应位置的元素char tmp = s[front];s[front] =s[behind];s[behind] = tmp;}return ;}
};

注意，这道题是考察反转字符串实现的逻辑，如果用reverse函数反转就失去了考察的意义。

541. 反转字符串Ⅱ

题目链接：541. 反转字符串Ⅱ
题目内容：

题目意思是，将字符串s分组：

• 每一组包括2k个字符；
• 每一组里面反转前k个字符，后面k个字符位置不变；
• 对于最后一组，要是少于k个字符，那全部反转；要是在k~2k之间，照样反转前k个字符；

怎么实现分组呢？用start表示每组开始的下标，start从0开始，每次+2k。这里的反转每组前k个字符，可以直接调用reverse函数，也可以自己写一个反转的函数。
代码如下（C++）：

class Solution {
public://自己定义的反转[start,end)间字符的函数void myReverse(string& s, int start, int end){for(int i = start, j = end -1; i < j; i++, j--)swap(s[i],s[j]);}string reverseStr(string s, int k) {int n = s.size();//遍历所有分组for(int start = 0; start < n ; start += 2*k){//判断前k个元素是否越界if(start + k < n) //反转前k个元素myReverse(s, start, start + k);//替换成内置函数 reverse(s.begin() + i, s.begin() + i + k);也可以else //反转最后剩余的不足k的元素   myReverse(s, start, n);//替换成内置函数 reverse(s.begin() + i, s.end());也可以}return s;}
};

151. 反转字符串中的单词

题目链接：151. 反转字符串中的单词
题目内容：

根据题目描述和示例，可以知道，所谓的反转单词，是反转单词间的顺序，但是单词内部的字符顺序是不变的。另外还需要处理多余的空格——最前面、最后面的空格需要全部删除；单词间的空格只保留一个。
首先处理掉多余的空格，再进行单词顺序的翻转。移除多余的空格，参考27. 移除元素，直接使用双指针，原地操作，移除掉多余空格后，s有效长度是小于等于实际长度的，resize一下就好。
一开始我的移除空格逻辑是：①第一个单词前，所有的空格都移除掉：用while，直到s[fats] != ‘ ’结束；②单词间的空格只保留一个，如果s[fast] == ‘ ’但是前面一个字符s[fast-1] != ‘ ’那么这个空格就保留，其他的就全部删除；③由于第二步，最后一个单词后如果有大于等于一个空格，最后会保留一个，最终是要把这个删除掉的。 当然过程中s[fast] != ‘ ’，就直接保留。【整体是双指针原地移动】
删除多余空格代码Ⅰ（C++）：

  		int fast;int count= 0;  //统计移除多余空格后的字符串长度，同样可以当slow指针用//删除前导空格，找到第一个单词起始的字符for(fast = 0; fast < n && s[fast] == ' ' ; )fast++;  while(fast<n){//如果是空格if(s[fast] == ' '){ //前面一个字符不是空格，那么这个空格保留作为单词间的分隔符if(s[fast-1]!=' ') s[count++] = s[fast++];else//否则就删掉空格，并且向后移动直到定位到不是空格的字符处while(fast < n && s[fast] == ' '){fast++;};}//如果不是空格就保留elses[count++] = s[fast++];}//处理最后个单词后可能保留的一个空格if(s[count-1]==' ') count--;s.resize(count);

另外一个删除多余空格的逻辑，重点是针对s[fast] != ‘ ’进行分类讨论。直接从头开始遍历s，如果s[fast] != ‘ ’，就是找到了单词，应该直接保留：①slow == 0，表示这是第一个单词开始，单词前不能有空格，那么从当前的s[fast] != ‘ ’开始，一直到s[fast] == ‘ ’结束，中间的单词字符全都保留；②如果slow != 0，说明这不是第一个单词，当前单词和前面单词间需要有一个空格，那么先添加一个空格，再加入当前单词。
代码如下（C++）：

        int slow = 0;for(int fast = 0; fast < s.size() ; fast++){ //如果不是空格，就是单词if(s[fast] != ' '){//如果slow不等于0，表示不是第一个单词，单词前需要加空格if(slow!=0) s[slow++] = ' ';   //找完这个单词全部字符，直到遇到空格             while(fast < s.size() && s[fast]!=' ')s[slow++] = s[fast++];}}s.resize(slow); //slow表示指针也统计字符数

接下来解决怎么反转单词间的顺序？

• 1、反转整个字符串【已经移除了多余空格了】，这个时候不仅单词的顺序已经反转了，单词内部的字符顺序也反转了；
• 2、反转单词内字符的顺序，变成原始的顺序；

经过上面两步全部反转和单词内部反转就能实现单词顺序的反转，这两步是可以交换顺序的。实现的时候定义一个start表示单词的开始，end找到空格或者移动到string外，表示单词结束，反转[start，end)间的字符；end+1，即空格后下一个字符，又是下一个单词的开始。整体代码如下（C++）：

class Solution {
public://自定义一个移除多余空格的函数void Remove_Spaces(string& s){int slow = 0;for(int fast = 0; fast < s.size() ; fast++){if(s[fast] != ' '){if(slow!=0) s[slow++] = ' ';                while(fast < s.size() && s[fast]!=' ')s[slow++] = s[fast++];}}s.resize(slow);}string reverseWords(string s) {Remove_Spaces(s); //先移除多余空格int start = 0;//反转单词间字符顺序for(int end = 0;  end <= s.size() ; end++){//遇到空格反转前面一个单词if(end == s.size() || s[end] == ' '){reverse(s.begin()+start, s.begin()+end);//下一个单词的开始start = end+1;}}   //反转整个字符串sreverse(s.begin(), s.end());return s;}
};

代码中需要注意if(end == s.size() || s[end] == ‘ ’)，实际上对于||和&&这样的逻辑运算是短路运算的。在A||B中，如果A已经为true了整个表达式是true的，B不需要判断了；在A&&B中，如果A已经是false了整个表达式是false的，B也不需要判断了。式子end == s.size() || s[end] == ‘ ’需要把end == s.size() 写在前面，如果把s[end] == ‘ ’写在前面而end = s.size()的话，就会出现下标越界。

剑指 Offer 58 - II. 左旋转字符串

题目链接：剑指 Offer 58 - II. 左旋转字符串
题目内容：

反转单词思路

理解题意，其实和上一题反转单词是一样的思路，把前k个字符看成单词1，剩下的字符看成单词2，那就是把单词1和单词2交换顺序，单词内容的字符顺序是不变的。
代码如下（C++）：

class Solution {
public:string reverseLeftWords(string s, int n) {//反转单词1reverse(s.begin(), s.begin() + n);//反转单词2reverse(s.begin() + n, s.end());//整体反转，最终只反转了单词1和单词2的顺序reverse(s.begin(), s.end());return s;}
};

分析时间复杂度：reverse是O(n)的，三次reverse最终的时间复杂度也是O(n)的。

循环挪动

根据示例我们可以看出，这个左旋的过程，可以看做是把字符串向左移动k个位置，而下标越界的部分【就是往左多出来的部分】移动到尾部。这个过程可以通过①整个字符串向左移动1个位置，第一个位置移动到末尾；②循环移动k次。
注意，如果k等于size-1呢？时间复杂度变成了O(n^2)了。对于k大于了size/2的情况，右边部分更短，考虑将整个字符串向右移，右边第一个元素移动到字符串头部，移动size-k次。 整体的时间复杂度是O(nk)或者O(n(size-k))的。比上一种解法时间复杂度更高。
代码如下（C++）：

class Solution {
public:void left_move(string& s, int k){ //循环左移for(int i = 0; i < k; i++){char tmp = s[0];int j;for(j = 0; j < s.size() - 1; j++)s[j] = s[j+1];s[j] = tmp;}}void right_move(string& s, int k){ //循环右移int n = s.size();for(int i = 0; i < k; i++){char tmp = s[n-1];int j;for(j = n-1; j > 0; j--)s[j] = s[j-1];s[j] = tmp;}}string reverseLeftWords(string s, int n) {//如果n在前半段就循环左移if(n <= s.size()/2)     left_move(s, n);//n在后半段就右移elseright_move(s, s.size() - n);return s;       }
};

这个解题逻辑是没有问题的，但是当n很大的是，时间复杂度很高，以下是运行结果：

子串和子串的拼接

还有一种办法是把前面半截用新的string变量保存，然后拼接起来。代码如下（C++）：

class Solution {
public:string reverseLeftWords(string s, int n) {string sub = s.substr(0, n);for(int i = 0; i < s.size() - n; i++)s[i] = s[i+n];for(int i = s.size() -n, j = 0; i < s.size() && j < n; i++, j++)s[i] = sub[j] ;  return s;}
};

这个时间复杂度也是O(n)的，但是需要额外的空间保存前半截子串。
总结还是第一种方法最优。