湖北平台网站建设制作,seo运营学校,域名可以做网站吗,大兴安岭商城网站开发设计题目列表
2996. 大于等于顺序前缀和的最小缺失整数
2997. 使数组异或和等于 K 的最少操作次数
2998. 使 X 和 Y 相等的最少操作次数
2999. 统计强大整数的数目
一、大于等于顺序前缀和的最小缺失整数 简单的模拟题#xff0c;只要按照题目的要求去写代码即可#xff0c;…题目列表
2996. 大于等于顺序前缀和的最小缺失整数
2997. 使数组异或和等于 K 的最少操作次数
2998. 使 X 和 Y 相等的最少操作次数
2999. 统计强大整数的数目
一、大于等于顺序前缀和的最小缺失整数 简单的模拟题只要按照题目的要求去写代码即可代码如下
class Solution {
public:int missingInteger(vectorint nums) {int i1,ansnums[0],nnums.size();while(in){if(nums[i]-nums[i-1]!1)break;ansnums[i];i;}unordered_setints(nums.begin(),nums.end());while(s.count(ans))ans;return ans;}
};
二、使数组异或和为K的最小操作次数 这题考异或的性质---相同为0相异为1我们只要关心nums的异或和与K的二进制位有几个不同即可也就是将k和nums一起异或最后看二进制位上还有几个1
(这里可能有人还是很懵简单说一下思路的正确性异或运算的性质决定了它不会干扰到其他位我们可以把异或运算看作是每个二进制位的单独的运算且满足交换律现在我们单独看某一个二进制位如果共有3个12个0异或那么异或结果为1如果我们将其中的一个1换成0或者将一个0换成1异或的结果就会改变至于被修改的是哪个数字的二进制位无所谓都行所以二进制位的单一位只需进行一次操作就能发生改变所以我们的答案如上诉所说)
代码如下
class Solution {
public:int minOperations(vectorint nums, int k) {for(autoe:nums)k^e;return __builtin_popcount(k);//求二进制位上的1的个数}
};
三、使X和Y相等的最小操作次数 这题有两种思路都给大家讲一讲在讲思路之前我们都应该能观察得到当xy时我们只能用1操作即操作个数一定为y-x也就是说我们只要考虑xy的情况
思路一图的bfs
我们将x-y过程中经过的每个数看作是图上的结点然后我们用层序遍历的思路一层层往外遍历直到我们找到y返回结果因为我们的操作次数是累加的所以第一次找到y时我们一定能得到最小的操作次数(不代表层序遍历的次数就是最小操作次数也可能出现操作后的数小于y然后通过1操作实现y的情况具体看代码)。这个思路的关键是你能想到它能用图来类比从而想到层序遍历当然实现细节还是很多的。
(启发图的遍历不是只有图能用像这种抽象的从一个点到另一个点且中间经过的点是确定的然后要求最小操作次数就可以往图的层序遍历去思考)
代码如下
class Solution {
public:int minimumOperationsToMakeEqual(int x, int y) {if(xy)return y-x;int ansx-y;//代表操作上限只用减法//ansx是在操作上限的范围内只做加法操作的最大数字1是因为下标vectorboolvis(ansx1);//记录遍历到的结点能减少重复数字的遍历次数int step0;vectorintq;auto add[](int v){if(vy)ansmin(ans,step1y-v);else if(!vis[v]){vis[v]true;q.push_back(v);}};add(x);while(1){auto tmpq;q.clear();for(auto v:tmp){if(vy)return min(ans,step);if(v%50)add(v/5);if(v%110)add(v/11);add(v-1);add(v1);}step;}}
};
思路二记忆化搜索
首先我们要对递归有一个大体的方向由于我们只考虑xy的情况所以要求操作次数最少我们肯定希望尽可能的用/5 、/11让x能快速的接近y即我们将加减1当作辅助操作同时还要考虑到只用减法操作得到最小操作次数的情况。
我们根据题意确定递归的参数和返回值dfs(v)返回从v到y的最小操作次数
接下来我们来想想如何从v-y
1、vy只能进行1操作操作次数为v-y直接返回
2、vy
1只用减法操作操作次数为v-y
2用/5操作两种可能进行v%5次减法操作或者进行5-v%5次加法操作让v变成5的倍数后/5操作次数为min(dfs(v/5)v%5,dfs(v/51)5-v%5)11是因为/5也要算操作次数
3用/11操作两种可能进行v%11次减法操作或者进行11-v%11次加法操作让v变成11的倍数后/11操作次数为min(dfs(v/11)v%11,dfs(v/111)11-v%11)1
返回三者的最小值
对于vy的后两种情况我们是根据红字部分得来的其实并不严谨因为我们没有证明v到它前后最近的5的倍数是最优解即它再5/-5得到的另一个5的倍数是否会更好这个其实很好想5/-5的操作次数导致的结果就是/5之后的数字相差了一个1那么我先/5后再1/-1不是能更快得到结果嘛(11同理)所以我们只考虑v前后的5的倍数即可代码如下
class Solution {
public:int minimumOperationsToMakeEqual(int x, int y) {if(xy)return y-x;int memo[x1];memset(memo,-1,sizeof(memo));functionint(int)dfs[](int v)-int{if(vy)return y-v;if(memo[v]!-1) return memo[v];int resv-y;resmin(res,min(dfs(v/5)v%5,dfs(v/51)5-v%5)1);resmin(res,min(dfs(v/11)v%11,dfs(v/111)11-v%11)1);return memo[v]res;};return dfs(x);}
}; 四、统计强大整数的数目 这题很典型的数位dp题要求我们返回在所给范围内的满足条件的数字个数。数位dp的思路就是考虑如何构造出这样一个符合要求的数字我们一位一位的考虑即可。
代码如下
class Solution {typedef long long LL;
public:long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {//将数字区间端点变成字符串string leftto_string(start);string rightto_string(finish);int nright.size();leftstring(n-left.size(),0)left;//补上前导零方便后面的计算int diffn-s.size();//记忆化搜索vectorLLmemo(n,-1);functionLL(int,bool,bool)dfs[](int i,bool limit_low,bool limit_high)-LL{if(in)//递归到这说明构造的数字合法返回1return 1;if(!limit_high!limit_lowmemo[i]!-1) //这个是因为限制高/限低在递归中只会走一次没有必要进行记忆化所以记忆数组可以是一维的return memo[i];//求当前位置的数的取值范围int highlimit_high?right[i]-0:9;int lowlimit_low?left[i]-0:0;LL res0;//根据题目的其他限制条件进行递归if(idiff)for(int dlow;dmin(high,limit);d)resdfs(i1,dlowlimit_low,dhighlimit_high);else{int ds[i-diff]-0;if(dlowdmin(high,limit))resdfs(i1,dlowlimit_low,dhighlimit_high);}if(!limit_high!limit_low)memo[i]res;return res;};return dfs(0,true,true);}
};
