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

代码随想录 Day26 贪心 01 全集 LeetCode455 分发饼干 LeetCodeT346摆动序列 LeetCdoe T53 最大子数组和

 前言:贪心无套路

本质:

局部最优去推导全局最优

两个极端

贪心算法的难度一般要么特别简单,要么特别困难,所以我们只能多见识多做题,记住无需数学证明,因为两道贪心基本上毫无关系,我们只需要去思考局部最优即可

 贪心的小例子

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

那肯定是每次拿最大的就行,局部最优就是每次拿最大数额的钞票,全局最优就是最后数额的总和是最大的.

贪心无套路!!!

这里贪心没有任何的模板总结,因为解决不同问题的贪心策略是完全不同的,我们不需要严格的数学证明,如果面对一道题你有这么一种贪心的策略,同时你找不到任何明显的反例,那么就可以照着这个思路来思考问题... 

LeetCode T455 分发饼干

题目链接:455. 分发饼干 - 力扣(LeetCode)

题目思路:

这题我们有两种思路可以解决问题

1.优先考虑胃口:大饼干喂饱大胃口

这里的局部最优就是充分利用大饼干来喂饱小孩,全局最优就是喂饱尽可能多的小孩

(尽可能让吃饱的人多)

2.优先考虑饼干:小饼干先喂饱小胃口

这里的局部最优是花费掉最小的饼干,让小饼干物尽其用,全局最优是使饼干的花费更有性价比.

(尽可能让饼干发挥最大的效果)

题目代码

//解法一:
class Solution {int count = 0;int start = 0;public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);for(int i = 0;i<s.length && start<g.length;i++){if(s[i]>=g[start]){start++;count++;}}return count;}
}//解法2
class Solution {int count = 0;int start ;public int findContentChildren(int[] g, int[] s) {start = s.length-1;Arrays.sort(g);Arrays.sort(s);for(int i = g.length-1;i>=0;i--){if(start >= 0 && s[start]>=g[i]){start--;count++;}}return count;}
}

 LeetCode T376 摆动序列

题目链接:376. 摆动序列 - 力扣(LeetCode)

前言 

 这题我们看到可以删除数组中的元素也可以不删除可能就吓到了,其实是这道题可以用动态规划或者贪心的策略去解决问题,这里我们还是用贪心的解法去解决问题,具体动态规划的思路可以参照网站:代码随想录 (programmercarl.com)

摆动数列的定义 

做这题之前我们得明白什么是摆动序列,举个例子[2,6,1,9,3]这个数组,呈现一个波动变化的形态,就称为摆动序列

如果序列只有两个元素,这里就认为摆动序列的长度为2,默认有两个摆动

题目思路:

这题我们首先要考虑情况,我列出以下三种情况:

1.首末元素

2.上下有平坡

3.单调有平坡

变量定义

curDiff:记录当前差值        假设目前遍历到的元素为i  ,curDiff = nums[i+1] - nums[i]

preDiff:记录之前的差值                              preDiff = nums[i] - nums[i-1]

count 记录结果,为了满足默认首尾元素的情况,我们默认count从1开始取值

我们只需要遍历一次数组,满足前后diff不同号即可

注意不能写成curDiff>=0这种情况,因为这样就表示从高或者低值到平坡,是不增加波动的

最后每次结束让pre更新为cur就可以了

这是一个错误的思路,我们是只有遇到了坡度变化才会让pre更新

for(int i = 0;i<nums.length-1;i++){curDiff = nums[i+1] - nums[i];if((curDiff>0 && preDiff<=0 ) || (curDiff<0 && preDiff>=0)){count++;preDiff = curDiff;}}

代码模板:

class Solution {public int wiggleMaxLength(int[] nums) {if(nums.length<=1){return nums.length;}int preDiff = 0;int count = 1;int curDiff = 0;for(int i = 0;i<nums.length-1;i++){curDiff = nums[i+1] - nums[i];if((curDiff>0 && preDiff<=0 ) || (curDiff<0 && preDiff>=0)){count++;preDiff = curDiff;}}return count;}
}

 LeetCode T53 最大子数组和

题目链接:53. 最大子数组和 - 力扣(LeetCode)

 

题目思路:

贪心贪的是哪里呢?

如果 -2 1 在一起,计算起点的时候,一定是从 1 开始计算,因为负数只会拉低总和,这就是贪心贪的地方!

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

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

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

从代码角度上来讲:遍历 nums,从头开始用 count 累积,如果 count 一旦加上 nums[i]变为负数,那么就应该从 nums[i+1]开始从 0 累积 count 了,因为已经变为负数的 count,只会拖累总和。

