day08 反转字符串 反转字符串Ⅱ 替换数字 翻转字符串里的单词 右旋转字符串

发布时间:2024年01月07日

题目1:344 反转字符串

题目链接:344 反转字符串

题意

字符串是数组的形式,使用O(1)的空间将字符串反转

双指针法

法一

代码

class Solution {
public:
    void reverseString(vector<char>& s) {
        for(int i=0,j=s.size()-1;i<s.size()/2;i++,j--){
            swap(s[i],s[j]);
        }
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)
法二

代码

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0;
        int right = s.size()-1;
        while(left<=s.size() && right>=0 && right>left){
            swap(s[left],s[right]);
            left++;
            right--;
        }
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

延伸(swap的实现)

法一(使用中间变量temp)
int temp = s[i];
s[i] = s[j];
s[j] = temp;
法二(使用位运算)异或交换法
//开始s[i]==a  s[j]==b
s[i]^=s[j];  //s[i]=a^b   a异或b
s[j]^=s[i];  //s[j]=b^(a^b)=a
s[i]^=s[j];  //s[i]=a^(a^b)=b
//最终s[i]==b  s[j]==a

题目2:反转字符串Ⅱ

题目链接:541 反转字符串Ⅱ

题意

字符串s每计数至2k个字符,就反转这2k个字符的前k个字符;

剩余字符少于k个,就将剩余字符全部反转;如果剩余字符大于等于k个且小于2k个,反转前k个字符

巧妙解法

i+=(2*k),i每次移动2k个距离

代码

class Solution {
public:
    string reverseStr(string s, int k) {
       for(int i=0;i<s.size();i+=2*k){
           if(i+k<=s.size()){
               reverse(s.begin()+i,s.begin()+i+k);
               continue;//继续寻找下一组
           }
           reverse(s.begin()+i,s.end());
       }
       return s;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

代码

class Solution {
public:
    string reverseStr(string s, int k) {
       for(int i=0;i<s.size();i+=2*k){
           if(i+k<=s.size()){
               reverse(s.begin()+i,s.begin()+i+k);
           }
           else{
               reverse(s.begin()+i,s.end());
           }
       }
       return s;
    }
};

题目3:54 替换数字

题目链接:54 替换数字

题意

字符串s(包含小写字母和数字字符)将数字字符替换位number,字母不变

不能简单地遇到数字就将其替换位number,因为数字是1个字符,而number是6个字符,直接替换的话,大小不对等,需要扩充大小

双指针

i指向新串的末尾,j指向旧串的末尾,从后向前遍历

详细的遍历过程

逻辑问题
例1:for循环中j<i? ?为啥j不能小于等于i呢?

原因

例2 为啥i,j要从后往前遍历,从前向后遍历不行嘛?

从前向后遍历的话,遇到数字字符,就需要将该数字字符后面的字符向后移动5个格,然后才可以填充number,时间复杂度是O(n^2)

代码

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int main(){
    string s;
    cin>>s;
    int count = 0;
    int oldsize = s.size();
    for(int i=0;i<s.size();i++){
        if(s[i]>='0'&& s[i]<='9'){
            count++;
        }
    }
    s.resize(s.size()+count * 5);
    int newsize = s.size();
    for(int i=newsize-1,j=oldsize-1;j<i;i--,j--){
        if(s[j]>='a'&&s[j]<='z'){
            s[i]=s[j];
        }
        else{
            s[i] = 'r';
            s[i-1] = 'e';
            s[i-2] = 'b';
            s[i-3] = 'm';
            s[i-4] = 'u';
            s[i-5] = 'n';
            i -= 5;
        }
    }
    cout<<s<<endl;
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

题目4:151 反转字符串里的单词

题目链接:151 反转字符串中的单词

题意

反转字符串s中单词的顺序? ?输入的字符串的开头或结尾可能会存在多个空格,单词与单词之间可能也存在多个空格

反转字符串时,仅仅在单词与单词之间有1个空格?

关键是字符串去除空格的逻辑,反转的逻辑:整体反转+局部反转

双指针(删除多余空格)

fast指向单词,slow指向单词所在的新的位置??

添加空格

在每个单词移动之前,添加一个空格,第一个单词除外

实例

代码

class Solution {
public:
    string reverseWords(string s) {
        //1 移除多余空格
        int slow = 0;
        for(int fast=0;fast<s.size();fast++){
            if(s[fast]!=' '){//找到了单词
                //单词前添加一个空格
                if(slow!=0){
                    s[slow] = ' ';
                    slow++;
                }
                //将单词移动到新的位置
                while(fast<s.size() && s[fast]!=' '){
                    s[slow] = s[fast];
                    slow++;
                    fast++;
                }  
            }
        }
        s.resize(slow);
        //2 反转单词
        //①整体反转
        reverse(s.begin(),s.end());//左闭右开
        //②单词反转
        int start = 0;
        for(int i=0;i<=s.size();i++){//reverse左闭右开
            if(s[i]==' ' || i==s.size()){//每个单词后有空格,最后一个单词后没空格
                reverse(s.begin()+start,s.begin()+i);//reverse左闭右开
                start = i + 1;
            }
        }
        return s;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)?
一般思路(分3种情况讨论)

字符串前有空格? 字符串中有多余空格? ? 字符串后有多余空格

代码

class Solution {
public:
    void removespace(string& s){
        int slow = 0;
        int fast = 0;
        //去掉前面的空格,寻找有效的字符,持续过程,开头可能有多个空格
        while(fast<s.size()&&s[fast]==' '){
            fast++;
        }
        //去掉中间多余的空格,如果原字符串末尾有空格的话,会使得末尾有1个空格
        for(;fast<s.size();fast++){//使用fast+1的话,fast+1可能会越界
            if(fast-1>0 && s[fast]==s[fast-1] && s[fast]==' '){
                continue;
            }
            else{//不是空格时,直接将fast位置处的值赋值给slow,然后slow向后移动一个位置
                s[slow] = s[fast];
                slow++;}
        }
        //去掉末尾的1个空格,因为上述代码的slow++了,slow会移动到多一个位置的地方,所以判断slow-1
        if(slow-1>0&&s[slow-1]==' '){
            s.resize(slow-1);
        }
        else{//原字符串末尾没有空格
            s.resize(slow);
        }
    }
    string reverseWords(string s) {
        removespace(s);//去除字符串中多余的空格
        reverse(s.begin(),s.end());//左闭右开,将字符串全部反转
        int start = 0;//反转单词的首字母的位置
        for(int i=0;i<=s.size();i++){
            if(s[i]==' ' || i==s.size()){//这里有两种情况,单词以空格结尾,单词是最后一个单词
                reverse(s.begin()+start,s.begin()+i);
                start = i + 1;//下一个单词的首字母的位置
            }
        }
        return s;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)?

题目5:55? 右旋转字符串

题目链接:55 右旋转字符串

题意

将字符串s后面的k个字符移到字符串的前面,实现右旋转操作

整体反转+局部反转

代码

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    string s;
    int k;
    cin>>k;
    cin>>s;
    //整体反转
    reverse(s.begin(),s.end());
    //局部反转
    reverse(s.begin(),s.begin()+k);
    reverse(s.begin()+k,s.end());
    cout<<s<<endl;
}

局部反转+整体反转

代码

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    string s;
    int k;
    cin>>k;
    cin>>s;
    //整体反转
    reverse(s.begin(),s.begin()+s.size()-k);
    //局部反转
    reverse(s.begin()+s.size()-k,s.end());
    reverse(s.begin(),s.end());
    cout<<s<<endl;
}
文章来源:https://blog.csdn.net/qq_43773652/article/details/135430781
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。