代码随想录算法训练营 || 贪心算法 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贪心算法基础贪心的本质是选择每一阶段的局部最优,从而达到全局最优。刷题或者面试的时候,手动模拟一下感觉可以局部最优推出整体最优,而且想不到反例,那么就试一试贪心。做题的时候,只要想清楚 局部最优 是什么&…...
PMP考前冲刺2.25 | 2023新征程,一举拿证
题目1-2:1.项目经理正在进行挣值分析,计算出了当前的成本偏差和进度偏差。发起人想要知道基于当前的绩效水平,完成所有工作所需的成本。项目经理应该提供以下哪一项数据?A.完工预算(BAC)B.完工估算(EAC)C.完工尚需估算(ETC)D.完工偏差(VAC)2…...
【自然语言处理】Topic Coherence You Need to Know(主题连贯度详解)
Topic Coherence You Need to Know皮皮,京哥皮皮,京哥皮皮,京哥CommunicationUniversityofChinaCommunication\ University\ of\ ChinaCommunication University of China 在大多数关于主题建模的文章中,常用主题连贯度ÿ…...
C++入门:模板
模板是泛型编程的基础,泛型编程即以一种独立于任何特定类型的方式编写代码。模板是创建泛型类或函数的蓝图或公式。库容器,比如迭代器和算法,都是泛型编程的例子,它们都使用了模板的概念。每个容器都有一个单一的定义,…...
【MySQL】索引常见面试题
文章目录索引常见面试题什么是索引索引的分类什么时候需要 / 不需要创建索引?有什么优化索引的方法?从数据页的角度看B 树InnoDB是如何存储数据的?B 树是如何进行查询的?为什么MySQL采用B 树作为索引?怎样的索引的数…...
【Web逆向】万方数据平台正文的逆向分析(上篇--加密发送请求)—— 逆向protobuf
【Web逆向】万方数据平台正文的逆向分析(上篇--加密发送请求)—— 逆向protobuf声明一、了解protobuf协议:二、前期准备:二、目标网站:三、开始分析:我们一句句分析:先for循环部分:后…...
Amazon S3 服务15岁生日快乐!
2021年3月14日,作为第一个发布的服务,Amazon S3 服务15周岁啦!在中国文化里,15岁是个临界点,是从“舞勺之年”到“舞象之年”的过渡。相信对于 Amazon S3 和其他的云服务15周岁也将是其迎接更加美好未来的全新起点。亚…...
【python】函数详解
注:最后有面试挑战,看看自己掌握了吗 文章目录基本函数-function模块的引用模块搜索路径不定长参数参数传递传递元组传递字典缺陷,容易改了原始数据,可以用copy()方法避免变量作用域全局变量闭包closurenonlocal 用了这个声明闭包…...
AoP-@Aspect注解处理源码解析
对主类使用EnableAspectJAutoProxy注解后会导入组件, Import(AspectJAutoProxyRegistrar.class) public interface EnableAspectJAutoProxy {AspectJAutoProxyRegistrar类实现了ImportBeanDefinitionRegistrar接口中的registerBeanDefinitions()方法,此…...
宝塔搭建实战php悟空CRM前后端分离源码-vue前端篇(二)
大家好啊,我是测评君,欢迎来到web测评。 上一期给大家分享了悟空CRM server端在宝塔部署的方式,但是由于前端是用vue开发的,如果要额外开发新的功能,就需要在本地运行、修改、打包重新发布到宝塔才能实现功能更新&…...
FastASR+FFmpeg(音视频开发+语音识别)
想要更好的做一件事情,不仅仅需要知道如何使用,还应该知道一些基础的概念。 一、音视频处理基本梳理 1.多媒体文件的理解 1.1 结构分析 多媒体文件本质上可以理解为一个容器 容器里有很多流 每种流是由不同编码器编码的 在众多包中包含着多个帧(帧在音视…...
二分查找的实现代码JAVA
二分查找一、思路二、实现代码(普通版)三、整数溢出问题四、改进代码一、思路 1.前提: 有已排序数组A (假设已经做好) 2.定义左边界L、 右边界R,确定搜索范围,循环执行二分查找(3、4两步) 3.获取中间索引 M Floor((LR) 1/2) 4.中间素索引的值…...
cesium: 设置skybox透明并添加背景图 ( 003 )
第003个 点击查看专栏目录 本示例的目的是介绍如何在vue+cesium中设置skybox透明并添加背景图。 我们不想要黑乎乎的背景,想自定义一个背景图,然后前面显示地球。 直接复制下面的 vue+cesium源代码,操作2分钟即可运行实现效果. 文章目录 示例效果配置方式示例源代码(共70…...
【python】类的详解
注:最后有面试挑战,看看自己掌握了吗 文章目录PO verses OOPOOO当一个类很复杂的时候,考虑多弄一个类的改造私有类的模块化静态类verses动态类动态类查看模块源代码对象机制的基石 PyObjectPO verses OO PO PO耦合性高,很多过程…...
西安银行就业总结
引 进银行性价比最高的时刻是本科,研究生的话可以去需要研究生较多的银行,比如邮储或者证券类的中信建投。中信建投很香,要求本硕西电。研究生学历的话,一般情况下银行不会卡本科,只看最高学历,部分银行需…...
JavaScript Window
文章目录JavaScript Window浏览器对象模型 (BOM)Window 对象Window 尺寸其他 Window 方法JavaScript Window 浏览器对象模型 (BOM) 使 JavaScript 有能力与浏览器"对话"。 浏览器对象模型 (BOM) 浏览器对象模型(Browser Object Model (BOM))…...
那些开发过程中需要遵守的开发规范
入职公司三天,没干啥其他活,基本在配置本地环境和阅读相关文档。技术方面公司基本用的是主流的技术体系,入职后需要先阅读阿里的开发规范和其他的一些产研文档。今天整理一些平时需要关注的阿里规约和数据库开发规范,方便今后在开…...
EFCore 基础入门教程
一、EFCore 基础入门教程EF 框架的简介、发展历史;ORM框架概念学习地址:https://blog.csdn.net/u011127019/article/details/129212786?spm1001.2014.3001.5502EFCore 安装,引入、支持的数据库学习地址:https://www.cnblogs.com/…...
HTML5 Drag and Drop
这是2个组合事件 dom对象分源对象和目标对象 绑定的事件也是分别区分源对象和目标对象 事件绑定 事件顺序 被拖拽元素,事件触发顺序是 dragstart->drag->dragend; 对于目标元素,事件触发的顺序是 dragenter->dragover->drop/…...
惠普m1136打印机驱动程序安装教程
惠普m113打印机是一款功能强大的多功能打印机,它能够打印、复印、扫描和传真等。如果你要使用这款打印机,你需要下载并安装驱动程序,以确保它能够在你的计算机上正常工作。在本文中,我们将介绍如何下载和安装惠普m1136打印机驱动程…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...
MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释
以Module Federation 插件详为例,Webpack.config.js它可能的配置和含义如下: 前言 Module Federation 的Webpack.config.js核心配置包括: name filename(定义应用标识) remotes(引用远程模块࿰…...
QT开发技术【ffmpeg + QAudioOutput】音乐播放器
一、 介绍 使用ffmpeg 4.2.2 在数字化浪潮席卷全球的当下,音视频内容犹如璀璨繁星,点亮了人们的生活与工作。从短视频平台上令人捧腹的搞笑视频,到在线课堂中知识渊博的专家授课,再到影视平台上扣人心弦的高清大片,音…...
Linux-进程间的通信
1、IPC: Inter Process Communication(进程间通信): 由于每个进程在操作系统中有独立的地址空间,它们不能像线程那样直接访问彼此的内存,所以必须通过某种方式进行通信。 常见的 IPC 方式包括&#…...
