企业网站是否可以做淘宝客,滨州的网站建设,资源猫,网站开发后台题目列表
2965. 找出缺失和重复的数字
2966. 划分数组并满足最大差限制
2967. 使数组成为等数数组的最小代价
2968. 执行操作使频率分数最大
一、找到缺失和重复的数字 由于数据范围不是很大#xff0c;可以直接暴力统计每个数字出现的次数#xff0c;时间复杂度为O(n^2…题目列表
2965. 找出缺失和重复的数字
2966. 划分数组并满足最大差限制
2967. 使数组成为等数数组的最小代价
2968. 执行操作使频率分数最大
一、找到缺失和重复的数字 由于数据范围不是很大可以直接暴力统计每个数字出现的次数时间复杂度为O(n^2)
class Solution {
public:vectorint findMissingAndRepeatedValues(vectorvectorint grid) {vectorintans(2);int ngrid.size();vectorintcnt(n*n1);for(int i0;in;i){for(int j0;jn;j){cnt[grid[i][j]];}}for(int i1;in*n;i){if(cnt[i]2){ans[0]i;}else if(cnt[i]0){ans[1]i;}}return ans;}
};
二、划分数组并满足最大差限度 这题题目说的不是很清楚这里的子数组不要求连续即与数字的顺序无关(可以看示例)所以我们可以直接排序 然后找元素的最大最小值简单模拟一下
class Solution {
public:vectorvectorint divideArray(vectorint nums, int k) {vectorvectorintans;int nnums.size();sort(nums.begin(),nums.end());for(int i0;in;i3){if(nums[i2]-nums[i]k)ans.push_back({nums[i],nums[i1],nums[i2]});elsereturn {};}return ans;}
};
三、使数组成为等数数组的最小代价 这题的难点有两个 1、回文数怎么处理 2、抛开回文数只看x我们该如何选择x让它的代价尽可能的小 问题1回文数要求左右数字对应相等即我们只要枚举它的前半部分然后对称过去就能得到一个回文数我们这里选择先预处理得到数据范围内的所有回文串具体看代码
问题2如何选择x这里是中位数贪心的思想即x选择数组中的中位数最好。为什么 结合上面两个问题的思路我们来看看该如何写首先我们有所有的回文数然后我们通过中位数贪心知道我们选择的回文数要尽可能的在中间位置可以用二分找到附近的回文串进行比较找到最符合条件的
//预处理
vectorintv;
int init[](){for(int i1;i10000;i*10){//枚举回文串的前缀for(int ji;ji*10;j){int xj/10;int yj;while(x){yy*10x%10;x/10;}v.push_back(y); }if(i1000){//i10000会超范围比如 12345 54321 数量级为1e9for(int ji;ji*10;j){int xj;int yj;while(x){yy*10x%10;x/10;}v.push_back(y); }}}v.push_back(1000000001);//方便后面计算return 0;
}();class Solution {
public:long long minimumCost(vectorint nums) {sort(nums.begin(),nums.end());//中位数贪心一定要先排序int nnums.size();auto cost[](int x)-long long{long long s0;for(int i0;in;i)sabs(x-nums[i]);return s;};//找中位数附近的回文串如果n为奇数nums[(n-1)/2]为正中间那个数如果n为偶数nums[(n-1)/2]为中间两个数的左边那个int ilower_bound(v.begin(),v.end(),nums[(n-1)/2])-v.begin();//如果n为奇数不成立(因为(n-1)/2n/2)得找前面的回文数和它比较//如果n为偶数则nums[n/2]为中间两个数的右边那个即v[i]在两个数之间正好符合中位数贪心直接放回if(nums[n/2]v[i])return cost(v[i]);//否则需要比较return min(cost(v[i]),cost(v[i-1]));}
};
四、执行操作使频率分数最大 这题其实也和中位数贪心有关。为了让一个数成为出现次数最大的众数那么我们操作的这些数肯定是相邻的因为它们本身就很接近这样我们将单一数字变成我们希望的众数的操作次数才会尽可能的少才能有更多的操作次数让其他的数更有可能变成我们想要的众数增加众数的频率。
那么选择什么数作为众数比较好呢
如果我们选择了一些连续的数字进行操作那么根据中位数贪心的原理我们选择的众数最好是这些数字的中位数这样其它数字到它的距离之和才会是最小的也就是操作次数最少。如果操作次数k就需要去掉一些数如果操作次数k就增加一些数很明显的滑动窗口
代码如下
class Solution {typedef long long LL;
public:int maxFrequencyScore(vectorint nums, long long k) {sort(nums.begin(),nums.end());int ans0;int nnums.size();vectorLLpre(n1);for(int i0;in;i)pre[i1]pre[i]nums[i];functionLL(LL,LL)check[](LL l,LL r)-LL{LL mid(lr)/2;//这里的中位数下标要算对LL left(mid-l)*nums[mid]-(pre[mid]-pre[l]);//中位数左边的数需要的操作数LL rightpre[r1]-pre[mid1]-(r-mid)*nums[mid];//中位数右边的数需要的操作数return leftright;};for(int l0,r0;rn;r){while(check(l,r)k)l;ansmax(ans,r-l1);}return ans;}
};
