反转字符串

344. 反转字符串

class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int i = 0, j = s.size() - 1; i < j; i ++,j --) {
            swap(s[i], s[j]);
        }
    }
};

541. 反转字符串 II

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

54. 替换数字（第八期模拟笔试）

一种神奇的替换字符串中元素的方式：先将空间开好，然后倒序枚举添加元素和要替换的元素。

#include <iostream>

using namespace std;

int main()
{
    string s; cin >> s;
    int count = 0, n = s.size();
    for (int i = 0; i < n; i ++) {
        if (s[i] >= '0' && s[i] <= '9') {
            count ++;
        }
    }

    s.resize(s.size() + count * 5);
    int m = s.size();
    for (int i = n - 1, j = m - 1; i < j; i --, j --) {
        if (s[i] < '0' || s[i] > '9') {
            s[j] = s[i];
        } else {
            s[j --] = 'r';
            s[j --] = 'e';
            s[j --] = 'b';
            s[j --] = 'm';
            s[j --] = 'u';
            s[j] = 'n';
        }
    }

    cout << s << endl;
    return 0;
}

151. 反转字符串中的单词
暴力解法

class Solution {
public:
    string reverseWords(string s) {
        stringstream ssin(s);
        string word;
        vector<string>q; // 默认为二维数组形式
        while (ssin >> word) {
            q.push_back(word);
        }
        reverse(q.begin(), q.end());
        string res = "";
        for (int i = 0; i < q.size(); i ++) {
            res += q[i];
            if (i != q.size() - 1) res += " ";
        }
        return res;
    }
};

优雅解

首先使用双指针删除空格，注意我们不能将所有的空格删除，所以我们可以在每个单词前面添加一个空格，这里使用while处理每个单词。
然后再使用双指针算法将所有的单词位置遍历出来使用reverse函数进行翻转就能得到最终的答案了。

class Solution {
public:
    string reverseWords(string s) {
        // 首先使用双指针删除空格
        // 然后将整个字符串进行翻转
        // 最后将每个单词进行翻转
        int j = 0;
        for (int i = 0; i < s.size(); i ++) {
            if (s[i] != ' ') {
                if (j != 0) s[j ++] = ' '; // 在处理单词之前添加一个空格作为分割
                // 手动处理完当前的单词
                while (i < s.size() && s[i] != ' ') {
                    s[j ++] = s[i ++];
                }
            }
        }
        s.resize(j);

        reverse(s.begin(), s.end());

        for (int i = 0; i < s.size(); i ++) {
            int j = i;
            while (j < s.size() && s[j] != ' ') {
                j ++;
            }
            reverse(s.begin() + i, s.begin() + j);
            if (j != i) i = j - 1;
        }
        return s;
    }
};

55. 右旋字符串（第八期模拟笔试）

本题可以使用substr函数直接进行拼接，也可以使用reverse函数进行翻转实现。

#include <iostream>

using namespace std;

int main()
{
    int n; cin >> n;
    string s; cin >> s;
    string res = s.substr(s.size() - n, n) + s.substr(0, s.size() - n);
    cout << res << endl;
    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int k; cin >> k;
    string s; cin >> s;

    reverse(s.begin(), s.end());
    reverse(s.begin(), s.begin() + k);
    reverse(s.begin() + k, s.end());

    cout << s << endl;
    return 0;
}

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

KMP算法

class Solution {
public:
    int strStr(string s, string p) {
        int n = s.size(), m = p.size();
        const int N = 1e4 + 10;
        int ne[N];
        s = " " + s, p = " " + p;
        for (int i = 2, j = 0; i <= m; i ++) {
            while (j && p[i] != p[j + 1]) j = ne[j];
            if (p[i] == p[j + 1]) j ++;
            ne[i] = j;
        }

        for (int i = 1, j = 0; i <= n; i ++) {
            while (j && s[i] != p[j + 1]) j = ne[j];
            if (s[i] == p[j + 1]) j ++;
            if (j == m) {
                return i - m;
                j = ne[j];
            }
        }
        return -1;
    }
};

459. 重复的子字符串

将当前字符串进行拼接，如果当前字符串是子串构成的，那么我们考虑最坏的情况，即当前字符串是由其中的一个子串重复两次构成的，只要在拼接后的字符串中还能找到原串就说明是合法的。

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string t = s + s;
        t.erase(t.begin()); t.erase(t.end() - 1); // 掐头去尾
        if (t.find(s) != string::npos) return true; // r
        return false;
    }
};