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

贪心算法|135.分发糖果

力扣题目链接

class Solution {
public:int candy(vector<int>& ratings) {vector<int> candyVec(ratings.size(), 1);// 从前向后for (int i = 1; i < ratings.size(); i++) {if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;}// 从后向前for (int i = ratings.size() - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1] ) {candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);}}// 统计结果int result = 0;for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];return result;}
};

看着是困难题,其实仔细理解并不是很吓人。

这题的重点在如何遍历。

 vector<int> candyVec(ratings.size(), 1); 还有它是个啥?

vector < int > myVector(num); 或者 vector < int > myVector(n,num);

类似于resize的用法

 函数原型:
void resize (size_type n);
void resize (size_type n, const value_type& val);
 作用:
改变容器的大小,使得其包含n个元素。常见三种用法。

1、如果n小于当前的容器大小,那么则保留容器的前n个元素,去除(erasing)超过的部分。

2、如果n大于当前的容器大小,则通过在容器结尾插入(inserting)适合数量的元素使得整个容器大小达到n。且如果给出val,插入的新元素全为val,否则,执行默认构造函数。

3、如果n大于当前容器的容量(capacity)时,则会自动重新分配一个存储空间。

注意:如果发生了重新分配,则使用容器的分配器分配存储空间,这可能会在失败时抛出异常。

思路

这道题目一定是要确定一边之后,再确定另一边,例如比较每一个孩子的左边,然后再比较右边,如果两边一起考虑一定会顾此失彼

先确定右边评分大于左边的情况(也就是从前向后遍历)

此时局部最优:只要右边评分比左边大,右边的孩子就多一个糖果,全局最优:相邻的孩子中,评分高的右孩子获得比左边孩子更多的糖果

局部最优可以推出全局最优。

如果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;
}

如图:

135.分发糖果

再确定左孩子大于右孩子的情况(从后向前遍历)

遍历顺序这里有同学可能会有疑问,为什么不能从前向后遍历呢?

因为 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]的糖果多

如图:

135.分发糖果1

所以该过程代码如下:

// 从后向前
for (int i = ratings.size() - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1] ) {candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);}
}

自己的思路: 

其实我没太搞懂这个遍历的意思,但是知道只能从一边开始看

好吧,我承认这题还是有点难的,一直没搞清楚从前向后和从后向前什么意思啊!!!

相关文章:

贪心算法|135.分发糖果