这相当于是暴力解法中的不断调整最大子序和区间的起始位置

定义变量:

count:记录局部和

sum:记录目前出现的最大和

思路:一层for循环遍历数组,每次遇到连续子数组之和为负数的时候,就从下一个元素继续开始叠加,每次叠加一个元素对sum进行一次更新.

题目代码:

class Solution {public int maxSubArray(int[] nums) {int count = 0;//目前值int sum = Integer.MIN_VALUE;//目前出现的最大值for(int i = 0;i<nums.length;i++){count+=nums[i];sum = Math.max(count,sum);if(count < 0){count = 0;}}return sum;}
}

相关文章:

代码随想录 Day26 贪心 01 全集 LeetCode455 分发饼干 LeetCodeT346摆动序列 LeetCdoe T53 最大子数组和

前言:贪心无套路 本质: 局部最优去推导全局最优 两个极端 贪心算法的难度一般要么特别简单,要么特别困难,所以我们只能多见识多做题,记住无需数学证明,因为两道贪心基本上毫无关系,我们只需要去思考局部最优即可 贪心的小例子 比如有一堆钞票&#xff0c;你可以拿走十张&#x…...

【前端vue面试】TypeScript

目录 快速入门0、TypeScript简介1、TypeScript 开发环境搭建2、基本类型3、编译选项4、webpack5、Babel面向对象1、类(class)2、面向对象的特点3、接口(Interface)4、泛型(Generic)快速入门 0、TypeScript简介 TypeScript是JavaScript的超集。它对JS进行了扩展,向JS中引…...

vue-next-admin框架的认识

最近利用这个框架二开了一个后台管理系统&#xff0c;这里简单介绍一下&#xff0c;后续会进行框架的修改等文章 1&#xff1a;介绍 Vue-next-admin是一个基于Vue3和Element-Plus的后台管理系统框架。它提供了一套完整的、易于扩展的后台管理界面解决方案&#xff0c;可用于快…...

【2024秋招】2023-9-14 最右线下后端开发二面

1 OS 1.1 讲讲什么是虚拟内存&#xff0c;怎么实现的 虚拟内存是一种存储器管理能力&#xff0c;它使得一个应用程序似乎有更多的物理内存&#xff08;RAM&#xff09;可用&#xff0c;而实际上&#xff0c;系统使用了一部分硬盘空间来模拟额外的 RAM。通过使用虚拟内存&…...

LeetCode 2678. 老人的数目

【LetMeFly】2678.老人的数目 力扣题目链接&#xff1a;https://leetcode.cn/problems/number-of-senior-citizens/ 给你一个下标从 0 开始的字符串 details 。details 中每个元素都是一位乘客的信息&#xff0c;信息用长度为 15 的字符串表示&#xff0c;表示方式如下&#…...

java--三元运算符、运算符的优先级

1.三元运算符介绍 1.格式&#xff1a;条件表达式&#xff1f;值1&#xff1a;值2&#xff1b; 2.执行流程&#xff1a;首先计算关系表达式的值&#xff0c;如果值为true&#xff0c;返回值1&#xff0c;如果为false&#xff0c;返回值2 2.运算符优先级 1.在表达式中&#xf…...

在推荐系统中,BPRloss、Embloss、CrossEntropyloss是怎么计算的,代表的意义是什么

一、BPRloss&#xff08;Bayesian Personalized Ranking loss&#xff09;是一种用于推荐系统中的损失函数&#xff0c;用于衡量预测的排序与真实的用户行为排序之间的差异。BPRloss的计算过程如下&#xff1a; 输入&#xff1a;BPRloss的输入包括用户u、物品i和物品j&#xff…...

【Python语言速回顾】——异常文件操作

目录 一、异常 1、检测异常try语句 2、抛出异常 3、异常处理流程 二、文件操作 1、打开文件 ①文件模式acess_mode ②文件缓冲区 2、基本的文件方法 ①读和写、关闭文件 ②读取行 ③文件重命名 ④删除文件&#xff08;系统中已存在的文件&#xff09; 3、基本的目…...

SAP POorPI RFC接口字段调整后需要的操作-针对SP24及以后的PO系统

文章目录 问题描述解决办法 问题描述 在SAP系统的RFC接口结构中添加了字段&#xff0c;RFC也重新引用到了PO系统&#xff0c;Cache和CommunicationChannel都刷新或启停了&#xff0c;但是新增的字段在调用接口的时候数据进不到SAP系统&#xff0c;SAP系统内的值也出不来。经过…...

【ArcGIS模型构建器】03:多个shp批量按属性分割(多个县区批量提取乡镇)

文章目录 一、数据预览二、模型构建三、保存模型一、数据预览 加载实验数据: 本试验实现将两个县区的数据分割为乡镇数据。 二、模型构建 1. 添加数据文件夹 将县区数据所在的根目录文件夹拖进模型。 2. 添加要素类迭代器 插入→迭代器→要素类。 用连接工具,将数据文件…...

JavaScript中JSON和Bom对象模型

JSON JSON是一种轻量级的数据交换格式 简洁和清晰的层次结构使得JSON成为理想的数据交换语言 易于人们解析和生成&#xff0c;并有效的提升网络传输效率 javaScript一切皆为对象&#xff0c;任何js支持的对象都可以使用JSON来表示 格式&#xff1a; 对象都用[] 数组都用{}…...

Ubuntu下载、安装QGIS软件的方法

本文介绍在Linux操作系统Ubuntu版本中&#xff0c;通过命令行的方式&#xff0c;配置QGIS软件的方法。 在Ubuntu等Linux系统中&#xff0c;可以对空间信息加以可视化的遥感、GIS软件很少&#xff0c;比如ArcGIS下属的ArcMap就没有对应的Linux版本&#xff08;虽然有ArcGIS Serv…...

spring sharding JDBC 动态调整数据库连接

spring sharding JDBC 动态调整数据库连接 通过重写ShardingSphereDataSource类来实现 代码 package org.apache.shardingsphere.driver.jdbc.core.datasource;import com.alibaba.druid.pool.DruidDataSource; import lombok.extern.slf4j.Slf4j; import org.apache.shardi…...

解决CondaHTTPError HTTP 000 CONNECTION FAILED for url解决方法

解决CondaHTTPError: HTTP 000 CONNECTION FAILED for url解决方法 问题&#xff1a;使用conda install命令安装包提示CondaHTTPError: HTTP 000 CONNECTION FAILED for url 分析&#xff1a;网络连接问题&#xff0c;大概率是网速不行或者源没有换 解决方案&#xff1a;修改国…...

10 创建型模式-原型模式

引言&#xff1a; 创建对象的五种方式&#xff1a; 通过new关键字通过Class类的newInstance()方法通过Constructor类的newInstance()方法利用Clone方法反序列化 Clone方法&#xff1a; 其实现方式正是通过调用 Object 类的 clone() 方法来完成。 protected native Object cl…...

MSQL系列(七) Mysql实战-SQL语句Join,exists,in的区别

Mysql实战-SQL语句Join&#xff0c;exists&#xff0c;in的区别 前面我们讲解了索引的存储结构&#xff0c;BTree的索引结构&#xff0c;以及索引最左侧匹配原则及讲解一下常用的SQL语句的优化建议&#xff0c;今天我们来详细讲解一下 我们经常使用的 join&#xff0c; exist&…...

最新壁纸自动采集系统网站PHP源码/360壁纸官方数据接口采集/ZHEYI采集源码

源码介绍&#xff1a; 最新壁纸自动采集系统网站PHP源码&#xff0c;它是ZHEYI自动采集源码&#xff0c;能够在360壁纸官方数据接口采集。很好用的壁纸网站源码分享&#xff0c;仅供学习&#xff0c;请勿商用。 ZHEYI自动采集壁纸PHP源码&#xff0c;能全自动采集高清壁纸网源…...

Redis在分布式场景下的应用

分布式缓存 缓存的基本作用是在高并发场景下对应服务的保护缓冲 – 基于Redis集群解决单机Redis存在的问题 单机的Redis存在四大问题&#xff1a; redis由于高强度性能采用内存 但是意味着丢失的风险单结点redis并发能力有限分布式服务中数据过多 依赖内存的redis 明显单机不…...

2316. 统计无向图中无法互相到达点对数

2316. 统计无向图中无法互相到达点对数 难度: 中等 来源: 每日一题 2023.10.21 给你一个整数 n &#xff0c;表示一张 无向图 中有 n 个节点&#xff0c;编号为 0 到 n - 1 。同时给你一个二维整数数组 edges &#xff0c;其中 edges[i] [ai, bi] 表示节点 ai 和 bi 之间…...

Selenium定向爬取海量精美图片及搜索引擎杂谈

我自认为这是自己写过博客中一篇比较优秀的文章,同时也是在深夜凌晨2点满怀着激情和愉悦之心完成的。首先通过这篇文章,你能学到以下几点: 1.可以了解Python简单爬取图片的一些思路和方法 2.学习Selenium自动、测试分析动态网页和正则表达式的区别和共同点 …...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...