目录
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) {
}
};思路分析
前后缀问题很容易想到字符串哈希和字典树
这里使用字典树解法
- 遍历字符串数组，用kmp的next数组推导方式计算出所有公共前后缀，并插入到哈希表中
- 倒序遍历，在字典树上匹配，如果匹配长度在哈希表中存在，我们就加上这个字典树节点处的权值
- 结束后倒序插入当前字符串
时间复杂度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. 最长公共前缀的长度
原题链接
题目描述
给你两个 正整数 数组
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) {
}
};思路分析
还是字典树
- 把arr1中所有数字转化为字符串插入到字典树中
- 遍历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. 出现频率最高的素数
原题链接
题目描述
给你一个大小为
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
原题链接
题目描述
给你一个下标从 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) {
}
};思路分析
思路同第一题
代码详解
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;
}
};
