代码随想录27天|贪心

455.分发饼干

代码随想录

第一想法

将孩子胃口值g[i] 按从小到达的顺序排列,饼干尺寸也按照从小到大的顺序去排列。

优先将大尺寸喂给大胃口孩子。如果满足不了胃口那么久试着分给下一个孩子。

要尽量满足更多的孩子,那么大尺寸的饼干就不能喂给小胃口的孩子

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

代码

虽然知道倒着分配的基本思路,但是还是非常出错。关键在于遍历孩子作为主体。

遍历孩子还是遍历饼干要在纸上模拟一遍。

class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int count = 0;int start = s.length-1;//目前有这么多饼干for(int index = g.length-1;index>=0;index--){//从胃口最大的孩子开始分发if(start>=0&&g[index]<=s[start]){//如果还有饼干且能满足的话start--;count++;}}return count;}
}

 376.摆动序列

代码随想录

代码随想录

preddiff =  nums[i] - nums[i-1]

curdiff = nums[i+1] - nums[i]

在峰值出现的要保留 即prediff>0&&curdiff<0 || prediff<0&&curdiff>0

上下有平坡只取最右一侧,则 prediff>=0&&curdiff<0  || prediff<=0 &&curdiff >0

首尾元素: 首尾元素不相同算两个摆动,因此直接用i = 0 || i = nums.leng()-1 判断是否为首尾元素直接加摆动是错误的。

        比如数组 [1 2] , 在左边延长 1 即[1 1 2],因此真正的首元素第二个1 可以通过计算prediff 和 curdiff 判断得出,而默认右侧就是有一个摆动序列,即count初始值为1

prediff和curdiff 的计算:当前元素判断完后逻辑上已经移动到下一个元素,那么curdiff就可以赋值给prediff,而prediff初始值为0,但是这样在单调有平坡时会出现问题/

单调坡中有平坡 [1 2 2 2 3 4],摆动为2,prediff不是跟着curdiff实时摆动,而是在摆动出现时只记录坡度的初始方向,也就是prediff = curdiff 写在if逻辑里,那么当碰到 [1 2]段时prediff = 1 ,而后两个 2 时prediff都不会变化。

代码

class Solution {public int wiggleMaxLength(int[] nums) {if(nums.length==1)return 1;int result = 1; //默认最右侧有摆动,初始值为1int prediff = 0;//默认延长首元素int curdiff = 0;for(int i = 0;i<nums.length-1;i++){curdiff = nums[i+1]-nums[i];if((prediff<=0&&curdiff>0)||(prediff>=0&&curdiff<0)){result++;prediff = curdiff;}}return result;}
}

