代码随想录day4

BaLaLaLa261

32人浏览 · 2026-07-13 22:26:14

BaLaLaLa261 · 2026-07-13 22:26:14 发布

字符串

1.翻转字符串

力扣题目链接(opens new window)

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

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

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

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（1）空间

2.反转字符串II

力扣题目链接(opens new window)

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

如果剩余字符少于 k 个，则将剩余字符全部反转。

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

示例:

输入: s = "abcdefg", k = 2
输出: "bacdfeg"

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

pos作为索引，每次加2k个大小，分段反转

3.替换数字

卡码网题目链接(opens new window)

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。

例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。

对于输入字符串 "a5b"，函数应该将其转换为 "anumberb"

输入：一个字符串 s,s 仅包含小写字母和数字字符。

输出：打印一个新的字符串，其中每个数字字符都被替换为了number

样例输入：a1b2c3

样例输出：anumberbnumbercnumber

数据范围：1 <= s.length < 10000

#include<iostream>
#include<string>
using namespace std;
int main(){
    string s;
    while(cin>>s){
        int oldIndex=s.size()-1;
        int count=0;
        for(int i=0;i<s.size();i++){
            if(s[i]>='0'&&s[i]<='9'){
                count++;
            }
        }
        s.resize(s.size()+count*5);
        int newIndex=s.size()-1;
        while(oldIndex>=0){
            if(s[oldIndex]>='0'&&s[oldIndex]<='9'){
                s[newIndex--]='r';
                s[newIndex--]='e';
                s[newIndex--]='b';
                s[newIndex--]='m';
                s[newIndex--]='u';
                s[newIndex--]='n';
            }else{
                s[newIndex--]=s[oldIndex];
            }
            oldIndex--;
        }
    }
    cout<<s;
}

就是将其中的数字换成number，需要先记录有多少个数字，之后重新分配字符串的大小，之后倒着遍历进行修改，这样就不用修改后面的字符位置，使用双指针法，旧指针与新指针，旧指针指向的是原来字符串的末尾，新指针指向的是扩容后的末尾，旧指针向前遍历，遍历到数字就倒着向前填入rebmun，遍历到字符就正常填入，类似双指针题目中的移除元素问题27. 移除元素 - 力扣（LeetCode）

4.翻转字符串里的单词

力扣题目链接(opens new window)

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：
输入: "the sky is blue"
输出: "blue is sky the"

示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个

class Solution {
public:
    void reverseString(string& s,int begin,int end){
        for(int i=begin,j=end;i<j;i++,j--){
            swap(s[i],s[j]);
        }
    }
    void deleteSpace(string& s){//去除多于的空格
        int slow=0;
        for(int i=0;i<s.size();i++){//快慢指针，类似移除元素
            if(s[i]!=' '){
                if(slow!=0){
                    s[slow++]=' ';
                }
                while(i<s.size()&&s[i]!=' '){
                    s[slow++]=s[i++];
                } 
            }
        }
        s.resize(slow);//注意要重置大小
    }
    string reverseWords(string s) {
        deleteSpace(s);
        reverseString(s,0,s.size()-1);
        int start=0;
        for(int i=0;i<=s.size();i++){
            if(i==s.size()||s[i]==' '){
                reverseString(s,start,i-1);
                start=i+1;
            }
        }
        return s;
    }
};

这里要注意的就是要对空格进行处理，开头与结尾的空格要去除，这里也是与移除元素类似，使用快慢指针的方法，之后慢指针的大小就是要更改字符串的大小，这里将多于空格去除后将整个字符串反转，之后再使用双指针的方法，遇到空格就反转这一段位置的单词。

5.右旋字符串

卡码网题目链接(opens new window)

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

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

输入：输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。

输出：输出共一行，为进行了右旋转操作后的字符串

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    int n;
    string s;
    cin >> n;
    cin >> s;
    int len = s.size(); //获取长度

    reverse(s.begin(), s.end()); // 整体反转
    reverse(s.begin(), s.begin() + n); // 先反转前一段，长度n
    reverse(s.begin() + n, s.end()); // 再反转后一段

    cout << s << endl;

}

这里也是类似，先整体反转，之后再分段反转就可以了。

6. 实现 strStr()

力扣题目链接(opens new window)

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2

示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1

说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符

class Solution {
public:
    int strStr(string haystack, string needle) {
        int index1=0;
        int index2=0;
        int len1=haystack.size();
        int len2=needle.size();
        if(len1<len2){
            return -1;
        }
        while(index1<=len1-len2){
            if(haystack[index1+index2]==needle[index2]){
                index2++;
                if(index2==len2){
                    return index1;
                }
            }else{
                index1++;
                index2=0;
            }
        }
        return -1;
    }
};

