【leetcode 力扣刷题】字符串翻转合集（全部反转///部分反转）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【leetcode 力扣刷题】字符串翻转合集（全部反转///部分反转）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

344. 反转字符串

题目链接：344. 反转字符串
题目内容：
【leetcode 力扣刷题】字符串翻转合集（全部反转///部分反转）,力扣刷题,leetcode,算法,字符串,string,反转字符串
题目中重点强调了必须原地修改输入数组，即不能新建一个数组来完成字符串的反转。我们注意到：

原来下标为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. 反转字符串Ⅱ
题目内容：
【leetcode 力扣刷题】字符串翻转合集（全部反转///部分反转）,力扣刷题,leetcode,算法,字符串,string,反转字符串
题目意思是，将字符串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. 反转字符串中的单词
题目内容：
【leetcode 力扣刷题】字符串翻转合集（全部反转///部分反转）,力扣刷题,leetcode,算法,字符串,string,反转字符串
根据题目描述和示例，可以知道，所谓的反转单词，是反转单词间的顺序，但是单词内部的字符顺序是不变的。另外还需要处理多余的空格——最前面、最后面的空格需要全部删除；单词间的空格只保留一个。
首先处理掉多余的空格，再进行单词顺序的翻转。移除多余的空格，参考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++;
                    };
            }
            //如果不是空格就保留
            else
                s[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;
            }
        }   
        //反转整个字符串s
        reverse(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. 左旋转字符串
题目内容：
【leetcode 力扣刷题】字符串翻转合集（全部反转///部分反转）,力扣刷题,leetcode,算法,字符串,string,反转字符串

反转单词思路

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

class Solution {
public:
    string reverseLeftWords(string s, int n) {
    	//反转单词1
        reverse(s.begin(), s.begin() + n);
        //反转单词2
        reverse(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在后半段就右移
        else
            right_move(s, s.size() - n);
        return s;       
    }
};

这个解题逻辑是没有问题的，但是当n很大的是，时间复杂度很高，以下是运行结果：
【leetcode 力扣刷题】字符串翻转合集（全部反转///部分反转）,力扣刷题,leetcode,算法,字符串,string,反转字符串

子串和子串的拼接

还有一种办法是把前面半截用新的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;
    }
};