代码随想录算法训练营第八天 | 344.反转字符串、541. 反转字符串II、卡码网：54.替换数字 、151.翻转字符串里的单词、卡码网：55.右旋转字符串

344.反转字符串

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

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。

文章讲解/视频讲解：https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html

思路

一次遍历即可，每次循环时，交换下标i和下标len - 1 - i的数值。循环在遍历到字符串中间时停止，因为如果循环遍历完这个数组，得到的结果和原数组相同。

C++实现

class Solution {
public:
    void reverseString(vector<char>& s) {
        for(int i = 0;i<s.size() / 2;i++){
            swap(s[i], s[s.size() - 1 - i]);
        }
    }
};

541. 反转字符串II

题目链接：541. 反转字符串II

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

文章讲解/视频讲解：https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html

思路

首先，定义一个reverse(s, begin, end)函数，实现字符串[begin, end)范围内的元素反转。

然后循环遍历这个数组，每次循环跨度为2k，如题意所示，每次反转这2k字符中的前k个字符。

如果剩余字符小于k个，则将剩余字符全部反转，如果小于2k但大于等于k，则反转前k个字符。

重点是这个reverse(s, begin, end)函数的实现，注意循环的范围，改了好几遍。。

C++实现

class Solution {
public:
    void reverseInrange(string& s, int begin, int end){
        for(int i = 0;i < (end - begin) / 2;i++){
            swap(s[begin + i], s[end - i - 1]);
        }
    }

    string reverseStr(string s, int k) {
        for(int i = 0;i<s.size();i += 2 * k){
            if(i + 2 * k >= s.size()){
                if(i + k >= s.size()){
                    reverseInrange(s, i, s.size());
                }
                else{
                    reverseInrange(s, i, i + k);
                }
            }
            else{
                reverseInrange(s, i, i + k);
            }
        }
        return s;
    }
};

卡码网：54.替换数字

题目链接：卡码网：54.替换数字

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。

**注意：**答案中不可以包含重复的三元组。

文章讲解/视频讲解：https://programmercarl.com/kama54.%E6%9B%BF%E6%8D%A2%E6%95%B0%E5%AD%97.html

思路

设置一个指针p，用指针p循环遍历字符串s。若当前遍历到的是字母，指针的位置+1；当字符串中遍历到数字时，在字符串中删除该位置的数字char，然后插入“number”字符串，同时指针p的位置+6。一直遍历到字符串末尾。

这一题让我熟悉了字符串insert和erase的用法。

C++实现

#include<iostream>
#include<string>
using namespace std;


int main(){
    string input;
    
    getline(cin, input);
    
    int p = 0;
    string padding = "number";
    while(p < input.size()){
        if(input[p] >= '0' && input[p] <= '9'){
            input.erase(input.begin() + p);
            input.insert(p, padding);
            p += 6;
        }
        else{
            p++;
        }
    }
    
    cout<<input<<endl;
    
    return 0;
}

151.翻转字符串里的单词

题目链接：151.翻转字符串里的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

文章讲解/视频讲解：https://programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html

思路

首先把多余的空格删除掉：先删除字符串前导空格和尾随空格，然后遍历字符串，遇到空格时，统计此时连续空格的个数，如果超过一个，则删除。这里我使用的是erase来进行删除，看了卡哥的教程后，发现这种方法的时间复杂度为o(n^2)，若想有o(n)的时间复杂度，应当采用双指针，采用3. 移除元素的方法。

然后做反转操作：首先把整个字符串反转，然后以空格为分隔，将每个单词反转，实现题意中的反转效果。做反转时，利用541. 反转字符串II题目里实现的反转函数。

C++实现

class Solution {
public:
    // 用erase实现的删除空格
    void removeExtraSpace(string& s){
        // 删除前导
        int p = 0;
        while(s[p] == ' '){
            s.erase(s.begin() + p);
        }

        // 删除尾随
        p = s.size() - 1;
        while(s[p] == ' '){
            s.erase(s.begin() + p);
            p--;
        }

        //删除单词间空格
        p = 0;
        int space = 0;
        while(p < s.size()){
            if(s[p] != ' '){
                space = 0;
                p++;
            }
            else{
                if(space != 0){
                    s.erase(s.begin() + p);
                }
                else{
                    space = 1;
                    p++;
                }
            }
        }
    }
    // 用双指针实现的移除空格
    void removeExtraSpace(string& s){
        int slow = 0, fast = 0;

        while(fast < s.size()){
            if(s[fast] != ' '){
                if(slow > 0) s[slow++] = ' ';
                while(fast < s.size() && s[fast] != ' '){
                    s[slow++] = s[fast++];
                }
            }
            else{
                fast++;
            }
        }

        s.resize(slow);
    }

    void reverseInrange(string& s, int begin, int end){
        // [begin, end)
        for(int i = 0;i<(end - begin) / 2;i++){
            swap(s[begin + i], s[end - i - 1]);
        }
    }

    string reverseWords(string s) {
        removeExtraSpace(s);

        reverseInrange(s, 0, s.size());

        int begin = 0;
        for(int i = 0;i<s.size();i++){
            if(s[i] == ' '){
                reverseInrange(s, begin, i);
                begin = i + 1;
            }
        }
        reverseInrange(s, begin, s.size());
        return s;
    }
};

卡码网：55.右旋转字符串

题目链接：卡码网：55.右旋转字符串

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。

例如，对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。

文章讲解/视频讲解：https://programmercarl.com/kama55.%E5%8F%B3%E6%97%8B%E5%AD%97%E7%AC%A6%E4%B8%B2.html

思路

首先，需要让k对字符串的size取模，避免重复计算以及越界。

之后可以利用双指针来解决：把字符串s复制一下，复制成s1，然后用p指针来遍历s1，q指针来遍历s。令q指针指向s的倒数第k个字符，p指针指向s1的开头位置。然后开始遍历，令s1[p++] = s[(q++)%s.size()]，直到p遍历到s1的结尾。

看了卡哥的教程，发现还可以采用上一题的思路，先整体反转再局部反转的方法，这样不用再申请一个新的区域，只用o(1)的空间复杂度。orz，妙啊！

C++实现

// 双指针的解法
#include<iostream>
#include<string>
using namespace std;


int main(){
    
    int k;
    string input;
    cin>>k;
    getline(cin, input);
    getline(cin, input);
    
    k = k % (input.size());
    
    int p = 0, q = input.size() - k;
    
    string output(input);
    
    while(p < output.size()){
        output[p++] = input[(q++) % (input.size())];
    }
    
    cout<<output<<endl;
    
    return 0;
}

// 反转法

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;


int main(){
    
    int k;
    string input;
    cin>>k;
    cin>>input;
    
    k = k % (input.size());
    
    reverse(input.begin(), input.end());
    reverse(input.begin(), input.begin() + k);
    reverse(input.begin() + k, input.end());
    
    cout<<input<<endl;
    
    return 0;
}