 53.最大子序和

第一想法

从起始开始加,如果比原来更大则接收,并同时记录数组长度,如果一旦变小那么就归零重新计算。想法是找到一个连续子序和大的,那么基于它应该能找到更大的。

但是例如数组 [5,4,-1,7,8] ,需要短暂接收 -1 ,最终最大子序和是所有数值相加 即23.

或者双层for循环,枚举所有的子序和,时间复杂度为 n^2

代码随想录

遍历数组时会累加连续和 ,如果连续和是负数 ,加后面的数只会让后面的数更小,对求值不利。例如 -2 1 ,-2 +1 < 1,那么不如使用1作为新起点。

局部最优:当连续和为负数的时候,立即抛弃它,选择下一个数作为新的起点

全局最优:子序和最大 

贪在哪里

这题贪心的核心就是,以当前的子序和为视角,每次选择时都可能让子序和更大: 当子序和负数时,替换新子序和,因为无论如何加下一个数都不如直接选下一个数成为新子序和大 当子序和正数时,直接加新数字,因为无论如何替换下一个数都不如当前子序和加数字大 很经典地体现了 “贪” 的特点,目标就是要让子序和尽可能大!

——B友 杏吧阿伟 

从编程到哲学

[妙啊]

我我我悟到了一个道理!当我们遇到困难的时候(负数)不要逃避(跳过负数),我们试着去接受它(加入连续和),然后尝试更好地未来;如果遇到了太多的伤心事(连续和变成负数了),那都是些没有办法改变的事情,我们不如卸下包袱(连续和归0),然后奔赴一个新的起点(新的连续和起点)

——B友 猫猫灵机一动时

代码

class Solution {public int maxSubArray(int[] nums) {int result = Integer.MIN_VALUE;//求解最大子序和,先将比较结果初始为最小值int sum = 0;for(int i = 0;i<nums.length;i++){sum +=  nums[i];if(sum>result)result = sum;if(sum<0) sum = 0;//如果当前子序和为负数,立即归零,选择下一个数作为新起点}return result;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/390101.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【多线程】线程状态与并发三大特性的细节剖析

这篇文章主要用于对于多线程的一些查缺补漏。 一、 线程的状态 1&#xff0c;操作系统层面&#xff0c;线程的5种状态 关于线程有几种状态&#xff0c;有多种说法&#xff0c;5、6、7都有。 首先对于操作系统来说&#xff0c;只有5种状态&#xff0c;状态如下新建&#xff…

浅谈KMP算法(c++)

目录 前缀函数应用【模板】KMP题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示样例 1 解释数据规模与约定 思路AC代码 本质不同子串数 例题讲解[NOI2014] 动物园题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示思路AC代码 [POI2006] OKR-Periods of …

智慧水务项目(一)django(drf)+angular 18 通过pycharm建立项目

一、环境准备 windows 10 pycharm python3.11 二、pycharm 创建django项目 三、建立requirements.txt 在根目录创建requirements.txt,也就是与manage.py同一目录下&#xff0c;先放下面几个依赖 Django djangorestframeworkpip install -r .\requirements.txt 更新下pip python…

ShardingSphere实战(1)- 分库分表基础知识

一、为什么要分库分表 分库分表是一种数据库优化策略&#xff0c;主要用于解决大型应用或高并发场景下数据库性能瓶颈的问题。具体来说&#xff0c;分库分表可以带来以下好处&#xff1a; 提高性能&#xff1a; 减少单个数据库实例的负载&#xff0c;避免单点性能瓶颈。当数据…

【香橙派系列教程】(五)Linux的热拔插UDEV机制

【五】Linux的热拔插UDEV机制 在上一篇中我们发现&#xff0c;当手机接入开发板时&#xff0c;系统并不认识&#xff0c;当我们在/etc/udev目录下创建一个规则后&#xff0c;就可以通过adb访问到手机了&#xff0c;这里到底是怎么回事&#xff1f; 文章目录 【五】Linux的热拔插…

武汉流星汇聚:亚马逊平台消费者众多,助力中国卖家销售额大幅增长

在全球电商的浩瀚星空中&#xff0c;亚马逊凭借其庞大的消费者规模和强大的市场影响力&#xff0c;为无数商家特别是中国卖家提供了前所未有的发展机遇。近年来&#xff0c;越来越多的中国卖家选择通过亚马逊平台&#xff0c;将优质产品直接送达全球消费者的手中&#xff0c;并…

精选3款国内wordpress 主题,建站首选

WordPress作为一款功能强大且易于使用的建站平台&#xff0c;已经成为了许多企业和个人搭建网站的首选。为了帮助大家更好地选择适合自己的WordPress主题&#xff0c;小编将为大家推荐三款国内优秀的WordPress主题&#xff1a;子比主题、OneNav主题和RiTheme主题。 1.子比主题…

JavaScript ES6语法详解(下)

前言&#xff1a;哈喽&#xff0c;大家好&#xff0c;我是码喽的自我修养&#xff01;今天给大家分享JavaScript ES6语法详解(下)&#xff01;并提供具体代码帮助大家深入理解&#xff0c;彻底掌握&#xff01;创作不易&#xff0c;如果能帮助到带大家&#xff0c;欢迎收藏关注…

Qt Creator 与 ESP-IDF QEMU 模拟器使用指南

标题: Qt Creator 与 ESP-IDF QEMU 模拟器使用指南 概要: 本文为开发者提供了使用 Qt Creator 和 ESP-IDF QEMU 模拟器进行 ESP32 开发的详细指南&#xff0c;包括环境准备、项目创建和编译、模拟器设置、编程和调试等方面的内容。通过本指南&#xff0c;可以快速上手 Qt Crea…

Learning vtkjs之Calculator

过滤器 公式计算器 Calculator 介绍 The Calculator filter is a fast way to add derived data arrays to a dataset. These arrays can be defined over points, cells, or just field data that is “uniform” across the dataset (i.e., constant over all of space). Va…

手把手教你实现日期类

目录 前言 1.头文件的实现 2.日期类函数各项功能实现 2.1 初始化和打印&#xff08;比较简单&#xff09; 2.2日期大小判断 2.3日期的加减运算 3.日期类的输入输出 4.测试代码参考 结束语 前言 前面我们讲解了类的对象的大部分知识&#xff0c;例如拷贝构造&#xff0c…

优化数据处理效率,解读 EasyMR 大数据组件升级

EasyMR 作为袋鼠云基于云原生技术和 Hadoop、Hive、Spark、Flink、Hbase、Presto 等开源大数据组件构建的弹性计算引擎。此前&#xff0c;我们已就其展开了多方位、多角度的详尽介绍。而此次&#xff0c;我们成功接入了大数据组件的升级和回滚功能&#xff0c;能够借助 EasyMR …

乐乐音乐Kotlin版

简介 乐乐音乐Kotlin版&#xff0c;主要是基于ExoPlayer框架开发的Android音乐播放器&#xff0c;它支持lrc歌词和动感歌词(ksc歌词、krc歌词、trc歌词、zrce歌词和hrc歌词等)、多种格式歌词转换器及制作动感歌词、翻译歌词和音译歌词。 编译环境 Android Studio Jellyfish | …

canvas-视频绘制

通过Canvas元素来实时绘制一个视频帧&#xff0c;并在视频帧上叠加一个图片的功能可以当作水印。 获取Canvas元素&#xff1a; let canvas document.getElementById(canvas) 通过getElementById函数获取页面中ID为canvas的Canvas元素&#xff0c;并将其存储在变量canvas中。 …

【C++】C++11(可变参数模板、lambda表达式、包装器)

文章目录 1. 可变参数模板1.1 介绍1.2 emplace系列接口实现 2. lambda表达式2.1 语法介绍2.2 原理 3. 包装器4. bind 1. 可变参数模板 1.1 介绍 可变参数我们在C语言阶段已经了解过了&#xff0c;C语言中叫做可变参数列表&#xff0c;其中使用 ... 代表可变参数。 C语言中的可…

【给嵌入式新人的几条建议(共勉):三-C语言基础怎么补?】

给嵌入式新人的几条建议&#xff08;共勉&#xff09;&#xff1a;三-C语言基础怎么补&#xff1f; 前言1、先回答一个问题&#xff0c;对C语言的害怕到底在哪&#xff1f;&#xff08;纠正认知&#xff09;2、C语言基础&#xff0c;要补全部吗&#xff1f;No2.1 先看下自己属于…

企业个人信息安全保护实践

在数字化浪潮的推动下&#xff0c;个人信息安全问题日益凸显&#xff0c;企业如何在合规的框架下保护个人信息安全&#xff0c;成为了一项重要课题。结合国家标准的个人信息合规审计要求&#xff0c;以下为企业个人信息安全保护的最佳实践路径。 一、构建合规的个人信息保护体…

【文件解析漏洞】

使用windows2003sever服务器 第一个&#xff1a;目录解析 1、打开网站目录&#xff0c;右键打开资源管理器 新建一个1.asp文件 在1.asp目录下新建一个2.txt&#xff0c;输入asp的语句 2、使用本机访问windows2003的IP地址 访问http://192.168.189.155/1.asp/2.txt即可 第…

论文翻译:Large Language Models in Education: Vision and Opportunities

Large Language Models in Education: Vision and Opportunities 文章目录 教育中的大型语言模型&#xff1a;愿景与机遇摘要1 引言2. 教育与LLMsA. 教育背景B. LLMs背景C. 智能教育D. 教育中的LLMs 3. EduLLMs的关键技术4. LLM赋能教育A. LLMs在教育中的应用B. LLMs下教育的特…

Netty4自学笔记 (3) - Netty NIO Server和Client 样例说明

全文详见个人独立博客&#xff1a;Netty4自学笔记 (3) - Netty NIO Server和Client 样例说明 Netty4自学笔记 (3) - Netty NIO Server和Client 样例说明更新节奏缓慢&#xff0c;因为每晚学习注意力不够集中&#xff0c;学习进展缓慢。本还给自己找了一大堆其他理由&#xff0…