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

算法训练营Day28

#Java #贪心

开源学习资料

Feeling and experiences:

这周来到了贪心算法,简要概述:

贪心算法是一种在每个步骤中都采取最优解(即,在当前看来最好的解)的算法设计策略。它通常用于求解优化问题。这种方法不总是能得到全局最优解,但在很多情况下能产生接近最优的解决方案。

这里是一些贪心算法的关键特点和应用实例:

1. 局部最优选择:在每个决策点,算法选择当前情况下的最佳选项,而不考虑未来的结果。

2. 无回溯:一旦做出选择,算法就不会撤销或重新考虑这个决策。

3. 应用领域:贪心算法适用于任务调度、图算法(如最小生成树和最短路径问题)、压缩编码(如霍夫曼编码)等。

4. 效率和简单性:通常,贪心算法比其他更复杂的算法更快、更简单。

5. 局限性:不是所有问题都可以用贪心算法有效解决。在某些情况下,贪心选择可能阻止达到全局最优解。

6. 实例:一个典型的例子是找零问题,即用最少的硬币数量找零。在美国货币系统中,使用贪心策略(总是选择可能的最大面值硬币)可以得到最优解。

要有效地应用贪心算法,关键是正确识别问题是否适合使用这种策略,并理解它可能只提供近似解而不是最优解。
 

分发饼干:力扣题目链接

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

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

如果没有想到贪心的思想,正常解答也很容易解出来:

class Solution {public int findContentChildren(int[] g, int[] s) {//贪心,先满足胃口最大的孩子//先排序Arrays.sort(g);Arrays.sort(s); //都是从小到大升序排列int endg = g.length -1;int ends = s.length -1;int count = 0;while(ends>=0 && endg>=0){if(s[ends] >= g[endg]){count++;ends--;endg--;}else{endg--;}}return count;}
}

官解用的是for循环,我认为while循环更容易理解

思路都是一样的,只要就是把这两个数组进行排序,这样我们从最后开始遍历比较,以我们的饼干数组为准。

从最大的满足度和饼干大小开始,逐一向下遍历。用两个指针endg和ends分别指向g数组和s数组的末尾元素(最大值)。
如果当前最大的饼干ends可以满足当前最大的满足度endg(即s[ends] >= g[endg]),则意味着这个孩子可以被满足。此时,将计数器count增加1,并将两个指针都向前移动一位,以检查下一个孩子和饼干。
如果当前饼干不能满足当前孩子(即s[ends] < g[endg]),则只将endg指针向前移动一位,检查下一个较小的满足度,因为当前饼干无论如何都无法满足当前孩子。

摆动序列:力扣题目链接

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

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

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

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

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

class Solution {public int wiggleMaxLength(int[] nums) {if (nums == null || nums.length == 0) {return 0;}if (nums.length == 1) {return 1;}int maxCount = 1;Integer prevDiff = null; // 使用Integer以便能存储nullfor (int i = 1; i < nums.length; i++) {int diff = nums[i] - nums[i - 1];if (diff != 0) {// 只在差值符号变化时增加maxCountif (prevDiff == null || (diff > 0 && prevDiff < 0) || (diff < 0 && prevDiff > 0)) {maxCount++;prevDiff = diff;}}}return maxCount;}
}

 最开始的一个想法是,把nums遍历计算,把得到的差放到另一个数组或者集合中,再用该数组或者集合进行遍历求解。

最大子序和:力扣题目链接

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

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

这道题利用前缀和来计算,非常简单:

class Solution {public int maxSubArray(int[] nums) {//初始化为数组的第一个元素int maxSum = nums[0];int sum = 0;for(int i = 0;i<nums.length;i++){sum += nums[i];sum = Math.max(sum,nums[i]);maxSum = Math.max(maxSum,sum);}return maxSum;}
}

力扣评论:

