LeetCode 第385场周赛个人题解

目录

100212. 统计前后缀下标对 I

原题链接

题目描述

接口描述

思路分析

代码详解

100229. 最长公共前缀的长度

原题链接

题目描述

接口描述

思路分析

代码详解

100217. 出现频率最高的素数

原题链接

题目描述

接口描述

思路分析

代码详解

100212. 统计前后缀下标对 II

原题链接

题目描述

接口描述

思路分析

代码详解

100212. 统计前后缀下标对 I

原题链接

100212. 统计前后缀下标对 I

题目描述

给你一个下标从 0 开始的字符串数组 words 。

定义一个 布尔 函数 isPrefixAndSuffix ，它接受两个字符串参数 str1 和 str2 ：

• 当 str1 同时是 str2 的前缀（

  prefix

  ）和后缀（

  suffix

  ）时，isPrefixAndSuffix(str1, str2) 返回 true，否则返回 false。

例如，isPrefixAndSuffix("aba", "ababa") 返回 true，因为 "aba" 既是 "ababa" 的前缀，也是 "ababa" 的后缀，但是 isPrefixAndSuffix("abc", "abcd") 返回 false。

以整数形式，返回满足 i < j 且 isPrefixAndSuffix(words[i], words[j]) 为 true 的下标对 (i, j) 的 数量 。

示例 1：

输入：words = ["a","aba","ababa","aa"]
输出：4
解释：在本示例中，计数的下标对包括：
i = 0 且 j = 1 ，因为 isPrefixAndSuffix("a", "aba") 为 true 。
i = 0 且 j = 2 ，因为 isPrefixAndSuffix("a", "ababa") 为 true 。
i = 0 且 j = 3 ，因为 isPrefixAndSuffix("a", "aa") 为 true 。
i = 1 且 j = 2 ，因为 isPrefixAndSuffix("aba", "ababa") 为 true 。
因此，答案是 4 。

示例 2：

输入：words = ["pa","papa","ma","mama"]
输出：2
解释：在本示例中，计数的下标对包括：
i = 0 且 j = 1 ，因为 isPrefixAndSuffix("pa", "papa") 为 true 。
i = 2 且 j = 3 ，因为 isPrefixAndSuffix("ma", "mama") 为 true 。
因此，答案是 2 。

示例 3：

输入：words = ["abab","ab"]
输出：0
解释：在本示例中，唯一有效的下标对是 i = 0 且 j = 1 ，但是 isPrefixAndSuffix("abab", "ab") 为 false 。
因此，答案是 0 。

接口描述

class Solution {
public:
    int countPrefixSuffixPairs(vector<string>& words) {
        
    }
};

思路分析

前后缀问题很容易想到字符串哈希和字典树

这里使用字典树解法

1. 遍历字符串数组，用kmp的next数组推导方式计算出所有公共前后缀，并插入到哈希表中
2. 倒序遍历，在字典树上匹配，如果匹配长度在哈希表中存在，我们就加上这个字典树节点处的权值
3. 结束后倒序插入当前字符串

时间复杂度O(Σlen(s))

代码详解

class Solution
{
public:
    struct node
    {
        int cnt = 0;
        unordered_map<char, node *> ch;
    } *root, *t;
    bool isloop(const string &s)
    {
        int l = 0, r = (int)s.size() - 2;
        while (l < r)
            if (s[l] != s[r])
                return false;
            else
                l++, r--;
        return true;
    }
    long long countPrefixSuffixPairs(vector<string> &words)
    {
        long long ret = 0;
        root = new node;
        for (auto &s : words)
        {
            int n = s.size();
            vector<int> nxt(n + 1, -1);
            s.push_back('#');
            int j = 0, k = -1;
            unordered_set<int> mp;
            while (j < n)
            {
                if (k == -1 || s[j] == s[k])
                {
                    k++, j++;
                    nxt[j] = k;
                }
                else
                    k = nxt[k];
            }
            while (j)
                mp.insert(nxt[j]), j = nxt[j];

                mp.insert(n);
            t = root;
            for (int i = n - 1; i >= 0; i--)
            {
                if (!t->ch.count(s[i]))
                    break;
                t = t->ch[s[i]];
                if (mp.count(n - i))
                    ret += t->cnt;
            }
            t = root;
            for (int i = n - 1; i >= 0; i--)
            {
                if (!t->ch.count(s[i]))
                    t->ch[s[i]] = new node;
                t = t->ch[s[i]];
            }
            t->cnt++;
        }
        return ret;
    }
};

