Leetcode 第 385 场周赛题解
- Leetcode 第 385 场周赛题解
- 题目1：3042. 统计前后缀下标对 I
- 思路
- 代码
- 复杂度分析
- 题目2：3043. 最长公共前缀的长度
- 思路
- 代码
- 复杂度分析
- 题目3：3044. 出现频率最高的质数
- 思路
- 代码
- 复杂度分析
- 题目4：3045. 统计前后缀下标对 II
- 思路
- 代码
- 复杂度分析
Leetcode 第 385 场周赛题解
题目1：3042. 统计前后缀下标对 I
思路
暴力枚举下标为 i 和 j 的字符串 words[i] 和 words[j]，当满足条件：
words[i] == words[j].substr(0, words[i].size()) && words[i] == words[j].substr(words[j].size() - words[i].size()) 时，
计数器 count++，最后返回 count。
代码
/*
* @lc app=leetcode.cn id=3042 lang=cpp
*
* [3042] 统计前后缀下标对 I
*/
// @lc code=start
class Solution
{
public:
int countPrefixSuffixPairs(vector<string> &words)
{
if (words.empty())
return 0;
int n = words.size(), count = 0;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
{
int len1 = words[i].size(), len2 = words[j].size();
if (len1 <= len2)
if (words[i] == words[j].substr(0, len1) &&
words[i] == words[j].substr(len2 - len1))
count++;
}
return count;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(n2)，其中 n 是数组 words 的元素个数。
空间复杂度：O(1)。
题目2：3043. 最长公共前缀的长度
思路
数字不好比较前缀，把它们转换成字符串再进行比较。
将数组 arr1 的元素的所有前缀插入到一个字符串集合 strSet 中，遍历数组 arr2 的元素 x，转换成字符串 s，取 s 的前缀在集合中搜索，若找到，更新最长公共前缀的长度。
最后返回最大值即可。
代码
/*
* @lc app=leetcode.cn id=3043 lang=cpp
*
* [3043] 最长公共前缀的长度
*/
// @lc code=start
class Solution
{
public:
int longestCommonPrefix(vector<int> &arr1, vector<int> &arr2)
{
set<string> strSet;
for (int &x : arr1)
{
string s = to_string(x);
for (int i = 1; i <= s.length(); i++)
strSet.insert(s.substr(0, i));
}
int ans = 0;
for (int &x : arr2)
{
string s = to_string(x);
for (int len = 1; len <= s.length(); len++)
{
string temp = s.substr(0, len);
if (strSet.count(temp))
ans = max(ans, len);
}
}
return ans;
}
};
// @lc code=end
复杂度分析
时间复杂度：O((n+m)log2U)，，其中 n 为数组 arr1 的长度，m 为数组 arr2 的长度，U 为数组元素的最大值。
空间复杂度：O(nlog2U)，，其中 n 为数组 arr1 的长度，U 为数组元素的最大值。
题目3：3044. 出现频率最高的质数
思路
对于每个单元格，枚举八个方向，生成数字，用一个哈希表统计其中质数个数。
最后返回出现次数最多的质数，如果有多个这样的质数，返回最大的那个。
代码
/*
* @lc app=leetcode.cn id=3044 lang=cpp
*
* [3044] 出现频率最高的质数
*/
// @lc code=start
class Solution
{
private:
const int dx[8] = {-1, -1, -1, 1, 1, 1, 0, 0};
const int dy[8] = {0, -1, 1, 0, -1, 1, -1, 1};
public:
int mostFrequentPrime(vector<vector<int>> &mat)
{
if (mat.empty())
return 0;
int m = mat.size(), n = m ? mat[0].size() : 0;
unordered_map<int, int> cnt;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < 8; k++)
{
int r = i + dx[k], c = j + dy[k], v = mat[i][j];
// 只统计大于 10 的质数
// if (isPrime(v))
// cnt[v]++;
while (r >= 0 && r < m && c >= 0 && c < n)
{
v = 10 * v + mat[r][c];
if (isPrime(v))
cnt[v]++;
r += dx[k];
c += dy[k];
}
}
int ans = -1, maxCount = 0;
for (auto &[num, count] : cnt)
{
if (count > maxCount)
{
ans = num;
maxCount = count;
}
else if (count == maxCount)
ans = max(ans, num);
}
return ans;
}
// 辅函数 - 判断数字 n 是否是质数
bool isPrime(int n)
{
for (int i = 2; i * i <= n; i++)
{
if (n % i == 0)
return false;
}
return true;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(mnk*10k/2)，其中 m 和 n 分别为 mat 的行数和列数，k=max(m,n)。总共有 O(mnk) 个数，判断质数需要 O(10k/2) 的时间。
空间复杂度：O(mnk)，其中 m 和 n 分别为 mat 的行数和列数，k=max(m,n)。
题目4：3045. 统计前后缀下标对 II
思路
将这个列表哈希化：idx = (s[i] - ‘a’) * 26 + (s[j] - ‘a’)。
枚举 t=words[j]，怎么统计有多少个 s=words[i] 是 t 的前缀？
这可以用字典树解决，在遍历 words 的同时，维护每个字符串的出现次数。当我们遍历 t 时，同时遍历字典树上的对应节点，并把 t 插入字典树。
代码
/*
* @lc app=leetcode.cn id=3045 lang=cpp
*
* [3045] 统计前后缀下标对 II
*/
// @lc code=start
// 字典树
class Solution
{
public:
struct Trie
{
unordered_map<int, Trie *> childs;
int cnt = 0;
};
Trie *trie = new Trie();
void add(const string &s)
{
Trie *cur = trie;
int n = s.size();
for (int i = 0, j = n - 1; i < n; ++i, --j)
{
int idx = (s[i] - 'a') * 26 + (s[j] - 'a');
if (!cur->childs.count(idx))
{
cur->childs[idx] = new Trie();
}
cur = cur->childs[idx];
cur->cnt += 1;
}
}
int query(const string &s)
{
Trie *cur = trie;
int n = s.size();
for (int i = 0, j = n - 1; i < n; ++i, --j)
{
int idx = (s[i] - 'a') * 26 + (s[j] - 'a');
if (!cur->childs.count(idx))
return 0;
cur = cur->childs[idx];
}
return cur->cnt;
}
long long countPrefixSuffixPairs(vector<string> &words)
{
int n = words.size();
long long ans = 0;
for (int i = n - 1; i >= 0; --i)
{
ans += query(words[i]);
add(words[i]);
}
return ans;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(L)，其中 L 为所有 words[i] 的长度之和。
空间复杂度：O(L)，其中 L 为所有 words[i] 的长度之和。
