Day31 贪心算法 part01 理论基础 455.分发饼干 376.摆动序列 53.最大子序和
贪心算法 part01 理论基础 455.分发饼干 376.摆动序列 53.最大子序和
理论基础(转载自代码随想录)
什么是贪心
贪心的本质是选择每一阶段的局部最优,从而达到全局最优。
这么说有点抽象,来举一个例子:
例如,有一堆钞票,你可以拿走十张,如果想达到最大的金额,你要怎么拿?
指定每次拿最大的,最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优,最后拿走最大数额的钱就是推出全局最优。
再举一个例子如果是 有一堆盒子,你有一个背包体积为n,如何把背包尽可能装满,如果还每次选最大的盒子,就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。
贪心的套路(什么时候用贪心)
很多同学做贪心的题目的时候,想不出来是贪心,想知道有没有什么套路可以一看就看出来是贪心。
说实话贪心算法并没有固定的套路。
所以唯一的难点就是如何通过局部最优,推出整体最优。
那么如何能看出局部最优是否能推出整体最优呢?有没有什么固定策略或者套路呢?
不好意思,也没有! 靠自己手动模拟,如果模拟可行,就可以试一试贪心策略,如果不可行,可能需要动态规划。
有同学问了如何验证可不可以用贪心算法呢?
最好用的策略就是举反例,如果想不到反例,那么就试一试贪心吧。
可有有同学认为手动模拟,举例子得出的结论不靠谱,想要严格的数学证明。
一般数学证明有如下两种方法:
- 数学归纳法
- 反证法
看教课书上讲解贪心可以是一堆公式,估计大家连看都不想看,所以数学证明就不在我要讲解的范围内了,大家感兴趣可以自行查找资料。
面试中基本不会让面试者现场证明贪心的合理性,代码写出来跑过测试用例即可,或者自己能自圆其说理由就行了。
举一个不太恰当的例子:我要用一下1+1 = 2,但我要先证明1+1 为什么等于2。严谨是严谨了,但没必要。
虽然这个例子很极端,但可以表达这么个意思:刷题或者面试的时候,手动模拟一下感觉可以局部最优推出整体最优,而且想不到反例,那么就试一试贪心。
例如刚刚举的拿钞票的例子,就是模拟一下每次拿做大的,最后就能拿到最多的钱,这还要数学证明的话,其实就不在算法面试的范围内了,可以看看专业的数学书籍!
所以这也是为什么很多同学通过(accept)了贪心的题目,但都不知道自己用了贪心算法,因为贪心有时候就是常识性的推导,所以会认为本应该就这么做!
那么刷题的时候什么时候真的需要数学推导呢?
例如这道题目:链表:环找到了,那入口呢? (opens new window),这道题不用数学推导一下,就找不出环的起始位置,想试一下就不知道怎么试,这种题目确实需要数学简单推导一下。
贪心一般解题步骤
贪心算法一般分为如下四步:
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
这个四步其实过于理论化了,我们平时在做贪心类的题目 很难去按照这四步去思考,真是有点“鸡肋”。
做题的时候,只要想清楚 局部最优 是什么,如果推导出全局最优,其实就够了。
455. 分发饼干
思路:
这里的局部最优就是大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个,全局最优就是喂饱尽可能多的小孩。
可以尝试使用贪心策略,先将饼干数组和小孩数组排序。
然后从后向前遍历小孩数组,用大饼干优先满足胃口大的,并统计满足小孩数量。
如图:

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(),g.end()); //胃口sort(s.begin(),s.end()); //饼干int index = s.size()-1; //饼干最大尺寸int result = 0;//存放结果for(int i =g.size()-1; i>=0;i--){ //遍历胃口if(index>=0&&s[index]>=g[i]){index--;result++;}} return result;}
};
376. 摆动序列
class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if(nums.size()<=1) return nums.size();int prediff = 0;int curdiff = 0;int result = 1;for(int i = 0; i<nums.size()-1;i++){curdiff = nums[i+1] - nums[i];if((prediff>=0&&curdiff<0) || (prediff<=0&&curdiff>0)){result++;prediff = curdiff;}}return result;}
};
53. 最大子数组和
注释掉的是贪心算法,下面的是dp动态规划
class Solution {
public:int maxSubArray(vector<int>& nums) { //贪心算法
// int result = INT32_MIN;
// int count = 0;
// for(int j = 0; j<nums.size();j++){
// count += nums[j];
// result = count > result ? count : result;
// count = count < 0 ? 0 :count;
// }
// return result;vector<int> dp(nums.size());//dp动态规划if (dp.size()==0) return 0;dp[0] = nums[0];int result = dp[0];for(int i = 1; i<nums.size();i++){dp[i] = max(dp[i-1]+nums[i],nums[i]);result = (result>dp[i])?result:dp[i];}return result;}
};
相关文章:
Day31 贪心算法 part01 理论基础 455.分发饼干 376.摆动序列 53.最大子序和
贪心算法 part01 理论基础 455.分发饼干 376.摆动序列 53.最大子序和 理论基础(转载自代码随想录) 什么是贪心 贪心的本质是选择每一阶段的局部最优,从而达到全局最优。 这么说有点抽象,来举一个例子: 例如&#…...
行为型模式 | 观察者模式
一、观察者模式 1、原理 观察者模式又叫做发布-订阅(Publish/Subscribe)模式,定义了一种一对多的依赖关系。让多个观察者对象同时监听某一个主题对象,这个主题对象在状态上发生变化时,会通知所有观察者对象࿰…...
Python面向对象之继承
【 一 】什么是继承(Inheritance) 继承允许创建一个新类(称为子类或派生类),从已存在的类(称为父类或基类)继承属性和方法。子类可以继承父类的特性,并可以通过添加新的属性和方法来…...
如何使用CFImagehost结合内网穿透搭建私人图床并无公网ip远程访问
[TOC] 推荐一个人工智能学习网站点击跳转 1.前言 图片服务器也称作图床,可以说是互联网存储中最重要的应用之一,不仅网站需要图床提供的外链调取图片,个人或企业也用图床存储各种图片,方便随时访问查看。不过由于图床很不挣钱&a…...
Wargames与bash知识14
Wargames与bash知识13 Bandit22 基于时间的作业调度程序cron会定期自动运行一个程序。在/etc/cron.d/中查找配置,并查看正在执行的命令。 注意:查看其他人编写的shell脚本是一项非常有用的技能。此级别的脚本有意使其易于阅读。如果您在理解它的作用时…...
2020年认证杯SPSSPRO杯数学建模C题(第二阶段)抗击疫情,我们能做什么全过程文档及程序
2020年认证杯SPSSPRO杯数学建模 C题 抗击疫情,我们能做什么 原题再现: 2020 年 3 月 12 日,世界卫生组织(WHO)宣布,席卷全球的冠状病毒引发的病毒性肺炎(COVID-19)是一种大流行病。…...
JAVA基础学习笔记-day17-反射
JAVA基础学习笔记-day17-反射 1. 反射(Reflection)的概念1.1 反射的出现背景1.2 反射概述1.3 Java反射机制研究及应用1.4 反射相关的主要API1.5 反射的优缺点 2. 理解Class类并获取Class实例2.1 理解Class2.1.1 理论上2.1.2 内存结构上 2.2 获取Class类的实例(四种方法)2.3 哪些…...
经典算法-模拟退火算法的python实现
经典算法-模拟退火算法的python实现 模拟退火算法基本思想 模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却。加温时,固体内部粒子随温度升高变为无序状,内能增大,而缓慢冷却时粒子又逐渐趋有序。…...
谷粒学院项目redirect_uri 参数错误微信二维码登录
谷粒学院项目redirect_uri 参数错误_redirect_uri": "http%3a%2f%2fguli.shop%2fapi%2fuce-CSDN博客 修改本地配置 # ����˿� server.port8160 # ����&#x…...
Jenkins+nexus
jiekins安装完成 1、安装java环境 [rootnexus ~]# tar -xf jdk-8u211-linux-x64.tar.gz -C /usr/local [rootnexus ~]# vim /etc/profile.d/java.sh JAVA_HOME/usr/local/jdk1.8.0_211 PATH$PATH:$JAVA_HOME/bin [rootnexus ~]# source /etc/profile.d/java.sh 必须要选择与n…...
「JavaSE」类和对象1
🎇个人主页:Ice_Sugar_7 🎇所属专栏:快来卷Java啦 🎇欢迎点赞收藏加关注哦! 类和对象 🍉类的定义🍌类的实例化 🍉this引用🍉对象的构造及初始化🍌…...
Ubuntu server搭建dhcp服务器
安装 直接使用一下命令进行安装 apt-get install isc-dhcp-server 以下就是安装好的图片 然后进入dhcp目录 cd /etc/dhcp 进入后用ls查看当前目录存在哪些文件 使用如下进入dhcp.conf vim dhcpd.conf 红:设置ip域和子网掩码 绿:设置ip池范围 黄…...
2024--Django平台开发-Web框架和Django基础(二)---Mysql多版本共存(Mac系统)
MySQL多版本共存(Mac系统) 想要在Mac系统上同时安装【MySQL5.7 】【MySQL8.0】版本,需要进行如下的操作和配置。 想要同时安装两个版本可以采取如下方案: 方案1:【讲解】 MySQL57,用安装包进行安装。 MyS…...
Pytorch 反向传播 计算图被修改的报错
先看看报错的内容 RuntimeError: one of the variables needed for gradient computation has been modified by an inplace operation: [torch.FloatTensor [5, 1]], which is output 0 of AsStridedBackward0, is at version 2; expected version 1 instead. Hint: enable an…...
android studio设置gradle和gradle JDK版本
文章目录 1.gradle JDK版本2.gradle版本 1.gradle JDK版本 file -> project structure -> SDK Location -> Gradle Settings -> Gradle JDK -> Download JDK 2.gradle版本 file -> project structure -> Project...
Android 15即将到来,或将推出5大新功能特性
Android15 OneUI电池优化 三星最近完成了对其所有设备的稳定版 One UI 6.0 更新的推出,引起了用户的极大兴奋。据新出现的互联网统计数据显示,即将发布的基于 Android 15 的 One UI 7 将通过优化电池和功耗来重新定义用户体验,这是一项具有突…...
sqlalchemy 事务自动控制(类java aop)
最近使用它交互数据库,想实现类似java aop那种自动事务控制,不用手动commit或者rollback。我是用的是flaskdenpendency-injecter 这是我的db的配置类,里面会初始化一些session配置,里面比较重要的是把autocommit和autoflush关闭了…...
vue2-手写轮播图
轮播图5长展示,点击指示器向右移动一个图片,每隔2秒移动一张照片! <template><div class"top-app"><div class"carousel-container"><div class"carousel" ref"carousel">&…...
Google I/O大会:Android 13
3个体验升级的方向 以智能手机为场景核心、 扩大智能终端的应用边界以及实现多设备间更好地协同。具体到系统体验层,安卓13将支持图标颜色随主题更换、为不同应用设定使用的语言、新的媒体中心界面等等,同时谷歌也推出了自家的钱包应用(Goog…...
VUE指令(一)
vue会根据不同的指令,针对不同的标签实现不同的功能。指令是带有 v- 前缀的特殊标签属性。指令的职责是,当表达式的值改变时,将其产生的连带影响,响应式地作用于 DOM。 1、v-text:设置元素的文本内容,不会解…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