100229. 最长公共前缀的长度

原题链接

　　100229. 最长公共前缀的长度

题目描述

　　

给你两个 正整数 数组 arr1 和 arr2 。

正整数的 前缀 是其 最左边 的一位或多位数字组成的整数。例如，123 是整数 12345 的前缀，而 234 不是 。

设若整数 c 是整数 a 和 b 的 公共前缀 ，那么 c 需要同时是 a 和 b 的前缀。例如，5655359 和 56554 有公共前缀 565 ，而 1223 和 43456 没有 公共前缀。

你需要找出属于 arr1 的整数 x 和属于 arr2 的整数 y 组成的所有数对 (x, y) 之中最长的公共前缀的长度。

返回所有数对之中最长公共前缀的长度。如果它们之间不存在公共前缀，则返回 0 。

示例 1：

输入：arr1 = [1,10,100], arr2 = [1000]
输出：3
解释：存在 3 个数对 (arr1[i], arr2[j]) ：
- (1, 1000) 的最长公共前缀是 1 。
- (10, 1000) 的最长公共前缀是 10 。
- (100, 1000) 的最长公共前缀是 100 。
最长的公共前缀是 100 ，长度为 3 。

示例 2：

输入：arr1 = [1,2,3], arr2 = [4,4,4]
输出：0
解释：任何数对 (arr1[i], arr2[j]) 之中都不存在公共前缀，因此返回 0 。
请注意，同一个数组内元素之间的公共前缀不在考虑范围内。

接口描述

class Solution {
public:
    int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
        
    }
};

思路分析

　　还是字典树

1. 把arr1中所有数字转化为字符串插入到字典树中
2. 遍历arr2，在字典树上进行匹配，维护最长前缀长度

代码详解

class Solution
{
public:
    struct node
    {
        unordered_map<char, node *> ch;
    } *root;
    int longestCommonPrefix(vector<int> &arr1, vector<int> &arr2)
    {
        root = new node;
        int ret = 0;
        for (auto v : arr1)
        {
            node *t = root;
            for (auto x : to_string(v))
            {
                if (!t->ch.count(x))
                    t->ch[x] = new node;
                t = t->ch[x];
            }
        }
        for (auto &v : arr2)
        {
            node *t = root;
            int s = 0;
            for (auto x : to_string(v))
            {
                if (!t->ch.count(x))
                    break;
                t = t->ch[x];
                s++;
            }
            ret = max(ret, s);
        }
        return ret;
    }
};

100217. 出现频率最高的素数

原题链接

　　100217. 出现频率最高的素数

题目描述

　　

给你一个大小为 m x n 、下标从 0 开始的二维矩阵 mat 。在每个单元格，你可以按以下方式生成数字：

• 最多有 8 条路径可以选择：东，东南，南，西南，西，西北，北，东北。
• 选择其中一条路径，沿着这个方向移动，并且将路径上的数字添加到正在形成的数字后面。
• 注意，每一步都会生成数字，例如，如果路径上的数字是 1, 9, 1，那么在这个方向上会生成三个数字：1, 19, 191 。

返回在遍历矩阵所创建的所有数字中，出现频率最高的、大于 10的

素数

；如果不存在这样的素数，则返回  -1  。如果存在多个出现频率最高的素数，那么返回其中最大的那个。

注意：移动过程中不允许改变方向。

接口描述

class Solution {
public:
    int mostFrequentPrime(vector<vector<int>>& mat) {
        
    }
};

思路分析

　　素数筛+暴力模拟

预处理素数筛，遍历每个网格的八个方向维护出现的大于10的素数的次数即可

代码详解

