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:设置元素的文本内容,不会解…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
wpf在image控件上快速显示内存图像
wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像(比如分辨率3000*3000的图像)的办法,尤其是想把内存中的裸数据(只有图像的数据,不包…...
在 Spring Boot 中使用 JSP
jsp? 好多年没用了。重新整一下 还费了点时间,记录一下。 项目结构: pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...
