贪心算法(1)

ops/2024/11/22 14:51:46/

目录

 柠檬水找零

题解:

代码:

将数组和减半的最少操作次数(大根堆)

题解:

代码:

最大数(注意 sort 中 cmp 的写法)

题解:

代码:

摆动序列(如何判断波峰、波谷、平台)

题解:

代码:


贪心策略

解决问题的策略:局部最优-> 全局最优

1、把解决问题的过程分为若干步;

2、解决每一步的时候,都选择当前看起来“最优的”解法;

3、希望得到全局最优解。

 柠檬水找零

860. 柠檬水找零 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/lemonade-change/description/

题解:

假设当前顾客付了 5 美元,则无需找零,摊主手中 5 美元的张数+1;

假设当前顾客付了 10 美元,那么摊主需要返还 5 美元

  • 如果摊主手中有 5 美元,则摊主手中 10 美元的张数 +1,且返还顾客 5 美元,即摊主手中 5 美元的张数 -1 ;
  • 如果摊主手中没有 5 美元,说明摊主此时无法找零,直接返回 false;

假设当前顾客付了 20 美元,那么摊主需要返还 15 美元

  • 如果摊主手中有 10 美元 和 5 美元,则摊主手中 10 美元和 5 美元的张数都 -1;
  • 如果摊主手中有 3 张 5 美元,则摊主手中 5 美元的张数 -3;

在可以找零的这两种情况中,就可以体现贪心策略。可以发现在找零的过程中,5 美元经常使用,所以不能让 5 美元的张数太快消耗完,可能会影响后面找零,所以在返还 15 美元的情况下,应该优先返还 1张 10 美元和 1张 5 美元,其次选择返还 3张 5 美元。

代码:

