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

day31 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和

● 455.分发饼干
● 376. 摆动序列
● 53. 最大子序和

在本次的题目中,我们使用了贪心算法来解决三个问题:分发饼干、摆动序列、最大子序和。这三个问题都可以使用贪心算法来解决,而且贪心算法的时间复杂度相对较低,能够在较短的时间内得出解决方案。

  1. 分发饼干

题目描述:有一群孩子和一些饼干,每个孩子有一个贪心因子g,每个饼干有一个大小s。只有当一个孩子的贪心因子小于等于饼干的大小时,这个孩子才能获得这个饼干。求最多能满足多少个孩子。

贪心思路:首先将孩子的贪心因子g和饼干的大小s从小到大排序,然后从贪心因子最小的孩子开始,依次判断每个孩子是否能够获得一块饼干。如果可以获得,则将饼干的大小s++,继续判断下一个孩子是否能够获得饼干。如果不能获得,则继续寻找下一个大小更大的饼干,直到找到一个能够满足当前孩子的饼干或者没有更大的饼干为止。

Java代码如下:

public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int i = 0, j = 0;int count = 0;while (i < g.length && j < s.length) {if (g[i] <= s[j]) {count++;i++;j++;} else {j++;}}return count;
}
  1. 摆动序列

题目描述:给定一个整数序列,你的任务是找到其中最长的摆动子序列的长度。摆动序列的定义:如果连续元素之间的差的正负性交替出现,则称这样的序列为摆动序列。

贪心思路:从序列的第一个数开始,判断当前数与下一个数之间的差的正负性。如果这两个数之间的差为正,则说明下一个数应该比当前数大;如果这两个数之间的差为负,则说明下一个数应该比当前数小。如果这两个数之间的差为0,则说明这两个数相等,直接跳过。通过这样的方式,每次找到一个摆动序列的峰值或者谷值,最终就能得到最长的摆动子序列的长度。

Java代码如下:

public int wiggleMaxLength(int[] nums) {if (nums.length < 2) {return nums.length;}int preDiff = 0;int curDiff = 0;int count = 1;for (int i = 1; i < nums.length; i++) {curDiff = nums[i] - nums[i - 1];if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {count++;preDiff = curDiff;}}return count;
}
  1. 最大子序和

题目描述:给定一个整数序列,找到一个具有最大和的连续子序列(至少包含一个数)。

贪心思路:从序列的第一个数开始,依次将每个数加到当前的子序列中,并记录当前子序列的最大值和当前子序列的和。如果当前子序列的和小于0,则说明当前子序列已经不可能是最大的连续子序列了,需要重新开始寻找从下一个数开始的子序列。通过这样的方式,每次找到一个最大的连续子序列的和,最终就能得到整个序列中的最大子序和。

Java代码如下:

public int maxSubArray(int[] nums) {int maxSum = nums[0];int curSum = 0;for (int i = 0; i < nums.length; i++) {curSum += nums[i];if (curSum > maxSum) {maxSum = curSum;}if (curSum < 0) {curSum = 0;}}return maxSum;
}

贪心算法理论知识总结

贪心算法是一种解决最优化问题的算法,它是一种启发式算法,通过每一步的最优选择来达到整体的最优解。贪心算法的具体实现方法就是在每一步选择中都采取当前状态下最优的选择,从而希望得到全局最优解。

贪心算法的时间复杂度通常比较低,因为它每次只考虑当前状态下的最优解,不需要考虑全局的情况。但是,贪心算法并不能保证得到全局最优解,因为它每次都只考虑局部最优解,可能会导致整体上的局部最优解并不是全局最优解。

因此,在使用贪心算法时,需要确定一个贪心策略,即确定每一步的最优选择,以保证最终得到的解是全局最优解。同时,需要证明所采用的贪心策略是正确的,即证明每一步的最优选择可以推导出全局最优解。

相关文章:

day31 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和

● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和 在本次的题目中&#xff0c;我们使用了贪心算法来解决三个问题&#xff1a;分发饼干、摆动序列、最大子序和。这三个问题都可以使用贪心算法来解决&#xff0c;而且贪心算法的时间复杂度相对较低&#xff0c;能够在较短的…...

