LeetCode（Weekly Contest 183）題解

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<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;
    }
};      

2. 小結

• 本期題目相對較水，前三題不是暴力就是模拟，第四題找到規律即可
• 切記不要排斥暴力求解法，有的時候挺好用的，哈哈哈