分发糖果[困难]

优质博文:IT-BLOG-CN

一、题目

n个孩子站成一排。给你一个整数数组ratings表示每个孩子的评分。你需要按照以下要求,给这些孩子分发糖果:
【1】每个孩子至少分配到1个糖果。
【2】相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目。

示例 1:
输入:ratings = [1,0,2]
输出:5
解释:你可以分别给第一个、第二个、第三个孩子分发2、1、2颗糖果。

示例 2:
输入:ratings = [1,2,2]
输出:4
解释:你可以分别给第一个、第二个、第三个孩子分发1、2、1颗糖果。第三个孩子只得到1颗糖果,这满足题面中的两个条件。

n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104

二、代码

【1】两次遍历: 我们可以将「相邻的孩子中,评分高的孩子必须获得更多的糖果」这句话拆分为两个规则,分别处理。
左规则:ratings[i−1] < ratings[i]时,i号学生的糖果数量将比i−1号孩子的糖果数量多。
右规则:ratings[i] > ratings[i+1]时,i号学生的糖果数量将比i+1号孩子的糖果数量多。
我们遍历该数组两次,处理出每一个学生分别满足左规则或右规则时,最少需要被分得的糖果数量。每个人最终分得的糖果数量即为这两个数量的最大值。

具体地,以左规则为例:我们从左到右遍历该数组,假设当前遍历到位置i,如果有ratings[i−1] < ratings[i]那么i号学生的糖果数量将比i−1号孩子的糖果数量多,我们令left[i]=left[i−1] + 1即可,否则我们令left[i] = 1。在实际代码中,我们先计算出左规则left数组,在计算右规则的时候只需要用单个变量记录当前位置的右规则,同时计算答案即可。

