【LeetCode-135】分发糖果(贪心)
LeetCode135.分发糖果
题目描述
老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。
你需要按照以下要求,帮助老师给这些孩子分发糖果:
- 每个孩子至少分配到 1 个糖果。
- 相邻的孩子中,评分高的孩子必须获得更多的糖果。
那么这样下来,老师至少需要准备多少颗糖果呢?
示例 1:
- 输入: [1,0,2]
- 输出: 5
- 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2:
- 输入: [1,2,2]
- 输出: 4
- 解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果,这已满足上述两个条件。
解法1:贪心
这道题目一定是要确定一边之后,再确定另一边,例如比较每一个孩子的左边,然后再比较右边,如果两边一起考虑一定会顾此失彼。
先确定右边评分大于左边的情况(也就是从前向后遍历)
此时局部最优:只要右边评分比左边大,右边的孩子就多一个糖果,全局最优:相邻的孩子中,评分高的右孩子获得比左边孩子更多的糖果
局部最优可以推出全局最优。
如果ratings[i] > ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一个,所以贪心:candyVec[i] = candyVec[i - 1] + 1
代码如下:
// 从前向后
for (int i = 1; i < ratings.size(); i++) {if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
}
如图:

再确定左孩子大于右孩子的情况(从后向前遍历)
遍历顺序这里有同学可能会有疑问,为什么不能从前向后遍历呢?
因为 rating[5]与rating[4]的比较 要利用上 rating[5]与rating[6]的比较结果,所以 要从后向前遍历。
如果从前向后遍历,rating[5]与rating[4]的比较 就不能用上 rating[5]与rating[6]的比较结果了 。如图:

所以确定左孩子大于右孩子的情况一定要从后向前遍历!
如果 ratings[i] > ratings[i + 1],此时candyVec[i](第i个小孩的糖果数量)就有两个选择了,一个是candyVec[i + 1] + 1(从右边这个加1得到的糖果数量),一个是candyVec[i](之前比较右孩子大于左孩子得到的糖果数量)。
那么又要贪心了,局部最优:取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量,保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优:相邻的孩子中,评分高的孩子获得更多的糖果。
局部最优可以推出全局最优。
所以就取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量,candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多,也比右边candyVec[i + 1]的糖果多。