MobTech 秒验|本机号码一键登录会泄露隐私吗

本机号码一键登录是一种新型的应用登录方式&#xff0c;它可以利用运营商的数据网关认证能力&#xff0c;实现手机号免密登录&#xff0c;提高用户体验和转化率&#xff0c;降低验证成本和流失率。本机号码一键登录支持三大运营商号码认证&#xff0c;3秒内完成手机号验证&…...

2023年供销合作社研究报告

第一章 行业概况 1.1 供销合作社概述 中华全国供销合作总社&#xff0c;是中华人民共和国全国供销合作社的联合组织。中华全国供销合作总社的前身可以追溯到1949年11月成立的中央合作事业管理局。在新中国成立初期&#xff0c;供销合作社就基本形成了自上而下、覆盖全国的组织…...

【ansible】实施任务控制

目录 实施任务控制 一&#xff0c;循环&#xff08;迭代&#xff09;--- loop 1&#xff0c;利用loop----item循环迭代任务 2&#xff0c;item---loop循环案例 1&#xff0c;定义item循环列表 2&#xff0c;通过变量应用列表格式 3&#xff0c;字典列表&#xff08;迭代嵌套子…...

49天精通Java,第11天,java接口和抽象类的异同,default关键字

目录一、什么是接口二、接口的特点三、接口和类的区别四、接口和抽象类的区别五、接口的声明方式六、default默认方法大家好&#xff0c;我是哪吒。 一、什么是接口 Java接口是一系列方法的声明&#xff0c;是一些方法特征的集合&#xff0c;一个接口只有方法的特征没有方法的…...

JAVA练习99-逆波兰表达式求值

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 前言 一、题目-逆波兰表达式求值 1.题目描述 2.思路与代码 2.1 思路 2.2 代码 总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 4月5…...

恶意软件、恶意软件反杀技术以及反病毒技术的详细介绍

1.恶意软件简单介绍恶意软件是指在计算机系统上执行恶意任务的病毒、蠕虫和特洛伊木马的程序&#xff0c;通过破坏软件进程来实施控制。腾讯移动安全实验室发布的数据显示&#xff0c;恶意软件由多种威胁组成&#xff0c;会不断弹出&#xff0c;所以需要采取多种方法和技术来进…...

【数据库运维】mysql备份恢复练习

目录 数据库备份&#xff0c;数据库为school&#xff0c;素材如下 1.创建student和score表 2.为student表和score表增加记录 3.备份数据库school到/backup目录 4.备份MySQL数据库为带删除表的格式&#xff0c;能够让该备份覆盖已有数据库而不需要手动删除原有数据库 5.直接将My…...

刷题30-对称的二叉树

对称的二叉树 思路&#xff1a;用递归&#xff0c;首先明白递归中止的条件是什么 搬用别人的看法&#xff1a; 做递归思考三步&#xff1a; 1.递归的函数要干什么&#xff1f; 函数的作用是判断传入的两个树是否镜像。 输入&#xff1a;TreeNode left, TreeNode right 输出…...

精选简历模板

1.应届生通用简历模板&#xff08;.docx) 适用于应届生找工作的学生群体 https://download.csdn.net/download/weixin_43042683/87652099https://download.csdn.net/download/weixin_43042683/87652099 部分缩略图如下&#xff1a; 2.研究生通用简历模板&#xff08;.docx)…...

蓝桥杯嵌入式第十三届客观题解析

文章目录 前言一、题目1二、题目2三、题目3四、题目4五、题目5六、题目6七、题目7八、题目8九、题目9十、题目10总结前言 本篇文章将带大家来学习蓝桥杯嵌入式的客观题了,蓝桥杯嵌入式的客观题涉及到模电,数电,单片机等知识,需要非常扎实的基础,客观题不能急于求成只能脚…...

【Redis】线程问题

文章目录单线程版本演化工作流程为什么逐渐又加入了多线程特性?影响Redis性能的主要因素->网络I/O多线程工作流程Unix网络编程中的五种I/O模型I/O多路复用工作原理&#xff1a;select、poll、epoll为什么Redis快单线程与多线程的比较配置文件开启多线程单线程 版本演化 Re…...