 走完这一生 如果我和你在一起会变得更好,那我们就在一起,否则我就丢下你。 我回顾我最光辉的时刻就是和不同人在一起,变得更好的最长连续时刻~~

Fighting!

相关文章:

算法训练营Day28

#Java #贪心 开源学习资料 Feeling and experiences&#xff1a; 这周来到了贪心算法&#xff0c;简要概述&#xff1a; 贪心算法是一种在每个步骤中都采取最优解&#xff08;即&#xff0c;在当前看来最好的解&#xff09;的算法设计策略。它通常用于求解优化问题。这种方…...

鸿蒙OS应用开发之日期选择

前面学习了时间选择组件,实现了时间的选择,这样非常方便用户进行时间的输入,通过手动就可以输入时间,比直接文本输入要省不少时间,特别对于手机这样单手操作的设备,更加重要了。因此,日期的输入工作也不能落后,本文将要学习日期选择组件,这样就可以实现日期通过手上下…...

Mysql 查看表注释或字段注释

查看所有表的注释 SELECT table_name 表名, table_comment 表说明 FROM information_schema.TABLES WHERE table_schema ‘数据库名’ ORDER BY table_name 查询所有表及字段的注释 SELECT a.table_name 表名, a.table_comment 表说明, b.COLUMN_NAME 字段名, b.column_commen…...

MySQL InnoDB引擎

1、逻辑存储结构 2、架构 a. 内存结构 Change Buffer的意义是什么? 与聚集索引不同&#xff0c;二级索引通常是非唯一的&#xff0c;并且以相对随机的顺序插入二级索引。同样&#xff0c;删除和更新可能会影响索引树中不相邻的二级索引页&#xff0c;如果每一次都操作磁盘&am…...

C++完成Query执行sql语句的接口封装和测试

1、在LXMysql.h 创建Query执行函数 //封装 执行sql语句 if sqllen 0 strlen获取字符长度bool Query(const char*sql,unsigned long sqllen0); 2、在LXMysql.cpp编写函数 bool LXMysql::Query(const char* sql, unsigned long sqllen){if (!mysql)//如果mysql没有初始化好{c…...

C:宏:编程风格:井号与define之间的空格

在这一篇中有提到&#xff0c;井号与define之间空格&#xff0c;可能导致搜索上的一些问题。 https://mzhan017.blog.csdn.net/article/details/135289451 今天看到有专门做这个空格的修改&#xff1a; https://sourceware.org/git/?pglibc.git;acommitdiff;hfcf70d4114db9ff…...

django websocket

目录 核心代码 consumers.py from channels.generic.websocket import WebsocketConsumer from channels.exceptions import StopConsumer import datetime import time from asgiref.sync import async_to_sync class ChatConsumer(WebsocketConsumer):def websocket_conne…...

HackTheBox - Medium - Linux - Bagel

Bagel 今天我开始了《Red Team Development and Operations A Practical Guide》的学习&#xff0c;保持学习&#xff0c;后面差不多到时机后就学CRTOⅡ Bagel 是一款中等难度的 Linux 机器&#xff0c;其特点是电子商店容易受到路径遍历攻击&#xff0c;通过该攻击可以获取应…...

Capsolver:解决Web爬虫中CAPTCHA挑战的最优解决方案

Web爬虫已经成为从各种在线来源提取和分析数据的不可或缺的技术。然而&#xff0c;在Web爬取过程中&#xff0c;经常会遇到的一个共同挑战是CAPTCHA。CAPTCHA&#xff08;完全自动化的公共图灵测试&#xff0c;用于区分计算机和人类&#xff09;是一种安全措施&#xff0c;旨在…...

大数据系列之:读取parquet文件统计数据量

大数据系列之&#xff1a;读取parquet文件统计数据量 一、Spark读取parquet文件统计数据量二、parquet-tools统计parquet文件数据量三、实际应用案例 一、Spark读取parquet文件统计数据量 首先&#xff0c;创建一个 SparkSession 对象&#xff1a; val spark SparkSession.b…...

力扣题:字符串变换-1.5

力扣题-1.5 [力扣刷题攻略] Re&#xff1a;从零开始的力扣刷题生活 力扣题1&#xff1a;482. 密钥格式化 解题思想&#xff1a;首先先将破折号去除,并将所有字母转换为大写,然后计算第一组的长度,进行结果字符串的拼接,如果第一组的长度为0,则需要删除开头的’-符号 class S…...

el-autocomplete远程搜索使用及el-upload上传多个文件流给后端,详情接口返回的是文件地址,前端将文件地址转成文件流,回传文件流给后端

最近遇到一个项目,里面有2个需求我觉得挺常见的,第一个需求是一个表单里,当用户在输入名称后,前端调接口发请求获取到关联名称的企业名称,并展示,然后当用户选中企业后,前端调接口获取选中企业的具体信息,并填充到表单里;第二个需求是,表单里有个上传图片的功能,前端…...

2024年度 ROTS - 实时操作系统 Top 15

RTOS&#xff08;实时操作系统&#xff09;。 这里说的 RTOS 并非新星球大战电影中的机器人&#xff0c;而是物联网设备、航空系统、空中交通管制等背后的无声协调者&#xff0c;就在地球上。 RTOS&#xff0c;或称实时操作系统&#xff0c;设计它们是为了更好的管理资源&…...

苹果怎么同步备忘录?教程来了,干货满满!

在苹果设备中&#xff0c;备忘录是一款非常实用的应用程序&#xff0c;可用于记录日常生活中的各种事项。然而&#xff0c;还有一些小伙伴不知道苹果怎么同步备忘录&#xff0c;这可能会成为他们的一个困扰。别着急&#xff01;本文将详细介绍同步苹果手机备忘录的方法&#xf…...

Nginx(十八) 性能调优之 - 哪些层面可以进行优化

Nginx三大优势&#xff0c;动静分离、反向代理、负载均衡 1、线程 worker 2、http/tcp tcp_nopush tcp_nodelay 3、Buffer 调整请求体缓存区大小、将请求体缓存到一个缓冲区&#xff0c;降低CPU负载 4、连接队列 5、超时时间 6、静态文件缓存 open_file_cache 7、gzip压…...

OpenStack云计算(三)neutron

neutron 介绍&#xff1a; Neutron 概述传统的网络管理方式很大程度上依赖于管理员手工配置和维护各种网络硬件设备;而云环境下的网络已经变得非常复杂,特别是在多户场景里,用户随时都可能需要创建、修改和删除网络,网络的连通性和隔离不已经太可能通过手工配置来保证了。 如…...

Linux期末复习笔记

一、管理文件系统 1、文件系统类型 ext2&#xff1a;早期Linux中常用的文件类型。ext3&#xff1a;ext2的升级版&#xff0c;带日志功能。RAMFS&#xff1a;内存文件系统&#xff0c;速度很快。NFS&#xff1a;网络文件系统&#xff0c;由SUM发明&#xff0c;主要用于远程文件…...

PHP实现多继承

php支持多继承吗 不可以,只支持单继承。 可以使用 interface 或 trait 实现 。 实现方法 https://www.php.cn/faq/430197.html https://blog.58heshihu.com/index.php/archives/2288/...

pulsar原来是这样操作topic的

本篇主要讲述pulsar topic部分&#xff0c;主要从设计以及源码的视角进行讲述。在pulsar中&#xff0c;一个Topic的新建、扩容以及删除操作都是由Broker来处理的&#xff0c;而Topic相关的数据是存储在zookeeper上的。本篇文章模拟一个高效的学习流程进行展开 介绍使用方式(To…...

日常工作 经验总结

1,在使用vue2开发项目时,快捷有效的组件化component 若有参数传递时,可以通过这样传递 在component中: 2,上拉加载,下拉刷新 若是使用局部进行上拉加载 下拉刷新 且需要用到scroll-view时 那么需要切记scroll-view在内被mescroll-uni包裹。若场景有限 对于无数据显示…...

【Proteus仿真】【Arduino单片机】水箱液位监控系统

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用Proteus8仿真Arduino单片机控制器&#xff0c;使用LCD1602液晶、按键、蜂鸣器、液位传感器、ADC转换器、水泵等。 主要功能&#xff1a; 系统运行后&#xff0c;LCD1602显示当前水位、上下限阈…...

【已解决】若依系统前端打包后,部署在nginx上,点击菜单错误:@/views/system/role/index

​ 上面错误&#xff0c;是因为/views/system/role/index动态路由按需加载时候&#xff0c;错误导致。 解决办法&#xff1a; 如果您的前端项目访问时候&#xff0c;需要带有项目名称的话&#xff0c;参考凯哥上一篇文章&#xff1a;【已解决】若依前后端分离版本&#xff0…...

Java中compareTo方法使用

compareTo方法 1. compareTo方法参数2. compareTo方法返回值3. String类型使用CompareTo方法进行比较 compareTo 是实例方法&#xff0c;只能对象调用。所以不能比较基本类型 1. compareTo方法参数 public int compareTo(参数类型 值) {... }参数类型可以是一个 Byte, Double…...

【霹雳吧啦】手把手带你入门语义分割の番外11:U2-Net 源码讲解(PyTorch)—— 代码的使用

目录 前言 Preparation 一、U2-Net 网络结构图 二、U2-Net 网络源代码 1、train.py &#xff08;1&#xff09;parse_args 参数 &#xff08;2&#xff09;SODPresetTrain 类 &#xff08;3&#xff09;SODPresetEval 类 &#xff08;4&#xff09;main 函数 &#x…...

威尔仕2023年的统计数据

威尔仕健身房更新了2023年的统计数据&#xff0c;大家可以猜一猜我是哪一个称号&#xff1f;虽然小伙伴们的健身时长各有不同&#xff0c;有时候在课程中我也会分享自己健身的案例&#xff0c;看似一个简单的增强环路&#xff0c;旁边会有很多的调节环路来限制增强环路的增长&a…...

Spring——Spring基于注解的IOC配置

基于注解的IOC配置 学习基于注解的IOC配置&#xff0c;大家脑海里首先得有一个认知&#xff0c;即注解配置和xml配置要实现的功能都是一样的&#xff0c;都是要降低程序间的耦合。只是配置的形式不一样。 1.创建工程 1.1 pom.xml <?xml version"1.0" encoding…...

spring常用注解(一)springbean生命周期类

一、PostConstruct&#xff1a; 被PostConstruct修饰的方法会在服务器加载Servlet的时候运行&#xff0c;并且只会被服务器调用一次&#xff0c;类似于servlet的inti()方法。被PostConstruct修饰的方法会在构造函数之后&#xff0c;init()方法之前运行。...

【软件测试】2024年准备中/高级测试岗技术面试...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 1、软件测试基础知…...

第11课 实现桌面与摄像头叠加

在上一节&#xff0c;我们实现了桌面捕获功能&#xff0c;并成功把桌面图像和麦克风声音发送给对方。在实际应用中&#xff0c;有时候会需要把桌面与摄像头图像叠加在一起发送&#xff0c;这节课我们就来看下如何实现这一功能。 1.备份与修改 备份demo10并修改demo10为demo11…...

SAP 检验批状态修改(QA32质检放行报错:BS002 不允许 “访问使用决定“ (INL 101105415 ))

问题&#xff1a;在做QA32进行使用决策处理的时候发现这个报错&#xff1a; BS002 不允许 "访问使用决定" (INL 101105415 ) 原因&#xff1a;是因为这个检验批的状态已经变成Relase的状态了&#xff0c;但是决策还没有做 解决方案&#xff1a;将这个检验批的REL状态…...

wordpress 调用新浪微博内容/重要新闻今天8条新闻

输入输出定义&#xff1a; 输入&#xff1a;键盘&#xff0c;鼠标和我们用这些硬件在系统录入的字符 输出&#xff1a;系统接受到我们想要得到的功能字符后&#xff0c;经过进程的处理产生字符 输入会有两种出现&#xff0c;编号1为正确输出&#xff0c;编号2位错误输出&#…...

哪类型网站容易做/百度竞价排名利弊

MRAM速度快且非易失性。实时监控的传感器数据可以实时写入&#xff0c;无需负载均衡或ECC开销。AEC-Q1001级合格MRAM将在发动机罩下应用的扩展温度&#xff08;-40℃至125℃&#xff09;内保留数据20年。意外断电不会影响数据完整性。 Everspin的汽车规AEC-Q100MRAM内存可用于…...

郑州的做网站公司有哪些/怎么用手机制作网站

滑动窗口 (TCP流量控制)介绍UDP时我们描述了这样的问题&#xff1a;如果发送端发送的速度较快&#xff0c;接收端接收到数据后处理的速度较慢&#xff0c;而接收缓冲区的大小是固定的&#xff0c;就会丢失数据。TCP协议通过“滑动窗口(Sliding Window)”机制解决这一问题。看下…...

医疗行业网站备案/清远今日头条新闻

摘要 mongo 的索引非常强大&#xff0c;和关系型数据库索引没什么区别。这里主要介绍mongo索引基本知识和mongo本人在索引上的犯的错。 索引种类 单字段索引 复合索引 复合索引各个字段的顺序应该是精确匹配字段(xxx),排序字段(避免在内存中排序&#xff0c;使用index排序)&am…...

影院网站建设/湛江百度网站快速排名

图片上传及路径设置对于在该编辑器中生成的图片为 base64 编码&#xff0c;所生成的字符占据太大空间&#xff0c;可考虑将其上传至服务器中&#xff0c;在该图片设置保存好的文件路径即可&#xff0c;以 php 为例。js 代码// 圖片上傳quill.on(text-change, function(delta, o…...

建设网站的具体步骤是什么/每天看七个广告赚40元的app

寻源到付款&#xff08;S2P&#xff09;是端到端的过程&#xff0c;通过在采购过程中添加战略性采购&#xff0c;S2P向采购到付款&#xff08;P2P&#xff09;迈进了一步。在此过程中&#xff0c;寻找最佳供应商并制定工作的行为与他们的交易会添加到流程中&#xff0c;最终导致…...