135. 分发糖果(力扣LeetCode)

文章目录

  • 135. 分发糖果
    • 题目描述
    • 贪心算法
      • 代码如下
    • 总结

135. 分发糖果

题目描述

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求,给这些孩子分发糖果:

  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目 。

示例 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

贪心算法

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

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

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

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

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

代码如下

这段代码是解决了一个分发糖果的问题,确保每个孩子根据自己的评分获得适当数量的糖果,同时满足相邻两个孩子之间评分高的孩子获得更多糖果的规则。下面是这段代码的详细注释:

class Solution {
public:
    int candy(vector<int>& ratings) {
        // 1. 初始化一个与评分数组等长的糖果数组,每个孩子先分配1个糖果
        vector<int> sum(ratings.size(),1);
        // 用于记录需要分发的糖果总数
        int num=0;

        // 2. 从左向右遍历,确保每个孩子比其左边评分低的孩子获得更多糖果
        for(int i=0;i<ratings.size()-1;i++)
        {
            // 如果右边孩子的评分比左边的高,则右边孩子的糖果数为左边孩子的糖果数加1
            if(ratings[i+1]>ratings[i])
                sum[i+1]=sum[i]+1;
        }

        // 3. 从右向左遍历,确保每个孩子比其右边评分低的孩子获得更多糖果
        for(int i=ratings.size()-1-1;i>=0;i--)
        {
            // 如果左边孩子的评分比右边的高,且左边孩子目前的糖果数不多于右边孩子,
            // 则左边孩子的糖果数更新为右边孩子的糖果数加1
            if(ratings[i]>ratings[i+1])
                sum[i]=max(sum[i+1]+1,sum[i]);
        }

        // 4. 计算总糖果数
        for(int i=0;i<ratings.size();i++)
            num+=sum[i];
        
        // 返回总糖果数
        return num;
    }
};

这个算法实际上是进行了两次贪心算法的应用:第一次遍历保证了每个孩子都至少比他左边评分低的孩子多一个糖果;第二次遍历则保证了每个孩子都至少比他右边评分低的孩子多一个糖果。这样,就同时满足了题目中的两个条件,而且保证了使用的糖果数目最少。

总结

这在leetcode上是一道困难的题目,其难点就在于贪心的策略,如果在考虑局部的时候想两边兼顾,就会顾此失彼。

那么本题我采用了两次贪心的策略:

  • 一次是从左到右遍历,只比较右边孩子评分比左边大的情况。
  • 一次是从右到左遍历,只比较左边孩子评分比右边大的情况。

这样从局部最优推出了全局最优,即:相邻的孩子中,评分高的孩子获得更多的糖果。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Leetcode - 周赛389

目录 一&#xff0c;3083. 字符串及其反转中是否存在同一子字符串 二&#xff0c;3084. 统计以给定字符开头和结尾的子字符串总数 三&#xff0c;3085. 成为 K 特殊字符串需要删除的最少字符数 四&#xff0c;3086. 拾起 K 个 1 需要的最少行动次数 一&#xff0c;3083. 字符…

Java的三大特性之一——继承

前言 http://t.csdnimg.cn/uibg3 在上一篇中我们已经讲解过封装&#xff0c;这里就主要讲解继承与多态 继承 1.为什么需要继承 Java中使用类对现实世界中实体来进行描述&#xff0c;类经过实例化之后的产物对象&#xff0c;则可以用来表示现实中的实体&#xff0c;但是现实…

centos7安装jdk详细步骤(yum安装与手动安装)

centos7安装jdk详细步骤&#xff08;yum安装与手动安装&#xff09; 一、使用yum安装1. 准备工作2. 检查系统是否自带jdk3. 安装jdk 二、手动安装jdk1. 下载上传jdk2. 安装jdk3. 配置环境变量 一、使用yum安装 1. 准备工作 如果你的机器可以联网可以使用此方法 ping www.baidu…

2、Java虚拟机之类的生命周期-连接(验证、准备、解析)

一、类的生命周期 连接阶段之验证 连接阶段的第一个环节是验证&#xff0c;验证的主要目的是检测Java字节码文件是否遵守了<Java虚拟机规范>中的约束。这个阶段一般是不需要程序员进行处理。 主要包含如下四个部分,具体详见<<Java虚拟机规范>>: 1、文件格…

mysql+keepalived实现对mysql的高可用

mysql数据库出现问题 133 解决方案: 在133mysql终端 实行如下命令 mysqlkeepalived实现对mysql的高可用 132 keepalived配置如下 133 keepalived配置如下 132重启keepalived服务 132关闭mysqld服务&#xff0c;vip不见了 133收到vip 132重启mysqld服务和keepalived服务,vip…

C语言——程序拷贝文件

问题如下&#xff1a; 写一个程序拷贝文件&#xff1a; 使用所学文件操作&#xff0c;在当前目录下放一个文件data.txt&#xff0c;写一个程序&#xff0c;将data.txt文件拷贝一份&#xff0c;生成data_copy.txt文件。 基本思路&#xff1a; 打开文件data.txt&#xff0c;读…

PTA题解 --- 剪切粘贴(C语言)

今天是PTA题库解法讲解的第五天&#xff0c;今天我们要讲解剪切粘贴&#xff0c;题目如下&#xff1a; 解题思路&#xff1a; 为了解决这个问题&#xff0c;你可以按照以下步骤进行&#xff1a; 读取输入字符串&#xff1a;首先读取原始字符串。 进行操作&#xff1a;根据输入…

