【leetcode面试经典150题】15.分发糖果(C++)
【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主,题解使用C++语言。(若有使用其他语言的同学也可了解题解思路,本质上语法内容一致)
【题目描述】
n
个孩子站成一排。给你一个整数数组 ratings
表示每个孩子的评分。
你需要按照以下要求,给这些孩子分发糖果:
- 每个孩子至少分配到
1
个糖果。 - 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目 。
【示例一】
输入:ratings = [1,0,2] 输出:5 解释:你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
【示例二】
输入:ratings = [1,2,2] 输出:4 解释:你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果,这满足题面中的两个条件。
【提示及数据范围】
n == ratings.length
1 <= n <= 2 * 10的4次方
0 <= ratings[i] <= 2 * 10的4次方
【代码】
// 方法一:两次遍历// 我们可以将「相邻的孩子中,评分高的孩子必须获得更多的糖果」这句话拆分为两个规则,分别处理。
// 左规则:当 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。class Solution {
public:int candy(vector<int>& ratings) {int n = ratings.size();vector<int> left(n);for(int i = 0;i<n;i++){if(i > 0 && ratings[i] > ratings[i-1]){left[i] = left[i-1] + 1;}else{left[i] = 1;}}int right = 0,ret = 0;for(int i = n-1;i>=0;i--){if(i < n-1 && ratings[i] > ratings[i+1]){right++;}else{right = 1;}ret += max(left[i],right);}return ret;}
};// 方法二:常数空间遍历// 依据前面总结的规律,我们可以提出本题的解法。
// 我们从左到右枚举每一个同学,记前一个同学分得的糖果数量为 pre:// 如果当前同学比上一个同学评分高,说明我们就在最近的递增序列中,
// 直接分配给该同学 pre+1 个糖果即可。// 否则我们就在一个递减序列中,我们直接分配给当前同学一个糖果,
// 并把该同学所在的递减序列中所有的同学都再多分配一个糖果,以保证糖果数量还是满足条件。// 我们无需显式地额外分配糖果,只需要记录当前的递减序列长度,即可知道需要额外分配的糖果数量。// 同时注意当当前的递减序列长度和上一个递增序列等长时,
// 需要把最近的递增序列的最后一个同学也并进递减序列中。// 只要记录当前递减序列的长度 dec,最近的递增序列的长度 inc
// 和前一个同学分得的糖果数量 pre 即可。class Solution {
public:int candy(vector<int>& ratings) {int n = ratings.size();int ret = 1;int inc = 1, dec = 0, pre = 1;for (int i = 1; i < n; i++) {if (ratings[i] >= ratings[i - 1]) {dec = 0;pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;ret += pre;inc = pre;} else {dec++;if (dec == inc) {dec++;}ret += dec;pre = 1;}}return ret;}
};
相关文章:
【leetcode面试经典150题】15.分发糖果(C++)
【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主,题解使用C语言。(若有使用其他语言的同学也可了解题解思路,本质上语法内容一致&…...
Elasticsearch如何选择版本
不同版本的ES差异非常大,包括不局限于ES语法、架构、API、集群搭建等等。这些差异足以导致不同版本是否能满足你的业务场景以及后续开发维护成本等各种问题。 先说结论,以个人实践经验及综合考虑推荐使用 7.x 版本中的 7.10版本 ES版本对比 以下是通过…...
P8749 [蓝桥杯 2021 省 B] 杨辉三角形
[蓝桥杯 2021 省 B] 杨辉三角形 题目描述 下面的图形是著名的杨辉三角形: 如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下数列: 1 , 1 , 1 , 1 , 2 , 1 , 1 , 3 , 3 , 1 , 1 , 4 , 6 , 4 , 1 , … 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1, …...
MySQL数据库——1.创建数据库
在 MySQL 数据库中,要创建一个新的数据库,可以使用 SQL 命令 CREATE DATABASE。创建数据库是管理数据的第一步,它提供了一个容器,用于存储表、视图、存储过程等数据库对象。 示例: CREATE DATABASE my_database; 在…...
计算机视觉研究院 | Drone-YOLO:一种有效的无人机图像目标检测
本文来源公众号“计算机视觉研究院”,仅用于学术分享,侵权删,干货满满。 原文链接:Drone-YOLO:一种有效的无人机图像目标检测 无人机图像中的目标检测是各个研究领域的重要基础。然而,无人机图像带来了独…...
[C#]使用OpencvSharp去除面积较小的连通域
【C介绍】 关于opencv实现有比较好的算法,可以参考这个博客OpenCV去除面积较小的连通域_c#opencv 筛选小面积区域-CSDN博客 但是没有对应opencvsharp实现同类算法,为了照顾懂C#编程同学们,因此将 去除面积较小的连通域算法转成C#代码。 方…...
联邦学习目前面临的挑战以及解决方案
学习目标: 联邦学习目前面临的挑战以及解决方案 学习内容: 联邦学习是一种新兴的人工智能基础技术,它在保障大数据交换时的信息安全、保护终端数据和个人数据隐私、保证合法合规的前提下,在多参与方或多计算结点之间开展高效率的…...
Day60:WEB攻防-XMLXXE安全无回显方案OOB盲注DTD外部实体黑白盒挖掘
目录 XML&XXE-传输-原理&探针&利用&玩法 XXE 黑盒发现 XXE 白盒发现 XXE修复防御方案 有回显 无回显 XML&XXE-黑盒-JSON&黑盒测试&类型修改 XML&XXE-白盒-CMS&PHPSHE&无回显 知识点: 1、XXE&XML-原理-用途&…...
解锁网络安全新境界:雷池WAF社区版让网站防护变得轻而易举!
网站运营者的救星:雷池WAF社区版 ️ 嘿朋友们!今天我超级激动要跟你们分享一个神器——雷池WAF社区版。这个宝贝对我们这帮网站运营者来说,简直就是保护伞! 智能语义分析技术:超级侦探上线 先说说为啥我这么稀饭它。雷…...
RabbitMQ安装详细教程
(一)在Windows系统上安装Erlang的步骤如下: 打开Erlang的官方下载页面,选择适合你的Windows系统的版本进行下载。 下载完成后,双击运行下载的.exe文件,进入Erlang的安装向导。 在安装向导中,按…...
如何快速写出一个完整的测试用例
测试用例是为了验证软件功能或需求而设计的一组测试输入、执行条件和预期结果。编写测试用例的目的是确保测试过程全面高效、有据可查。 一般来说,编写测试用例的流程包括以下几个步骤: 分析需求:阅读需求文档,理解软件的功能和业…...
Docker容器与虚拟化技术:OpenEuler 部署 ES 与 Kibana
目录 一、实验 1.环境 2.OpenEuler 部署 ES (EalasticSearch) 3.OpenEuler 部署 Kibana 4.部署 Elasticvue插件 5.使用cpolar内网穿透 6.使用Elasticvue 一、实验 1.环境 (1)主机 表1 主机 系统架构版本IP备注LinuxopenEuler22.03 LTS SP2 1…...
数学中的各种符号虚数概念
max i∈SA i ≥ ∑ i∈SB i. 这个不等式表达的意思是对于集合 S 中的任意非空子集,子集中的最大的 A_i(A 的元素)的值都大于等于子集中所有 B_i(B 的元素)的值的总和。换句话说,集合 S 中的最大…...
什么是中间件
中间件是指在应用程序与操作系统之间提供服务的软件,它可以隐藏底层操作系统的复杂性,为应用程序提供各种实用的服务,以便应用程序更好地实现业务逻辑。中间件通常提供如下几种服务: 数据库连接:中间件可以为应用程序提…...
RabbitMQ面经 手敲浓缩版
保证可靠性 生产者 本地事务完成和消息发送同时完成 通过事务消息完成 重写confirm在里面做逻辑处理 确保发送成功(不成功就放入到重试队列) MQ 打开持久化确保消息不会丢失 消费者 改成手动回应 不重复消费 生产者 保证不重复发送消息 消费者…...
解锁金融数据中心场景,实现国产化AD替代,宁盾身份域管为信创电脑、应用提供统一管理
随着信创国产化改造持续推进,越来越多的金融机构不断采购信创服务器、PC、办公软件等,其 IT 基础设施逐渐迁移至国产化 IT 架构下。为支撑国产化 IT 基础设施的正常使用和集中管理运维,某金融机构数据中心的微软Active Directory(…...
Django的js文件没有响应(DOMContentLoaded)
问题出现的原因是因为当浏览器解析到“script”标签并执行其中的JavaScript代码时,页面上的DOM元素尚未完全加载和渲染。这意味着,当尝试通过document.getElementById(‘create-theme-button’)获取元素时,该元素还不存在,导致add…...
滑动窗口代码模板
代码模板: //滑动窗口伪代码 class Solution { public:int minWindow(string s) {// 同方向移动,起始的时候,都位于 0,表示我们定义搜索区间为 [left, right) ,此时区间为空区间int left 0;int right 0;while(right…...
SpringBoot实现邮箱验证
目录 1、开启邮箱IMAP/SMTP服务,获取授权码 2、相关代码 1、使用配置Redis(用于存储验证码,具有时效性) 2、邮箱依赖和hutool(用于随机生成验证码) 3、配置Redis和邮箱信息 4、开启Redis服务 5、编写发送…...
Mac安装Docker提示Another application changed your Desktop configuration解决方案
1. 问题描述 Mac安装Docker后,提示Another application changed your Desktop configuration,Re-apply configurations无效 2. 解决方案 在终端执行下述命令即可解决: sudo ln -sf /Applications/Docker.app/Contents/Resources/bin/docke…...
5分钟安装docker和docker compose环境
5分钟安装docker和docker compose环境 5分钟安装docker和docker compose环境环境介绍卸载docker环境安装docker安装docker compose 5分钟安装docker和docker compose环境 你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑…...
leetcode热题100.跳跃游戏2
Problem: 45. 跳跃游戏 II 文章目录 题目思路复杂度Code 题目 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i j] 处: …...
【前端】CSS(引入方式+选择器+常用元素属性+盒模型+弹性布局)
文章目录 CSS一、什么是CSS二、语法规范三、引入方式1.内部样式表2.行内样式表3.外部样式 四、选择器1.选择器的种类1.基础选择器:单个选择器构成的1.标签选择器2.类选择器3.id 选择器4.通配符选择器 2.复合选择器1.后代选择器2.子选择器3.并集选择器4.伪类选择器 五…...
迷茫下是自我提升
长夜漫漫,无心睡眠。心中所想,心中所感,忧愁当前,就执笔而下,写下这篇文章。 回忆过往 回想当初为啥学前端,走前端这条路,学校要求嘛,兴趣爱好嘛,还是为了钱。 时间带着…...
用vscode仿制小米官网
html内容: <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title><link rel&quo…...
【Java+Springboot】------ 通过JDBC+GetMapping方法进行数据select查询、多种方式传参、最简单的基本示例!
一、JDBC如何使用、PostGresql数据库 1、在pom.xml 先引用jdbc组件。 <!--jdbc--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-jdbc</artifactId></dependency> 2、在pom.xml 再引用p…...
基于单片机光伏太阳能跟踪系统设计
**单片机设计介绍,基于单片机光伏太阳能跟踪系统设计 文章目录 一 概要二、功能设计三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机光伏太阳能跟踪系统的设计,旨在通过单片机技术实现对光伏太阳能设备的自动跟踪,以提高太阳…...
Stable Diffusion 本地化部署
一、前言 最近在家背八股文背诵得快吐了,烦闷的时候,看到使用 AI 进行作图,可以使用本地话部署。刚好自己家里的电脑,之前买来玩暗黑4,配置相对来说来可以,就拿来试试。 此篇是按照 Github 上的 stable-d…...
C++ Algorithm 常用算法
C <algorithm> 头文件是标准库中提供的一系列算法,用于操作范围(range)内的元素。这些算法可以用于数组、容器如vector和list,以及其他满足相应迭代器要求的数据结构。以下是一些常用的C <algorithm> 中的算法及其使用…...
线程安全--深入探究线程等待机制和死锁问题
꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转…...
网站成功案例怎么做/什么是关键词
在postman中,大家都使用过断言,但是我们使用的断言都是针对每一个接口或者是每一个用例添加的,那么是否有可以同时对多个用例或接口添加断言呢 ? 答案是肯定有的。 那么接下来我就带领大家认识下Postman中的批量断言,…...
网站建设服务后所有权归谁/东莞百度快速排名优化
ExtJS的下拉选单组件Combobox如果有空选项时,会有空选项高度太小的问题,如下图: 解决方法是为Combobox的tpl属性设置template string,并在该template string中添加高度样式定义,例如: Java代码 new Ext.for…...
个人网站赚广告费/长沙排名推广
bodyStyle :overflow-x:hidden;overflow-y:scroll, //隐藏水平滚动条,显示用overflow-x:visiblehidden 隐藏scroll :一定有 auto:自动通过这个方法可以显示或隐藏滚动条var form new Ext.form.FormPanel({frame : true,labelWidth : 80,height : 400,autoScroll : true,bodyS…...
企业电子网站建设/青岛排名推广
解决Maven Projects中plugins文件报错问题参考文章: (1)解决Maven Projects中plugins文件报错问题 (2)https://www.cnblogs.com/book3/p/11750252.html 备忘一下。...
毕业设计选择做网站的意义/软文代发布
1.使用brew 安装brew install mysql 扩展 brew info mysql(软件) 可以查看安装的软件启动 数据库服务 mysql.server start2.安装好后登录数据库 mysql -u root -p show databases; show tables; select version();查看版本号 create database zp;创建zp数据库 use zp; 像zp数…...
南通网站建设知识/网站换了域名怎么查
mysql有个字段是bit,只存储1和0,是二进制存储,那么在java的dao层如何映射成boolean呢 Column(name"is_standard") private boolean isStandard;public void setIsStandard(boolean isStandard){this.isStandard isStandard; }publ…...