当前位置: 首页 > 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;…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

Vue3 PC端 UI组件库我更推荐Naive UI

一、Vue3生态现状与UI库选择的重要性 随着Vue3的稳定发布和Composition API的广泛采用&#xff0c;前端开发者面临着UI组件库的重新选择。一个好的UI库不仅能提升开发效率&#xff0c;还能确保项目的长期可维护性。本文将对比三大主流Vue3 UI库&#xff08;Naive UI、Element …...