7.字符串子序列问题

可以用双指针/动态规划完成。

如392、524题

注：compare方法模板str1.compare(str2);用来比较两个字符串哪个的字符序更小（而非长度）

1
2
3
4
std::string str1 = "abc";
std::string str2 = "def";

int result = str1.compare(str2);//返回负数
  • 如果 str1 小于 str2，则 result 将为负数。
  • 如果 str1 等于 str2，则 result 将为 0。
  • 如果 str1 大于 str2，则 result 将为正数。

判断s是否是t的子字符串

1
2
3
4
5
6
7
8
9
10
11
bool isSubsequence(string s, string t) {
        int sPos=0,tPos=0;
        int n=s.length(),m=t.length();
        while(sPos<n&&tPos<m){
            if(s[sPos]==t[tPos]){
                sPos++;
            }
            tPos++;
        }
        return sPos==n;
}

8.高精度运算

8-1.加一：66

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size(), pos = n - 1;
        while (pos >= 0) {
            if (digits[pos] != 9) {
                digits[pos]++;
                return digits;
            } else {
                digits[pos--] = 0;
            }
        }
        //全是9的情况
        digits.emplace_back(0);
        digits[0] = 1; //其他数字已经在while循环中被改成9了
        return digits;
    }
};

8-2.二进制求和：67

法一：模拟(最优)

关键在于多次进行reverse方便运算和进位；同时进位数carry的处理也很巧妙。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string addBinary(string a, string b) {
        string ans;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        int n = max(a.size(), b.size()), carry = 0;
        for (size_t i = 0; i < n; i++) {
            carry += i < a.size() ? (a[i] == '1') : 0;
            carry += i < b.size() ? (b[i] == '1') : 0;
            ans += carry % 2 ? "1" : "0";
            carry /= 2;
        }
        if (carry) {
            ans += "1";
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

法二：位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string addBinary(string a, string b) {
        // 使用bitset来处理二进制相加
        bitset<10000> x(a);
        bitset<10000> y(b);
        while (y.any()) {
            // 计算当前位的和和进位
            bitset<10000> sum = x ^ y;
            bitset<10000> carry = (x & y) << 1;
            // 更新x和y
            x = sum;
            y = carry;
        }
        // 将bitset转换为字符串，并去除前导零
        string ans = x.to_string();
        size_t startPos = ans.find('1');
        if (startPos != string::npos) {  //能找到
            return ans.substr(startPos);
        } else {
            return "0";
        }
    }
};

  • 根据题干，由于1 <= a.length, b.length <= 10^4，因此a可能位数很长，需要很长的二进制数来存储，常规的int x=stoi(a,0,2)会导致溢出，因此这里使用1e4位的bitset来存储转换的a.a不需要转换为其他参数，string或者int等等都可以直接转换为bitset。一般来说，如果a仅仅是一个int型整数，那么只需要bitset<32>即可，因为int范围在$-2^{31}$ 到 $2^{31} - 1$，

  • while循环中应该使用y.any()而非y：在C++中，std::bitset 类型的对象不可以隐式地被转换为 bool 类型。如果 y 是一个 std::bitset 对象，y 会被用作一个条件表达式时，它无法隐式地转换为 bool。使用 y.any() 是一种更明确的方式来表达循环的终止条件，因为它直接检查 std::bitset 是否有任何非零位，所有位均为0时为false退出循环。

  • (x&y)<<1:处理进位。

    1. x & y: 这是 x 和 y 的按位与运算。在二进制中，每一位上的结果是取两个数对应位上的逻辑与（AND）运算。例如，如果 x 的某一位是1，而 y 的相同位置也是1，那么结果的相应位就是1；否则为0。

    2. (x & y) << 1: 这是将上述按位与运算的结果左移一位。左移运算是将二进制数的每一位向左移动指定的位数，右侧空出的位补0。因此，(x & y) << 1 就是将 (x & y) 的所有位都向左移动一位。

  • x.to_string():x为bitset类型的对象。x.to_string() 是用于调用对象的成员函数，而 to_string(x) 是用于将基本数据类型(比如int)转换为字符串。

  • size_t startPos = ans.find('1'):字符串中的find方法在找寻到第一个‘1’后，返回size_t类型的结果。如果没有找到，则返回std::string::npos。size_t 是一种无符号整数类型，通常用于表示对象的大小、索引或长度。它是通过包含头文件 <cstddef>（或 <stddef.h>，在C语言中）来引入的。

    C++标准规定了 size_t 的属性，它被定义为一个足够大以容纳程序中可能的最大对象大小的无符号整数类型。因此，size_t 的大小在不同的平台和编译器中可能会有所不同，但通常足够大以满足实际需求。

  • ans.substr(startPos);：substr方法可以只接受一个参数pos,表示这个子字符串时从pos这个位置开始一直到最后(这时候不用再特地说明长度length)

  • stoi(a,0,2)或者stoi(a,nullptr,2):将字符串a转换为2进制的数，并用int表达。比如a=”10101111”，则转换为int x=101011111。0或者nullptr 是用于存储转换错误位置的指针。如果转换过程中发生错误，stoi 函数会将错误的位置存储在这个指针指向的位置。在这里，0或者nullptr表示不存储错误位置。2表示基数，即转换为几进制。

8-3.字符串相加：415、字符串相乘：43

类似8-2，使用模拟法

字符串相乘法二：优化竖式

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
class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        int n = num1.length() + num2.length();
        vector<int> res(n);
        for (int i = num1.length() - 1; i >= 0; i--) {
            for (int j = num2.length() - 1; j >= 0; j--) {
                int sum = res[i + j + 1] + (num1[i] - '0') * (num2[j] - '0');
                res[i + j + 1] = sum % 10;
                res[i + j] += sum / 10;
            }
        }
        string ans = "";
        for (int i = 0; i < n; i++) {
            if (i == 0 && res[i] == 0) {
                continue; //去掉前置0
            }
            ans += to_string(res[i]);
        }
        return ans;
    }
};

