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

代码随想录算法训练营 || 贪心算法 455 376 53

Day27

贪心算法基础

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

  • 刷题或者面试的时候,手动模拟一下感觉可以局部最优推出整体最优,而且想不到反例,那么就试一试贪心

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

  • 贪心没有套路,说白了就是常识性推导加上举反例

455.分发饼干

力扣题目链接

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

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

思路

  • 贪心算法,每一次都拿着一个小孩,让这个小孩去吃尺寸最小的饼干,这样能达到全局最优,尽量能喂饱更多的小孩

  • 先把数组进行排序,因为要有序

  • 用index来处理小孩,i来遍历饼干,因为对每个小孩,饼干的尺寸要不断移动

  • 都从最小开始,如果遍历到某个位置饼干能满足小孩,那count++,同时这个小孩被满足了,index++

  • 最后返回count

  • 或者是每一次拿着一个饼干,让这个饼干尽可能满足胃口大的小孩,所以要遍历小孩,找到符合要求的,饼干位置减一

代码

class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);//先排序int count = 0;//满足的胃口int index = 0;//小孩的位置for (int i = 0; i < s.length && index < g.length; i++){//饼干进行遍历,因为要看哪个饼干能满足小孩if (s[i] >= g[index]){//找到了符合要求的count++;index++;//小孩位置自增}}return count;}
}class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int count = 0;int index = s.length - 1;for (int i = g.length - 1; i >= 0; i--){if (index >= 0 && s[index] >= g[i]){count++;index--;}}return count;}
}

376. 摆动序列

力扣题目链接

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

例如, [1,7,4,9,2,5] 是一个摆动序列,因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。

给定一个整数序列,返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些(也可以不删除)元素来获得子序列,剩下的元素保持其原始顺序。

思路

  • 这个解法很巧妙

  • 先剪枝,如果长度小于2,直接return 1

  • 之后使用up和down进行记录

  • 从1开始遍历,因为要和前一个元素进行比较

  • 如果比前一个大,那up就是down + 1

  • 如果比前一个小,那down就是up + 1

  • 最后返回两者较大值即可

代码

class Solution {public int wiggleMaxLength(int[] nums) {if (nums.length < 2) return 1;int up = 1;int down = 1;for (int i = 1; i < nums.length; i++) {if (nums[i] < nums[i - 1]) down = up + 1;if (nums[i] > nums[i - 1]) up = down + 1;}return Math.max(up,down);}
}

53. 最大子序和

力扣题目链接

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

思路

  • 先简单看一下暴力解法

  • 外层循环给出子数组起始位置,内层循环不断遍历后面的元素并更新res

  • 时间复杂度O(n2)

  • 贪心算法

  • 贪心的点在于,计算一个连续和,如果遍历到某个元素,加上这个元素让连续和变为负数了,那我们就把连续和置为0,从下一个元素开始重新计算连续和,因为加上一个负数肯定会让结果变小

代码

