当前位置： 首页 > article >正文

贪心c++（结合LeetCode例题）

article 来源：原创 2022/10/5 15:43:50

目录

前言 

LeetCode455分发饼干

思考 

算法思路

LeetCode376摆动序列 

思考

思路

 代码

前言 

有1元，5元10，元，20元，100元，200，元的钞票无穷多张。先使用这些钞票支付x元支付x元，最少需要多少张？

列如,X= 628

最佳支付方法

3张200的，一张20的，1张5块的，3张一块的，共需要8张

直觉告诉我们：尽可能的多实用面值较大的钞票

贪心：遵循某种规律，不断贪心的选取当前最优策略的算法设计方法

为什么这么做是对的，面额为1元，5元，10元，20元，100元，200元，任意面额是比自己小的面额的倍数关系。

所以当使用一张较大面额的钞票时，若用较小面额钞票替换，，一定需要更多的其他面额钞票。

如10 = 5  + 5

故当前最优解即为全局最优解，贪心成立

思考：如果增加7元面额，贪心还成立吗？（不成立，不满足倍数关系，可以用动态规划解决）

代码：

#include <iostream>
using namespace std;
int main()
{int rmb[] = {200,100,20,10,5,1};int num = 6;     //六种面值 int x = 628;int count = 0;for(int i =0 ;i < num;i++){int use = x/rmb[i];count += use;x = x - rmb[i] * use;printf("需要支付面额为%d的%d张，",rmb[i],use);printf("剩余需要支付金额%d.\n", x); }printf("总共需要支付%d张\n",count++);
}

 

下面用六个题目深入了解贪心 

LeetCode455分发饼干

分发饼干

思考： 

做这个题目考虑好俩个问题

第一： 当某个孩子可以被多个饼干满足时，是否需要优先用某个饼干满足这个孩子

第二：当某个饼干可以满足多个孩子时是否需要优先满足某个孩子

为了让更多孩子得到满足有如下规律

1：某个饼干不能满足某个孩子，则饼干也不一定满足需求因子更大的孩子；

2：某个孩子可以更小的饼干满足，没必要用更大的糖果满足，因此可以保留更大的饼干满足需求因子更大的孩子（贪心）

3：孩子的需求因子更小更容易满足，姑优先从需求因子小的孩子尝试，可以得到正确的结果

算法思路：

1、将g与s从小到大排序

 2、从小到大的顺序使用各个饼干尝试是否可以满足某个孩子，每个饼干只尝试1次，若尝试成功，则换一个孩子尝试，知道发现没更多孩子或者没更多的的饼干，循环结束

代码：

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(),g.end()); sort(s.begin(),s.end());int child = 0; //代表满足几个孩子int bis = 0;   //代表尝试几个饼干while(child < g.size() && bis <s.size()){if(g[child] <= s[bis]){child++;     //满足孩子孩子指针向后移动}bis ++;       //每个饼干只尝试一次}return child;}
};

LeetCode376摆动序列 

376. 摆动序列

思考：

[1,17,5,10,13,15,10,5,16,8],整体不是摇摆序列，观察该序列前六位：[1,17,5,10,13,15]橙色部分为上升段：

其中它的三个子序列是摇摆序列：

[1,17,5,10...]

[1,17,5,13...]

[1,17,5,15...]

在不清楚原始第七位是什么情况下，只看前六位，摇摆子序列的第四位从10,13,15中选择一个数

思考选则那个好

我们的目的是希望第七位成为摇摆序列的概率更大，，应该尽可能的选择大的更大的，所以选择15

思路

状态机 

 代码

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if (nums.size() < 2){return nums.size();}static const int BEGIN = 0;static const int UP = 1;static const int DOWN = 2;int STATE = BEGIN;int max_length = 1;for(int i = 1;i < nums.size();i ++){switch(STATE){case BEGIN:if(nums[i-1] < nums[i]){STATE =UP;max_length ++;}else if(nums[i-1] > nums[i]){STATE = DOWN;max_length++;}break;case UP:if(nums[i-1]>nums[i]){STATE =DOWN;max_length++;}break;case DOWN:if(nums[i-1] < nums[i]){STATE =UP;max_length++;}break;} }return max_length++;}
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.dgrt.cn/a/58376.html

如若内容造成侵权/违法违规/事实不符，请联系我爱学习网进行投诉反馈，一经查实，立即删除！

相关文章：

贪心c++（结合LeetCode例题）