这里也可以先像前面的题一样反转字符串以后再从前往后算，之后再倒回来。

8-4.累加数：306

1

9.字符串变换

9-1.Z字形变换：6

法一：压缩矩阵存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string convert(string s, int numRows) {
        int n = s.length(), r = numRows;
        if (r == 1 || r == n) {
            return s;
        }
        vector<string> mat(r);
        for (int i = 0, x = 0, t = r * 2 - 2; i < n; i++) {
            mat[x] += s[i];//x记录行数
            i % t < r - 1 ? ++x : --x;//第i%t行读取结束就继续下一行
        }
        string ans;
        for (auto& row : mat) {
            ans += row;
        }
        return ans;
    }
};

法二：直接构造

观察下标规律：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string convert(string s, int numRows) {
        int n = s.length(), r = numRows;
        if (r == 1 || r == n) {
            return s;
        }
        string ans;
        int t = r * 2 - 2; //使得s[t]是第二个竖直列的第一个元素
        for (int i = 0; i < r; i++) {
            for (int j = 0; j + i < n; j += t) { //遍历第i行的元素
                ans += s[j + i];
                if (i > 0 && i < r - 1 && j + t - i < n) {
                    ans += s[j + t - i];
                }
            }
        }
        return ans;
    }
};

9-2.文本左右对齐：68

贪心算法+模拟

详见：平均分布额外空格

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    string fillWords(vector<string>& words, int bg, int ed, int maxWidth,
                     bool lastLine = false) {
        int wordCount = ed - bg + 1;//end减去begin后再加1
        int spaceCount =
            maxWidth + 1 - wordCount; // 除去每个单词尾部空格， + 1
                                      // 是最后一个单词的尾部空格的特殊处理
        for (int i = bg; i <= ed; i++) {
            spaceCount -= words[i].size(); // 除去所有单词的长度
        }
        int spaceSuffix = 1; // 词尾空格
        int spaceAvg = (wordCount == 1)
                           ? 1
                           : spaceCount / (wordCount - 1); // 额外空格的平均值
        int spaceExtra = (wordCount == 1)
                             ? 0
                             : spaceCount % (wordCount - 1); // 额外空格的余数
        string ans;
        for (int i = bg; i < ed; i++) {
            ans += words[i]; // 填入单词
            if (lastLine) {  // 特殊处理最后一行
                fill_n(back_inserter(ans), 1, ' ');
                continue;
            }
            fill_n(back_inserter(ans),
                   spaceSuffix + spaceAvg + ((i - bg) < spaceExtra),
                   ' '); // 根据计算结果补上空格
        }
        ans += words[ed]; // 填入最后一个单词
        fill_n(back_inserter(ans), maxWidth - ans.size(), ' ');
        // 补上这一行最后的空格
        return ans;
    }
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> ans;
        int cnt = 0;
        int bg = 0;
        for (int i = 0; i < words.size(); i++) {
            cnt += words[i].size() + 1;
            if (i + 1 == words.size() ||
                cnt + words[i + 1].size() >
                    maxWidth) { // 如果是最后一个单词，或者加上下一个词就超过长度了，即可凑成一行
                ans.push_back(
                    fillWords(words, bg, i, maxWidth, i + 1 == words.size()));
                bg = i + 1;
                cnt = 0;
            }
        }
        return ans;
    }
};

10.字符串匹配(难度较高)

10-1.找出字符串中第一个匹配项的下标:28

法一：暴力匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        for (int i = 0; i + m <= n; i++) {
            bool flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack[i + j] != needle[j]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }
};

