当前位置: 首页 > news >正文

Day31 贪心算法 part01 理论基础 455.分发饼干 376.摆动序列 53.最大子序和

贪心算法 part01 理论基础 455.分发饼干 376.摆动序列 53.最大子序和

理论基础(转载自代码随想录)

什么是贪心

贪心的本质是选择每一阶段的局部最优,从而达到全局最优

这么说有点抽象,来举一个例子:

例如,有一堆钞票,你可以拿走十张,如果想达到最大的金额,你要怎么拿?

指定每次拿最大的,最终结果就是拿走最大数额的钱。

每次拿最大的就是局部最优,最后拿走最大数额的钱就是推出全局最优。

再举一个例子如果是 有一堆盒子,你有一个背包体积为n,如何把背包尽可能装满,如果还每次选最大的盒子,就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。

贪心的套路(什么时候用贪心)

很多同学做贪心的题目的时候,想不出来是贪心,想知道有没有什么套路可以一看就看出来是贪心。

说实话贪心算法并没有固定的套路

所以唯一的难点就是如何通过局部最优,推出整体最优。

那么如何能看出局部最优是否能推出整体最优呢?有没有什么固定策略或者套路呢?

不好意思,也没有! 靠自己手动模拟,如果模拟可行,就可以试一试贪心策略,如果不可行,可能需要动态规划。

有同学问了如何验证可不可以用贪心算法呢?

最好用的策略就是举反例,如果想不到反例,那么就试一试贪心吧

可有有同学认为手动模拟,举例子得出的结论不靠谱,想要严格的数学证明。

一般数学证明有如下两种方法:

  • 数学归纳法
  • 反证法

看教课书上讲解贪心可以是一堆公式,估计大家连看都不想看,所以数学证明就不在我要讲解的范围内了,大家感兴趣可以自行查找资料。

面试中基本不会让面试者现场证明贪心的合理性,代码写出来跑过测试用例即可,或者自己能自圆其说理由就行了

举一个不太恰当的例子:我要用一下1+1 = 2,但我要先证明1+1 为什么等于2。严谨是严谨了,但没必要。

虽然这个例子很极端,但可以表达这么个意思:刷题或者面试的时候,手动模拟一下感觉可以局部最优推出整体最优,而且想不到反例,那么就试一试贪心

例如刚刚举的拿钞票的例子,就是模拟一下每次拿做大的,最后就能拿到最多的钱,这还要数学证明的话,其实就不在算法面试的范围内了,可以看看专业的数学书籍!

所以这也是为什么很多同学通过(accept)了贪心的题目,但都不知道自己用了贪心算法,因为贪心有时候就是常识性的推导,所以会认为本应该就这么做!

那么刷题的时候什么时候真的需要数学推导呢?

例如这道题目:链表:环找到了,那入口呢? (opens new window),这道题不用数学推导一下,就找不出环的起始位置,想试一下就不知道怎么试,这种题目确实需要数学简单推导一下。

贪心一般解题步骤

贪心算法一般分为如下四步:

  • 将问题分解为若干个子问题
  • 找出适合的贪心策略
  • 求解每一个子问题的最优解
  • 将局部最优解堆叠成全局最优解

这个四步其实过于理论化了,我们平时在做贪心类的题目 很难去按照这四步去思考,真是有点“鸡肋”。

做题的时候,只要想清楚 局部最优 是什么,如果推导出全局最优,其实就够了。

455. 分发饼干

思路:

这里的局部最优就是大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个,全局最优就是喂饱尽可能多的小孩

可以尝试使用贪心策略,先将饼干数组和小孩数组排序。

然后从后向前遍历小孩数组,用大饼干优先满足胃口大的,并统计满足小孩数量。

如图:

img

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.最大子序和 理论基础&#xff08;转载自代码随想录&#xff09; 什么是贪心 贪心的本质是选择每一阶段的局部最优&#xff0c;从而达到全局最优。 这么说有点抽象&#xff0c;来举一个例子&#xff1a; 例如&#…...

行为型模式 | 观察者模式

一、观察者模式 1、原理 观察者模式又叫做发布-订阅&#xff08;Publish/Subscribe&#xff09;模式&#xff0c;定义了一种一对多的依赖关系。让多个观察者对象同时监听某一个主题对象&#xff0c;这个主题对象在状态上发生变化时&#xff0c;会通知所有观察者对象&#xff0…...

Python面向对象之继承

【 一 】什么是继承&#xff08;Inheritance&#xff09; 继承允许创建一个新类&#xff08;称为子类或派生类&#xff09;&#xff0c;从已存在的类&#xff08;称为父类或基类&#xff09;继承属性和方法。子类可以继承父类的特性&#xff0c;并可以通过添加新的属性和方法来…...

如何使用CFImagehost结合内网穿透搭建私人图床并无公网ip远程访问

[TOC] 推荐一个人工智能学习网站点击跳转 1.前言 图片服务器也称作图床&#xff0c;可以说是互联网存储中最重要的应用之一&#xff0c;不仅网站需要图床提供的外链调取图片&#xff0c;个人或企业也用图床存储各种图片&#xff0c;方便随时访问查看。不过由于图床很不挣钱&a…...

Wargames与bash知识14