目录 前言 LeetCode455分发饼干 思考 算法思路 LeetCode376摆动序列 思考 思路 代码 前言 有1元&#xff0c;5元10&#xff0c;元&#xff0c;20元&#xff0c;100元&#xff0c;200&#xff0c;元的钞票无穷多张。先使用这些钞票支付x元支付x元&#xff0c;最少需要…...

编程日记 2022/10/5 15:43:50

【python】文本处理：删除包含关键词的行、删除指定列、删除指定字符、替换关键字……...

目录 1、行处理 删除文件中包含关键词的行 删除TXT中的带/不带指定字符的行(并保留带指定字符的行) 删除匹配or不匹配某些条件的行 2、字符处理 删除特定字符 1.1、删除特定位置的字符 1.2、删除指定字符 1.3、删除每一行首/尾匹配条件的字符 正则表达式 替换文件里的字符 3、列…...

编程日记 2022/10/5 15:43:16

手写节流防抖函数

1. 认识防抖和节流函数 防抖和节流的概念最早不是出现在软件工程中&#xff0c;防抖是出现在电子元件中&#xff0c;节流是出现的流体流动中。 而javascript是事件驱动的&#xff0c;大量的操作会触发事件&#xff0c;加入到事件队列中处理而对于某些频繁的事件处理会造成性能…...

编程日记 2022/10/5 15:41:15

camunda_11_connector

Camunda 的 service task 推荐使用 external task, 它有很多优点: 流程引擎可以做到轻量级, 流程引擎实例可以支持更多的业务.解耦流程引擎和业务代码, 以后的升级和部署将非常方便.借助external task SDK, 业务代码实现也非常简单external task 采用 pull 模式, 由 external t…...

编程日记 2022/10/5 15:40:34

通达信自动交易接口设置止损程序解析

通达信自动交易接口设置止损程序并不是很难&#xff0c;对于交易者来说&#xff0c;还是需要去学习一些编程知识&#xff0c;像交易中的止损程序&#xff0c;可以这样去编写和输入你的止损策略&#xff1a; &#xff08;1&#xff09;# 设置买卖止损值 def set_stop_lose_n…...

编程日记 2022/10/5 15:39:59

MySQL事务的理解

什么是事务 事务是是数据库操作的最小的单元&#xff0c;它包含了一个或者多个操作命令&#xff0c;这些命令作为一个整体来执 行&#xff0c;要么一起成功要么一起失败&#xff0c;事务是不可在分的一个整体的操作集合。 事务具备的四大特性 原子性&#xff1a;事务是一个…...

编程日记 2022/10/5 15:39:26

ubantu服务器崩溃，重装系统如何使用之前的账号

1.进入root账户下&#xff1a; sudo su 2.查看账号拥有者和所属组 ls -la 2.给现在系统&#xff0c;添加原来相同的已存在账号名&#xff1a; adduser newusername 注意&#xff1a;报告已存在用户名称&#xff01;不用管&#xff0c;这个错误。已经添加到新系统中了。 3.修…...

编程日记 2022/10/5 15:38:53

Python 逻辑回归

逻辑回归分类 训练二元分类器 加载仅有两个分类的数据 from sklearn.linear_model import LogisticRegression from sklearn import datasets from sklearn.preprocessing import StandardScaleriris datasets.load_iris() features iris.data[:100,:] target iris.target…...

编程日记 2022/10/5 15:38:18

web前端面试题附答案016-怎么让顶部轮播图渲染的更快？

一、为什么强调轮播图&#xff1f; 很多时候我们强调用户体验&#xff0c;而这里更多时候我们更强调完美的首屏体验&#xff0c;而现在几乎每个网站顶部第一个大模块就是轮播图。轮播图占得区域最大&#xff0c;图片质量也更高&#xff0c;几乎一张图片的面积&#xff0c;体积就…...

编程日记 2022/10/5 15:37:44

Python脚本，物联网云服务器端口监控

事实上&#xff0c;物联网的思路很简单&#xff0c;客户端设备通过TCP协议上传到某个云服务器的端口&#xff0c;我们需要在这个云服务器上编写一个小小的脚本去创建某个端口&#xff0c;持续监听&#xff0c;可以互相发送数据&#xff0c;这个脚本语言可以是JAVA&#xff0c;也…...

编程日记 2022/10/5 15:37:02

NAND VT Distribution 和失效模式