使用substr与之同理：

substr()的时间复杂度为$O(n)$,空间复杂度是$O(1)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int strStr(string haystack, string needle) {
        for (int i = 0; i < haystack.size(); i++) {
            if (haystack[i] == needle[0]) { //第一个字符是否相等再决定是不是要尝试匹配整个字符串
                string x = haystack.substr(i, needle.size());
                if (x == needle) {
                    return i;
                }
            }
        }
        return -1;
    }
};

法二：KMP算法

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
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) {
            return 0;
        }
        vector<int> next(m);
        for (int i = 1, j = 0; i < m; i++) { //计算出next数组
            while (j > 0 && needle[i] != needle[j]) {
                j = next[j - 1];
            }
            if (needle[i] == needle[j]) {
                j++;
            }
            next[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) { //根据next数组进行匹配
            while (j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
};

关于KMP

常见字符串匹配算法

讲解：字符串匹配之Sunday、KMP和BM算法入门级讲解

  1. 暴力匹配算法（Brute Force）：也称为朴素字符串匹配算法，它通过逐个比较文本和模式串的字符来进行匹配。

  2. KMP算法：KMP算法利用模式串自身的特点，通过构建部分匹配表（next数组）来实现快速匹配。

  3. Boyer-Moore算法：该算法通过从右往左比较模式串和文本串，利用坏字符规则和好后缀规则来快速定位匹配位置。

  4. Rabin-Karp算法：Rabin-Karp算法利用哈希函数来快速比较文本中的子串和模式串，以确定是否需要进行进一步的精确比较（首先是计算两个字符串的哈希值，然后通过比较这两个哈希值的大小来判断是否出现匹配）。

  5. Sunday算法：Sunday算法是一种简单而高效的字符串匹配算法，它利用预处理模式串得到的偏移表，以便在匹配失败时快速移动模式串。

10-2.重复叠加字符串匹配：686

法一：KMP.

时间复杂度：$O(n+m)$，空间复杂度：$O(m)$。

该题代码：

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
37
38
39
40
41
42
43
44
45
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) {
            return 0;
        }
        vector<int> next(m);
        // 计算出next数组
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle[i] != needle[j]) {
                j = next[j - 1];
            }
            if (needle[i] == needle[j]) {
                j++;
            }
            next[i] = j;
        }
        // 根据next数值进行匹配
        for (int i = 0, j = 0; i - j < n; i++) { // b 开始匹配的位置是否超过第一个叠加的 a
            while (j > 0 && haystack[i % n] != needle[j]) { //i%n,因为可能是多个haystack重复
                j = next[j - 1];
            }
            if (haystack[i % n] == needle[j]) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }

    int repeatedStringMatch(string a, string b) {
        int an = a.size(), bn = b.size();
        int index = strStr(a, b);
        if (index == -1) {
            return -1;
        }
        if (an - index >= bn) {
            return 1;
        }
        return (bn + index - an - 1) / an + 2;
    }
};

法二：Rabin-Karp算法

时间复杂度：O(n+m)，空间复杂度：O(1)。

关于Rabin-Karp的讲解:Rabin–Karp 算法

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
37
38
#define BASE 256
#define MODULUS 101

void RabinKarp(char t[], char p[])
{
    int t_len = strlen(t);
    int p_len = strlen(p);

    // 哈希滚动之用
    int h = 1;
    for (int i = 0; i < p_len - 1; i++)
        h = (h * BASE) % MODULUS;

    int t_hash = 0;
    int p_hash = 0;
    for (int i = 0; i < p_len; i++)
    {
        t_hash = (BASE * t_hash + t[i]) % MODULUS;
        p_hash = (BASE * p_hash + p[i]) % MODULUS;
    }

    int i = 0;
    while (i <= t_len - p_len)
    {
         // 考虑到哈希碰撞的可能性，还需要用 memcmp 再比对一下
        if (t_hash == p_hash && memcmp(p, t + i, p_len) == 0)
            cout << p << " is found at index " << i << endl;

        // 哈希滚动
        t_hash = (BASE * (t_hash - t[i] * h) + t[i + p_len]) % MODULUS;

        // 防止出现负数
        if (t_hash < 0)
            t_hash = t_hash + MODULUS;

        i++;
    }
}

