鸽到第九周周二来写倍感惭愧。

这周东西有点多，力扣做了不少，数据结构实验课强度也高。

数据结构实验课

KMP模板

给出两个字符串 s1​ 和 s2​，若 s1​ 的区间 [l,r] 子串与 s2​ 完全相同，则称 s2​ 在 s1​ 中出现了，其出现位置为 l。 现在请你求出 s2​ 在 s1​ 中所有出现的位置。

定义一个字符串 s 的 border 为 s 的一个非 s 本身的子串 t，满足 t 既是 s 的前缀，又是 s 的后缀。 对于 s2​，你还需要求出对于其每个前缀 s′ 的最长 border t′ 的长度。

解答

我已经累到不想解释了。

#include <string>
#include <vector>
#include <iostream>
using namespace std;

string s1;
string s2;


vector<int> getNext(string &s) {
    vector<int> nextArr(s.size());
    nextArr[0] = 0;
    nextArr[1] = 0;
    for (int i = 1, j = 0; i < nextArr.size(); i++) {
        while (j > 0 && s[i] != s[j]) {
            j = nextArr[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        nextArr[i] = j;
    }
    return nextArr;
}

int main() {
    cin >> s1;
    cin >> s2;
    auto nextArr = getNext(s2);
    for (int i = 0, j = 0; i < s1.size(); i++) {
        while (j > 0 && s1[i] != s2[j]) {
            j = nextArr[j - 1];
        }
        if (s1[i] == s2[j]) {
            j++;
        }
        if (j == s2.size()) {
            cout << i - s2.size() + 2 << endl;
            j = nextArr[j - 1];
        }
    }
    for (auto &n : nextArr) {
        cout << n << " ";
    }
}

最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串，假定唯一。

解答

其实做法很暴力，直接从头到尾每个位置找最长回文子串，然后记录最大长度即可。

注意回文子串有奇偶两种，要分别计算。记录答案直接存起始下标和长度即可，长度可以在找回文串时计算出来。

#include <string>
#include <iostream>
using namespace std;

int main() {
    string s;
    cin >> s;
    int maxAns = 0;
    int start = 0;
    for (int i = 0; i < s.size(); i++) {
        int right = i;
        int left = i;
        int maxLength;
        int len1, len2;
        while (left >= 0 && right < s.size()) {
            if (s[left] == s[right]) {
                left--;
                right++;
            } else {
                len1 = right - left - 1;
                break;
            }
        }
        len1 = right - left - 1;
        left = i;
        right = i + 1;
        while (left >= 0 && right < s.size()) {
            if (s[left] == s[right]) {
                left--;
                right++;
            } else {
                len2 = right - left - 1;
                break;
            }
        }
        len2 = right - left - 1;
        maxLength = max(len1, len2);
        if (maxLength > maxAns) {
            maxAns = maxLength;
            start = i - (maxLength - 1) / 2;
        }
    }
    cout << s.substr(start, maxAns);
}

力扣

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

示例 1：

• 输入：s = "ADOBECODEBANC", t = "ABC"
• 输出："BANC"
• 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

思路

这题算是做过的滑动窗口最难的。思路是先向右延展窗口，找到第一个包含成功的子串，然后由左侧收缩窗口，对向右时遗漏的子串进行分析，直到不能收缩为止。此时再进行第一步的向右延展窗口，重复刚才的步骤。

如何对子串进行分析呢？我们建立一个哈希表来记录t中字符的个数。再建立一个动态哈希表记录动态变化子串中字符的个数。只要t表中所有字符都被动态表包含，且个数都小于动态表中的，我们就可以认为子串符合要求。

同样地，记录答案时我们只需要记录起始下标和子串长度（可以在遍历中计算出来）即可，使用string::sunstr(index, length)函数获得正确答案。

解答

class Solution {
public:

    bool check(unordered_map<char, int> &table, unordered_map<char, int> &dynamic) const {
        for (auto &p : table) {
            if (dynamic[p.first] < p.second) {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t) {
        int sLength = s.size();
        int tLength = t.size();
        if (sLength < tLength) {
            return "";
        } else if (sLength == tLength && s == t) {
            return s;
        }
        unordered_map<char, int> table;
        unordered_map<char, int> dynamic;
        for_each(t.begin(), t.end(), [&table](char ch) { table[ch]++; });
        
        int left = 0;
        int right = -1;
        int ansLength = INT_MAX;
        int ansIndex = -1;
        while (right < sLength) {
            if (table.find(s[++right]) != table.end()) {
                dynamic[s[right]]++;
            }
            while (check(table, dynamic) && left <= right) {
                int newLength = right - left + 1;
                if (newLength < ansLength) {
                    ansLength = newLength;
                    ansIndex = left;
                }
                if (table.find(s[left]) != table.end()) {
                    dynamic[s[left]]--;
                }
                left++;
            }
        }
        return ansIndex == -1 ? "" : s.substr(ansIndex, ansLength);
    }
};

3289. 数字小镇中的捣蛋鬼

思路

这种技巧类的题确实难，没见过真的很难想到好的方法。首先读清楚题意：这个数组中出现的数字是$[0, n - 1]$的所有数，其中有两个数出现两次，所以长度为$n + 1$。这种找重复第一反应肯定还是异或，只不过这题的分析稍微复杂点，让我想到了做CSAPP中Data Lab的感觉。

用一个$0$，先把nums中所有数字异或了，再把$[0,n-1]$的数字异或了，得到的就是多出来的两数字$x1 \oplus x2$的结果ans。然后通过经典技巧获得他们最小的不相同位int lowbit = ans ^ (-ans)。这时我们将数组里原有的数分为两组，一组是该位为1，一组该位为0，可以保证x1, x2分别位于两个组。然后对两组分别异或完就可以得到x1和x2的值了。

解答

class Solution {
public:
    vector<int> getSneakyNumbers(vector<int>& nums) {
        int ans {0};
        for (auto N : nums) {
            ans ^= N;
        }
        for (int i = 0; i < nums.size() - 2; i++) {
            ans ^= i;
        }
        int lowbit = ans & (-ans);
        int x1 = 0;
        int x2 = 0;
        for (auto n : nums) {
            if (lowbit & n) {
                x1 ^= n;
            } else {
                x2 ^= n;
            }
        }
        for (int i = 0; i < nums.size() - 2; i++) {
            if (lowbit & i) {
                x1 ^= i;
            } else {
                x2 ^= i;
            }
        }
        return {x1, x2};
    }
};