当前位置: 首页 > 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;}
};

相关文章:

【贪心算法题目】

1. 柠檬水找零 这一个题目是一个比较简单的模拟算法&#xff0c;只需要根据手里的钱进行找零即可&#xff0c;对于贪心的这一点&#xff0c;主要是在20元钱找零的情况下&#xff0c;此时会出现两种情况&#xff1a;10 5 的组合 和 5 5 5 的组合&#xff0c;根据找零的特点&a…...

yarn常用命令

Yarn 是一个快速、可靠且安全的依赖管理工具&#xff0c;用于替代 npm。以下是一些常用的 Yarn 命令&#xff0c;用于不同的包管理和项目依赖安装场景&#xff1a; 初始化一个新的项目 yarn init这个命令会引导你创建一个 package.json 文件。 安装依赖 yarn add [package]…...

nginx+nginx-http-flv-module在Linux服务器搭建

需求 在服务器搭建点播/视频平台的话需要在服务器搭建nginx和rtmp模块 rtmp模块 rtmp 模块有 nginx-rtmp-module &#xff0c;但是我们这里使用 nginx-http-flv-module 来替代。因为后者是基于前者开发的&#xff0c;前者拥有的功能后者都有&#xff0c;后者是国内的开发开…...

多线程(八)

一、wait和notify 等待 通知 机制 和join的用途类似,多个线程之间随机调度,引入 wait notify 就是为了能够从应用层面上,干预到多个不同线程代码的执行顺序.( 这里说的干预,不是影响系统的线程调度策略 内核里的线程调度,仍然是无序的. 相当于是在应用程序…...

投骰子——(随机游戏的控制)

精华点在于&#xff1a;利用封装&#xff0c;函数之间的良好调用&#xff0c;从而清晰明了的解决问题。 #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> # include<stdlib.h> # include<time.h> # include"math.h" # define ARR_LEN 10 # d…...

找出最长等值子数组

问题 给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 如果子数组中所有元素都相等&#xff0c;则认为子数组是一个 等值子数组 。注意&#xff0c;空数组是 等值子数组 。 从 nums 中删除最多 k 个元素后&#xff0c;返回可能的最长等值子数组的长度。 子数组 是数…...

Go 切片常用操作与使用技巧

1.什么是切片 在 Go 语言中的切片&#xff08;slice&#xff09;是一种灵活的动态数组&#xff0c;它可以自动扩展和收缩&#xff0c;是 Go 语言中非常重要的数据结构之一。切片是基于数组实现的&#xff0c;它的底层是数组&#xff0c;可以理解为对底层数组的抽象。它会生成一…...

2024 中青杯高校数学建模竞赛(A题)数学建模完整思路+完整代码全解全析

你是否在寻找数学建模比赛的突破点&#xff1f;数学建模进阶思路&#xff01; 作为经验丰富的数学建模团队&#xff0c;我们将为你带来2024 长三角高校数学建模竞赛&#xff08;A题&#xff09;的全面解析。这个解决方案包不仅包括完整的代码实现&#xff0c;还有详尽的建模过…...

开源与闭源:AI模型发展的双重路径之争

前言 随着人工智能&#xff08;AI&#xff09;技术的飞速发展&#xff0c;AI模型的应用已经渗透到各行各业&#xff0c;从医疗、金融到制造、教育&#xff0c;无不受到AI技术的深刻影响。在讨论一个AI模型“好不好”“有没有发展”时&#xff0c;绕不过“开源”和“闭源”两条…...

微信小程序---小程序文档配置(2)

一、小程序文档配置 1、小程序的目录结构 1.1、目录结构 小程序包含一个描述整体程序的 app 和多个描述各自页面的 page 一个小程序主体部分由三个文件组成&#xff0c;必须放在项目的根目录 比如当前我们的《第一个小程序》项目根目录下就存在这三个文件&#xff1a; 1…...

15:00面试,15:08就出来了,问的问题有点变态。。。

从小厂出来&#xff0c;没想到在另一家公司又寄了。 到这家公司开始上班&#xff0c;加班是每天必不可少的&#xff0c;看在钱给的比较多的份上&#xff0c;就不太计较了。没想到8月一纸通知&#xff0c;所有人不准加班&#xff0c;加班费不仅没有了&#xff0c;薪资还要降40%…...

电磁兼容(EMC):去耦电容设计详解

目录 1. 概念 2. 去耦电容工作机理 3. 去耦电容大小选择 4. 去耦电容PCB布局 电容在电路中不同作用有不同的称呼去耦电容、旁路电容、储能电容&#xff0c;而这些作用又可以统称为滤波。本文将详细解读一下三者之间的差别&#xff0c;并着重说明一下去耦电容的设计方法。 …...

《数组逆序输出》

描述 编写程序&#xff0c;输入10个整数n存入&#xff0c;再按逆序重新存放后再输出。 输入描述 输入共10个数。 输出描述 输出共1行&#xff0c;每个数字用空格隔开。 样例输入 1 -5 -4 -3 -2 -1 0 1 2 3 4 样例输出 1 4 3 2 1 0 -1 -2 -3 -4 -5 提示 对于100%的数据…...

必应崩了?

目录 今天使用必应发现出现了不能搜索&#xff0c;弹出乱码的情况。 搜了一下&#xff0c;发现其他人也出现了同样的问题。 使用Edge浏览器的话&#xff0c;可以试着改一下DNS&#xff0c;有可能会恢复正常&#xff08;等官方修复了记得改回来&#xff09; 使用谷歌浏览器打开…...

Elasticsearch集群和Logstash、Kibana部署

1、 Elasticsearch集群部署 服务器 安装软件主机名IP地址系统版本配置ElasticsearchElk10.3.145.14centos7.5.18042核4GElasticsearchEs110.3.145.56centos7.5.18042核3GElasticsearchEs210.3.145.57centos7.5.18042核3G 软件版本&#xff1a;elasticsearch-7.13.2.tar.gz 示…...

网络的基础理解

文章目录 网络的基础认识 网络协议协议分层OSI七层模型TCP/IP 五层/四层 模型 网络的基础认识 先来看下面几个问题 什么是网络&#xff1f; 网络就是有许多台设备包括计算机单不仅限于计算机&#xff0c;这些设备通过相互通信所组成起来系统&#xff0c;我们称之为网络所以如…...

Android Studio 与 Gradle 及插件版本兼容性

Android Studio 开始新项目时&#xff0c;会自动创建其中部分文件&#xff0c;并为其填充合理的默认值。 项目文件结构布局&#xff1a; 一、Android Gradle 及插件作用&#xff1a; Android Studio 构建系统以 Gradle 为基础&#xff0c;并且 Android Gradle 插件 (AGP) 添加…...

【BUG】Edge|联想电脑 Bing 搜索报错“Ref A: 乱码、 Ref B:乱码、Ref C: 日期” 的解决办法

文章目录 省流版前言解决办法 详细解释版前言问题描述与排查过程解决办法与总结 省流版 我原以为我解决了&#xff0c;才发的博客&#xff0c;晚上用了一下其他设备发现还是会出现这个问题… 这篇博客并未解决该问题&#xff0c;如果评论里有人解决了这个问题不胜感激&#x…...

深度学习小车操作手册全

深度学习小车_操作手册_全 资源链接 分享文件&#xff1a;深度学习小车_操作手册_全.pdf 链接&#xff1a;https://pan.xunlei.com/s/VNy-KXPDZw64RqQGXiWVEDMRA1?pwdymu4# 复制这段内容后打开手机迅雷App&#xff0c;查看更方便智能车简介 2019 年的特斯拉自动驾驶开放日上…...

Python实现天气数据采集

Python实现天气数据采集 一、需求介绍二、完整代码一、需求介绍 本次天气数据采集的需求是获取每日的最高温、最低温、风力、风向、天气状况、AQI指数,如图所示,完整代码附后: 本次采集的目标网址是2345天气网: 上图的URL中,beijing是城市名称的缩写,54511即为城市代码…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

云安全与网络安全:核心区别与协同作用解析

在数字化转型的浪潮中&#xff0c;云安全与网络安全作为信息安全的两大支柱&#xff0c;常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异&#xff0c;并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全&#xff1a;聚焦于保…...