第 385 场 LeetCode 周赛题解-Toy模板网

这篇具有很好参考价值的文章主要介绍了第 385 场 LeetCode 周赛题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

A 统计前后缀下标对 I

第 385 场 LeetCode 周赛题解,LeetCode,leetcode,算法,模拟,字典树,哈希,字符串哈希

模拟

class Solution {
public:
    int countPrefixSuffixPairs(vector<string> &words) {
        int n = words.size();
        int res = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (words[i].size() <= words[j].size()) {
                    int li = words[i].size(), lj = words[j].size();
                    if (words[i] == words[j].substr(0, li) && words[i] == words[j].substr(lj - li, li))
                        res++;
                }
        return res;
    }
};

B 最长公共前缀的长度

第 385 场 LeetCode 周赛题解,LeetCode,leetcode,算法,模拟,字典树,哈希,字符串哈希

字典树：先将 $a rr 1$ 中元素加入字典树，然后遍历 $a rr 2$ 中元素，在字典树上查询最长的匹配的前缀

class Solution {
public:
    int longestCommonPrefix(vector<int> &arr1, vector<int> &arr2) {
        trie tree;
        for (auto x: arr1)
            tree.insert(x);
        int res = 0;
        for (auto x: arr2)
            res = max(res, tree.query(x));
        return res;
    }

    class trie {//字典树
    public:
        vector<trie *> next;

        trie() {
            next = vector<trie *>(10);
        }

        void insert(int x) {
            string s = to_string(x);
            trie *cur = this;
            for (auto c: s) {
                if (!cur->next[c - '0'])
                    cur->next[c - '0'] = new trie();
                cur = cur->next[c - '0'];
            }
        }

        int query(int x) {
            string s = to_string(x);
            trie *cur = this;
            int res = 0;
            for (auto c: s)
                if (cur->next[c - '0']) {
                    res++;
                    cur = cur->next[c - '0'];
                } else
                    break;
            return res;
        }
    };
};

C 出现频率最高的素数

第 385 场 LeetCode 周赛题解,LeetCode,leetcode,算法,模拟,字典树,哈希,字符串哈希

枚举：枚举并计数各个单元格向各方向能生成的大于10的素数

class Solution {
public:
    int mostFrequentPrime(vector<vector<int>> &mat) {
        int m = mat.size(), n = mat[0].size();
        int dr[8] = {1, 0, -1, 0, 1, 1, -1, -1};
        int dc[8] = {0, 1, 0, -1, 1, -1, 1, -1};
        unordered_map<int, int> cnt;
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++) {
                for (int k = 0; k < 8; k++) {
                    int cur = mat[r][c];
                    for (int nr = r + dr[k], nc = c + dc[k];; nr += dr[k], nc += dc[k]) {
                        if (nr < 0 || nr >= m || nc < 0 || nc >= n)
                            break;
                        cur = cur * 10 + mat[nr][nc];
                        if (isprime(cur))
                            cnt[cur]++;
                    }
                }
            }
        int mx = 0, res = -1;
        for (auto &[vi, ci]: cnt)
            if (ci > mx || ci == mx && vi > res) {
                res = vi;
                mx = ci;
            }
        return res;
    }

    bool isprime(int x) {
        for (int i = 2; i * i <= x; i++)
            if (x % i == 0)
                return false;
        return true;
    }
};

D 统计前后缀下标对 II

第 385 场 LeetCode 周赛题解,LeetCode,leetcode,算法,模拟,字典树,哈希,字符串哈希

哈希 + 字符串哈希：遍历 $w or d [i]$ ，枚举 $w or d [i]$ 的前缀，若其长为 $l$ 的前缀和长为 $l$ 的后缀相同，则答案增加 $w or d [0, i - 1]$ 中 $w or d [i]$ 长为 $l$ 的前缀的出现次数文章来源地址https://www.toymoban.com/news/detail-835091.html

class Solution {
public:
    long long countPrefixSuffixPairs(vector<string> &words) {
        int n = words.size();
        srand(time(0));
        int e = 2333 + rand() % 10, mod = 1e9 + rand() % 10;
        unordered_map<int, int> cnt;//记录字符串(通过哈希值表示)的出现次数
        long long res = 0;
        for (int i = 0; i < n; i++) {
            shash hi(words[i], e, mod);
            int m = words[i].size();
            for (int l = 1; l <= m; l++) {
                if (auto pre = hi(0, l - 1);pre == hi(m - l, m - 1) && cnt.count(pre))
                    res += cnt[pre];
            }
            cnt[hi(0, m - 1)]++;
        }
        return res;
    }

    class shash {//字符串哈希模板
    public:
        using ll = long long;
        vector<ll> pres;
        vector<ll> epow;
        ll e, p;

        shash(string &s, ll e, ll p) {
            int n = s.size();
            this->e = e;
            this->p = p;
            pres = vector<ll>(n + 1);
            epow = vector<ll>(n + 1);
            epow[0] = 1;
            for (int i = 0; i < n; i++) {
                pres[i + 1] = (pres[i] * e + s[i]) % p;
                epow[i + 1] = (epow[i] * e) % p;
            }
        }

        ll operator()(int l, int r) {
            ll res = (pres[r + 1] - pres[l] * epow[r - l + 1] % p) % p;
            return (res + p) % p;
        }
    };
};