Wargames与bash知识13 Bandit22 基于时间的作业调度程序cron会定期自动运行一个程序。在/etc/cron.d/中查找配置&#xff0c;并查看正在执行的命令。 注意&#xff1a;查看其他人编写的shell脚本是一项非常有用的技能。此级别的脚本有意使其易于阅读。如果您在理解它的作用时…...

2020年认证杯SPSSPRO杯数学建模C题(第二阶段)抗击疫情,我们能做什么全过程文档及程序

2020年认证杯SPSSPRO杯数学建模 C题 抗击疫情&#xff0c;我们能做什么 原题再现&#xff1a; 2020 年 3 月 12 日&#xff0c;世界卫生组织&#xff08;WHO&#xff09;宣布&#xff0c;席卷全球的冠状病毒引发的病毒性肺炎&#xff08;COVID-19&#xff09;是一种大流行病。…...

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实现 模拟退火算法基本思想 模拟退火算法来源于固体退火原理&#xff0c;将固体加温至充分高&#xff0c;再让其徐徐冷却。加温时&#xff0c;固体内部粒子随温度升高变为无序状&#xff0c;内能增大&#xff0c;而缓慢冷却时粒子又逐渐趋有序。…...

谷粒学院项目redirect_uri 参数错误微信二维码登录

谷粒学院项目redirect_uri 参数错误_redirect_uri": "http%3a%2f%2fguli.shop%2fapi%2fuce-CSDN博客 修改本地配置 # &#xfffd;&#xfffd;&#xfffd;&#xfffd;˿&#xfffd; server.port8160 # &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#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

&#x1f387;个人主页&#xff1a;Ice_Sugar_7 &#x1f387;所属专栏&#xff1a;快来卷Java啦 &#x1f387;欢迎点赞收藏加关注哦&#xff01; 类和对象 &#x1f349;类的定义&#x1f34c;类的实例化 &#x1f349;this引用&#x1f349;对象的构造及初始化&#x1f34c;…...

Ubuntu server搭建dhcp服务器

安装 直接使用一下命令进行安装 apt-get install isc-dhcp-server 以下就是安装好的图片 然后进入dhcp目录 cd /etc/dhcp 进入后用ls查看当前目录存在哪些文件 使用如下进入dhcp.conf vim dhcpd.conf 红&#xff1a;设置ip域和子网掩码 绿&#xff1a;设置ip池范围 黄…...

2024--Django平台开发-Web框架和Django基础(二)---Mysql多版本共存(Mac系统)

MySQL多版本共存&#xff08;Mac系统&#xff09; 想要在Mac系统上同时安装【MySQL5.7 】【MySQL8.0】版本&#xff0c;需要进行如下的操作和配置。 想要同时安装两个版本可以采取如下方案&#xff1a; 方案1&#xff1a;【讲解】 MySQL57&#xff0c;用安装包进行安装。 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 更新的推出&#xff0c;引起了用户的极大兴奋。据新出现的互联网统计数据显示&#xff0c;即将发布的基于 Android 15 的 One UI 7 将通过优化电池和功耗来重新定义用户体验&#xff0c;这是一项具有突…...

sqlalchemy 事务自动控制(类java aop)

最近使用它交互数据库&#xff0c;想实现类似java aop那种自动事务控制&#xff0c;不用手动commit或者rollback。我是用的是flaskdenpendency-injecter 这是我的db的配置类&#xff0c;里面会初始化一些session配置&#xff0c;里面比较重要的是把autocommit和autoflush关闭了…...

vue2-手写轮播图

轮播图5长展示&#xff0c;点击指示器向右移动一个图片&#xff0c;每隔2秒移动一张照片&#xff01; <template><div class"top-app"><div class"carousel-container"><div class"carousel" ref"carousel">&…...

Google I/O大会:Android 13

3个体验升级的方向 以智能手机为场景核心、 扩大智能终端的应用边界以及实现多设备间更好地协同。具体到系统体验层&#xff0c;安卓13将支持图标颜色随主题更换、为不同应用设定使用的语言、新的媒体中心界面等等&#xff0c;同时谷歌也推出了自家的钱包应用&#xff08;Goog…...

VUE指令(一)

vue会根据不同的指令&#xff0c;针对不同的标签实现不同的功能。指令是带有 v- 前缀的特殊标签属性。指令的职责是&#xff0c;当表达式的值改变时&#xff0c;将其产生的连带影响&#xff0c;响应式地作用于 DOM。 1、v-text&#xff1a;设置元素的文本内容&#xff0c;不会解…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

Ubuntu系统多网卡多相机IP设置方法

目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机&#xff0c;交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息&#xff0c;系统版本&#xff1a;Ubuntu22.04.5 LTS&#xff1b;内核版本…...

C++实现分布式网络通信框架RPC(2)——rpc发布端

有了上篇文章的项目的基本知识的了解&#xff0c;现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...

[特殊字符] 手撸 Redis 互斥锁那些坑

&#x1f4d6; 手撸 Redis 互斥锁那些坑 最近搞业务遇到高并发下同一个 key 的互斥操作&#xff0c;想实现分布式环境下的互斥锁。于是私下顺手手撸了个基于 Redis 的简单互斥锁&#xff0c;也顺便跟 Redisson 的 RLock 机制对比了下&#xff0c;记录一波&#xff0c;别踩我踩过…...