贵阳网站建设加q479185700,衡阳市城市建设投资有限公司网站,河南住房和城乡建设局网站,厦门 网站建设公司题目列表
3005. 最大频率元素计数
3006. 找出数组中的美丽下标 I
3007. 价值和小于等于 K 的最大数字
3008. 找出数组中的美丽下标 II
一、最大频率元素计数 这题就是个简单的计数题#xff0c;正常遍历统计数据即可#xff0c;关键是你要会写代码逻辑。
代码如下…题目列表
3005. 最大频率元素计数
3006. 找出数组中的美丽下标 I
3007. 价值和小于等于 K 的最大数字
3008. 找出数组中的美丽下标 II
一、最大频率元素计数 这题就是个简单的计数题正常遍历统计数据即可关键是你要会写代码逻辑。
代码如下如果代码看不懂的建议按照代码逻辑手动模拟几次
//两次遍历
class Solution {
public:int maxFrequencyElements(vectorint nums) {unordered_mapint,intmp;for(autoe:nums) mp[e];int sum0,mx0;for(auto itmp.begin();it!mp.end();it){if(mxit-second){sumit-second;mxit-second;}else if(mxit-second){summx;}}return sum;}
};//一次遍历
class Solution {
public:int maxFrequencyElements(vectorint nums) {int mx0,s0;unordered_mapint,intcnt;for(auto x:nums){cnt[x];if(cnt[x]mx){smxcnt[x];}else if(cnt[x]mx){smx;}}return s;}
};
二、找出数组中的美丽下标III 这题就按照题目说的去模拟就行关键是优化时间复杂度当然这题暴力也可以过但是第四题就不行了。这里先用暴力去写。
简单说一下思路先分别找出字符串a、b在s中可以匹配的位置放到两个数组中然后再找出符合条件的字符串a的下标最后返回答案即可
代码如下
class Solution {vectorint Get(string s,string a){vectorintv;size_t poss.find(a);while(pos!string::npos){v.push_back(pos);poss.find(a,pos1);}return v;}
public:vectorint beautifulIndices(string s, string a, string b, int k) {int ns.size();vectorintvaGet(s,a);vectorintvbGet(s,b);vectorintans;for(int i0;iva.size();i){for(int j0;jvb.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]加入答案ij不用加因为vb[ j ]有可能让va[i1]也符合条件vb[ j ] - va[ i ] k 不满足条件i因为vb[j]后面的数只会离va[i]最来越远i不可能在满足条件j不用加因为vb[ j ]有可能让va[i1]也符合条件 2、va[ i ] vb[ j ] va[ i ] - vb[ j ] k 满足条件将va[i]加入答案ij不用加因为vb[ j ]有可能让va[i1]也符合条件va[ i ] - vb[ j ] k 不满足条件ji不变因为vb[ j 1] 可能离va[ i ]更近 双指针的本质就是让va[ i ]尽可能地与它相隔最近的vb[ j ]比较从而避免一些没有必要的比较在上面的遍历过程中只有i和j时间复杂度为O(mn)m、n为两个数组的大小
当然用二分查找也能优化但是双指针更快。
代码如下(双指针KMP)
class Solution {//KMPvectorint Get(string s,string a){int na.size();vectorintnext(n);for(int i1,j0;in;i){while(ja[j]!a[i])jnext[j-1];if(a[j]a[i])j;next[i]j;}vectorintret;for(int i0,j0;is.size();i){while(js[i]!a[j])jnext[j-1];if(s[i]a[j])j;if(jn){ret.push_back(i-n1);jnext[j-1];}}return ret;}
public:vectorint beautifulIndices(string s, string a, string b, int k) {vectorintvaGet(s,a);vectorintvbGet(s,b);vectorintans;int nva.size(),mvb.size();int i0,j0;while(injm){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的位不考虑 因为我们取的是一个区间并不要求准确 ] 是 kx 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 m64-__builtin_clz(n);vectorvectorLLmemo(m,vectorLL(m1,-1));functionLL(int,int,bool)dfs[](int i,int j,bool limit_high)-LL{if(i0)return j;if(!limit_highmemo[i][j]!-1) return memo[i][j];LL res0;int uplimit_high?(ni)1:1;for(int d0;dup;d)resdfs(i-1,j(d1(i1)%x0),limit_highupd);if(!limit_high)memo[i][j]res;return res;};return dfs(m-1,0,true);}long long findMaximumNumber(long long k, int x) {LL l0,rkx;while(lr){LL midl(r-l)/2;if(check(mid,x)k)//二分的判断条件 lmid1;else rmid-1;}return r;}
};
下面来讲讲数学规律
题目要求特定二进制位上的1的个数那么我们是不是可以看看这些特定二进制位对1的贡献然后将贡献相加得到1的个数解析如下 class Solution {typedef long long LL;
public:LL check(LL n,int x){LL ans0;int ix-1;for(LL y ni; y; yx,ix){ans(y/2)i;//求[1,(ni)-1]的奇数个数if(y%2){// LL mask(1LLi)-1;// ans(nmask)1;//注意这里是nLL mod1LLi;ansn%mod1;//注意这里是n}}return ans;}long long findMaximumNumber(long long k, int x) {LL l0,rkx;while(lr){LL midl(r-l)/2;if(check(mid,x)k) lmid1;else rmid-1;}return r;}
};
