Leetcode—135. 分发糖果【中等】

2024每日刷题(113)

Leetcode—135. 分发糖果

在这里插入图片描述

算法思想

这里可以利用贪心策略,求局部最优解,然后合并为全局最优解。具体来说,将原问题中相邻孩子的条件划分为左相邻孩子和右相邻孩子两个条件,依次求解出两个条件下每个孩子所需要的最小糖果数。

在只考虑左相邻孩子的条件下,如果一个孩子比左边孩子的评分高,要求得到比左边孩子更多的糖果,为了降低总体的糖果数量,分配给这个孩子的最小糖果数是左边孩子的糖果数+1;反之则只分配1个糖果。由于每个孩子得到的糖果数量取决于左相邻的孩子,应该从左向右依次遍历每个孩子。

在只考虑右相邻孩子的条件下,如果一个孩子比右边孩子的评分高,要求得到比右边孩子更多的糖果,为了降低总体的糖果数量,分配给这个孩子的最小糖果数是右边孩子的糖果数+1;反之,则只分配1个糖果。由于每个孩子得到的糖果数量取决于右相邻的孩子,应该从右向左依次遍历每个孩子。

只考虑左相邻孩子条件的图示如下
在这里插入图片描述
最后将两种条件的结果合并,分配给每个孩子的糖果数为两个条件下的最大值,即同时满足两个条件,才能达到全局最优解。

在这里插入图片描述

实现代码

class Solution {
public:int candy(vector<int>& ratings) {int n = ratings.size();int ans = 0;vector<int> l(n, 1);vector<int> r(n, 1);for(int i = 1; i < n; i++) {if(ratings[i] > ratings[i - 1]) {l[i] = l[i - 1] + 1;}}for(int i = n - 2; i >= 0; i--) {if(ratings[i] > ratings[i + 1]) {r[i] = r[i + 1] + 1;}}for(int i = 0; i < n; i++) {ans += max(l[i], r[i]);}return ans;}
};

运行结果

在这里插入图片描述
之后我会持续更新,如果喜欢我的文章,请记得一键三连哦,点赞关注收藏,你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 !!!↖(▔▽▔)↗感谢支持!

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

Phobos捆绑某数控软件AdobeIPCBroker组件定向勒索

前言 Phobos勒索病毒最早于2019年被首次发现并开始流行起来&#xff0c;该勒索病毒的勒索提示信息特征与CrySiS(Dharma)勒索病毒非常相似&#xff0c;但是两款勒索病毒的代码特征却是完全不一样&#xff0c;近日笔者在逛某开源恶意软件沙箱的时候发现了一款Phobos勒索病毒捆绑…

应用层DoS

应用层&#xff08;application layer&#xff09;是七层OSI模型的第七层。应用层直接和应用程序 对接并提供常见的网络应用服务&#xff0c;能够在实现多个系统应用进程相互通信的同 时&#xff0c;完成一系列业务处理所需的服务。位于应用层的协议有很多&#xff0c;常见的包…

【已解决】:pip is configured with locations that require TLS/SSL

在使用pip进行软件包安装的时候出现问题&#xff1a; WARNING: pip is configured with locations that require TLS/SSL, however the ssl module in Python is not available. 解决&#xff1a; mkdir -p ~/.pip vim ~/.pip/pip.conf然后输入内容&#xff1a; [global] ind…

07-OpenFeign-HTTP压缩优化

gzip是一种数据格式&#xff0c;采用用deflate算法压缩数据&#xff1b;gzip是一种流行的数据压缩算法&#xff0c;应用十分广泛&#xff0c;尤其是在Linux平台。 当GZIP压缩到一个纯文本数据时&#xff0c;效果是非常明显的&#xff0c;大约可以减少70&#xff05;以上的数据…

第九个知识点:内部对象

Date对象: <script>var date new Date();date.getFullYear();//年date.getMonth();//月date.getDate();//日date.getDay();//星期几date.getHours();//时date.getMinutes();//分date.getSeconds();//秒date.getTime();//获取时间戳&#xff0c;时间戳时全球统一&#x…

C++力扣题目494--目标和 474--一和零

494.目标和 力扣题目链接(opens new window) 难度&#xff1a;中等 给定一个非负整数数组&#xff0c;a1, a2, ..., an, 和一个目标数&#xff0c;S。现在你有两个符号 和 -。对于数组中的任意一个整数&#xff0c;你都可以从 或 -中选择一个符号添加在前面。 返回可以使…

Backtrader 文档学习- Plotting

Backtrader 文档学习- Plotting 虽然回测是一个基于数学计算的自动化过程&#xff0c;还是希望实际通过可视化验证。无论是使用现有算法回测&#xff0c;还是观察数据驱动的指标&#xff08;内置或自定义&#xff09;。 凡事都要有人完成&#xff0c;绘制数据加载、指标、操作…

PostgreSql与Postgis安装

