题目
3042. 统计前后缀下标对 I
3043. 最长公共前缀的长度
3044. 出现频率最高的质数
3045. 统计前后缀下标对 II
一、最长公共前缀的长度
这题可以用字典树来做。
这里简单介绍一下字典树，顾名思义，这是用来存放单词的树，如何存？？？如下图
（上面对字典树的介绍只是方便大家理解，要想有更深入的了解可以去自行查看文档）
当然字典树不仅仅只能用来存放字符串，它是一种思想的体现，放在这题，我们同样可以将数字每一位拆开来存放进这样一棵树中。同时这题不是查看数字是否出现在字典树中，所以Node结构体没必要有bool end这个变量。
代码如下
struct Node{
Node* son[10]={0};
};
class Solution {
public:
int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
int n=arr1.size(),m=arr2.size();
//用arr1构造字典树
Node* root = new Node();
for(auto x:arr1){
Node*cur=root;
string s=to_string(x);
for(auto e:s){
if(cur->son[e-'0']==nullptr)
cur->son[e-'0']=new Node();
cur=cur->son[e-'0'];
}
}
//找最大公共前缀
int ans=0;
for(auto x:arr2){
Node*cur=root;
string s=to_string(x);
int res=0;
for(auto e:s){
if(cur->son[e-'0']){
cur=cur->son[e-'0'];
res++;
}else{
break;
}
}
ans=max(res,ans);
}
return ans;
}
};总结：字典树可以用来解决前缀/后缀匹配的问题(不仅限于字符串)，同时字典树的结点中的数据可以根据自己的需要进行改变
二、出现频率最高的质数
这题只要读懂题意，然后直接模拟即可，对质数的判断也可以直接暴力，代码如下
class Solution {
const int dir[8][2]={0,1, 0,-1, 1,0, -1,0, 1,1, -1,-1, 1,-1, -1,1};
public:
bool is_prime(int x){
for(int i=2;i<=sqrt(x);i++){
if(x%i==0)
return false;
}
return true;
}
int mostFrequentPrime(vector<vector<int>>& mat) {
int n = mat.size(), m = mat[0].size();
unordered_map<int,int>mp;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
for(int k=0;k<8;k++){
int x=i,y=j;
int dx=dir[k][0],dy=dir[k][1];
int val = 0;
while(x>=0&&x<n&&y>=0&&y<m){
val=val*10+mat[x][y];
if(val>10&&is_prime(val))
mp[val]++;
x+=dx;y+=dy;
}
}
}
}
int mx=0,val=-1;
for(const auto&[v,c]:mp){
if(mx==0) mx=c,val=v;
else if(mx<c) mx=c,val=v;
else if(mx==c&&val<v) val=v;
}
return val;
}
};三、统计前后缀下标对I&II
第一题由于数据范围小，我们可以直接暴力枚举所有可能的组合即可，代码如下
class Solution {
public:
int countPrefixSuffixPairs(vector<string>& words) {
int n=words.size(),ans=0;
for(int j=0;j<n;j++){
for(int i=j-1;i>=0;i--){
if(words[i].size()<=words[j].size()
&&words[i]==words[j].substr(0,words[i].size())
&&words[i]==words[j].substr(words[j].size()-words[i].size()))
ans++;
}
}
return ans;
}
};但是在第四题的数据范围变大了，我们又该如何去做？？？
我们依旧可以用字典树来做，只不过从单一的匹配前缀/后缀，到现在的前后缀都需要匹配。那么我们该如何去修改字典树，或者添加什么算法去辅助字典树去完成这项工作呢？？？
1、修改字典树---将前缀字典树和后缀字典树结合起来，即将判断前缀和判断后缀是否相等的元素组合成一个pair进行比较，举个例子：
struct Node{
unordered_map<int,Node*>mp;
int cnt = 0;//记录以该节点为结尾的字符串的个数
};
class Solution {
public:
long long countPrefixSuffixPairs(vector<string>& words) {
long long ans = 0;
Node*root=new Node();
for(const auto& s:words){
int n=s.size();
Node*cur=root;
for(int i=0;i<n;i++){
int flag=s[i]<<8|s[n-1-i];//将两个字符hash，这样就不用存pair类型了
if(cur->mp.count(flag)==0)
cur->mp[flag]=new Node();
cur=cur->mp[flag];
ans += cur->cnt;
}
cur->cnt++;
}
return ans;
}
};2、字典树+z函数----利用z函数的性质，有兴趣可以看看
struct Node{
Node* son[26]={0};
int cnt = 0;
};
class Solution {
public:
long long countPrefixSuffixPairs(vector<string>& words) {
long long ans = 0;
Node*root=new Node();
for(const auto& s:words){
int n=s.size();
vector<int>z(n);
z[0]=n;
int l=0,r=0;
for(int i=1;i<n;i++){
if(i<=r) z[i]=min(r-i+1,z[i-l]);
while(i+z[i]<n&&s[i+z[i]]==s[z[i]]) z[i]++;
if(i+z[i]-1>r) l=i,r=i+z[i]-1;
}
Node*cur=root;
for(int i=0;i<n;i++){
if(cur->son[s[i]-'a']==nullptr)
cur->son[s[i]-'a']=new Node();
cur=cur->son[s[i]-'a'];
if(z[n-1-i]==i+1)
ans += cur->cnt;
}
cur->cnt++;
}
return ans;
}
};