class Solution {
public:bool lemonadeChange(vector<int>& bills) {int ten=0,five=0;for(auto x:bills){if(x==5)    five++;else if(x==10){if(five>0){five--;    ten++;}else    return false;//无法找零}else//x=20{if(ten>0 && five>0)//找10+5{ten--;  five--;}else if(five>=3) five-=3;//没有10,找5+5+5else    return false;//无法找零}}return true;}
};

将数组和减半的最少操作次数(大根堆)

2208. 将数组和减半的最少操作次数 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/minimum-operations-to-halve-array-sum/description/ 

题解:

数组减半的最少操作数,其实就是找到数组中的最大值,并将其减半,为了方便找到数组的最大值,可以使用大根堆,找到堆顶元素,将其减半后再次放回大根堆中,直到数组和减半,就可以得出最少操作数。

代码:

class Solution {
public:int halveArray(vector<int>& nums) {priority_queue<double> p;double sum=0.0;for(auto x:nums){p.push(x);sum+=x;}sum/=2.0;int count=0;while(sum>0){double tmp=p.top();p.pop();tmp/=2.0;sum-=tmp; p.push(tmp);count++;}return count;}
};

最大数(注意 sort 中 cmp 的写法)

179. 最大数 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/largest-number/description/

题解:

以示例一为例,数字 10 和数字 2 拼在一起,会得到数字 102 和数字 210,由于 210 > 102,所以返回 210;

以示例二为例,我们可以对数组排序

数字 3 和 数字 30 拼在一起,得到数字 330 和 数字 303,由于 330 > 303,所以 数字 3 和 数字 30 排序后为 [ 3 , 30 ]

数字 30 和 数字 34 拼在一起,得到数字 3430 和数字 3034,所以排序结果为 [ 34, 30 ],数字 34 再和 数字 3 拼在一起,得到343 和 334,所以最终排序结果为 [ 34 , 3 , 30 ]

用这个规则排序后得到的数组为 [ 9 , 5 , 34 , 3 , 30 ],最终拼到的最大数为 9534330

可以看出排序的规则就是把两个数 a 和 b 拼在一起,拼接后的数为 ab 和 ba,

  • 若 ab > ba,a 就排在 b 前面;
  • 若 ab < ba,b 就排在 a 前面。

为了方便拼接和比较大小,可以把数字都转换为字符串,比较拼接后字符串的字典序

  • 字典序 ab > ba ,a 排在前面;
  • 字典序 ab < ba ,b 排在前面。 

代码:

class Solution {
public:string largestNumber(vector<int>& nums) {vector<string> str;for(auto x:nums){str.push_back(to_string(x));}sort(str.begin(),str.end(),[](const string s1,const string s2){   return s1+s2>s2+s1; });string ret;for(auto x:str)ret+=x;if(ret[0]=='0') return "0";else return ret;}
};

摆动序列(如何判断波峰、波谷、平台)

376. 摆动序列 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/wiggle-subsequence/description/

题解:

以示例二为例,将数字的升降趋势画出图:

可以看出图中存在波峰(极大值),波谷(极小值),波峰和波峰左、右边的数的差值恰好一正一负, 波谷和波谷左、右边的数的差值恰好一正一负, 满足摆动序列的条件,即数组中所有的极大值和极小值构成的子数组就是题目所说的摆动序列,我们只需要得到摆动序列的长度即可

判断一个数和这个数左边的数的差值为 left,和右边的数的差值为 right,判断 left * right 是否小于 0 就可以知道这个数是不是极大/小值

同时,数组最左端和最右端的数也可以视为极大值或极小值,也应该被计入摆动序列中,但最左端的数左边没有数字了,最右端的数右边没有数字了,没办法用 left * right 的积是否小于 0 来判断是否为极大/小值。

  • 针对最端的数,我们将 left 初始化为 0,left * right 为 0,摆动序列的长度 +1,就可以解决最左端的问题;
  • 针对最端的数,在整个数组判断完 left * right 之后,得到的摆动序列的长度 +1 即可。

但是 left * right == 0 还有以下特殊情况,也就是出现了平台

1、数组中连续的几个数的数值相等,即 right = 0,但这几个数总体是呈现上升或下降趋势的,并没有极大/小值

2、数组中连续的几个数的数值相等,即 right = 0,但这几个数中总体上是存在极大/小值的(把这几个数值相同的点视为一个点的话):

 

当 right = 0 时,说明存在平台,我们可以跳过平台, 不要计算 left * right,避免与最左端的情况的判断混淆,跳过平台后,left 是平台左边的差值,right 是平台右边的差值

left * right < 0 则摆动序列的长度 +1(该平台中存在极大/小值,选择平台中的任意一点计入摆动序列即可)。

代码:

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int left=0,ret=0,n=nums.size();for(int i=0;i<n-1;i++){int right=nums[i+1]-nums[i];if(right==0)    continue;//平台else if(left*right<=0)  ret++;//存在波峰或波谷left=right;}return ret+1;//数组的最左/右端也算是波峰/波谷}
};


http://www.ppmy.cn/ops/135808.html

相关文章

Linux进阶:用户、用户组、权限

root用户&#xff1a;超级管理员 root用户拥有最大的系统操作权限&#xff0c;而普通用户在许多地方的权限是受限的 普通用户的权限&#xff0c;一般在其HOME目录内是不受限的。一旦出了HOME目录&#xff0c;在大多数地方&#xff0c;普通用户仅有只读和执行权限&#xff0c;无…

如何通过低代码逻辑编排实现业务流程自动化?

随着数字化转型的加速&#xff0c;企业对高效、灵活的业务流程自动化需求日益增加。传统开发模式下的定制化解决方案往往周期长、成本高且难以适应快速变化的需求。低代码平台以其直观、简便的操作界面和强大的功能逐渐成为企业实现业务流程自动化的理想选择。本文将探讨低代码…

鸿蒙多线程开发——线程间数据通信对象01

1、线程间通信 线程间通信指的是并发多线程间存在的数据交换行为。由于ArkTS语言兼容TS/JS&#xff0c;其运行时的实现与其它所有的JS引擎一样&#xff0c;都是基于Actor内存隔离的并发模型提供并发能力。 对于不同的数据对象&#xff0c;在ArkTS线程间通信的行为是有差异的&…

大三学生面试经历(2)

继续昨天的内容&#xff0c;我面试的是一个Java实习岗&#xff0c;但是居然也问了我前端&#xff08;vue&#xff09;相关的问题 最大的感觉就是&#xff0c;现在真的越来越卷了&#xff0c;后端都把前端的东西卷完了&#xff0c;当时是线上面试&#xff0c;感觉答的不太好&…

Hello-Go

Hello-Go 环境变量 GOPATH 和 GOROOT &#xff1a;不同于其他语言&#xff0c;go中没有项目的说法&#xff0c;只有包&#xff0c;其中有两个重要的路径&#xff0c;GOROOT 和 GOPATH Go开发相关的环境变量如下&#xff1a; GOROOT&#xff1a;GOROOT就是Go的安装目录&…

【大选】2024年美国总统选举数据分析可视化

前言 • &#x1f453; 可视化主要使用 Plotly • &#x1f50e; 数据处理主要使用 pandas • &#x1f449; 本文是我自己在和鲸社区的原创 1.项目背景描述 2024年美国大选是该国政治生活中的重要事件&#xff0c;吸引了全球的关注。本报告通过对选举数据的分析&#xff0c…

Linux-Apache静态资源

文章目录 静态资源权限设置 &#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f916;Linux专栏&#xff1a;点击&#xff01; ⏰️创作时间&#xff1a;2024年11月20日11点21分 静态资源 Apache配置静态资源 可以在网页上配置一个静态的FTP服务器&#xff0c;让用户…

hadoop+wsl 10.255.255.254,BlockMissingException: Could not obtain block: 踩坑

起因&#xff1a; 我在我的wsl中启动一个hadoop 用java客户端连接hadoop&#xff0c;读取某个文件的内容异常&#xff0c;但是读取文件名&#xff0c;文件列表正常 问题&#xff1a; BlockMissingException: Could not obtain block:BP-xxx 显示缺少文件块&#xff0c;因此…