接网站建设 网站设计,做网站难么,图片制作视频手机软件,WordPress画表格题目列表 2833. 距离原点最远的点
2834. 找出美丽数组的最小和
2835. 使子序列的和等于目标的最少操作次数
2836. 在传球游戏中最大化函数值
一、距离原点最远的点 这题主要是理解题意#xff0c;遇到L往左走#xff0c;遇到R往右走#xff0c;遇到_左右都可以走#x…题目列表 2833. 距离原点最远的点
2834. 找出美丽数组的最小和
2835. 使子序列的和等于目标的最少操作次数
2836. 在传球游戏中最大化函数值
一、距离原点最远的点 这题主要是理解题意遇到L往左走遇到R往右走遇到_左右都可以走题目问移动完成后距离原点的最长距离这很显然只有所有的‘_’都往一个方向走的时候才是最大的
代码如下
class Solution {
public:int furthestDistanceFromOrigin(string moves) {int ret0,l0;for(int i0;imoves.size();i){if(moves[i]L) l;else if(moves[i]R) l--;else ret;}retabs(l);return ret;}
};
二、找出美丽数组的最小和
这题和359周赛的第二题一样就不再写了贴个代码
class Solution {
public:long long minimumPossibleSum(int n, int target) {long long mmin(target/2,n);return m*(m1)/2(targettarget(n-m-1))*(n-m)/2;}
};
三、使子序列的和等于目标的最小操作次数 这题思路在于题目给的数组存放的是2的幂我们要想到数的二进制表示从而想到用nums中的数据来凑出target的每一个二进制位上的1。
而target的每一个二进制上的1有三个来源
1.数组本身就有
2.用2^i的数凑出一个2^i
3.将大于2^i的数拆分成我们需要的2^i
而题目要求我们返回最少的操作次数那么我们肯定优先前两个方案尽量避免拆分所以我们将nums数组排序并且从低位开始枚举target的二进制位上的1
方案一和方案二可以合并成用2^i的数字凑出2^i
首先我们明确2^i的各个数字之和一定2^i才有可能凑出2^i接下来我们用数学归纳法进行证明用2^i的数子之和2^i的这些数一定能凑出2^is代表2^i的数字之和
当i1s2时用2的数凑出2
1如果存在2很显然直接得到2
2如果不存在2那么2^1的数字只能是1而1相加很显然能得到2^1
所以2^1的数字之和2^1的这些数一定能凑出2^1
当i2s4时用4的数凑出4
1如果存在4显然能得到4
2如果不存在44的数字只能是1/2即2^1且s42所以根据上面的结论得到一个2剩下s-22同理还能得到一个2两个2相加得到4
所以2^2的数字之和2^2的这些数一定能凑出2^2
当i3s8时用8的数凑出8
1如果存在8显然能得到8
2如果不存在88的数字只能是1/2/4即2^2且s84所以根据上面的结论得到一个4剩下s-44同理还能得到一个4两个4相加得到8
所以2^3的数字之和2^3的这些数一定能凑出2^3
综上所诉一直这样推到下去就会得到用2^i的数子之和2^i的这些数一定能凑出2^i
方案三根据题目要求我们选择数组中离2^i最近的2^j (ji) 进行拆分这样操作次数最少而我们很容易知道一旦差分了2^j那么2^(i1)2^(i2)...2^(j-1)就都不用考虑了因为在拆分2^j时已经得到了这些数拆分的次数为 j-i (可以找个例子看看)
那么这题什么时候返回-1我们知道任何一个2的幂都能被拆成1所以只有数组之和小于target时才会返回-1
技巧当我们在凑出2^i之后原本的算法应该是需要减去2^i再去看剩下的数能不能凑出下一个2^i但是我们也可以只加不减只要我们在比较时连同target的二进制i位之前的位数一起比较
代码如下
class Solution {
public:int minOperations(vectorint nums, int target) {//返回-1的情况if(accumulate(nums.begin(),nums.end(),0LL)target)return -1;//记录每一位二级制1的个数long long cnt[32]{0};for(autox:nums)cnt[__builtin_ctz(x)];//__builtin_ctz得到最右边二进制位1的位数int i0,ret0;long long sum0;while(target(1ui)){sumcnt[i]i;int mask(1u(i1))-1;//小技巧if(sum(masktarget)){//能凑出来i;continue;}//需要拆分i,ret;while(cnt[i]0)i,ret;}return ret;}
};
四、在传球游戏中最大化函数值 这题题目看起来很复杂但是其实就是让你求传k次球之后得到的最大下标和如果直接暴力这题的数据范围肯定会超时所以这题就是让我们优化时间复杂度
这里要提到一个倍增的算法思想本质就是预处理记录每个球员传2^i次球后的得分和接到球的人的下标(这里用x^i都无所谓只是2^i比较好计算)根据数据范围可以知道这样每个人的求解时间都在O(logk)以内时间复杂度为O(nlogk)
代码如下
class Solution {
public:long long getMaxFunctionValue(vectorint receiver, long long k) {int nreceiver.size();int m64 - __builtin_clzll(k);//k的二进制长度int g[n][m1];//记录2^i后的接球人的下标long long f[n][m1];//记录2^i后得到的下标和for(int i0;in;i)//初始化f[i][0]g[i][0]receiver[i];//预处理for(int i1;im1;i){for(int j0;jn;j){g[j][i]g[g[j][i-1]][i-1];f[j][i]f[j][i-1]f[g[j][i-1]][i-1];}}long long ans0;for(int i0;in;i){long long resi;for(int j0,nodei;jm1;j){if((kj)1){resf[node][j];nodeg[node][j];} }ansmax(ans,res);}return ans;}
};
