【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(): 返回栈中元素的数量 …...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
