力扣贪心算法--第一天

news/2024/4/24 4:11:16/

前言

今天是贪心算法的第一天,算法之路重新开始!

内容

之前没了解过贪心算法。

什么是贪心

贪心的本质是选择每一阶段的局部最优,从而达到全局最优。难点就是如何通过局部最优,推出整体最优。

一、455.分发饼干

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。

对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

思路:

大饼干可以满足胃口大的,也可以满足胃口小的,应该优先满足胃口大的。

这里的局部最优就是大饼干喂给胃口大的,全局最优就是喂饱尽可能多的小孩

先将饼干数组和小孩数组排序,然后从后向前遍历小孩数组,如果饼干的大小大于或等于孩子的为空则给与,否则不给予,继续寻找选一个饼干是否符合。

func findContentChildren(g []int, s []int) int {sort.Ints(g)sort.Ints(s)child:=0for sIdx:=0;sIdx<len(s)&&child<len(g);sIdx++{if s[sIdx]>=g[child]{child++}}return child
}
二、376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

  • 例如, [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ,因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

  • 相反,[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。

给你一个整数数组 nums ,返回 nums 中作为 摆动序列 的 最长子序列的长度 。

思路:

将数组用坡度表示出来,

局部最优:删除单调坡度上的节点(不包括单调坡度两端的节点),那么这个坡度就可以有两个局部峰值

整体最优:整个序列有最多的局部峰值,从而达到最长摆动序列

但本题要考虑三种情况:

  1. 情况一:上下坡中有平坡
  2. 情况二:数组首尾两端
  3. 情况三:单调坡中有平坡
func wiggleMaxLength(nums []int) int {n:=len(nums)if n<2{return n}ans:=1preDiff:=nums[1]-nums[0]if preDiff!=0{ans=2}for i:=2;i<n;i++{diff:=nums[i]-nums[i-1]if preDiff<=0&&diff>0||preDiff>=0&&diff<0{ans++preDiff=diff}}return ans
}
三、53. 最大子数组和

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组是数组中的一个连续部分。

思路:

负数只会拉低总和。

局部最优:当前“连续和”为负数的时候立刻放弃,从下一个元素重新计算“连续和”,因为负数加上下一个元素 “连续和”只会越来越小。

全局最优:选取最大“连续和”

局部最优的情况下,并记录最大的“连续和”,可以推出全局最优

func maxSubArray(nums []int) int {maxNum:=nums[0]for i:=1;i<len(nums);i++{if nums[i]+nums[i-1]>nums[i]{nums[i]+=nums[i-1]}if nums[i]>maxNum{maxNum=nums[i]}}return maxNum
}

最后

可预见的正在变好!加油!


http://www.ppmy.cn/news/1405261.html

相关文章

源浩流体设备与您相约2024年第13届生物发酵展

参展企业介绍 温州源浩流体设备科技有限公司是一家集设计、开发、制造、销售、服务于一体的高科技企业&#xff0c;公司主要生产各种不锈钢阀门、管件、卫生级流体设备(卫生级换向阀,卫生级减压阀,卫生级罐底阀)等。现为温州市泵阀协会会员&#xff0c;ISO9000 2008版质量质量…

单链表求集合的交集

#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct LinkNode {ElemType data;LinkNode* next; }LinkNode, * LinkList; //尾插法建立单链表 void creatLinkList(LinkList& L) {L (LinkNode*)mallo…

QT - 日志:qDebug/qInfo/qWarning/qCritical

篇一、日志打印函数 头文件&#xff1a; #include <QDebug> 代码&#xff1a;qDebug()<<"hello world!"; 其他打印级别&#xff1a; qInfo(): 普通信息 qDebug(): 调试信息 qWarning(): 警告信息 qCritical(): 严重错误 qFatal(): 致命错误 1. qDebug…

Verilog语法回顾--用户定义原语

目录 用户定义原语 UDP定义 UDP状态表 状态表符号 组合UDP 电平敏感UDP 沿敏感时序UDP 参考《Verilog 编程艺术》魏家明著 用户定义原语 用户定义原语&#xff08;User-defined primitive&#xff0c;UDP&#xff09;是一种模拟硬件技术&#xff0c;可以通过设计新的原…

EFPN代码解读

论文 Extended Feature Pyramid Network for Small Object Detection python3 D:/Project/EFPN-detectron2-master/tools/train_net.py --config-file configs/InstanceSegmentation/pointrend_rcnn_R_50_FPN_1x_coco.yaml --num-gpus 1 训练脚本 cfg 中的配置 先获取配置…

Python(乱学)

字典在转化为其他类型时&#xff0c;会出现是否舍弃value的操作&#xff0c;只有在转化为字符串的时候才不会舍弃value 注释的快捷键是ctrl/ 字符串无法与整数&#xff0c;浮点数&#xff0c;等用加号完成拼接 5不入&#xff1f;&#xff1f;&#xff1f; 还有一种格式化的方法…

Java(内部类)

1.内部类 内的五大成员&#xff1a;属性、方法、构造方法、代码块、内部类 解释&#xff1a;在一个类的里面&#xff0c;再定义一个类。举例:在A类的内部定义B类&#xff0c;B类就被称为内部类注意&#xff1a;内部类表示的事物是外部类的一部分&#xff0c;内部类单独出现没…

pymc,一个灵活的的 Python 概率编程库!

目录 前言 安装与配置 概率模型 贝叶斯推断 概率分布 蒙特卡罗采样 贝叶斯网络 实例分析 PyMC库的应用场景 1. 概率建模 2. 时间序列分析 3. 模式识别 总结 前言 大家好&#xff0c;今天为大家分享一个超强的 Python 库 - pymc Github地址&#xff1a;https://gith…

JavaScript 对象管家 Proxy

JavaScript 在 ES6 中&#xff0c;引入了一个新的对象类型 Proxy&#xff0c;它可以用来代理另一个对象&#xff0c;并可以在代理过程中拦截、覆盖和定制对象的操作。Proxy 对象封装另一个对象并充当中间人&#xff0c;其提供了一个捕捉器函数&#xff0c;可以在代理对象上拦截…

Qt中实现域(Unix)套接字通信

Qt中实现域&#xff08;Unix&#xff09;套接字通信可以使用QLocalServer和QLocalSocket类。以下是一个简单的示例&#xff0c;演示了如何在两个Qt应用程序之间使用域套接字进行通信。 一、在服务器端&#xff1a; cpp Copy code #include <QtWidgets> #include <QL…

Linux(centos7)部署spark

Spark部署模式主要有4种:Local模式(单机模式)、Standalone模式(使用Spark自带的简单集群管理器)、Spark On Yarn模式(使用YARN作为集群管理器)和Spark On Mesos模式(使用Mesos作为集群管理器)。 下面介绍Local模式(单机模式)、跟Spark On Yarn模式(使用YARN作为集…

OpenHarmony实战:轻量级系统之子系统移植概述

OpenHarmony系统功能按照“系统 > 子系统 > 部件”逐级展开&#xff0c;支持根据实际需求裁剪某些非必要的部件&#xff0c;本文以部分子系统、部件为例进行介绍。若想使用OpenHarmony系统的能力&#xff0c;需要对相应子系统进行适配。 OpenHarmony芯片适配常见子系统列…

Git常用语句

设置用户名 git config --global user.name "用户名" git config --global user.email "邮箱"查看git用户信息 cat ~/.gitconfig初始化本地库 git initclone指定分支的代码 git clone -b my_branch gitgitlabxxxxxxxxxxxxxxxxxxxxxx.gitpush三件套 gi…

Golang- 邮件服务,发送邮件

依赖 go get -u github.com/jordan-wright/email文档 文档 示例代码 邮箱的相关配置 # email configuration email:port: 25 # 端口要配置25 否则可能出现EOF错误from: xxx1qq.comhost: smtp.qq.comis-ssl: truesecret: xxxxxnickname: 大锦余发送邮件代码 package utili…

合宙4G模块Air724UG调试过程(短信发送、上传数据到华为云IOT)

合宙Air724UG-4G模块AT指令调试接线演示 一、前言 上海合宙Air724UG模块是一款高性能的4G Cat.1通信模组(全网通模块,支持移动、联通、电信,支持短信和网络通信),为开发者提供了丰富的接口和开发方式。 在本文中,将详述调试与集成该模块的关键步骤: (1)从基础硬件配…

PyTorch深度学习——框架简介

深度学习的算法是高度结构化的&#xff0c;主要组成部分是线性变换、激活函数、反向传播和梯度优化等模块&#xff0c;实际应用中&#xff0c;为了方便算法的实现&#xff0c;常会将算法模型抽象成对张量的一系列计算&#xff0c;并将计算设计的一些算法抽象层应用程序接口API供…

dm8 开启归档模式

dm8 开启归档模式 1 命令行 [dmdbatest1 dm8]$ disql sysdba/Dameng123localhost:5237服务器[localhost:5237]:处于普通打开状态 登录使用时间 : 3.198(ms) disql V8 SQL> select name,status$,arch_mode from v$database;行号 NAME STATUS$ ARCH_MODE ----------…

数字化营销:电子元器件商城的新战略路径

数字化营销对于电子元器件商城来说是一种重要的新战略路径&#xff0c;可以通过以下方式实施&#xff1a; 建立网上商城平台&#xff1a;搭建一个用户友好的网上商城平台&#xff0c;提供方便快捷的在线购物体验。通过优化网站界面设计、提供多样化的搜索和筛选功能&#xff0c…

uniapp路由传参存在数据类型失真的问题

export default {methods: {jump() {// 通过params传参this.$Router.push({name: demo, params: {number:1,name: 123,value: null}})}} }目标模块接收参数&#xff1a; export default {onLoad() {// 获取参数const {number,name, value} this.$Route.queryconsole.log(numb…

CITE 2024 开幕在即,共赴电子制造业一体化协同增长

“展望2024年&#xff0c;人工智能的热点将持续引领行业趋势&#xff0c;全球对算力的需求预计将持续快速增长。人工智能在前沿技术的开发、产品的商业化落地、市场开拓以及产业链布局等方面的竞争将进一步加剧。 智能可穿戴设备、智能家居等新兴消费电子产品&#xff0c;经过过…