当前位置: 首页 > 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的迭代器失效问题
  • Android单元测试 - 几个重要问题
  • angular2开源库收集
  • C++类的相互关联
  • CSS进阶篇--用CSS开启硬件加速来提高网站性能
  • Docker: 容器互访的三种方式
  • ES学习笔记(10)--ES6中的函数和数组补漏
  • Github访问慢解决办法
  • JavaScript工作原理(五):深入了解WebSockets,HTTP/2和SSE,以及如何选择
  • JavaScript实现分页效果
  • mysql 5.6 原生Online DDL解析
  • Promise面试题2实现异步串行执行
  • Python中eval与exec的使用及区别
  • quasar-framework cnodejs社区
  • Three.js 再探 - 写一个跳一跳极简版游戏
  • Vue.js-Day01
  • 不上全站https的网站你们就等着被恶心死吧
  • 机器学习 vs. 深度学习
  • 开放才能进步!Angular和Wijmo一起走过的日子
  • 猫头鹰的深夜翻译:JDK9 NotNullOrElse方法
  • 使用putty远程连接linux
  • 一些基于React、Vue、Node.js、MongoDB技术栈的实践项目
  • 哈罗单车融资几十亿元,蚂蚁金服与春华资本加持 ...
  • ​Java并发新构件之Exchanger
  • ​queue --- 一个同步的队列类​
  • ​草莓熊python turtle绘图代码(玫瑰花版)附源代码
  • ​云纳万物 · 数皆有言|2021 七牛云战略发布会启幕,邀您赴约
  • "无招胜有招"nbsp;史上最全的互…
  • #define,static,const,三种常量的区别
  • #控制台大学课堂点名问题_课堂随机点名
  • (Redis使用系列) Springboot 使用redis实现接口Api限流 十
  • (vue)页面文件上传获取:action地址
  • (二) Windows 下 Sublime Text 3 安装离线插件 Anaconda
  • (附表设计)不是我吹!超级全面的权限系统设计方案面世了
  • (教学思路 C#之类三)方法参数类型(ref、out、parmas)
  • .gitattributes 文件
  • .NET 依赖注入和配置系统
  • .net8.0与halcon编程环境构建
  • .netcore 6.0/7.0项目迁移至.netcore 8.0 注意事项
  • .NET开发人员必知的八个网站
  • @autowired注解作用_Spring Boot进阶教程——注解大全(建议收藏!)