代码随想录1刷—字符串篇

344. 反转字符串

class Solution {
public:
    void reverseString(vector<char>& s) {
        int i = 0;
        int j = s.size()-1;
        for(i,j;i<s.size()/2;i++,j--){
            s[i]^=s[j];
            s[j]^=s[i];
            s[i]^=s[j];
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

swap(s[i],s[j]);的两种实现方式

• 交换数值：

int tmp = s[i];
s[i] = s[j];
s[j] = tmp;
1
2
3

• 位运算：

s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
1
2
3

541. 反转字符串 II

class Solution {
public:
    void reverse(string&s,int start,int end){
        for(int i = start,j = end;i < j;i++,j--){
            swap(s[i],s[j]);
        }
    }
    string reverseStr(string s, int k) {
        for(int i = 0;i < s.size();i += (2 * k)){
            if(i + k <= s.size()){
                reverse(s,i,i + k - 1);
                continue;
            }
            reverse(s,i,s.size() - 1);
        }
        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

剑指 Offer 05. 替换空格

为什么要从后向前填充？

如果从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。

其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

这么做有两个好处：

1. 不用申请新数组。
2. 从后向前填充元素，避免了从前先后填充元素要来的 每次添加元素都要将添加元素之后的所有元素向后移动。

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0;
        int sizeOld = s.size();
        for(int i = 0;i < sizeOld;i++){
            if(s[i] == ' '){
                count++;
            }
        }
        s.resize(s.size() + count * 2);
        int sizeNew = s.size();
        for(int i = sizeOld - 1,j = sizeNew - 1;i < j;i--,j--){
            if(s[i] != ' '){
                s[j] = s[i];
            }else{
                s[j] = '0';
                s[j-1] = '2';
                s[j-2] = '%';
                j -= 2 ;
            }
        }
        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

151. 颠倒字符串中的单词

class Solution {
public:
    void reverse(string& s, int start, int end){            //翻转
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }

    void removeExtraSpaces(string& s) {             //去除所有空格并在相邻单词之间添加空格
        int slow = 0;   
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != ' ') {                  //遇到非空格就处理，即删除所有空格。
                if (slow != 0) s[slow++] = ' '; //给单词之间添加空格。
                                                //slow!=0说明不是第一个单词，需要在单词前加空格。
                while (i < s.size() && s[i] != ' ') {       //补上该单词，遇到空格说明单词结束。
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow);                         //slow的大小即为去除多余空格后的大小。
    }

    string reverseWords(string s) {
        removeExtraSpaces(s);           
        //去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。
        reverse(s, 0, s.size() - 1);
        int start = 0; 
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') { //到达空格或者串尾，说明一个单词结束。进行翻转。
                reverse(s, start, i - 1);       //翻转，注意是左闭右闭 []的翻转。
                start = i + 1;                  //更新下一个单词的开始下标start
            }
        }
        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

剑指 Offer 58 - II. 左旋转字符串

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(), s.begin() + n);
        reverse(s.begin() + n, s.end());
        reverse(s.begin(), s.end());
        return s;
    }
};
1
2
3
4
5
6
7
8
9

题外话：++i和i++到底有什么不一样？

本质上

单独拿出来说，i++和++i的意思是一样的，就是i = i + 1。

运算符

如果当做运算符来说，如果a = i++ 和 a = ++i这样的形式，情况就不一样了。

a = i++的意思是，先把i的值赋给a，即a = i，再执行i = i + 1；而a = ++i是先执行 i = i+1，再把i的值赋给a；

举个例子来说，如果一开始i=4。

那么执行a=i++这条语句之后，a=4，i=5；执行a=++i这条语句之后，i=5，a=5；

同理，i--和--i的用法也是一样的。

循环体

①for循环中，for(int i = 0;i < 6;i++)和for(int i = 0;i < 6;++i)效果一样

② while(i++)是先用i的初始化值做循环变量再i+1；而while(++i)是先用i的初始值+1,再循环

K！M！P！它！来！了！

基础知识

KMP的经典思想就是：**当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。**主要应用在字符串匹配上。如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。next数组就是一个前缀表（prefix table）。前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

首先要知道前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置。

什么是前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

其中n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)，之前还要单独生成next数组，时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(n+m)的。暴力的解法显而易见是O(n × m)，所以KMP在字符串匹配中极大的提高的搜索的效率。

getNext的代码！很重要！

void getNext(int* next, const string& s) {
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // 注意i从1开始
        while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
            j = next[j]; // 向前回退
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后缀
            j++;
        }
        next[i] = j; // 将j（前缀的长度）赋给next[i]
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

经典例题

28. 实现 strStr()

class Solution {
public:
    void getNext(int *next,const string& s){
        int j = 0;
        next[0] = j;
        for(int i = 1;i <s.size();i++){
            while(j > 0 && s[i] != s[j]){
                j = next[j - 1];    //回退
            }
            if(s[i] == s[j]){
                j++;
            }
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        if(needle.size() == 0) return 0;
        int next[needle.size()];
        getNext(next,needle);
        int j = 0;
        for(int i = 0;i < haystack.size();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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

459. 重复的子字符串

next 数组记录的就是最长相同前后缀， 如果 next[len - 1] != 0，则说明字符串有最长相同的前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度）。

最长相等前后缀的长度为：next[len - 1] 。数组长度为：len。

如果len % (len - (next[len - 1] )) == 0 ，则说明 (数组长度-最长相等前后缀的长度) 正好可以被数组的长度整除，说明有该字符串有重复的子字符串。

数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。

next[len - 1] =8，8就是此时字符串asdfasdfasdf的最长相同前后缀的长度。

(len - (next[len - 1])) 也就是： 12(字符串的长度) - 8(最长公共前后缀的长度) = 4， 4正好可以被 12(字符串的长度) 整除，所以说明有重复的子字符串（asdf）。

class Solution {
public:
    void getNext (int* next, const string& s){
        next[0] = 0;
        int j = 0;
        for(int i = 1;i < s.size(); i++){
            while(j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if(s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }

    bool repeatedSubstringPattern(string s) {
        if (s.size() == 0) {
            return false;
        }
        int next[s.size()];
        getNext(next, s);
        int len = s.size();
        if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
            return true;
        }
        else{
        return false;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31