【算法题】2498. 青蛙过河 II

题目&#xff1a; 给你一个下标从 0 开始的整数数组 stones &#xff0c;数组中的元素 严格递增 &#xff0c;表示一条河中石头的位置。 一只青蛙一开始在第一块石头上&#xff0c;它想到达最后一块石头&#xff0c;然后回到第一块石头。同时每块石头 至多 到达 一次。 一次…...

【新2023Q2押题JAVA】华为OD机试 - 整理扑克牌

最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为od机试,独家整理 已参加机试人员的实战技巧本篇题解:整理扑克牌 题目 给定一组数…...

【hello C语言】文件操作

目录 1. 什么是文件&#xff1f; 2. 程序文件 3. 数据文件 4. 文件名 5. 文件类型 5.1 二进制文件 5.2 文本文件 5.3 数据在内存中的存储 6. 文件缓冲区 7. 文件指针 8. 文件的打开和关闭 9. 文件的顺序读写 10. 文件的随机读写 10.1 fseek&#xff1a;根据文件指针的位置和偏移…...

OBCP第八章 OB运维、监控与异常处理-数据库监控

系统监控视图&#xff1a;系统视图 OceanBase 数据库为多租户架构&#xff0c;租户分为两种类型&#xff1a;普通租户以及 sys 租户。OceanBase 数据库系统表都存储在 sys 租户&#xff0c;且主键中存储租户号&#xff08;tenant_id&#xff09;&#xff0c;区分每个租户的内容…...

已经提了离职,还有一周就走,公司突然把我移出企业微信,没法考勤打卡, 还要继续上班吗?...

黎明前的黑暗最容易出事&#xff0c;离职前的几天也最容易出幺蛾子&#xff0c;比如下面这位网友的遭遇&#xff1a;已经提了离职&#xff0c;还有一周就正式离职了&#xff0c;公司突然把我移出企业微信&#xff0c;没法考勤打卡了&#xff0c; 还要继续上班吗&#xff1f;该怎…...

Win11启用IE方法

呉師傅 Win11是微软目前的最新系统&#xff0c;尽管该系统非常不错&#xff0c;但是还是有很多不一样的地方&#xff0c;有的用户发现Win11没有了IE浏览器&#xff0c;那么Win11没有IE浏览器怎么办呢&#xff0c;有的旧网页需要IE浏览器才能进入&#xff0c;下面就给大家提供一…...

有人靠ChatGPT 狂赚200W !有人到现在,连账号都没开通......

作者| Mr.K 编辑| Emma来源| 技术领导力(ID&#xff1a;jishulingdaoli)互联网风水轮流转&#xff0c;当初元宇宙盛极一时之际&#xff0c;在一些知识付费平台上&#xff0c;任何一个关于元宇宙的课程或培训&#xff0c;都很热销&#xff0c;有一定号召力的博主&#xff0c;登…...

基于GD32F470的mbedtls 3DES算法测试

3DES加密算法介绍 3DES数据加密算法是一种可逆的对称加密算法&#xff0c;也称三重数据加密算法。3DES块加密算法的设计用来提供一种相对简单的方法&#xff0c;即通过增加DES的密钥长度来避免类似的攻击&#xff0c;而不是设计一种全新的密码算法&#xff0c;目前3DES作为DES…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!

本文介绍了一种名为AnomalyAny的创新框架&#xff0c;该方法利用Stable Diffusion的强大生成能力&#xff0c;仅需单个正常样本和文本描述&#xff0c;即可生成逼真且多样化的异常样本&#xff0c;有效解决了视觉异常检测中异常样本稀缺的难题&#xff0c;为工业质检、医疗影像…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

云原生周刊:k0s 成为 CNCF 沙箱项目

开源项目推荐 HAMi HAMi&#xff08;原名 k8s‑vGPU‑scheduler&#xff09;是一款 CNCF Sandbox 级别的开源 K8s 中间件&#xff0c;通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度&#xff0c;为容器提供统一接口&#xff0c;实现细粒度资源配额…...