贪心算法(2)

devtools/2024/11/25 17:31:18/

目录

K次取反后最大化的数组和

题解:

代码:

按身高排序(田忌赛马的预备)

题解:

代码:

方法一:

方法二: 

优势洗牌(田忌赛马)

题解:

代码:

最长回文串

题解:

代码:

增减字符串匹配

题解:

代码: 

分发饼干(田忌赛马)

题解:

代码:

最优除法

题解:

代码:


K次取反后最大化的数组和

1005. K 次取反后最大化的数组和 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/

题解:

为了最大化数组和,就要对数组中最小的 k 个数取反,我们统计出数组中负数的个数 m

如果 m >= k,那么我们只需要对这 k 个负数取反,就可以得到最大的数组和;

如果 m < k,我们结合具体例子讨论,如下图所示,m = 4,

将所有的负数取反后,操作数剩下 k - m 次, 为了得到最大的数组和,我们只需要考虑如何操作取反后数组的最小值:

  • 如果  k - m 为偶数,那么我们无需操作取反后数组的最小值,因为负负得正,数组和不变;
  • 如果  k - m 为奇数,那么取反后数组的最小值取负值即可。

代码:

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {int minNum=INT_MAX,ret=0,n=nums.size(),m=0;for(auto x:nums){if(x<0) m++;minNum=min(minNum,abs(x));//找出绝对值最小的数}if(m>k)//负数的个数大于k,反转前k小负数{sort(nums.begin(),nums.end());for(int i=0;i<k;i++)ret+= -nums[i];for(int i=k;i<n;i++)ret+=nums[i];}else//负数的个数小于等于k,有的数字被多次反转{for(auto x:nums)ret+=abs(x);//反转所有负数if((k-m)%2)//有的数被反转奇数次{ret-=minNum*2;}}return ret;}
};

按身高排序(田忌赛马的预备)

2418. 按身高排序 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/sort-the-people/description/

题解:

这道题有两种方法:

方法一

用 pair 或者 struct 创建一个二元组,二元组的内容为姓名和对应的身高,将所有的二元组放入数组中,再对数组根据身高排序,排序后按照顺序把名字提取出来即可。

或者用哈希表,定义 map< int, string > hash,把身高和姓名放进哈希表中,再根据身高排序即可。

方法二

因为姓名、身高和下标是一一对应的关系,如果只是对身高排序,身高和下标原本的对应关系就被打乱了,就无法根据身高的下标找到对应的姓名了。

如图所示,原本 165 、John 对应 1 号下标,只对身高排序后,下标为 1 的身高变为 170,John 再次根据下标 1 去找自己的身高时,身高变成 170 了。 

为了保留身高、姓名和下标的对应关系, 我们可以重开一个数组 tmp,tmp 存的是身高数组的下标,新建一个排序规则根据身高对下标排序,但不改变身高数组

如下图,由于下标为 1 的身高165 小于 下标为 2 的身高 170,所以交换 tmp 中元素 1 和 2 的位置,tmp 排序后的最终顺序为 [ 0, 2, 1 ],然后遍历 tmp 数组,height[ tmp[0] ] 就是 Mary,height[ tmp[1] ] 就是 Emma,height[ tmp[2] ] 就是 John。

代码:

方法一:

class Solution {
public:struct person{string name;int height;}p[1010];vector<string> sortPeople(vector<string>& names, vector<int>& heights) {int n=names.size();for(int i=0;i<n;i++){p[i].name=names[i];p[i].height=heights[i];}sort(p,p+n,[](const struct person a,const struct person b){   return a.height>b.height;   });for(int i=0;i<n;i++){names[i]=p[i].name;}return names;}
};

方法二: 

class Solution {
public:vector<string> sortPeople(vector<string>& names, vector<int>& heights) {int n=names.size();vector<int> tmp(n);for(int i=0;i<n;i++){tmp[i]=i;//初始化}sort(tmp.begin(),tmp.end(),[&](int a,int b){   return heights[a]>heights[b]; });vector<string> ret;for(int i=0;i<n;i++){ret.push_back(names[tmp[i]]);}return ret;}
};

优势洗牌(田忌赛马)

870. 优势洗牌 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/advantage-shuffle/description/

题解:

我们对 nums1 和 nums2 排升序,以示例二为例,排序后 nums1 = [ 8, 12, 24, 32 ] ,nums2 = [ 11, 13, 25, 32 ],我们 用 i 遍历 nums1 ,用 left 指向 nums2 的较小数,right 指向 nums2 的较大数:

  • 如果 nums1[ i ] > nums2[ left ] ,说明 nums1[ i ] 有优势,i++,left++,去匹配下一对优势数;
  • 如果 nums1[ i ] <= nums2[ left ],说明该数没有优势没有优势的数应该去拖累 nums2 的较大数,即 nums1[ i ] 和 nums2[ right ] 匹配,然后 i++,right -- . 因为 nums2[ left ]  后面的数更大,nums1[ i ] 更没有优势了,继续匹配还不如去拖累较大数。

为了不打乱nums2 的下标和数字的相对位置,在排序 nums2 时,用了 按身高排序的 排序方法,即只排序下标。

代码:

class Solution {
public:vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {int n=nums1.size();vector<int> index(n);for(int i=0;i<n;i++)index[i]=i;sort(nums1.begin(),nums1.end());//排升序sort(index.begin(),index.end(),[&](const int a,const int b){return nums2[a]<nums2[b];});vector<int> ret(n);int left=0,right=n-1;for(auto x:nums1){if(x>nums2[index[left]])ret[index[left++]]=x;elseret[index[right--]]=x;}return ret;}
};

最长回文串

409. 最长回文串 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/longest-palindrome/description/

题解:

为了得到回文串,就需要让字符串对称轴左右两侧的字母一一对应。

从下图可以看出,

  • 如果回文串的长度为偶数,则每个字母的个数为偶数
  • 如果回文串的长度为奇数,则除了对称轴上的字母的个数为奇数之外,其余字母的个数为偶数。

统计提供的字符串 s 的每个字母出现的次数,

  • 如果某字母出现的次数为偶数,说明这个字母可以直接加入回文串
  • 如果某字母出现的次数为奇数,为了得到最长的回文串, 只放入偶数个该字母,且这个偶数要尽可能大。

上述过程得到的回文串的长度为偶数,我们可以考虑一下对称轴上是否可以放一个字母,这里有一个小巧思,

  • 如果得到的回文串的长度 ==  s 的长度,说明 s 中每个字母出现的次数都是偶数,已经没有多余的字母可以让我们放在对称轴上了;
  • 如果得到的回文串的长度 <  s 的长度,说明 s 中至少存在一个字母出现的次数为奇数,我们只需要让个数为奇数个的这个字母放在对称轴上,放一个就可以了,最后让回文串的长度 +1。

代码:

class Solution {
public:int longestPalindrome(string s) {int ret=0;vector<int> count(256);for(auto x:s)count[x]++;for(auto x:count){ret+=(x/2*2);}return ret<s.size()?ret+1:ret;}
};

增减字符串匹配

942. 增减字符串匹配 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/di-string-match/description/

题解:

定义两个指针 left 和 right,left 初始化为 0,right 初始化为 1,用 i 遍历字符串 s,将结果存在数组 ret 中:

  • 如果 s[ i ] == ' I ',说明 ret[ i+1 ] > ret[ i ] ,即上升趋势,如果 ret[ i ] 的数字选得很大,上升的趋势很快,若后面出现连续的上升趋势,剩下的数字可能没办法满足上升的需求了,所以需要选择比较小的数字,减缓上升的趋势,而 left 指向的就是比较小的数,故 ret[ i ] = left,left++,指向下一个数;
  • 如果 s[ i ] == ' D ',说明 ret[ i+1 ] < ret[ i ] ,即下降趋势,如果 ret[ i ] 的数字选得很小,下降的趋势很快,若后面出现连续的下降趋势,剩下的数字可能没办法满足下降的需求了,所以需要选择比较大的数字,减缓下降的趋势,而 right 指向的就是比较小的数,故 ret[ i ] = right,right --,指向下一个数;
  • 因为 s 的长度为 n,而我们需要排 n+1 个数,最后 left 和 right 一定会相遇,指向同一个数,把这个数放在数组最后即可。

代码: 

class Solution {
public:vector<int> diStringMatch(string s) {int n=s.size();vector<int> ret;int left=0,right=n;for(int i=0;i<n;i++){if(s[i]=='I')   {ret.push_back(left);    left++;}else{ret.push_back(right);   right--;}}ret.push_back(left); return ret;}
};

分发饼干(田忌赛马)

455. 分发饼干 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/assign-cookies/description/

题解:

和田忌赛马的思路大同小异,对胃口 g 和饼干 s 排序,用 i 遍历 g,用 j 遍历 s,

  • 如果 g[ i ] > s[ j ] ,说明当前饼干不符合该小孩的胃口,后面的小孩的胃口就更不符合了,直接舍弃该饼干,即 j++;
  • 如果 g[ i ] <= s[ j ],说明当前饼干符合该小孩的胃口,该饼干直接给该小孩即可,即 i++,j++.

代码:

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {int ret=0;  int n1=g.size(),n2=s.size();sort(g.begin(),g.end());//排升序sort(s.begin(),s.end());//排升序int i=0,j=0;while(i<n1 && j<n2){if(g[i]>s[j])   j++;else{i++;    j++;    ret++;}}return ret;}
};

最优除法

553. 最优除法 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/optimal-division/description/

题解:

加括号就是为了尽可能地把除数转为被除数,把放在分母的数放到分子上。

代码:

class Solution {
public:string optimalDivision(vector<int>& nums) {string ret;ret+=to_string(nums[0]);int n=nums.size();if(n==2)ret+="/"+to_string(nums[1]);else if(n>2){ret+="/("+to_string(nums[1]);for(int i=2;i<n;i++){ret+="/"+to_string(nums[i]);}ret+=")";}return ret;}
};

http://www.ppmy.cn/devtools/136895.html

相关文章

bash笔记

0 $0 是脚本的名称&#xff0c;$# 是传入的参数数量&#xff0c;$1 是第一个参数&#xff0c;$BOOK_ID 是变量BOOK_ID的内容 1 -echo用于在命令窗口输出信息 -$()&#xff1a;是命令替换的语法。$(...) 会执行括号内的命令&#xff0c;并将其输出捕获为一个字符串&#xff…

Ubuntu问题 - 显示ubuntu服务器上可用磁盘空间 一条命令df -h

目的 想要放我的 数据集 到新的ubuntu服务器中, 不知道存储空间够不够 开始 使用以下命令直接查看 df -h

JVM垃圾回收详解.②

空间分配担保 空间分配担保是为了确保在 Minor GC 之前老年代本身还有容纳新生代所有对象的剩余空间。 《深入理解 Java 虚拟机》第三章对于空间分配担保的描述如下&#xff1a; JDK 6 Update 24 之前&#xff0c;在发生 Minor GC 之前&#xff0c;虚拟机必须先检查老年代最大…

3349、检测相邻递增子数组 Ⅰ

3349、[简单] 检测相邻递增子数组 Ⅰ 1、题目描述 给你一个由 n 个整数组成的数组 nums 和一个整数 k&#xff0c;请你确定是否存在 两个 相邻 且长度为 k 的 严格递增 子数组。具体来说&#xff0c;需要检查是否存在从下标 a 和 b (a < b) 开始的 两个 子数组&#xff0c…

【AIGC】破解ChatGPT!如何使用高价值提示词Prompt提升响应质量

文章目录 为什么高价值提示词如此重要&#xff1f;&#x1f50d;1.1 提升响应的相关性和准确性1.2 节省时间与资源1.3 增强用户体验 了解ChatGPT的工作原理&#x1f9e0;2.1 语言模型的训练过程2.2 上下文理解与生成2.3 限制与挑战 高价值提示词的核心要素✍️3.1 清晰明确的指…

Harbor2.11.1生成自签证和配置HTTPS访问

文章目录 HTTPS的工作流程部署Harbor可参考上一篇文章生成自签证书1.修改/etc/hosts文件2.生成证书a.创建存放证书路径b.创建ca.key密钥c.创建ca.crtd.创建给Harbor服务器使用密钥 yunzhidong.harbor.com.keye.创建给Harbor服务器使用证书签名请求文件 yunzhidong.harbor.com.c…

C51数字时钟/日历---LCD1602液晶显示屏

题目要求&#xff1a; 数字电子日历/时钟设计 设计一个基于MCS51的电子日历和时钟。 基本要求 &#xff08;1&#xff09; 可通过按键在日历和时间之间切换显示&#xff1b; &#xff08;2&#xff09; 可由按键调整日期和时间 &#xff08;3&#xff09; 可整点报时&#x…

Group Convolution(分组卷积)

分组卷积的优点&#xff1a; 减少参数数量&#xff1a; 在分组卷积中&#xff0c;每个分组只与一部分输入通道进行卷积运算&#xff0c;这意味着模型的参数数量会减少。例如&#xff0c;如果一个卷积层有8个输入通道和8个输出通道&#xff0c;且不使用分组&#xff0c;那么将有…