代码随想录算法训练营第八天 | LeetCode344.反转字符串 LeetCode 541. 反转字符串II 卡码网：54.替换数字

代码随想录算法训练营

Day8 代码随想录算法训练营第8 天 | LeetCode344.反转字符串 LeetCode 541. 反转字符串II 卡码网：54.替换数字

前言

LeetCode344.反转字符串

讲解文档

LeetCode541. 反转字符串II

讲解文档

卡码网：54.替换数字

讲解文档

一、、LeetCode344.反转字符串

1.题目链接

LeetCode344.反转字符串

2.思路

（1）双指针分别从第一个元素和最后一个元素出发（认为左闭右闭）
（2）不断交换两个指针所指的字符

3.题解

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

二、LeetCode 541. 反转字符串II

1.题目链接

LeetCode 541. 反转字符串II

2.思路

（1）reverse可以自己实现，也可以使用库函数
如果自己实现reverse，并且以字符串指针为参数，一定要注意解引用时要写(*s)，因为解引用的优先级不够高
（使用引用作为参数可以避免这个问题）
（2）整个字符串中中包含round个2k周期，最后余下left个元素
1）讨论能凑出2k周期的情况：每个2k周期中反转前k个
2）再讨论left个元素：
left大于k，则将前k个反转
left小于k，则left全部反转

3.题解

class Solution {
public:
    void reverse(string* s, int l, int r) {
        int i = l;
        int j = r;
        while (i < j) {
            swap((*s)[i], (*s)[j]);
            i++;
            j--;
        }
    }
    string reverseStr(string s, int k) {
        int n = s.size();
        int round = n / (2 * k);
        int left = n % (2 * k);
        for (int i = 0; i < round; i++) {
            reverse(&s, i * 2 * k, (i * 2 + 1) * k - 1);
        }
        if (left < k)
            reverse(&s, n - left, n - 1);
        else
            reverse(&s, n - left, n - left + k - 1);
        return s;
    }
};

三、卡码网：54.替换数字

1.题目链接

卡码网：54.替换数字

2.思路

双指针法
（1）先求出字符串中有count个数字，需要增加5*count位
（2）双指针
指针i从后向前遍历原字符串
指针new_i从后向前遍历新的字符串
如果i遍历到字符：用new_i在新字符串中添加，并将new_i移动1位
如果i遍历到数字：用new_i在新字符串中按照r-e-b-m-u-n顺序添加，并将new_i移动6位
（3）这种方法没有创建新的字符串，但是可以确保原来的字符串会在被处理并加入答案后再覆盖掉

3.题解

（1）暴力法

#include<bits/stdc++.h>
#include<string>
using namespace std;
int main()
{
    string s;
    cin>>s;
    std::vector<string> ans ;
    int n=s.size();
    for(int i=0;i<n;i++)
    {
        if(s[i]>='0'&&s[i]<='9')ans.push_back("number");
        else 
        {
            string temp;
            temp.append(1,s[i]);
            ans.push_back(temp);
        }
    }
    string res;
    int m=ans.size();
    for(int i=0;i<m;i++ )
    {
        res+=ans[i];
    }
    cout<<res;
    return 0;
}

（2）双指针法

#include<bits/stdc++.h>
#include<string>
using namespace std;
int main()
{
    string s;
    cin>>s;
    std::vector<string> ans ;
    int n=s.size();
    int count=0;
    
    for(int i=0;i<n;i++)
    {
        if(s[i]>='0'&&s[i]<='9')count++;
    }
    int m=n+count*5;
    s.resize(m);
    int new_i=m-1;
    for(int i=n-1;i>=0;i--)
    {
        if(s[i]>='0'&&s[i]<='9')
        {
            
            s[new_i]='r';
            s[new_i-1]='e';
            s[new_i-2]='b';
            s[new_i-3]='m';
            s[new_i-4]='u';
            s[new_i-5]='n';
            new_i-=6;
        }else
        {
            s[new_i]=s[i];
            new_i--;
        }
    }
    cout<<s;
    
    
    return 0;
}