Vt Distribution是NAND Flash非常重要的一个特性。 1 从NMOS Vt到FGNMOS Vt 阈值电压(Vt或Vth)的概念是从MOS(Metal-Oxide-Semicondutor)来的。MOS的工作原理就像一个水库，Gate就是闸，闸抬起来(VGate≥Vth)电流就可以流过沟道(Channel)，闸放下去(VGate<Vth)电流就不可以流…...

编程日记 2023/2/5 16:32:08

【C语言】编程初学者入门训练（1）

文章目录1. 实践出真知2. 我是大V3. 有容乃大4. 小飞机5. 缩短2进制6. 十六进制转十进制7. printf的返回值8. 成绩输入输出9. 学生基本信息输入输出10. 字符圣诞树1. 实践出真知 题目内容&#xff1a;于老师经常告诉我们“学习编程最好的办法就是上机实践&#xff0c;因为你要对…...

编程日记 2023/2/5 16:31:56

Python numpy.interp实例讲

​​​本文章向大家介绍Python numpy.interp实例讲解&#xff0c;主要分析其语法、参数、返回值和注意事项&#xff0c;并结合实例形式分析了其使用技巧&#xff0c;希望通过本文能帮助到大家理解应用这部分内容。用法: numpy.interp(x, xp, fp, leftNone, rightNone, periodN…...

编程日记 2023/2/5 16:31:45

Xavier参数初始化方法和Kaiming参数初始化方法详细介绍及其原理详解

相关文章 梯度下降算法、随机梯度下降算法、动量随机梯度下降算法、AdaGrad算法、RMSProp算法、Adam算法详细介绍及其原理详解反向传播算法和计算图详细介绍及其原理详解激活函数、Sigmoid激活函数、tanh激活函数、ReLU激活函数、Leaky ReLU激活函数、Parametric ReLU激活函数…...

编程日记 2023/2/5 16:30:55

线程池EterfreeA/ThreadPool的使用

在GitHub上有个线程池项目&#xff0c;地址为 https://github.com/EterfreeA/ThreadPool &#xff0c;开源&#xff0c;它的License为AFL-3.0&#xff0c;这里了解学习下&#xff0c;code中有较多的中文说明: (1).Core.hpp: 一些define和size函数 (2).DoubleQueue.…...

编程日记 2023/2/5 16:30:42

Python科学计算：用NumPy快速处理数据

NumPy是Python 中一个非常重要的第三方库 它不仅是 Python 中使用最多的第三方库&#xff0c;而且还是 SciPy、Pandas 等数据科学的基础 库。它所提供的数据结构比 Python 自身的“更高级、更高效”&#xff0c;可以这么说&#xff0c;NumPy 所 提供的数据结构是 Python 数据…...

编程日记 2023/2/5 16:29:39

基于python实现的生成对抗网络GAN

项目简介 这篇文章主要介绍了生成对抗网络（Generative Adversarial Network），简称 GAN。 GAN 可以看作是一种可以生成特定分布数据的模型。 2.生成人脸图像 下面的代码是使用 Generator 来生成人脸图像，Generator 已经训练好保存在 pkl 文件中，只需要加载参数即可。由…...

编程日记 2023/2/5 16:29:29

Matlab----绘图以及文件储存

目录 二维曲线 基础函数&#xff1a;plot/fplot 绘制图形的辅助操作 文件存储 二维曲线 基础函数&#xff1a;plot/fplot &#xff08;1&#xff09;plot函数的基本用法&#xff1a;plot(x,y)其中x和y分别用于储存x坐标和y坐标数据 &#xff08;2&#xff09;最简单plot函…...

编程日记 2023/2/5 16:28:44

Docker - 12. 容器卷基本概念

目录 1. 容器卷是什么&#xff1f; 2. 容器卷的特点 1. 容器卷是什么&#xff1f; 卷就是目录或文件&#xff0c;存在于一个或者多个容器中&#xff0c;由docker挂载到容器&#xff0c;但不属于联合文件系统&#xff0c;因此能够绕过联合文件系统而提供一些用于存储或共享数…...

编程日记 2023/2/5 16:28:32

PHP 5 MySQLi 函数

PHP MySQLi 简介 PHP MySQLi PHP MySQL Improved! MySQLi 函数允许您访问 MySQL 数据库服务器。 注释&#xff1a;MySQLi 扩展被设计用于 MySQL 4.1.13 版本或更新的版本。 安装 / Runtime 配置 为了能够顺利使用 MySQLi 函数&#xff0c;您必须在编译 PHP 时添加对 MySQL…...

编程日记 2023/2/5 16:28:15