当前位置: 首页 > news >正文

【贪心算法题目】

1. 柠檬水找零

这一个题目是一个比较简单的模拟算法,只需要根据手里的钱进行找零即可,对于贪心的这一点,主要是在20元钱找零的情况下,此时会出现两种情况:10 + 5 的组合 和 5 + 5 + 5 的组合,根据找零的特点,5元钱可以对10元和20元找零,而10元钱只能对20找零,5元钱的作用相对较大,所以根据贪心的思想,我们是对于20元找零优先0 + 5 的组合,直接上思路:

C++ 算法代码:

注意:由于本题最大的面值是20元,所以只需要统计5元和10元的数量即可。

class Solution {
public:bool lemonadeChange(vector<int>& bills) {int five = 0, ten = 0;for (auto x : bills){if (x == 5) five++; // 5 元:直接收下else if (x == 10) // 10 元:找零 5 元{if (five == 0) return false;else five--; ten++;}else // 20 元:分情况讨论{// 优先处理组合:10 + 5if (ten != 0 && five != 0) // 贪⼼{ten--; five--;}// 其次处理组合:5 + 5 + 5else if (five >= 3){five -= 3;}else return false;}}return true;}
};

2. 将数组和减半的最少操作次数

我们来看看这个题目,将数组和减半的最少操作此时,根据贪心的策略,只要我们每次都选择最大值,将最大值依次减半就可以控制到操作次数最少,直接看思路:

C++ 算法代码:

class Solution {
public:int halveArray(vector<int>& nums){priority_queue<double> heap; // 创建⼀个⼤根堆double sum = 0.0;for (int x : nums) // 把元素都丢进堆中,并求出累加和{heap.push(x);sum += x;}sum /= 2.0; // 先算出⽬标和int count = 0;while (sum > 0) // 依次取出堆顶元素减半,直到减到之前的⼀半以下{double t = heap.top() / 2.0;heap.pop();sum -= t;count++;heap.push(t);}return count;}
};

3. 最大数

这个题目依然是采用贪心来解决,将所有的数字当成字符串处理,那么两个数字之间的拼接操作以及比较操作就会很方便,此时我们只需要找出每次两个值组合的最大的排序方式重新定义⼀个新的排序规则,然后排序即可即可解决问题。

C++ 算法代码:

细节问题:有可能数组中所有的元素都是0,此时结果会有很多0,因此我们需要单独去除前导0。

class Solution
{
public:string largestNumber(vector<int>& nums){// 优化:把所有的数转化成字符串vector<string> strs;for (int x : nums) strs.push_back(to_string(x));// 排序 - lambda表达式sort(strs.begin(), strs.end(), [](const string& s1, const string& s2){return s1 + s2 > s2 + s1;});// 提取结果string ret;for (auto& s : strs) ret += s;if (ret[0] == '0') return "0";return ret;}
};

4. 摆动序列

何为一个摆动序列,我们可以类比一个折线图,题目上要求我们求出最长的摆动序列,那么根据贪心的思想,我们希望到达峰值或者峰低的点尽量大或者小,以此来达到最长的要求,直接上思路:

C++ 算法代码:

class Solution
{
public:int wiggleMaxLength(vector<int>& nums){int n = nums.size();if (n < 2) return n;int ret = 0, left = 0;for (int i = 0; i < n - 1; i++){int right = nums[i + 1] - nums[i]; // 计算接下来的趋势if (right == 0) continue; // 如果⽔平,直接跳过if (right * left <= 0) ret++; // 累加波峰或者波⾕left = right;}return ret + 1;}
};

相关文章:

  • 简述MyBatis中#{}引用和${}引用的区别
  • 春秋云境CVE-2023-50564
  • 金丝雀发布(灰度发布)介绍 及 声明式管理方法简介
  • 全国智慧海洋与大数据技术应用行业产教融合共同体成立
  • 【IPD进阶】学习IPD流程,从黑话开始
  • Shell编程之条件判断语句
  • 为什么说kafka没办法保证数据不丢?
  • 如何解决爬虫的IP地址受限问题?
  • flutter使用dbus插件时,在终端无法使用“dart-dbus”命令
  • PostgreSQL自带的命令行工具25- ecpg
  • onload和onunload有什么区别(代码举例说明)
  • 【元壤教育】全国最具价值的AIGC培训课程学前须知
  • 如何在 Git 中处理和解决分支合并冲突?
  • js如何遍历FormData的值
  • C++初阶学习第十弹——探索STL奥秘(五)——深入讲解vector的迭代器失效问题
  • 收藏网友的 源程序下载网
  • Angular2开发踩坑系列-生产环境编译
  • create-react-app项目添加less配置
  • ES6 ...操作符
  • JDK9: 集成 Jshell 和 Maven 项目.
  • macOS 中 shell 创建文件夹及文件并 VS Code 打开
  • XForms - 更强大的Form
  • 从伪并行的 Python 多线程说起
  • 前端之Sass/Scss实战笔记
  • 如何合理的规划jvm性能调优
  • 设计模式(12)迭代器模式(讲解+应用)
  • 跳前端坑前,先看看这个!!
  • ​LeetCode解法汇总307. 区域和检索 - 数组可修改
  • ​软考-高级-系统架构设计师教程(清华第2版)【第12章 信息系统架构设计理论与实践(P420~465)-思维导图】​
  • # 飞书APP集成平台-数字化落地
  • #include到底该写在哪
  • (8)STL算法之替换
  • (NSDate) 时间 (time )比较
  • (附源码)spring boot火车票售卖系统 毕业设计 211004
  • (附源码)ssm学生管理系统 毕业设计 141543
  • (附源码)计算机毕业设计SSM教师教学质量评价系统
  • (十) 初识 Docker file
  • (学习日记)2024.03.12:UCOSIII第十四节:时基列表
  • (一)kafka实战——kafka源码编译启动
  • (一)RocketMQ初步认识
  • (转)IIS6 ASP 0251超过响应缓冲区限制错误的解决方法
  • (转载)Linux网络编程入门
  • (轉貼) 2008 Altera 亞洲創新大賽 台灣學生成果傲視全球 [照片花絮] (SOC) (News)
  • *++p:p先自+,然后*p,最终为3 ++*p:先*p,即arr[0]=1,然后再++,最终为2 *p++:值为arr[0],即1,该语句执行完毕后,p指向arr[1]
  • .Net CF下精确的计时器
  • .NET Core 和 .NET Framework 中的 MEF2
  • .NET Framework与.NET Framework SDK有什么不同?
  • .NET 常见的偏门问题
  • .net之微信企业号开发(一) 所使用的环境与工具以及准备工作
  • /bin/bash^M: bad interpreter: No such file ordirectory
  • /etc/fstab和/etc/mtab的区别
  • @Valid和@NotNull字段校验使用
  • []T 还是 []*T, 这是一个问题
  • [Android]Android P(9) WIFI学习笔记 - 扫描 (1)
  • [CareerCup] 17.8 Contiguous Sequence with Largest Sum 连续子序列之和最大