贪心算法|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;
}
如图:

再确定左孩子大于右孩子的情况(从后向前遍历)
遍历顺序这里有同学可能会有疑问,为什么不能从前向后遍历呢?
因为 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]的糖果多。
如图:

所以该过程代码如下:
// 从后向前
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博客 三色标记产生的原因? 在并发标记的过程中,因为标记期间应用线程还在继续跑,对象间的引…...
怎么看有没有装python
windows系统,运行——cmd,进入dos窗口,输入python,安装成功的话可以看到版本信息并进入编程模式。 如下图(我安装的版本是python 3.5.1):...
VS CODE环境安装和hello world
SAP UI5 demo walkthrough tutorial step1 hello word 首先要安装nodejs,然后才能执行下面的操作 nodejs vscode 安装ui5 npm install --global ui5/cli报错解决: idealTree:npm: sill idealTree buildDeps 这个信息说明npm正在构建,如一直停留在这个…...
mysql性能索引调优易混点总结
文章目录 一、 前言二、explain相关三、索引优化相关联合索引索引下推排序和分组相关优化分页优化表关联优化嵌套循环连接 Nested-Loop Join(NLJ) 算法in和exsits优化 一、 前言 近几年看了很多和mysql相关的书,文章或视频,但仍然有一些点,看…...
区块链与数字身份:探索Facebook的新尝试
在数字化时代,随着区块链技术的崛起,数字身份成为了一个备受关注的话题。作为全球最大的社交媒体平台之一,Facebook一直在探索如何利用区块链技术来改善数字身份管理和用户数据安全。本文将深入探讨Facebook在这一领域的新尝试,探…...
【pycharm】在debug循环时,如何快速debug到指定循环次数
【pycharm】在debug循环时,如何快速debug到指定循环次数 【先赞后看养成习惯】求关注收藏点赞😀 在 PyCharm 中,可以使用条件断点来实现在特定循环次数后停止调试。这可以通过在断点处右键单击,然后选择 “Add Breakpoint” -&g…...
【蓝桥杯每日一题】4.8 公约数
题目来源: 4199. 公约数 - AcWing题库 问题描述: 找到最大整数x,需满足下面两个条件 x x x是 a a a, b b b的公约数 l < x < r l<x<r l<x<r 思路: 找到 a a a, b b b两个数的最大公约数 g c g c d (…...
【MySQL学习】MySQL的慢查询日志和错误日志
꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN …...
# C++之functional库用法整理
C之functional库用法整理 注:整理一些突然学到的C知识,随时mark一下 例如:忘记的关键字用法,新关键字,新数据结构 C 的function库用法整理 C之functional库用法整理一、functional库的内建仿函数1. 存储和调用函数2. 存…...
查看MySQL版本的方式
文章目录 一、使用cmd输入命令行查看二、在mysql客户端服务器里查询 一、使用cmd输入命令行查看 1、打开 cmd ,输入命令行: mysql --version 2、还是打开cmd,输入命令行:mysql -V (注意了,此时的V是个大写的V) 二、…...
k8s_入门_命令详解
命令详解 kubectl是官方的CLI命令行工具,用于与 apiserver进行通信,将用户在命令行输入的命令,组织并转化为 apiserver能识别的信息,进而实现管理k8s各种资源的一种有效途径 1. 帮助 2. 查看版本信息 3. 查看资源对象等 查看No…...
腾讯、阿里、字节….等大厂都更喜欢什么样的简历?
我985毕业,为什么筛选简历时输给了一个普通一本? 我投了20份简历,为什么没有一个大厂回我? 每次HR收到简历就没下文了,是我的简历有问题吗? 诚然,在求职时,简历往往就是我们给予H…...
OpenHarmony实战:帆移植案例(中)
OpenHarmony实战:帆移植案例(上) Audio服务介绍 服务节点 基于ADM框架的audio驱动对HDI层提供三个服务hdf_audio_render、hdf_audio_capture、hdf_audio_control。 开发板audio驱动服务节点如下: console:/dev # ls -al hdf_au…...
武汉星起航:创始人张振邦智慧领航,孵化伙伴共绘跨境新蓝图!
在风起云涌的跨境电商行业中,武汉星起航电子商务有限公司如同一颗璀璨的明星,引领着众多创业者迈向成功的彼岸。而这一切的背后,都离不开公司创始人张振邦先生的卓越领导与深厚经验。他凭借着在电子商务行业多年的深耕与积累,为武…...
上下收缩、折叠面板
效果: 上下收缩、折叠面板,类似QQ好友列表那种。原理就是在一个布局中,通过button来实现一个独立widget的visible/disable 实现: 1.分组按钮 #ifndef EXPANDPANEL_H #define EXPANDPANEL_H#include <QWidget>class…...
XC7A35T-2FGG484 嵌入式FPGA现场可编程门阵列 Xilinx
XC7A35T-2FGG484 是一款由Xilinx(赛灵思)制造的FPGA(现场可编程门阵列)芯片 以下是XC7A35T-2FGG484 的主要参数: 1. 系列:Artix-7 2. 逻辑单元数量:33280个 3. 工艺技术:28nm 4. …...
淘宝订单API接口:电商业务自动化的新选择
淘宝订单API接口在电商业务自动化中扮演了至关重要的角色。首先,通过API接口,商家可以自动化地查询、创建、修改和删除订单,极大地提高了订单处理效率,减少了人工操作,降低了错误率。其次,商家可以实时获取…...
识典百科词条创建技巧,教你如何轻松创建热门识典百科词条!
网络已经成为人们获取知识和信息的主要途径。在这样一个背景下,识典百科作为一个综合性的网络百科全书,在为读者们提供各种知识的同时,也给广大用户提供了一个创建、编辑和分享知识的平台。如何在识典百科上创建一个高质量的词条,…...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
GitFlow 工作模式(详解)
今天再学项目的过程中遇到使用gitflow模式管理代码,因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存,无论是github还是gittee,都是一种基于git去保存代码的形式,这样保存代码…...
用递归算法解锁「子集」问题 —— LeetCode 78题解析
文章目录 一、题目介绍二、递归思路详解:从决策树开始理解三、解法一:二叉决策树 DFS四、解法二:组合式回溯写法(推荐)五、解法对比 递归算法是编程中一种非常强大且常见的思想,它能够优雅地解决很多复杂的…...
基于 HTTP 的单向流式通信协议SSE详解
SSE(Server-Sent Events)详解 🧠 什么是 SSE? SSE(Server-Sent Events) 是 HTML5 标准中定义的一种通信机制,它允许服务器主动将事件推送给客户端(浏览器)。与传统的 H…...
Excel 怎么让透视表以正常Excel表格形式显示
目录 1、创建数据透视表 2、设计 》报表布局 》以表格形式显示 3、设计 》分类汇总 》不显示分类汇总 1、创建数据透视表 2、设计 》报表布局 》以表格形式显示 3、设计 》分类汇总 》不显示分类汇总...
学习 Hooks【Plan - June - Week 2】
一、React API React 提供了丰富的核心 API,用于创建组件、管理状态、处理副作用、优化性能等。本文档总结 React 常用的 API 方法和组件。 1. React 核心 API React.createElement(type, props, …children) 用于创建 React 元素,JSX 会被编译成该函数…...