该题代码：

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
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) {
            return 0;
        }

        long long k1 = 1e9 + 7;  // 选择一个较大的质数作为模数
        long long k2 = 1337;  // 另选一个较小的质数
        srand((unsigned)time(NULL));  // 初始化随机数种子
        long long kMod1 = rand() % k1 + k1;  // 生成一个随机数作为模数
        long long kMod2 = rand() % k2 + k2;  // 生成另一个随机数作为模数

        long long hash_needle = 0;  // 初始化模式串的哈希值
        for (auto c : needle) {
            hash_needle = (hash_needle * kMod2 + c) % kMod1;  // 计算模式串的哈希值
        }
        long long hash_haystack = 0, extra = 1;  // 初始化文本串的哈希值和额外变量
        for (int i = 0; i < m - 1; i++) {
            hash_haystack = (hash_haystack * kMod2 + haystack[i % n]) % kMod1;  // 计算文本串的哈希值
            extra = (extra * kMod2) % kMod1;  // 更新额外变量
        }
        for (int i = m - 1; (i - m + 1) < n; i++) {
            hash_haystack = (hash_haystack * kMod2 + haystack[i % n]) % kMod1;  // 更新文本串的哈希值
            if (hash_haystack == hash_needle) {  // 检查哈希值是否匹配
                return i - m + 1;  // 返回匹配位置
            }
            hash_haystack = (hash_haystack - extra * haystack[(i - m + 1) % n]) % kMod1;  // 更新文本串的哈希值
            hash_haystack = (hash_haystack + kMod1) % kMod1;  // 处理负数情况
        }
        return -1;  // 未找到匹配，返回-1
    }

    int repeatedStringMatch(string a, string b) {
        int an = a.size(), bn = b.size();  // 获取字符串a和b的长度
        int index = strStr(a, b);  // 调用strStr函数查找b在a中的匹配位置
        if (index == -1) {  // 如果未找到匹配位置
            return -1;  // 返回-1
        }
        if (an - index >= bn) {  // 如果匹配位置之后的长度大于等于b的长度
            return 1;  // 返回1，表示a本身就包含了至少一个b
        }
        return (bn + index - an - 1) / an + 2;  // 返回重复拼接a后能够包含b的最小次数
    }
};

10-3.重复的子字符串：459

10-4.最短回文串：214（困难）

11.中心拓展法

中心拓展法的基本思想是以字符串中的每个字符（或者每两个字符之间）为中心，向两边扩展，以寻找最长的回文串。这种方法的时间复杂度较低，因为在中心拓展时，只需要线性的时间。

具体步骤如下：

  1. 遍历字符串，以每个字符（或者每两个字符之间）为中心，向两边扩展，直到不再满足回文串的条件。
  2. 在扩展的过程中，记录下最长的回文串的起始位置和长度。

中心拓展法在解决回文串相关问题时非常有效，例如在寻找最长回文子串或者统计回文子串的个数时，该方法可以提供较高的效率。

11-1.最长回文子串：5

法一：动态规划

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
37
38
39
40
41
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2) {
            return s;
        }

        int maxLen = 1, begin = 0;
        vector<vector<int>> dp(n, vector<int>(n));
        // 边界条件P(i,i)=true
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        // 枚举子串长度L
        for (int L = 2; L <= n; L++) {
            for (int i = 0; i < n; i++) {
                int j = L + i - 1;
                if (j >= n) {
                    break;
                }
                if (s[i] != s[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) { //(j-1)-(i+1)<=0
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                // 只要 dp[i][j] == true 成立，就表示子串 s[i..j]
                // 是回文，此时记录回文长度和起始位置
                if (dp[i][j]) {
                    maxLen = max(maxLen, j - i + 1);
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxLen);
    }
};

法二：中心扩展法

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
class Solution {
public:
    pair<int, int> expandAroundCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            // 满足回文条件，向两边扩展
            --left;
            ++right;
        }
        return {left + 1, right - 1};
    }

    string longestPalindrome(string s) {
        int start = 0, end = 0; // 从最左侧边界开始
        // 如果从最右侧边界，则start和end初始值应为s.size;同时auto [left2,right2]=expandAroundCenter(s,i-1,i);
        // 然后i从s.size()-1反向遍历nter(s,i-1,i);
        for (int i = 0; i < s.size(); i++) {
            auto [left1, right1] = expandAroundCenter(s, i, i);     // a'b'a
            auto [left2, right2] = expandAroundCenter(s, i, i + 1); // a'bb'a
            if (right1 - left1 > end - start) {
                start = left1;
                end = right1;
            }
            if (right2 - left2 > end - start) {
                start = left2;
                end = right2;
            }
        }
        return s.substr(start, end - start + 1);
    }
};

法三：Manacher算法(了解)

11-2.统计回文子串数目：647

三个方法类似11-1，这里展示中心扩展法代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int expandAroundCenter(const string& s, int left, int right) {
        int ans = 0;
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left;
            ++right;
            ++ans;
        }
        return ans;
    }

    int countSubstrings(string s) {
        int left = 0, right = 0, ans = 0;
        for (int i = 0; i < s.size(); i++) {
            ans +=expandAroundCenter(s, i, i) + expandAroundCenter(s, i, i + 1);
        }
        return ans;
    }
};