LeetCode（Weekly Contest 184）题解

西凉风雷

发布于 2022-11-23 19:42:45

1800

发布于 2022-11-23 19:42:45

文章被收录于专栏：容器与 Kubernetes 游记容器与 Kubernetes 游记

0. 前言

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

1. 题解

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

中文版题目描述：https://leetcode-cn.com/problems/string-matching-in-an-array/
英文版题目描述：https://leetcode.com/problems/string-matching-in-an-array/
思路：排序+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 种 ABC 的情况，6 种 ABA 的情况
- 当前层只与上一层和本层有关
- 当上一层为 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<long long> dp1 = vector<long long>(n, (long long)1);
        vector<long long> dp2 = vector<long long>(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;
    }
};