POstgresql安装 1.登录官网 PostgreSQL: Linux downloads (Red Hat family) 2.选择版本 3.安装 ### 源 yum install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-7-x86_64/pgdg-redhat-repo-latest.noarch.rpm ### 客户端 yum install postgresql14 ###…

Java面向对象 继承

目录 继承继承的好处继承具有传递性实例创建Person类Student继承Person类测试 继承 Java中的继承是面向对象编程的一个核心特性&#xff0c;它允许一个类&#xff08;子类或派生类&#xff09;继承另一个类&#xff08;父类或基类&#xff09;的属性和方法。通过继承&#xff0…

【HarmonyOS应用开发】HTTP数据请求(十四)

文章末尾含相关内容源代码 一、概述 日常生活中我们使用应用程序看新闻、发送消息等&#xff0c;都需要连接到互联网&#xff0c;从服务端获取数据。例如&#xff0c;新闻应用可以从新闻服务器中获取最新的热点新闻&#xff0c;从而给用户打造更加丰富、更加实用的体验。 那么…

【Spring】GoF 之工厂模式

一、GoF 23 设计模式简介 设计模式&#xff1a;一种可以被重复利用的解决方案 GoF&#xff08;Gang of Four&#xff09;&#xff0c;中文名——四人组 《Design Patterns: Elements of Reusable Object-Oriented Software》&#xff08;即《设计模式》一书&#xff09;&…

JavaEE作业-实验三

目录 1 实验内容 2 实验要求 3 思路 4 核心代码 5 实验结果 1 实验内容 简单的线上图书交易系统的web层 2 实验要求 ①采用SpringMVC框架&#xff0c;采用REST风格 ②要求具有如下功能&#xff1a;商品分类、订单、购物车、库存 ③独立完成&#xff0c;编写实验报告 …

Unity2D 学习笔记 0.Unity需要记住的常用知识

Unity2D 学习笔记 0.Unity需要记住的常用知识 前言调整Project SettingTilemap相关&#xff08;创建地图块&#xff09;C#脚本相关程序运行函数private void Awake()void Start()void Update() Collider2D碰撞检测private void OnTriggerStay2D(Collider2D player)private void…

猫头虎分享已解决Bug || docker: Error response from daemon: network not found

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …

基于华为云欧拉操作系统(HCE OS)单节点容器化部署(Prometheus、node-exporter、Grafana)应用性能监控平台

写在前面 博文内容为 华为云欧拉操作系统入门级开发者认证(HCCDA – Huawei Cloud EulerOS)实验笔记整理认证地址&#xff1a;https://edu.huaweicloud.com/certificationindex/developer/9bf91efb086a448ab4331a2f53a4d3a1内容涉及&#xff0c;HCE OS 容器化部署(Prometheus、…

分布式springboot 3项目集成mybatis官方生成器开发记录

文章目录 说明实现思路实现步骤第一步&#xff1a;创建generator子模块第二步&#xff1a;引入相关maven插件和依赖第三步&#xff1a;编写生成器配置文件第四步&#xff1a;运行查看结果 说明 该文章为作者开发学习记录&#xff0c;方便以后复习和交流主要内容为&#xff1a;…

【精选】java继承进阶——构造方法的访问特点 this、super使用

&#x1f36c; 博主介绍&#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 hacker-routing &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【应急响应】 【python】 【VulnHub靶场复现】【面试分析】 &#x1f389;点赞➕评论➕收藏…

算法导论 总结索引 | 第一部分 第三章:函数的增长

研究算法的 渐近效率 1、渐近记号&#xff08;40&#xff09; 1、Θ&#xff1a; 使得 对于足够大的n&#xff0c;函数 f(n) 能 夹入 c1g(n) 与 c2g(n) 之间&#xff0c;则 f(n) ∈ 集合Θ(g(n)) g(n) 是 f(n) 的一个渐近紧确界 g(n)本身 必为渐近非负 使用 Θ(1) 来意指 …

【Spring源码解读!底层原理进阶】【下】探寻Spring内部:BeanFactory和ApplicationContext实现原理揭秘✨

&#x1f389;&#x1f389;欢迎光临&#x1f389;&#x1f389; &#x1f3c5;我是苏泽&#xff0c;一位对技术充满热情的探索者和分享者。&#x1f680;&#x1f680; &#x1f31f;特别推荐给大家我的最新专栏《Spring 狂野之旅&#xff1a;底层原理高级进阶》 &#x1f680…

[超分辨率重建]ESRGAN算法训练自己的数据集过程

一、下载数据集及项目包 1. 数据集 1.1 文件夹框架的介绍&#xff0c;如下图所示&#xff1a;主要有train和val&#xff0c;分别有高清&#xff08;HR&#xff09;和低清&#xff08;LR&#xff09;的图像。 1.2 原图先通过分割尺寸的脚本先将数据集图片处理成两个相同的图像…