力扣题目链接 class Solution { public:int candy(vector<int>& ratings) {vector<int> candyVec(ratings.size(), 1);// 从前向后for (int i 1; i < ratings.size(); i) {if (ratings[i] > ratings[i - 1]) candyVec[i] candyVec[i - 1] 1;}// 从后…...

c# wpf template itemtemplate+ListBox

1.概要 2.代码 <Window x:Class"WpfApp2.Window7"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schemas.microsoft.com/expression/blend/…...

关于JVM-三色标记算法剖析

相关系列 深入理解JVM垃圾收集器-CSDN博客 深入理解JVM垃圾收集算法-CSDN博客 深入理解jvm执行引擎-CSDN博客 jvm优化原则-CSDN博客 jvm流程图-CSDN博客 三色标记产生的原因&#xff1f; 在并发标记的过程中&#xff0c;因为标记期间应用线程还在继续跑&#xff0c;对象间的引…...

怎么看有没有装python

windows系统&#xff0c;运行——cmd&#xff0c;进入dos窗口&#xff0c;输入python&#xff0c;安装成功的话可以看到版本信息并进入编程模式。 如下图&#xff08;我安装的版本是python 3.5.1&#xff09;&#xff1a;...

VS CODE环境安装和hello world

SAP UI5 demo walkthrough tutorial step1 hello word 首先要安装nodejs&#xff0c;然后才能执行下面的操作 nodejs vscode 安装ui5 npm install --global ui5/cli报错解决: idealTree:npm: sill idealTree buildDeps 这个信息说明npm正在构建&#xff0c;如一直停留在这个…...

mysql性能索引调优易混点总结

文章目录 一、 前言二、explain相关三、索引优化相关联合索引索引下推排序和分组相关优化分页优化表关联优化嵌套循环连接 Nested-Loop Join(NLJ) 算法in和exsits优化 一、 前言 近几年看了很多和mysql相关的书&#xff0c;文章或视频&#xff0c;但仍然有一些点&#xff0c;看…...

区块链与数字身份:探索Facebook的新尝试

在数字化时代&#xff0c;随着区块链技术的崛起&#xff0c;数字身份成为了一个备受关注的话题。作为全球最大的社交媒体平台之一&#xff0c;Facebook一直在探索如何利用区块链技术来改善数字身份管理和用户数据安全。本文将深入探讨Facebook在这一领域的新尝试&#xff0c;探…...

【pycharm】在debug循环时,如何快速debug到指定循环次数

【pycharm】在debug循环时&#xff0c;如何快速debug到指定循环次数 【先赞后看养成习惯】求关注收藏点赞&#x1f600; 在 PyCharm 中&#xff0c;可以使用条件断点来实现在特定循环次数后停止调试。这可以通过在断点处右键单击&#xff0c;然后选择 “Add Breakpoint” -&g…...

【蓝桥杯每日一题】4.8 公约数

题目来源&#xff1a; 4199. 公约数 - AcWing题库 问题描述&#xff1a; ​ 找到最大整数x&#xff0c;需满足下面两个条件 x x x是 a a a, b b b的公约数 l < x < r l<x<r l<x<r 思路&#xff1a; 找到 a a a, b b b两个数的最大公约数 g c g c d (…...

【MySQL学习】MySQL的慢查询日志和错误日志

꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好&#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解&#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN …...

# C++之functional库用法整理

C之functional库用法整理 注&#xff1a;整理一些突然学到的C知识&#xff0c;随时mark一下 例如&#xff1a;忘记的关键字用法&#xff0c;新关键字&#xff0c;新数据结构 C 的function库用法整理 C之functional库用法整理一、functional库的内建仿函数1. 存储和调用函数2. 存…...

查看MySQL版本的方式

文章目录 一、使用cmd输入命令行查看二、在mysql客户端服务器里查询 一、使用cmd输入命令行查看 1、打开 cmd &#xff0c;输入命令行&#xff1a; mysql --version 2、还是打开cmd&#xff0c;输入命令行&#xff1a;mysql -V (注意了&#xff0c;此时的V是个大写的V) 二、…...

k8s_入门_命令详解

命令详解 kubectl是官方的CLI命令行工具&#xff0c;用于与 apiserver进行通信&#xff0c;将用户在命令行输入的命令&#xff0c;组织并转化为 apiserver能识别的信息&#xff0c;进而实现管理k8s各种资源的一种有效途径 1. 帮助 2. 查看版本信息 3. 查看资源对象等 查看No…...

腾讯、阿里、字节….等大厂都更喜欢什么样的简历?

我985毕业&#xff0c;为什么筛选简历时输给了一个普通一本&#xff1f; 我投了20份简历&#xff0c;为什么没有一个大厂回我&#xff1f; 每次HR收到简历就没下文了&#xff0c;是我的简历有问题吗&#xff1f; 诚然&#xff0c;在求职时&#xff0c;简历往往就是我们给予H…...

OpenHarmony实战:帆移植案例(中)

OpenHarmony实战&#xff1a;帆移植案例&#xff08;上&#xff09; Audio服务介绍 服务节点 基于ADM框架的audio驱动对HDI层提供三个服务hdf_audio_render、hdf_audio_capture、hdf_audio_control。 开发板audio驱动服务节点如下&#xff1a; console:/dev # ls -al hdf_au…...

武汉星起航:创始人张振邦智慧领航,孵化伙伴共绘跨境新蓝图!

在风起云涌的跨境电商行业中&#xff0c;武汉星起航电子商务有限公司如同一颗璀璨的明星&#xff0c;引领着众多创业者迈向成功的彼岸。而这一切的背后&#xff0c;都离不开公司创始人张振邦先生的卓越领导与深厚经验。他凭借着在电子商务行业多年的深耕与积累&#xff0c;为武…...

上下收缩、折叠面板

效果&#xff1a; 上下收缩、折叠面板&#xff0c;类似QQ好友列表那种。原理就是在一个布局中&#xff0c;通过button来实现一个独立widget的visible/disable 实现&#xff1a; 1.分组按钮 #ifndef EXPANDPANEL_H #define EXPANDPANEL_H#include <QWidget>class…...

XC7A35T-2FGG484 嵌入式FPGA现场可编程门阵列 Xilinx

XC7A35T-2FGG484 是一款由Xilinx&#xff08;赛灵思&#xff09;制造的FPGA&#xff08;现场可编程门阵列&#xff09;芯片 以下是XC7A35T-2FGG484 的主要参数&#xff1a; 1. 系列&#xff1a;Artix-7 2. 逻辑单元数量&#xff1a;33280个 3. 工艺技术&#xff1a;28nm 4. …...

淘宝订单API接口:电商业务自动化的新选择

淘宝订单API接口在电商业务自动化中扮演了至关重要的角色。首先&#xff0c;通过API接口&#xff0c;商家可以自动化地查询、创建、修改和删除订单&#xff0c;极大地提高了订单处理效率&#xff0c;减少了人工操作&#xff0c;降低了错误率。其次&#xff0c;商家可以实时获取…...

识典百科词条创建技巧,教你如何轻松创建热门识典百科词条!

网络已经成为人们获取知识和信息的主要途径。在这样一个背景下&#xff0c;识典百科作为一个综合性的网络百科全书&#xff0c;在为读者们提供各种知识的同时&#xff0c;也给广大用户提供了一个创建、编辑和分享知识的平台。如何在识典百科上创建一个高质量的词条&#xff0c;…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...