0. 前言

• 中文版地址：https://leetcode-cn.com/contest/weekly-contest-183/
• 英文版地址：https://leetcode.com/contest/weekly-contest-183/

1. 题解

1.1 5380. 数组中的字符串匹配（1408. String Matching in an Array）

• 中文版题目描述：https://leetcode-cn.com/problems/string-matching-in-an-array/submissions/
• 英文版题目描述：https://leetcode.com/problems/string-matching-in-an-array/
• 思路：暴力求解，数据很弱
  • 排序+KMP 判断子串（貌似也不用 KMP，直接判断即可）
  • 记得答案去重，因为一个字符串可能是好多个字符串的子串
• 代码如下：

class Solution {
public:
    vector<int> getNext(string pattern) {
        int len = (int)pattern.length();
        vector<int> res(len+1,0);
        int j = 0;
        for (int i = 1 ; i < len ; i++) {
            while (j && pattern[i] != pattern[j])   j = res[j];
            if (pattern[i] == pattern[j])   j++;
            res[i+1] = j;
        }
        return res;
    }

    int searchPosition(string text, string pattern, vector<int>& next) {
        int j = 0 , lt = (int)text.length() , lp = (int)pattern.length();
        for (int i = 0 ; i < lt ; i++) {
            while (j && text[i] != pattern[j])  j = next[j];
            if (text[i] == pattern[j])  j++;
            if (j == lp)    return i-j+1;
        }
        return -1;
    }
    bool isSubstr(string pattern, string text, unordered_map<string, vector<int>>& nextmp) {
        if (searchPosition(text, pattern, nextmp[pattern]) >= 0)    return true;
        else    return false;
    }
    vector<string> stringMatching(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string& a, const string& b) {
            return a.length() < b.length();
        });
        unordered_map<string, vector<int>> nextmp;
        for (auto str : words) {
            nextmp[str] = getNext(str);
        }
        int n = words.size();
        vector<string> ans;
        unordered_map<string, bool> vis;
        for (int i = 0 ; i < n ; i++) {
            for (int j = i+1 ; j < n ; j++) {
                if (!vis[words[i]] && isSubstr(words[i], words[j], nextmp)) {
                    ans.push_back(words[i]);
                    vis[words[i]] = true;
                }
            }
        }
        return ans;
    }
};

1.2 5381. 查询带键的排列（1409. Queries on a Permutation With Key）

• 中文版题目描述：https://leetcode-cn.com/problems/queries-on-a-permutation-with-key/
• 英文版题目描述：https://leetcode.com/problems/queries-on-a-permutation-with-key/
  
• 思路：模拟方法
  • 把题意走一遍即可，O(m^2 的复杂度
• 代码如下：

class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        vector<int> p = vector<int>(m, 0);
        for (int i = 0 ; i < m ; i++) {
            p[i] = i + 1;
        }
        vector<int> ans;
        for (auto q : queries) {
            for (int i = 0 ; i < m ; i++) {
                if (q == p[i]) {
                    ans.push_back(i);
                    for (int j = i ; j >= 1 ; j--) {
                        p[j] = p[j-1];
                    }
                    p[0] = q;
                }
            }
        }
        return ans;
    }
};

1.3 5382. HTML 实体解析器（1410. HTML Entity Parser）

• 中文版题目描述：https://leetcode-cn.com/problems/html-entity-parser/
• 英文版题目描述：https://leetcode.com/problems/html-entity-parser/
• 思路：Java 的库函数可以一行解决，C++ 采用模拟
  • 有的朋友说模拟超时，可能是遍历字符串没有注意跳转整个已经匹配的目标子串吧
• 代码如下：

class Solution {
public:
    string entityParser(string text) {
        int len = text.length();
        string ans = "";
        for (int i = 0 ; i < len ; ) {
            if (text[i] == '&') {
                if (text[i+1] == 'q' && text[i+2] == 'u' && text[i+3] == 'o' && text[i+4] == 't' && text[i+5] == ';') {
                    ans += '"';
                    i += 6;
                } else if (text[i+1] == 'a' && text[i+2] == 'p' && text[i+3] == 'o' && text[i+4] == 's' && text[i+5] == ';') {
                    ans += '\'';
                    i += 6;
                } else if (text[i+1] == 'a' && text[i+2] == 'm' && text[i+3] == 'p' && text[i+4] == ';') {
                    ans += '&';
                    i += 5;
                } else if (text[i+1] == 'g' && text[i+2] == 't' && text[i+3] == ';') {
                    ans += '>';
                    i += 4;
                } else if (text[i+1] == 'l' && text[i+2] == 't' && text[i+3] == ';') {
                    ans += '<';
                    i += 4;
                } else if (text[i+1] == 'f' && text[i+2] == 'r' && text[i+3] == 'a' && text[i+4] == 's' && text[i+5] == 'l' && text[i+6] == ';') {
                    ans += '/';
                    i += 7;
                } else {
                    ans += '&';
                    i++;
                }
            } else {
                ans += text[i];
                i++;
            }
        }
        return ans;
    }
};

1.4 5383. 给 N x 3 网格图涂色的方案数（1411. Number of Ways to Paint N × 3 Grid）

• 中文版题目描述：https://leetcode-cn.com/problems/number-of-ways-to-paint-n-x-3-grid/
• 英文版题目描述：https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/
• 思路：找规律
  • 第一层，有 12 种情况，分别为 6 种形如 ABA 和 6 种 ABC 的情况，分别分析这类情况
  • 当前层的颜色选择只取决于上一层和本层相邻位置
  • 如果上一层是 ABC 的情况，会产生 2 种 ABC 和 2 种 ABA 的情况
  • 如果上一层是 ABA 的情况，会产生 2 种 ABC 和 3 种 ABA 的情况
  • 设 dp1[i] 表示第 i 层，ABC 的情况，dp2[i] 表示第 i 层 ABA 的情况
  • dp1[i] = dp1[i-1] * 2 + dp2[i-1] * 2
  • dp2[i] = dp1[i-1] * 2 + dp2[i-1] * 3
• 代码如下：

class Solution {
public:
    int numOfWays(int n) {
        long long mod = 1000000007;
        vector dp1 = vector(n, (long long)1);
        vector dp2 = vector(n, (long long)1);
        for (int i = 1 ; i < n ; i++) {
            dp1[i] = (dp1[i-1] * (long long)2 + dp2[i-1] * (long long)2) % mod;
            dp2[i] = (dp1[i-1] * (long long)2 + dp2[i-1] * (long long)3) % mod;
        }
        long long ans = (long long)6 * (dp1[n-1] + dp2[n-1]) % mod;
        return (int)ans;
    }
};

2. 小结

• 本期题目相对较水，前三题不是暴力就是模拟，第四题找到规律即可
• 切记不要排斥暴力求解法，有的时候挺好用的，哈哈哈