class Solution {public int maxSubArray(int[] nums) {int res = Integer.MIN_VALUE;int sum;for (int i = 0; i < nums.length; i++){sum = 0;for (int j = i; j < nums.length; j++){sum += nums[j];res = Math.max(res,sum);}}return res;}
}class Solution {public int maxSubArray(int[] nums) {int res = Integer.MIN_VALUE;int sum = 0;for (int i = 0; i < nums.length; i++) {sum += nums[i];//加上这个位置的元素res = Math.max(res,sum);//这句话要写在前面,否则全是负数的情况会返回0,不断更新resif (sum < 0){//如果连续和变为负数了sum = 0;//把连续和置为0,继续遍历}}return res;//最后返回res}
}

相关文章:

代码随想录算法训练营 || 贪心算法 455 376 53

Day27贪心算法基础贪心的本质是选择每一阶段的局部最优&#xff0c;从而达到全局最优。刷题或者面试的时候&#xff0c;手动模拟一下感觉可以局部最优推出整体最优&#xff0c;而且想不到反例&#xff0c;那么就试一试贪心。做题的时候&#xff0c;只要想清楚 局部最优 是什么&…...

PMP考前冲刺2.25 | 2023新征程,一举拿证

题目1-2&#xff1a;1.项目经理正在进行挣值分析&#xff0c;计算出了当前的成本偏差和进度偏差。发起人想要知道基于当前的绩效水平&#xff0c;完成所有工作所需的成本。项目经理应该提供以下哪一项数据?A.完工预算(BAC)B.完工估算(EAC)C.完工尚需估算(ETC)D.完工偏差(VAC)2…...

【自然语言处理】Topic Coherence You Need to Know(主题连贯度详解)

Topic Coherence You Need to Know皮皮&#xff0c;京哥皮皮&#xff0c;京哥皮皮&#xff0c;京哥CommunicationUniversityofChinaCommunication\ University\ of\ ChinaCommunication University of China 在大多数关于主题建模的文章中&#xff0c;常用主题连贯度&#xff…...

C++入门:模板

模板是泛型编程的基础&#xff0c;泛型编程即以一种独立于任何特定类型的方式编写代码。模板是创建泛型类或函数的蓝图或公式。库容器&#xff0c;比如迭代器和算法&#xff0c;都是泛型编程的例子&#xff0c;它们都使用了模板的概念。每个容器都有一个单一的定义&#xff0c;…...

【MySQL】索引常见面试题

文章目录索引常见面试题什么是索引索引的分类什么时候需要 / 不需要创建索引&#xff1f;有什么优化索引的方法&#xff1f;从数据页的角度看B 树InnoDB是如何存储数据的&#xff1f;B 树是如何进行查询的&#xff1f;为什么MySQL采用B 树作为索引&#xff1f;怎样的索引的数…...

【Web逆向】万方数据平台正文的逆向分析(上篇--加密发送请求)—— 逆向protobuf

【Web逆向】万方数据平台正文的逆向分析&#xff08;上篇--加密发送请求&#xff09;—— 逆向protobuf声明一、了解protobuf协议&#xff1a;二、前期准备&#xff1a;二、目标网站&#xff1a;三、开始分析&#xff1a;我们一句句分析&#xff1a;先for循环部分&#xff1a;后…...

Amazon S3 服务15岁生日快乐!

2021年3月14日&#xff0c;作为第一个发布的服务&#xff0c;Amazon S3 服务15周岁啦&#xff01;在中国文化里&#xff0c;15岁是个临界点&#xff0c;是从“舞勺之年”到“舞象之年”的过渡。相信对于 Amazon S3 和其他的云服务15周岁也将是其迎接更加美好未来的全新起点。亚…...

【python】函数详解

注&#xff1a;最后有面试挑战&#xff0c;看看自己掌握了吗 文章目录基本函数-function模块的引用模块搜索路径不定长参数参数传递传递元组传递字典缺陷&#xff0c;容易改了原始数据&#xff0c;可以用copy()方法避免变量作用域全局变量闭包closurenonlocal 用了这个声明闭包…...

AoP-@Aspect注解处理源码解析

对主类使用EnableAspectJAutoProxy注解后会导入组件&#xff0c; Import(AspectJAutoProxyRegistrar.class) public interface EnableAspectJAutoProxy {AspectJAutoProxyRegistrar类实现了ImportBeanDefinitionRegistrar接口中的registerBeanDefinitions()方法&#xff0c;此…...

宝塔搭建实战php悟空CRM前后端分离源码-vue前端篇(二)

大家好啊&#xff0c;我是测评君&#xff0c;欢迎来到web测评。 上一期给大家分享了悟空CRM server端在宝塔部署的方式&#xff0c;但是由于前端是用vue开发的&#xff0c;如果要额外开发新的功能&#xff0c;就需要在本地运行、修改、打包重新发布到宝塔才能实现功能更新&…...

FastASR+FFmpeg(音视频开发+语音识别)

想要更好的做一件事情&#xff0c;不仅仅需要知道如何使用&#xff0c;还应该知道一些基础的概念。 一、音视频处理基本梳理 1.多媒体文件的理解 1.1 结构分析 多媒体文件本质上可以理解为一个容器 容器里有很多流 每种流是由不同编码器编码的 在众多包中包含着多个帧(帧在音视…...

二分查找的实现代码JAVA

二分查找一、思路二、实现代码&#xff08;普通版&#xff09;三、整数溢出问题四、改进代码一、思路 1.前提: 有已排序数组A (假设已经做好) 2.定义左边界L、 右边界R,确定搜索范围&#xff0c;循环执行二分查找(3、4两步) 3.获取中间索引 M Floor((LR) 1/2) 4.中间素索引的值…...

cesium: 设置skybox透明并添加背景图 ( 003 )

第003个 点击查看专栏目录 本示例的目的是介绍如何在vue+cesium中设置skybox透明并添加背景图。 我们不想要黑乎乎的背景,想自定义一个背景图,然后前面显示地球。 直接复制下面的 vue+cesium源代码,操作2分钟即可运行实现效果. 文章目录 示例效果配置方式示例源代码(共70…...

【python】类的详解

注&#xff1a;最后有面试挑战&#xff0c;看看自己掌握了吗 文章目录PO verses OOPOOO当一个类很复杂的时候&#xff0c;考虑多弄一个类的改造私有类的模块化静态类verses动态类动态类查看模块源代码对象机制的基石 PyObjectPO verses OO PO PO耦合性高&#xff0c;很多过程…...

西安银行就业总结

引 进银行性价比最高的时刻是本科&#xff0c;研究生的话可以去需要研究生较多的银行&#xff0c;比如邮储或者证券类的中信建投。中信建投很香&#xff0c;要求本硕西电。研究生学历的话&#xff0c;一般情况下银行不会卡本科&#xff0c;只看最高学历&#xff0c;部分银行需…...

JavaScript Window

文章目录JavaScript Window浏览器对象模型 (BOM)Window 对象Window 尺寸其他 Window 方法JavaScript Window 浏览器对象模型 (BOM) 使 JavaScript 有能力与浏览器"对话"。 浏览器对象模型 (BOM) 浏览器对象模型&#xff08;Browser Object Model (BOM)&#xff09;…...

那些开发过程中需要遵守的开发规范

入职公司三天&#xff0c;没干啥其他活&#xff0c;基本在配置本地环境和阅读相关文档。技术方面公司基本用的是主流的技术体系&#xff0c;入职后需要先阅读阿里的开发规范和其他的一些产研文档。今天整理一些平时需要关注的阿里规约和数据库开发规范&#xff0c;方便今后在开…...

EFCore 基础入门教程

一、EFCore 基础入门教程EF 框架的简介、发展历史&#xff1b;ORM框架概念学习地址&#xff1a;https://blog.csdn.net/u011127019/article/details/129212786?spm1001.2014.3001.5502EFCore 安装&#xff0c;引入、支持的数据库学习地址&#xff1a;https://www.cnblogs.com/…...

HTML5 Drag and Drop

这是2个组合事件 dom对象分源对象和目标对象 绑定的事件也是分别区分源对象和目标对象 事件绑定 事件顺序 被拖拽元素&#xff0c;事件触发顺序是 dragstart->drag->dragend&#xff1b; 对于目标元素&#xff0c;事件触发的顺序是 dragenter->dragover->drop/…...

惠普m1136打印机驱动程序安装教程

惠普m113打印机是一款功能强大的多功能打印机&#xff0c;它能够打印、复印、扫描和传真等。如果你要使用这款打印机&#xff0c;你需要下载并安装驱动程序&#xff0c;以确保它能够在你的计算机上正常工作。在本文中&#xff0c;我们将介绍如何下载和安装惠普m1136打印机驱动程…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...

【PX4飞控】mavros gps相关话题分析,经纬度海拔获取方法,卫星数锁定状态获取方法

使用 ROS1-Noetic 和 mavros v1.20.1&#xff0c; 携带经纬度海拔的话题主要有三个&#xff1a; /mavros/global_position/raw/fix/mavros/gpsstatus/gps1/raw/mavros/global_position/global 查看 mavros 源码&#xff0c;来分析他们的发布过程。发现前两个话题都对应了同一…...