代码实现
class Solution {/**分两个阶段1、起点下标1 从左往右,只要 右边 比 左边 大,右边的糖果=左边 + 12、起点下标 ratings.length - 2 从右往左, 只要左边 比 右边 大,此时 左边的糖果应该 取本身的糖果数(符合比它左边大) 和 右边糖果数 + 1 二者的最大值,这样才符合 它比它左边的大,也比它右边大*/public int candy(int[] ratings) {int len = ratings.length;int[] candyVec = new int[len];candyVec[0] = 1;for (int i = 1; i < len; i++) {candyVec[i] = (ratings[i] > ratings[i - 1]) ? candyVec[i - 1] + 1 : 1;}for (int i = len - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);}}int ans = 0;for (int num : candyVec) {ans += num;}return ans;}
}
相关文章:
【LeetCode-135】分发糖果(贪心)
LeetCode135.分发糖果 题目描述 老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。 你需要按照以下要求,帮助老师给这些孩子分发糖果: 每个孩子至少分配到 1 个糖果。…...
5G_射频测试_发射机测量(四)
6.2 Base station output power 用于测量载波发射功率的大小,功率越大小区半径越大但是杂散也会越大 载波功率(用频谱仪测)天线口功率(用功率计测)载波功率是以RBW为单位的filter测量的积分功率不同带宽的多载波测试时…...
MySQL经典50题
目录 一、数据表介绍 二、练习题 1. 查询" 01 "课程比" 02 "课程成绩高的学生的信息及课程分数 2. 查询同时存在" 01 "课程和" 02 "课程的情况 3. 查询存在" 01 "课程但可能不存在" 02 "课程的情况…...
常用的Qt开源库分享
1. Qwt (https://qwt.sf.net): Qwt是一个基于Qt的数据可视化库,提供了绘制曲线、图表、仪表盘等功能。 2. QJson (https://qjson.sourceforge.net): QJson是一个用于JSON数据解析和生成的库,使Qt应用程序能够方便地处理JSON格式的数据。 3. QCustomP…...
Unity开发授权系统
Unity开发授权系统 引子 因为有些客户尾款到账不及时,因此研究了一套授权系统,当授权到期后,系统就提示软件授权已到期,不能继续使用云云,这样方便尾款的收回。 大体需求就是 时间相关性,可以自由设置授…...
一周时间,开发了一款封面图生成工具
介绍 这是一款封面图的制作工具,根据简单的配置即可生成一张好看的封面图,目前已有七款主题可以选择。做这个工具的初衷来自平时写文章,都为封面图发愁,去图片 网站上搜索很难找到满意的,而且当你要的图如果要搭配上文…...
【.NET Core】深入理解异步编程模型(APM)
【.NET Core】深入理解异步编程模型(APM) 文章目录 【.NET Core】深入理解异步编程模型(APM)一、APM概述二、IAsyncResult接口2.1 BeginInvoke2.2 EndInvoke2.3 IAsyncResult属性2.4 IAsyncResult异步演示 三、通过结束异步操作来…...
pyqtgraph绘图类
pyqtgraph绘图类 pyqtgraph绘图有四种方法: 方法描述pyqtgraph.plot()创建一个新的QWindow用来绘制数据PlotWidget.plot()在已存在的QWidget上绘制数据PlotItem.plot()在已存在的QWidget上绘制数据GraphicsLayout.addPlot()在网格布局中添加一个绘图 上面四个方法都接收同样…...
C#6-10新增的内容
目录 异常筛选器 属性语法 表达式主体定义 Null 条件运算符 ?. 和 ?[] 使用 $ 的字符串内插 nameof 表达式 元组类型 模糊匹配 本地函数 Expression-bodied 成员 Reference 变量 ?、??和??= .. 模式匹配功能(C# 9) Record init c#8.NET Framework 4.8…...
【立创EDA-PCB设计基础】3.网络表概念解读+板框绘制
前言:本文对网络表概念解读板框绘制(确定PCB板子轮廓) 网络表概念解读 在本专栏的上一篇文章【嘉立创EDA-PCB设计指南】2,将设计的原理图转为了PCB,在PCB界面下出现了所有的封装,以及所有的飞线属性&…...
在Python环境中运行R语言的配环境实用教程
前情提要 在做一些生物信息与医学统计的工作,本来偷懒希望只靠python完成的,结果还是需要用R语言,倒腾了一会儿,调成功了,就记录一下这个过程。 我的环境: win10, pycharm, R-4.3.2 首先,我们…...
2023年总结我所经历的技术大变革
📢欢迎点赞 :👍 收藏 ⭐留言 📝 如有错误敬请指正,赐人玫瑰,手留余香!📢本文作者:由webmote 原创📢作者格言:新的征程,我们面对的不仅…...
基于YOLOv7算法的高精度实时车载摄像头下车辆检测系统(PyTorch+Pyside6+YOLOv7)
摘要:基于YOLOv7算法的高精度实时车载摄像头下车辆检测系统可用于日常生活中检测与定位车辆,此系统可完成对输入图片、视频、文件夹以及摄像头方式的目标检测与识别,同时本系统还支持检测结果可视化与导出。本系统采用YOLOv7目标检测算法来训…...
深度学习(3)--递归神经网络(RNN)和词向量模型Word2Vec
目录 一.递归神经网络基础概念 二.自然语言处理-词向量模型Word2Vec 2.1.词向量模型 2.2.常用模型对比 2.3.负采样方案 2.4.词向量训练过程 一.递归神经网络基础概念 递归神经网络(Recursive Neural Network, RNN)可以解决有时间序列的问题,处理诸如树、图这样…...
【江科大】STM32:中断系统(理论)
文章目录 中断系统为什么要使用中断中断优先级中断嵌套STM32的中断系统如何管理这些中断NVIC的结构 优先级窗口看门狗(WWDG):外部中断模块的特性&#…...
JAVA 学习 面试(六)数据类型与方法
数据类型 基本数据类型 为什么float3.4报错 3.4 默认是浮点double类型的,如果赋值给float是向下转型,会出现精度缺失,,需要强制转换 Switch支持的数据类型? byte、short、int、char 、 enum 、 String 基本类型与包…...
Java 一个数组集合List<People> 赋值给另一个数组集合List<NewPeople> ,两个数组集合属性部分一致。
Java 一个数组集合List 赋值给另一个数组集合List ,两个数组集合属性部分一致。 下面是一个Demo, 具体要根据自己的业务调整。 import java.util.ArrayList; import java.util.List;class People {private String name;private int age;private String address;publ…...
基于神经网络的电力系统的负荷预测
一、背景介绍: 电力系统负荷预测是生产部门的重要工作之一,通过准确的负荷预测,可以经济合理地安排机组的启停、减少旋转备用容量、合理安排检修计划、降低发电成本和提高经济效益。负荷预测按预测的时间可以分为长期、中期和短期负荷预测。…...
OpenCV第 1 课 计算机视觉和 OpenCV 介绍
文章目录 第 1 课 计算机视觉和 OpenCV 介绍1.机器是如何“看”的2.机器视觉技术的常见应用3.图像识别介绍4. 图像识别技术的常见应用5.OpenCV 介绍6.图像在计算机中的存储形式 第 1 课 计算机视觉和 OpenCV 介绍 1.机器是如何“看”的 我们人类可以通过眼睛看到五颜六色的世界…...
C++面试:stl的栈和队列介绍
目录 栈 栈(stack)的声明: push(): 将元素推入栈顶 pop(): 弹出栈顶元素 top(): 访问栈顶元素,但不弹出 empty(): 检查栈是否为空 size(): 返回栈中元素的数量 …...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
【第二十一章 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 arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)
目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 (1)输入单引号 (2)万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...