【网络】数据中心网络技术概览

数据中心网络技术概览 一、数据中心网络架构 Crossbar架构&#xff1a;源自早期电话交换网络&#xff0c;由多个输入/输出端口和开关矩阵组成&#xff0c;实现设备间的任意连接&#xff0c;灵活且高效。 **Crossbar架构&#xff08;Crossbar Architecture&#xff09;是一种计…

springboot+vue考试管理系统

基于springboot和vue的考试管理系统 001 springboot vue前后端分离项目 本文设计了一个基于Springbootvue的前后端分离的在线考试管理系统&#xff0c;采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&…

000_coolprop_in_matlab在Matlab中使用CoolProp

在Matlab中使用CoolProp 简介 CoolProp是一个开源的热力学性质库&#xff0c;可以计算多种流体的热力学性质。CoolProp支持多种编程语言&#xff0c;包括Python、C、Matlab等。本文将介绍如何在Matlab中使用CoolProp。 CoolProp官网 本文所使用的Matlab版本为R2021a。 在Ma…

大数据分析-基于Python的网络爬虫及数据处理---智联招聘人才招聘特征分析与挖掘的算法实现

概要 随着科学技术的发展&#xff0c;人类进入了互联网时代&#xff0c;不仅数据量庞大&#xff0c;而且数据种类繁多&#xff0c;Python简单易学, 语法清晰&#xff0c;在数据操作方面有着一定优势&#xff0c;成为了数据采集和可视化领域的热门语言。本论文主要是使用Python来…

SG5032VAN差分晶振X1G004261001100专用于5G通讯设备

差分晶体振荡器(DXO)是目前行业中公认高技术&#xff0c;高要求的一款晶体振荡器&#xff0c;是指输出差分信号使用2种相位彼此完全相反的信号,从而消除了共模噪声,并产生一个更高性能的系统。差分晶振一般为六脚贴片晶振&#xff0c;输出类型分为好几种,LVDS&#xff0c;LV-PE…

MySQL | 视图

视图是一个虚拟表&#xff0c;其内容由查询定义。同真实的表一样&#xff0c;视图包含一系列带有名称的列和行数据。视图的数据变化会影响到基表&#xff0c;基表的数据变化也会影响到视图。 1. 基本使用 1.1. 创建视图 create view 视图名 as select语句&#xff1b; 创建测…

(2023,图像放大与超分辨率,扩散,缩放堆叠表示,多分辨率混合,多尺度联合抽样)Ten 的生成能力

Generative Powers of Ten 公和众和号&#xff1a;EDPJ&#xff08;进 Q 交流群&#xff1a;922230617 或加 VX&#xff1a;CV_EDPJ 进 V 交流群&#xff09; 目录 0. 摘要 2. 相关工作 4. 方法 4.1. 缩放堆叠表示 4.2. 多分辨率混合 4.3. 多尺度一致抽样 4.4. 基于照片…

全球大型语言模型(LLMS)现状与比较

我用上个博文的工具将一篇ppt转换成了图片&#xff0c;现分享给各位看官。 第一部分&#xff1a;国外大语言模型介绍 1&#xff0c;openai的Chatgpt 免费使用方法1&#xff1a;choose-carhttps://share.freegpts.org/list 免费使用方法2&#xff1a;Shared Chathttps://share…

查看文件内容的指令:cat,tac,nl,more,less,head,tail.file

目录 cat 介绍 输入重定向 选项 -b -n -s tac 介绍 输入重定向 nl 介绍 示例 more 介绍 选项 less 介绍 搜索文本 选项 head 介绍 示例 选项 -n tail 介绍 示例 选项 file cat 介绍 将标准输入(键盘输入)的内容打印到标准输出: 输入重定向 本应…

Docker 存储

目录 1、概念介绍 Storage Driver 无状态容器 有状态容器 Data Volume 2、bind mount 指定挂载文件只读权限 bind mount 挂载目录 3、docker manage volume 查看 volume 自定义 volume 使用 NFS 存储 4、共享数据 容器与host共享数据 volume container data-pa…

200基于matlab的利用神经网络算法训练图片

基于matlab的利用神经网络算法训练图片&#xff0c;并利用GUI界面读取图片&#xff0c;最后将识别出的图片数值返回到GUI界面上。0-10数字数据库已有&#xff0c;可自行添加其他数据库进行训练和识别。程序已调通&#xff0c;可直接运行。 200 matlab BP神经网络 手写数字识别 …

liunx centos7 下通过yum删除安装已经安装的php

执行下面命令查看php相关的包 rpm -qa | grep php 只需要卸载几个名为common的包即可&#xff0c;其他同版本依赖会被全部删除&#xff0c;删除php71w-common&#xff0c;71w版本的依赖包全部会被删除。 查看php包的命令 rpm -qa | grep php 或 yum list installed | gre…

单引号 vs 双引号:在MyBatis条件判断中的选择困境

哈喽&#xff0c;大家好呀&#xff0c;好久不见&#xff01;今天是一篇浅记。MyBatis的条件判断中&#xff0c;使用单引号或双引号来判定字符串类型数值的坑… 一、单引号与双引号的区别 在MyBatis的条件判断中&#xff0c;使用单引号或双引号来括起字符串值都是可以的。但是在…