LeetCode---380周赛

题目列表

3005. 最大频率元素计数

3006. 找出数组中的美丽下标 I

3007. 价值和小于等于 K 的最大数字

3008. 找出数组中的美丽下标 II

一、最大频率元素计数

这题就是个简单的计数题，正常遍历统计数据即可，关键是你要会写代码逻辑。

代码如下（如果代码看不懂的，建议按照代码逻辑手动模拟几次）

//两次遍历
class Solution {
public:int maxFrequencyElements(vector<int>& nums) {unordered_map<int,int>mp;for(auto&e:nums) mp[e]++;int sum=0,mx=0;for(auto it=mp.begin();it!=mp.end();++it){if(mx<it->second){sum=it->second;mx=it->second;}else if(mx==it->second){sum+=mx;}}return sum;}
};//一次遍历
class Solution {
public:int maxFrequencyElements(vector<int>& nums) {int mx=0,s=0;unordered_map<int,int>cnt;for(auto x:nums){cnt[x]++;if(cnt[x]>mx){s=mx=cnt[x];}else if(cnt[x]==mx){s+=mx;}}return s;}
};

二、找出数组中的美丽下标I&II

这题就按照题目说的去模拟就行，关键是优化时间复杂度，当然这题暴力也可以过，但是第四题就不行了。这里先用暴力去写。

简单说一下思路：先分别找出字符串a、b在s中可以匹配的位置，放到两个数组中，然后再找出符合条件的字符串a的下标，最后返回答案即可

代码如下

class Solution {vector<int> Get(string& s,string& a){vector<int>v;size_t pos=s.find(a);while(pos!=string::npos){v.push_back(pos);pos=s.find(a,pos+1);}return v;}
public:vector<int> beautifulIndices(string s, string a, string b, int k) {int n=s.size();vector<int>va=Get(s,a);vector<int>vb=Get(s,b);vector<int>ans;for(int i=0;i<va.size();i++){for(int j=0;j<vb.size();j++){if(abs(va[i]-vb[j])<=k){ans.push_back(va[i]);break;}}}return ans;}
};

如何优化时间复杂度？

在上面的代码中，代码的逻辑有两个模块：1、字符串匹配    2、找符合条件的下标

针对上面的两个模块，我们的优化方案如下

1、对字符串匹配的优化---KMP算法---这个后面会出文章具体讲该算法的原理，这里就不细说了

2、找符合条件的下标，我们的暴力写法没有用到两个数组有序的条件，一般来说，数组有序都可以有优化的方法，这里就可以用双指针，操作和原理如下

设 i 和 j 为va、vb数组的下标

1、va[ i ] < vb[ j ]

• vb[ j ] - va[ i ] <= k 满足条件，将va[i]加入答案，i++，j不用加，因为vb[ j ]有可能让va[i+1]也符合条件
• vb[ j ] - va[ i ] > k 不满足条件，i++，因为vb[j]后面的数只会离va[i]最来越远，i不可能在满足条件，j不用加，因为vb[ j ]有可能让va[i+1]也符合条件

2、va[ i ] >= vb[ j ]

• va[ i ] - vb[ j ] <= k 满足条件，将va[i]加入答案，i++，j不用加，因为vb[ j ]有可能让va[i+1]也符合条件
• va[ i ] - vb[ j ] > k 不满足条件，j++，i不变，因为vb[ j + 1] 可能离va[ i ]更近

双指针的本质就是让va[ i ]尽可能地与它相隔最近的vb[ j ]比较，从而避免一些没有必要的比较，在上面的遍历过程中只有i++和j++，时间复杂度为O(m+n)（m、n为两个数组的大小）

当然用二分查找也能优化，但是双指针更快。

代码如下(双指针+KMP)

class Solution {//KMPvector<int> Get(string& s,string& a){int n=a.size();vector<int>next(n);for(int i=1,j=0;i<n;i++){while(j&&a[j]!=a[i])j=next[j-1];if(a[j]==a[i])j++;next[i]=j;}vector<int>ret;for(int i=0,j=0;i<s.size();i++){while(j&&s[i]!=a[j])j=next[j-1];if(s[i]==a[j])j++;if(j==n){ret.push_back(i-n+1);j=next[j-1];}}return ret;}
public:vector<int> beautifulIndices(string s, string a, string b, int k) {vector<int>va=Get(s,a);vector<int>vb=Get(s,b);vector<int>ans;int n=va.size(),m=vb.size();int i=0,j=0;while(i<n&&j<m){if(va[i]<vb[j]){if(vb[j]-va[i]<=k)ans.push_back(va[i]);i++;}else{if(va[i]-vb[j]<=k){ans.push_back(va[i]);i++;}else{j++;}}}return ans;}
};

三、价值和小于等于K的最大数字

题目中出现小于等于求最大，一般是用二分 (对二分不了解的可以看看我之前写的二分查找详解)，下面我们来分析一下，是否能用二分来做？即是否具有单调性。我们知道 num 越大，整数的价值和就会越大， 两者成正比，满足单调性，那么就能用二分来做。

(二分的上下界选择问题：一般我们选0为下界，选一个极大值作为上界，让答案在区间内即可，如果你想要更为精确的上下界，这里也简单说明一下，0为下界没什么好说的，那么这个上界怎么得到呢？这题可以这么想，我们只求每个整数第x位上的1，需要的数字为多少？[ 低于x的位不考虑 因为我们取的是一个区间，并不要求准确 ] 是 k<<x <=> k*2^x )

现在关键在于如何判断 [1,num] 区间内的整数价值和是否满足条件，即如何求该区间的价值和？

这里有两种做法：1、数位dp（暴力）     2、找数学规律

数位dp上周才写过，套路都差不多，这里就不多介绍了，代码如下

class Solution {typedef long long LL;
public:LL check(LL n,int x){//下面写的数位dp是从高位到低位枚举二进制//当然你也可以将n处理得到它的二进制字符串，都是可以的int m=64-__builtin_clz(n);vector<vector<LL>>memo(m,vector<LL>(m+1,-1));function<LL(int,int,bool)>dfs=[&](int i,int j,bool limit_high)->LL{if(i<0)return j;if(!limit_high&&memo[i][j]!=-1) return memo[i][j];LL res=0;int up=limit_high?(n>>i)&1:1;for(int d=0;d<=up;d++)res+=dfs(i-1,j+(d==1&&(i+1)%x==0),limit_high&&up==d);if(!limit_high)memo[i][j]=res;return res;};return dfs(m-1,0,true);}long long findMaximumNumber(long long k, int x) {LL l=0,r=k<<x;while(l<=r){LL mid=l+(r-l)/2;if(check(mid,x)<=k)//二分的判断条件 l=mid+1;else r=mid-1;}return r;}
};

下面来讲讲数学规律

题目要求特定二进制位上的1的个数，那么我们是不是可以看看这些特定二进制位对1的贡献，然后将贡献相加得到1的个数，解析如下

class Solution {typedef long long LL;
public:LL check(LL n,int x){LL ans=0;int i=x-1;for(LL y = n>>i; y; y>>=x,i+=x){ans+=(y/2)<<i;//求[1,(n>>i)-1]的奇数个数if(y%2){// LL mask=(1LL<<i)-1;// ans+=(n&mask)+1;//注意这里是nLL mod=1LL<<i;ans+=n%mod+1;//注意这里是n}}return ans;}long long findMaximumNumber(long long k, int x) {LL l=0,r=k<<x;while(l<=r){LL mid=l+(r-l)/2;if(check(mid,x)<=k) l=mid+1;else r=mid-1;}return r;}
};