代码随想录算法训练营

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;
}

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部