【数据结构字符串】题解+详细备注（共7题）

【数据结构/字符串】题解+详细备注

• 344.反转字符串
• 541.反转字符串II
• 剑指Offer05.替换空格
• 151.翻转字符串里的单词
• 剑指Offer58-II.左旋转字符串
• 28.实现strStr()
• 459.重复的子字符串

344.反转字符串

class Solution {
public:
	// 通过双指针交换字符
    void reverseString(vector<char>& s) {
        int n = s.size();

        for(int i{},j = n-1;i<n/2;i++,j--){
            swap(s[i],s[j]);
        }
    }
};

541.反转字符串II

class Solution {
public:
	// 每2k个字符，直接使用reverse翻转前k个字符
    string reverseStr(string s, int k) {
        int n = s.size();
        for(int i{};i<n;i+=2*k){
            if(i + k < n){
                reverse(s.begin() + i,s.begin() + i + k);
                continue;
            }

            reverse(s.begin() + i,s.end());
        }

        return s;
    }
};

剑指Offer05.替换空格

class Solution {
public:
    string replaceSpace(string s) {
        int spaceCount{};
		// 先计算空格数量
        for(char c : s){
            if(c == ' ') spaceCount++;
        }

		// 从新分配替换后的字符串长度
        int n = s.size();
        s.resize(n+spaceCount*2);
		
		// 然后从后向前赋值，遇到空格替换为“%20”
        for(int i = s.size() -1,j = n-1;i>=0;--i){
            if(s[j] != ' '){
                s[i] = s[j--];
                continue;
            }else{
                s[i--] = '0';
                s[i--] = '2';
                s[i] = '%';
                j--;
            }
        }


        return s;
    }
};

151.翻转字符串里的单词

class Solution {
public:
    // 清空字符串,双指针清空
    void emptySpace(string &s){
        int n = s.size();
        int slowIndex{},fastIndex = 0;
        // 清空前面的空格
        while(fastIndex < n && s[fastIndex] == ' ') fastIndex++;

        // 清空中间的空格
        for(;fastIndex < n;++fastIndex){
            if(fastIndex-1 > 0 && s[fastIndex] == s[fastIndex-1] && s[fastIndex] == ' '){
                continue;
            }else{
                s[slowIndex++] = s[fastIndex];
            }
        }

        // 清空尾部的空格
        if(slowIndex - 1 >0 && s[slowIndex-1] == ' '){
            s.resize(slowIndex-1);
        }else{
            s.resize(slowIndex);
        }
    }

    // 翻转字符串，双指针翻转
    void reverse(string &s,int start,int end){
        for(int i = start,j = end; i<j;++i,--j){
            swap(s[i],s[j]);
        }
    }

    string reverseWords(string s) {
        // 清空字符串空格
        emptySpace(s);
        // 翻转整体字符串
        reverse(s,0,s.size()-1);
        // 单个翻转字符串
        for(int i{};i<s.size();++i){
            int j = i;
            while(j < s.size() && s[j] != ' ') j++;
            reverse(s,i,j-1);
            i = j;
        }
        return s;
    }
};

剑指Offer58-II.左旋转字符串

class Solution {
public:
	// 直接使用reverse反转
    string reverseLeftWords(string s, int n) {
    	// 先翻转前n个字符
        reverse(s.begin(),s.begin() + n);
        // 再反转剩余的字符
        reverse(s.begin() + n,s.end());
        // 最后全部反转
        reverse(s.begin(),s.end());

        return s;
    }
};

28.实现strStr()

class Solution {
public:
    // 获取next数组
    void getNext(int *next,string& s){
        next[0] = 0;
        int i{},j{};

        for(i = 1;i<s.size();++i){
            while(j > 0 && s[i]!=s[j]){// 前后缀不相同了
                j = next[j-1]; // j向前回退
            }

            if(s[i] == s[j]){ // 找到相同的前后缀
                j++;
            }

            next[i] = j; // 将j（前缀的长度）赋给next[i]
        }
    }
    // KMP算法求解
    int strStr(string haystack, string needle) {
        if(needle.size() == 0) return 0;
        int next[needle.size()];
        // 获取next数组
        getNext(next,needle);

        int j{};
        for(int i{};i<haystack.size();++i){
            while(j > 0 && haystack[i] != needle[j]){// 不匹配
                j = next[j-1]; // j寻找之前匹配的位置
            }

            if(haystack[i] == needle[j]){// 匹配，j和i同时向后移动
                j++;
            }

            if(j == needle.size()){// 文本串haystack中出现了模式串needle
                return (i-needle.size() +1);
            }
        }

        return -1;
    }
};

459.重复的子字符串

class Solution {
public:
    // 获取next数组
    void getNext(int *next,string& s){
        next[0] = 0;
        int i{},j{};

        for(i = 1;i<s.size();++i){
            while(j > 0 && s[i]!=s[j]){// 前后缀不相同了
                j = next[j-1]; // j向前回退
            }

            if(s[i] == s[j]){ // 找到相同的前后缀
                j++;
            }

            next[i] = j; // 将j（前缀的长度）赋给next[i]
        }
    }
    bool repeatedSubstringPattern(string s) {
        if(s.size() == 0) return false;
        int next[s.size()];
        getNext(next,s);

        int n = s.size();
        if(next[n-1] !=0 && n%(n-next[n-1]) == 0){
            return true;
        }

        return false;
    }
};