网站外链建设的15个小技巧,黑龙江新闻法治在线,安溪哪里有学做网站,做网站主页题目列表
2908. 元素和最小的山形三元组 I
2909. 元素和最小的山形三元组 II
2910. 合法分组的最少组数
2911. 得到 K 个半回文串的最少修改次数
一、元素和最小的山形三元组I 没什么好说的#xff0c;不会其他方法就直接暴力#xff0c;时间复杂度O(n^3)#xff0c;代…题目列表
2908. 元素和最小的山形三元组 I
2909. 元素和最小的山形三元组 II
2910. 合法分组的最少组数
2911. 得到 K 个半回文串的最少修改次数
一、元素和最小的山形三元组I 没什么好说的不会其他方法就直接暴力时间复杂度O(n^3)代码如下
class Solution {
public:int minimumSum(vectorint nums) {int nnums.size();int ansINT_MAX;for(int i0;in;i)for(int ji1;jn;j)for(int kj1;kn;k)if(nums[i]nums[j]nums[j]nums[k])ansmin(ans,nums[i]nums[j]nums[k]);return ansINT_MAX?-1:ans;}
}; 二、元素和最小的山形三元组II
这题和上一题一样只是数据范围变大需要优化时间复杂度这也是老套路了直接先预处理出前后缀最小值就行然后枚举中间的那个元素O(n)时间复杂度代码如下
class Solution {
public:int minimumSum(vectorint nums) {int nnums.size(),ansINT_MAX;int suf[n];suf[n-1]nums.back();for(int in-2;i0;i--)suf[i]min(suf[i1],nums[i]);for(int i1,prenums[0];in-1;i){if(prenums[i]nums[i]suf[i1])ansmin(ans,prenums[i]suf[i1]);premin(pre,nums[i]);}return ansINT_MAX?-1:ans;}
};
三、合法分组的最少组数 这题还是有点难度的但是思路还是很明显先统计数字出现的次数然后对相同数字进行分组使得分出的组满足两个条件。关键是如何满足这两个条件第一个已经满足了主要看第二个
而第二个条件其实已经在提醒我们需要枚举分组数量了因为它限制了每个组的数量只能是x/x1都限定这么死了你不枚举真的是可惜了当然有人会想到二分其实这题如果是枚举每个组的数量的话是不满足二段性的(如果有能二分的方法欢迎大家在评论区留言)
那么我来举个例子讲讲为什么不能二分即为什么不满足二段性其实我们在想二段性的时候应该能感觉的出来这个二段性不是很明确因为它能被分成每组两个元素和它能被分成每组三个元素没有必然关系下面举个例子
假设我们要将7个1分成最少组很显然如果每组的个数是7/8肯定可以如果每组的个数是6/7也是可以的如果每组的个数是5/6就不可以了但是如果每组的个数是3/4那么又可以了所以不具有二段性所以我们选择从大往小枚举遇到的第一个符合条件的个数就是最优解
有人可能会对上面的枚举方法感到奇怪会觉得枚举7/8和枚举6/7这两个7是不是重复了你如果单看那种能被7整除的数那么当然是重复的如果是那些不能被7整除的数那么和7搭配的6/8就是两种不同组合方式
那么我们如何判断一个数y能否由x/x1这两个数组合而成呢即yaxb(x1)要求ab的值尽可能小(如果数学好这题也已经被秒了本质就是exgcd)如果数学不好怎么办
我们来想一想如果我们要让分配的每个组的个数相差为1其实就是让y平均分配到每组(注意这里的平均要求分出的组的个数最少)我们先用y/(x1)得到n组剩下my%(x1)个如果mnx那么我们可以从n中的m组各自拿出一个1使得剩下的元素个数也符合条件这样就能得到最少的分配组数而如果mnx显然这是不符合条件的
那么这时有人就会有另一个想法如果我们先用y/x得到n组剩余my/x个如果mn就符合条件如果mn就不符合条件是不是也行呢看似和上面的想法很契合很相似但是这是不行的不信可以去写一下代码试试你会在[10,10,10,3,1,1]这个样例挂掉这里简单说明一下原因这n/k不能保证是最小分组因为我们是每次的分组方案是k/k1你用n/k的结果其实和n/(k1)天差地别如果n20k4用n/k得到最小分组数为5但是n/(k1)的最小分组数却是4更别说n更大了只会相差越来越多这里本质还是没有明白上面绿色的句子即怎么平均才能让分出的组的个数尽可能的少好好理解一下
代码如下
class Solution {
public:int minGroupsForValidAssignment(vectorint nums) {unordered_mapint,intcnt;int mINT_MAX;for(auto e:nums) cnt[e];if(cnt.size()1) return 1;for(auto[a,c]:cnt) mmin(m,c);int ansINT_MAX;functionbool(int)check[](int k)-bool{int res0;for(auto[a,c]:cnt){int modc%(k1);int xc/(k1);if(mod0)resx;else if(kmodx)resresx1;elsereturn false;}ansmin(ans,res);return true;};for(int im;i1;i--){if(check(i))break;}return ans;}
};
四、得到k个半回文串的最小修改次数 这题主要是概念比较唬人这个半回文串估计很多人都看蒙了这里建议结合样例多手玩一下基本上就懂了这里就不对这个概念做深入讨论了这里提醒一下子串的长度2
这题其实不复杂只要预处理一下每个数的真因子和每个子串变成半回文串需要修改的最小字符数然后一个动态规划看看怎么划分子串就行了关键是你能不能将思路写成代码
//预处理出每个数的真因子
int MX201;
vectorvectorintv(MX);
int init[](){for(int i1;iMX;i)for(int j2*i;jMX;ji)v[j].push_back(i);return 0;
}();
class Solution {
public://计算每个子串变成半回文串的需要修改的最小字符数int get_min(const string s){int ns.size();int resn;for(int d:v[n]){//枚举因子进行划分int m0;for(int j0;jd;j){//枚举每一个子序列for(int lj,rn-dj;lr;ld,r-d){//计算每个子序列变成回文串需要修改的字符数m(s[l]!s[r]);}}resmin(res,m);}return res;}int minimumChanges(string s, int k) {int ns.size();vectorvectorintmodify(n,vectorint(n));//计算每个子串的最小修改次数for(int l0;ln-1;l){for(int rl1;rn;r){modify[l][r]get_min(s.substr(l,r-l1));}}vectorvectorintmemo(n,vectorint(k,n1));//n1代表没有计算过因为字符串最多只有n个元素不可能需要修改n1次functionint(int,int)dfs[](int r,int k)-int{if(k0) return modify[0][r];if(memo[r][k]n) return memo[r][k];int resINT_MAX;for(int lr-1;l2*k;l--){resmin(res,dfs(l-1,k-1)modify[l][r]);}return memo[r][k]res;};return dfs(n-1,k-1);//动态规划//vectorvectorintdp(k,vectorint(n));//dp[0]modify[0];//for(int i1;ik;i){// for(int r2*i1;rn;r){// int resINT_MAX;// for(int lr-1;l2*i;l--){// resmin(res,dp[i-1][l-1]modify[l][r]);// }// dp[i][r]res;// }//}//return dp[k-1][n-1];}
};