const int maxn = 1e7 + 10;
bitset<maxn + 1> prime; // 0为素数 1为合数
int primes[maxn + 1], cnt;
bool f = 0;
inline void calcprime(int x)
{
    prime[2] = 0;
    for (int i = 2; i <= x; i++)
    {
        if (!prime[i])
            primes[cnt++] = i;
        for (int j = 0; j < cnt && primes[j] * i <= x; j++)
        {
            prime[primes[j] * i] = 1;
            if (i % primes[j] == 0)
                break;
        }
    }
}
class Solution
{
public:
    Solution()
    {
        if (!f)
            calcprime(1e7), f = 1;
        ;
    }
    static constexpr int dir[9] = {1, 0, -1, 0, 1, 1, -1, -1, 1};
    int mostFrequentPrime(vector<vector<int>> &mat)
    {
        int m = mat.size(), n = mat[0].size(), ret = -1, ma = 0;
        int cnt[10000005]{0};
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                for (int k = 0, x, y; k < 8; k++)
                {
                    int s = 0;
                    x = i, y = j;
                    while (x >= 0 && x < m && y >= 0 && y < n)
                    {
                        s = (s << 3) + (s << 1) + mat[x][y];
                        if (s > 10 && !prime[s])
                        {
                            ++cnt[s];
                            if (cnt[s] > ma)
                                ma = cnt[s], ret = s;
                            else if (cnt[s] == ma)
                                ret = max(ret, s);
                        }
                        x += dir[k], y += dir[k + 1];
                    }
                }
            }
        }
        return ret;
    }
};

100212. 统计前后缀下标对 II

原题链接

　　100208. 统计前后缀下标对 II

题目描述

　　

给你一个下标从 0 开始的字符串数组 words 。

定义一个 布尔 函数 isPrefixAndSuffix ，它接受两个字符串参数 str1 和 str2 ：

• 当 str1 同时是 str2 的前缀（

  prefix

  ）和后缀（

  suffix

  ）时，isPrefixAndSuffix(str1, str2) 返回 true，否则返回 false。

例如，isPrefixAndSuffix("aba", "ababa") 返回 true，因为 "aba" 既是 "ababa" 的前缀，也是 "ababa" 的后缀，但是 isPrefixAndSuffix("abc", "abcd") 返回 false。

以整数形式，返回满足 i < j 且 isPrefixAndSuffix(words[i], words[j]) 为 true 的下标对 (i, j) 的 数量 。

接口描述

class Solution {
public:
    long long countPrefixSuffixPairs(vector<string>& words) {
        
    }
};

思路分析

　　思路同第一题文章来源地址https://www.toymoban.com/news/detail-826821.html

代码详解

class Solution
{
public:
    struct node
    {
        int cnt = 0;
        unordered_map<char, node *> ch;
    } *root, *t;
    bool isloop(const string &s)
    {
        int l = 0, r = (int)s.size() - 2;
        while (l < r)
            if (s[l] != s[r])
                return false;
            else
                l++, r--;
        return true;
    }
    long long countPrefixSuffixPairs(vector<string> &words)
    {
        long long ret = 0;
        root = new node;
        for (auto &s : words)
        {
            int n = s.size();
            vector<int> nxt(n + 1, -1);
            s.push_back('#');
            int j = 0, k = -1;
            unordered_set<int> mp;
            while (j < n)
            {
                if (k == -1 || s[j] == s[k])
                {
                    k++, j++;
                    nxt[j] = k;
                }
                else
                    k = nxt[k];
            }
            while (j)
                mp.insert(nxt[j]), j = nxt[j];

                mp.insert(n);
            t = root;
            for (int i = n - 1; i >= 0; i--)
            {
                if (!t->ch.count(s[i]))
                    break;
                t = t->ch[s[i]];
                if (mp.count(n - i))
                    ret += t->cnt;
            }
            t = root;
            for (int i = n - 1; i >= 0; i--)
            {
                if (!t->ch.count(s[i]))
                    t->ch[s[i]] = new node;
                t = t->ch[s[i]];
            }
            t->cnt++;
        }
        return ret;
    }
};

到了这里，关于LeetCode 第385场周赛个人题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！