class Solution {public int candy(int[] ratings) {// 1、定义left[]数组,计算每个小朋友符合左侧规则时,能获取到的糖果// 2、定义两个变量,第一个计算前一个小朋友的糖果,第二个计算总的糖果数量,从右侧开始计算if (ratings.length == 0) {return 0;}// 创建数组int[] left = new int[ratings.length];left[0] = 1;for(int i = 1; i < ratings.length; i++) {if (ratings[i] > ratings[i - 1]) {left[i] = left[i - 1] + 1;} else {left[i] = 1;}}// 先初始化最后一个小朋友的糖果int next = 1, count = Math.max(1, left[ratings.length - 1]);for(int i = ratings.length - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {next += 1;} else {next = 1;}count += Math.max(next, left[i]);}return count;}
}

时间复杂度: O(2n)其中n是孩子的数量。我们需要遍历两次数组以分别计算满足左规则或右规则的最少糖果数量。
空间复杂度: O(n)其中n是孩子的数量。我们需要保存所有的左规则对应的糖果数量。

【2】常数空间遍历: 定义两个变量,第一个计算当前小朋友的糖果pre,第一个小朋友默认为1,第二个计算总的糖果数量count,如果时递增的,那么就比较简单,我们给pre+1,如果递减了,我们重置pre = 1即可。下面考虑两个特殊场景:
 ● 当pre=1时,开始递减时,我们需要再创建一个变量decr,来表示递减的次数,然后将其累积到count中,也就达到了将递减转化为递增的效果。
 ● 当递减的队列长度,超过了递减前小朋友的糖果时,我们需要对递减前的小朋友的糖果+n,例如下图: 从左侧遍历时,第三个小朋友应该是3个糖果,所以定义inc记录递减前小朋友的糖果,如果递减的糖果decr等于递减前的糖果inc,就需要对inc + 1

class Solution {public int candy(int[] ratings) {// 1、定义两个变量,第一个计算当前小朋友的糖果pre,第二个计算总的糖果数量count。// 2、左侧遍历时,如果时递减的情况,需要再创建一个变量,计算递减的次数 decr。// 3、特殊处理:递减的时候,如果我拥有的糖果和递减前小朋友的糖果个数相同时,需要++,举例:5321的时候,5有3个糖果,此时的3再递减中也会有5个糖果,所以就需要对5的糖果+1if (ratings.length == 0) {return 0;}// 先初始化最后一个小朋友的糖果int pre = 1, count = 1, decr = 0, inc = 1;for(int i = 1; i < ratings.length; i++) {if (ratings[i] >= ratings[i - 1]) {pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;;// 如果时递增的,当前递减序列结束decr = 0;count += pre;// pre表示当前小朋友用于的当过inc = pre;} else {// 如果开始了递减序列,我们就开始记录递减序列的长度decr++;// 递减的时候,如果我拥有的糖果和递减的小朋友的个数相同时,需要++,举例:5321的时候,5有3个糖果,此时的3再递减中也会有5个糖果,所以就需要对5+1if (inc == decr) {decr++;}// 重置糖果为1pre = 1;count += decr;}}return count;}
}

时间复杂度: O(n)其中n是孩子的数量。我们需要遍历两次数组以分别计算满足左规则或右规则的最少糖果数量。
空间复杂度: O(1)我们只需要常数的空间保存若干变量。

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

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

相关文章

物联网_01_物理设备的网络接入

设备的网络接入及物理层使用到的传输协议 现在物理设备有两种接入方式,一种是直接接入另一种是网关接入 直接接入 给物理设备添加NB-IOT通信模组等设备使之具有直接接入网络的能力 网关接入 物理设备在本地组网后通过统一的网关接入到网络(ZigBee无线组网网关).网关是处在本地…

服务器数据恢复-某银行服务器硬盘数据恢复案例

服务器故障&分析&#xff1a; 某银行的某一业务模块崩溃&#xff0c;无法正常使用。排查服务器故障&#xff0c;发现运行该业务模块的服务器中多块硬盘离线&#xff0c;导致上层应用崩溃。 故障服务器内多块硬盘掉线&#xff0c;硬盘掉线数量超过服务器raid阵列冗余级别所允…

过硫酸铵溶液蚀刻回收铜上石墨烯片的合成

引言 石墨烯是一种原子级薄层2D碳纳米材料&#xff0c;具有以六方晶格结构排列的sp2键碳原子。石墨烯因其优异的物理和电子性能而受到广泛关注。自发现石墨烯以来&#xff0c;石墨烯的基础、合成方法和潜在应用的研究一直在积极进行。 化学气相沉积是大规模生产石墨烯的有前途…

【Docker】Dockerfile常用指令

参考官方文档&#xff1a;https://docs.docker.com/engine/reference/builder/ Dockerfile常用指令 指令说明from基础镜像&#xff0c;当前镜像基于&#xff08;依赖&#xff09;哪个镜像maintainer镜像的维护者和邮箱run镜像构建时需要执行的命令workdir镜像的工作目录expos…

NSS [NCTF 2018]滴!晨跑打卡

NSS [NCTF 2018]滴!晨跑打卡 很明显是sql注入 输入一个1&#xff0c;语句直接显示了&#xff0c;非常的真诚和坦率 简单尝试了一下&#xff0c;发现有waf&#xff0c;过滤了空格 拿burp跑一下fuzz&#xff0c;看看有多少过滤 过滤了# * - 空格那我们无法通过#或者–来注释掉…

CentOS 7设置固定IP地址

当我们安装了一个虚拟机或者装了一个系统的时候&#xff0c;经常会遇到需要设置固定ip的情况&#xff0c;本文就以Centos 7为例&#xff0c;讲述如何修改固定IP地址。 1、用ifconfig命令查看使用的网卡 如上图所示&#xff0c;我们就会看到我们目前使用的网卡名称 2、编辑网卡…

【机器学习】支持向量机(实战)

支持向量机&#xff08;实战&#xff09; 目录 一、准备工作&#xff08;设置 jupyter notebook 中的字体大小样式等&#xff09;二、线性支持向量机&#xff08;核函数为线性核&#xff09;三、数据标准化的影响四、软间隔五、非线性支持向量机5.1 手动升维5.2 对比试验&#…

洗车小程序源码:10个必备功能,提升洗车体验

作为洗车行业的专家&#xff0c;我们深知在如今数字化时代&#xff0c;拥有一款功能强大的洗车小程序是提升用户体验和业务发展的关键。本文将向您介绍洗车小程序源码中的10个必备功能&#xff0c;让您的洗车业务达到新的高度。 在线预约系统 通过洗车小程序源码&#xff0c;…

强化学习代码实战(1)

机器人领域&#xff1a;控制&#xff0c;规划&#xff0c;感知等都可以用&#xff0c;可以把它作为一个优化过程&#xff0c;那么任何需要优化的问题都可以用它解决。 1.应用 深度学习&#xff1a;智能感知&#xff0c;解决智能如何理解这个世界的问题。 强化学习&#xff1a…

华为云 CodeArts Snap 智能编程助手 PyCharm 插件安装与使用指南

1 插件安装下载 1.1 搜索插件 打开 PyCharm&#xff0c;选择 File&#xff0c;点击 Settings。 选择 Plugins&#xff0c;点击 Marketplace&#xff0c;并在搜索框中输入 Huawei Cloud CodeArts Snap。 1.2 安装插件 如上图所示&#xff0c;点击 Install 按钮安装 Huawei Cl…

C++IO流

文章目录 CIO流1. C语言的输入与输出2. 流是什么3. CIO流3.1 C标准IO流3.2 C文件IO流 4 stringstream的简单介绍 CIO流 1. C语言的输入与输出 C语言中我们用到的最频繁的输入输出方式就是scanf()与printf()。 scanf(): 从标准输入设备(键盘)读取数据&#xff0c;并将值存放在…

vue3 v-model的使用

&#x1f642;博主&#xff1a;锅盖哒 &#x1f642;文章核心&#xff1a;vue3 v-model的使用 目录 前言 什么是v-model&#xff1f; 基本的v-model用法 自定义组件中的v-model 前言 当涉及到Vue.js 3的前端开发时&#xff0c;v-model是一个不可或缺的工具&#xff0c;它…

Jmeter性能测试 —— TPS拐点寻找

寻找TPS性能拐点1、准备脚本①在本地电脑调试Jmeter压测脚本 ②上传到压测机Jmeter所在的服务器 2、执行压力测试①执行压测脚本 jmeter –n –t xianchengzuse.jmx ②记录业务压测数据 3、监控服务器性能指标 ①监控CPU输入top命令 ②监控内存 free –m ③jstat监控sweep和…

高效使用python之xlwt库编辑写入excel表内容

头条号&#xff1a;科雷软件测试 学习目录 了解下电脑中的excel表格文件格式 安装xlwt库 xlwt库写入表格内容 1 导入xlwt库 2 用一个图展示下xlwt常用的函数 3 往表格写入一些内容并保存 4 设置样式 1 先初始化XFStyle 2 设置字体font 3 设置边框 4 设置对齐方式 …

精讲stable diffusion的controlNet插件

controlNet插件是stable diffusion的一个重要插件&#xff0c;甚至可以说正是因为有了controlNet插件&#xff0c;stable diffusion才会具有midjourney所不具备的独特魅力&#xff01; 我们今天就一起来学习下controlNet插件的安装和每个模型的用法 插件主页 独立的controlN…

迷你洗衣机哪个牌子好又实惠?小型洗衣机全自动

现在洗内衣内裤也是一件较麻烦的事情了&#xff0c;在清洗过程中还要用热水杀菌&#xff0c;还要确保洗衣液是否有冲洗干净&#xff0c;还要防止细菌的滋生等等&#xff0c;所以入手一款小型的烘洗全套的内衣洗衣机是非常有必要的&#xff0c;专门的内衣洗衣机可以最大程度减少…

自然语言处理---Transformer机制详解之Self attention机制详解

1 Self-attention的特点 self-attention是一种通过自身和自身进行关联的attention机制, 从而得到更好的representation来表达自身. self-attention是attention机制的一种特殊情况&#xff0c;在self-attention中, QKV, 序列中的每个单词(token)都和该序列中的其他所有单词(to…

在edge浏览器中安装好了burp的ca证书,浏览器依旧不能访问https的原因

在edge浏览器中安装好了burp的ca证书&#xff0c;浏览器依旧不能访问https的原因 1.SwitchyOmega代理插件设置2.CA证书方法1方法2 1.SwitchyOmega代理插件设置 严格安装以下图片执行&#xff0c;不可少写或多写 2.CA证书 方法1 下载好证书&#xff0c;先导入到edge浏览器的中…

基于.Net CEF 实现 Vue 等前端技术栈构建 Windows 窗体应用

零、参考资料 1、https://github.com/cefsharp/CefSharp/wiki/Quick-Start-For-MS-.Net-5.0-or-greater 2、https://github.com/cefsharp/CefSharp/wiki/Quick-Start 3、https://github.com/cefsharp/CefSharp/wiki/General-Usage#javascript-integration 一、安装 Nuget 包…

MyBatis篇---第五篇

系列文章目录 文章目录 系列文章目录一、MyBatis 中见过什么设计模式&#xff1f;二、MyBatis 中比如 UserMapper.java 是接口&#xff0c;为什么没有实现类还能调用&#xff1f; 一、MyBatis 中见过什么设计模式&#xff1f; 二、MyBatis 中比如 UserMapper.java 是接口&#…