这里第一种方法，暴力双指针法复杂度为O(m*n)

第二种就是使用kmp算法来解决

class Solution {
public:
    void getNext(vector<int>& next,string& s){
        int j=0;//j是前缀的位置
        next[0]=0;
        for(int i=1;i<s.size();i++){//i是后缀的位置，所以从1开始
            while(j>0&&s[j]!=s[i]){//注意是while循环，因为有可能前面也不匹配
                j=next[j-1];
            }
            if(s[j]==s[i]){
                j++;
            }
            next[i]=j;
        }
    }
    int strStr(string haystack, string needle) {
        if(needle.size()==0){
            return 0;
        }
        vector<int>next(needle.size(),0);
        getNext(next,needle);
        int j=0;//j为匹配串索引
        for(int i=0;i<haystack.size();i++){//i为主串中索引
            while(j>0&&haystack[i]!=needle[j]){
                j=next[j-1];//出现不匹配的时候，更新匹配串索引位置
            }
            if(haystack[i]==needle[j]){
                j++;
            }
            if(j==needle.size()){
                return (i-needle.size()+1);
            }
        }
        return -1;
    }
};

复杂度为O(n)，kmp算法就是利用字符串的前后缀来记录以前出现过的位置，这样在遇到不匹配的字符的时候就可以根据next表来进行查找，判断在哪里更新字符的位置，而不是从头开始匹配。

这里的前后缀表就是记录了当前位置的最长相等前后缀的大小，这样再更新的时候就不从头再次匹配，而是由于前后缀有匹配的长度，这里直接移动到表中当前位置的前一个的值的位置就可以了。

比如f与b是不匹配的，但是aa与aa匹配，这样就直接从第二个位置开始继续判断，而不是从头开始。

void getNext(vector<int>& next,string& s){
        int j=0;//j是前缀的位置
        next[0]=0;
        for(int i=1;i<s.size();i++){//i是后缀的位置，所以从1开始
            while(j>0&&s[j]!=s[i]){//注意是while循环，因为有可能前面也不匹配
                j=next[j-1];
            }
            if(s[j]==s[i]){
                j++;
            }
            next[i]=j;
        }
    }

这里是next数组的求法，next[0]是0，所以后缀从1开始，两种情况，i是后缀索引，j是前缀索引。

第一种，前后缀位置值相等的时候更新前缀位置，j++，同时当前next[i]的长度就是前缀的长度，即索引

第二种，不相等的时候，就要更新前缀的位置，找与前缀位置的前一个位置元素相等的前缀位置在哪里

这样就求出了next数组。

之后求匹配开始的索引

int strStr(string haystack, string needle) {
        if(needle.size()==0){
            return 0;
        }
        vector<int>next(needle.size(),0);
        getNext(next,needle);
        int j=0;//j为匹配串索引
        for(int i=0;i<haystack.size();i++){//i为主串中索引
            while(j>0&&haystack[i]!=needle[j]){
                j=next[j-1];//出现不匹配的时候，更新匹配串索引位置
            }
            if(haystack[i]==needle[j]){
                j++;
            }
            if(j==needle.size()){
                return (i-needle.size()+1);
            }
        }
        return -1;
    }

这里只需要不断更新主串的索引，需要不断调整位置改变的是匹配串中的索引，索引改变的位置根据next数组来变化，不匹配的时候更新的位置为当前位置的前一个next的值，相等的话就更新匹配串的索引，长度与匹配串的长度相等的时候就成功，返回的索引位置是主串索引位置减匹配串的长度加一。

7.重复的子字符串

力扣题目链接(opens new window)

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:

输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。

示例 2:

输入: "aba"
输出: False

示例 3:

输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。

class Solution {
public:
    void getNext(vector<int>& next,string &s){
        int j=0;
        next[0]=0;
        for(int i=1;i<s.size();i++){
            while(j>0&&s[j]!=s[i]){
                j=next[j-1];
            }
            if(s[i]==s[j]){
                j++;
            }
            next[i]=j;
        }
    }    
    bool repeatedSubstringPattern(string s) {
        if(s.size()==0){
            return false;
        }
        vector<int> next(s.size());
        getNext(next,s);
        int len=s.size();
        if(next[len-1]!=0&&(len%(len-next[len-1]))==0){
            return true;
        }
        return false;
    }
};

这里其实可以推到出来，整个字符串的长度如果可以由其中字串重复组成的话，那么字符串的长度是可以整除字符串的长度减去最长相等前后缀的长度的。

具体推导主要是利用前后缀的错位匹配的性质