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

如何使用多种算法解决LeetCode第135题——分发糖果问题

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容,和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣!

  • 推荐:数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
    在这里插入图片描述

  • 导航

    • LeetCode解锁1000题: 打怪升级之旅:每题都包括3-5种算法,以及详细的代码实现,刷题面试跳槽必备
    • 漫画版算法详解:通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读,看一遍就掌握
    • python源码解读:解读python的源代码与调用关系,快速提升代码质量
    • python数据分析可视化:企业实战案例:企业级数据分析案例与可视化,提升数据分析思维和可视化能力
    • 程序员必备的数学知识与应用:全面详细的介绍了工程师都必备的数学知识

期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️

题目描述

老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。你需要按照以下要求,帮助老师给这些孩子分发糖果:

  1. 每个孩子至少分到一个糖果。
  2. 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

你需要最少准备多少糖果。

示例 1:

输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:

输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果,这满足题目要求。

方法一:两次遍历法

解题步骤

  1. 创建一个糖果数组,初始化每个孩子的糖果数为 1。
  2. 从左到右遍历,如果当前孩子的评分高于前一个孩子,则当前孩子的糖果数设置为前一个孩子的糖果数加一。
  3. 从右到左遍历,如果当前孩子的评分高于后一个孩子,并且当前孩子的糖果数不大于后一个孩子的糖果数,则当前孩子的糖果数设置为后一个孩子的糖果数加一。
  4. 返回糖果数组的总和。

Python 示例

def candy(ratings):n = len(ratings)candies = [1] * n# 从左到右遍历for i in range(1, n):if ratings[i] > ratings[i - 1]:candies[i] = candies[i - 1] + 1# 从右到左遍历for i in range(n - 2, -1, -1):if ratings[i] > ratings[i + 1] and candies[i] <= candies[i + 1]:candies[i] = candies[i + 1] + 1return sum(candies)# Example usage
ratings = [1, 0, 2]
print(candy(ratings))  # Output: 5ratings = [1, 2, 2]
print(candy(ratings))  # Output: 4

算法分析

  • 时间复杂度:O(N),其中 N 是孩子的数量。需要遍历两次数组。
  • 空间复杂度:O(N),用于存储糖果数量的数组。

算法图解与说明

考虑 ratings = [1, 0, 2]初始化糖果数组:candies = [1, 1, 1]左到右遍历:
索引1: 1 (评分 0) <= 0 (评分 1), 无变化
索引2: 2 (评分 2) > 0 (评分 0), 更新 candies[2] = candies[1] + 1 = 2
结果: candies = [1, 1, 2]右到左遍历:
索引1: 0 (评分 1) > 0 (评分 1) 且 candies[1] <= candies[2], 无变化
索引0: 1 (评分 1) > 0 (评分 0), 更新 candies[0] = candies[1] + 1 = 2
结果: candies = [2, 1, 2]总糖果数: 2 + 1 + 2 = 5

方法二:单次遍历法

解题步骤

  1. 创建一个糖果数组,初始化每个孩子的糖果数为 1。
  2. 使用一个标记数组来记录相邻孩子之间的关系(评分高的标记为 1,评分低的标记为 -1,相等标记为 0)。
  3. 单次遍历,根据标记调整糖果数,确保所有条件都满足。
  4. 返回糖果数组的总和。

Python 示例

def candy(ratings):n = len(ratings)if n == 0:return 0if n == 1:return 1candies = [1] * nfor i in range(1, n):if ratings[i] > ratings[i - 1]:candies[i] = candies[i - 1] + 1for i in range(n - 2, -1, -1):if ratings[i] > ratings[i + 1]:candies[i] = max(candies[i], candies[i + 1] + 1)return sum(candies)# Example usage
ratings = [1, 0, 2]
print(candy(ratings))  # Output: 5ratings = [1, 2, 2]
print(candy(ratings))  # Output: 4

算法分析

  • 时间复杂度:O(N),其中 N 是孩子的数量。需要遍历两次数组。
  • 空间复杂度:O(1),只使用了常数级别的额外空间。

算法图解与说明

考虑 ratings = [1, 0, 2]初始化糖果数组:candies = [1, 1, 1]单次遍历:
从左到右遍历:
索引1: 1 (评分 0) <= 0 (评分 1), 无变化
索引2: 2 (评分 2) > 0 (评分 0), 更新 candies[2] = candies[1] + 1 = 2
结果: candies = [1, 1, 2]从右到左遍历:
索引1: 0 (评分 1) > 0 (评分 1) 且 candies[1] <= candies[2], 无变化
索引0: 1 (评分 1) > 0 (评分 0), 更新 candies[0] = candies[1] + 1 = 2
结果: candies = [2, 1, 2]总糖果数: 2 + 1 + 2 = 5

这两种方法都能有效地解决分发糖果的问题,确保每个孩子至少得到一颗糖果,并且评分更高的孩子比相邻孩子获得更多糖果。选择哪种方法可以根据具体场景和个人喜好而定。

🌹🌹如果觉得这篇文对你有帮助的话,记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励,非常感谢 ❥(^_-)

❤️❤️作者知识有限,如有错误,请各位大佬评论区批评指正,不胜感激❥(^_-)
在这里插入图片描述

相关文章:

如何使用多种算法解决LeetCode第135题——分发糖果问题

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容&#xff0c;和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣&#xff01; 推荐&#xff1a;数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注 导航&#xff1a; LeetCode解锁100…...

泰拉瑞亚从零开始的开服教程

前言 本教程将讲诉使用Linux系统搭建泰拉瑞亚服务器&#xff08;因为网上已经有很完善的windows开服教程了&#xff09;&#xff0c;使用的Linux发行版是Debian11,服务端使用的程序是TShock&#xff0c;游戏版本是1.4.4.9 所需要准备的 一台服务器&#xff08;本教程使用的是…...

【云原生】K8s管理工具--Kubectl详解(一)

一、陈述式管理 1.1、陈述式资源管理方法 kubernetes 集群管理集群资源的唯一入口是通过相应的方法调用 apiserver 的接口kubectl 是官方的 CLI 命令行工具&#xff0c;用于与 apiserver 进行通信&#xff0c;将用户在命令行输入的命令&#xff0c;组织并转化为apiserver 能识…...

2024.5.26.python.exercise

# # 导入包 # from pyecharts.charts import Bar, Timeline # from pyecharts.options import LabelOpts, TitleOpts # from pyecharts.globals import ThemeType # # # 从文件中读取信息 # GDP_file open("1960-2019全球GDP数据.csv", "r", encoding&quo…...

代码随想录-Day20

654. 最大二叉树 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建: 创建一个根节点&#xff0c;其值为 nums 中的最大值。 递归地在最大值 左边 的 子数组前缀上 构建左子树。 递归地在最大值 右边 的 子数组后缀上 构建右子树。 返回 nums…...

揭秘C++ String容器:字符串操作的艺术

目录 ​编辑 引言 一、初识std::string&#xff1a;构造与初始化 二、字符串的操纵艺术&#xff1a;拼接、查找与替换 三、访问与遍历&#xff1a;字符的细腻触感 四、大小与容量&#xff1a;动态调整的智慧 五、进阶功能&#xff1a;探索更多可能 结语 引言 在C标准库…...

【C++】牛客 ——DP36 abb

✨题目链接&#xff1a; DP36 abb ✨题目描述 leafee 最近爱上了 abb 型语句&#xff0c;比如“叠词词”、“恶心心” leafee 拿到了一个只含有小写字母的字符串&#xff0c;她想知道有多少个 "abb" 型的子序列&#xff1f; 定义&#xff1a; abb 型字符串满足以下…...

SpringBoot如何实现跨域?

定义一个配置类&#xff0c;实现WebMvcConfigurer接口&#xff0c;重写addCorsMappings方法 Configuration public class CorsConfig implements WebMvcConfigurer {Overridepublic void addCorsMappings(CorsRegistry registry) {registry.addMapping("/**").allow…...

SW 草图偏移 先预选

因为有些不能用链全部选,可以先框选要偏移的,再点偏移命令...

5.23 Linux中超时检测方式+模拟面试

1.IO多路复用的原理&#xff1f; IO多路复用使得一个或少量线程资源处理多个连接的IO事件的技术。对于要处理的多个阻塞的IO操作&#xff0c;建立集合并存储它们的文件描述符&#xff0c;利用单个阻塞函数去监控集合中文件描述符事件到达的情况&#xff0c;&#xff08;如果到…...

MySQL数据表索引命名规范

在数据库设计和开发过程中&#xff0c;索引是提高查询性能的重要工具。合理的索引命名规范不仅能提高代码的可读性&#xff0c;还能便于维护和管理。本文将详细介绍MySQL数据表索引的命名规范&#xff0c;包括不同类型索引的命名方法&#xff0c;并提供多个代码示例以说明如何命…...

python内置函数map/filter/reduce详解

在Python中&#xff0c;map(), filter(), 和 reduce() 是内置的高级函数(实际是class)&#xff0c;用于处理可迭代对象&#xff08;如列表、元组等&#xff09;的元素。这些函数通常与lambda函数一起使用&#xff0c;以简洁地表达常见的操作。下面我将分别解释这三个函数。 1. …...

PICO VR眼镜定制播放器使用说明文档videoplayerlib-ToB.apk

安装高级定制播放器 高级定制播放器下载地址:https://download.csdn.net/download/ahphong/89360454 仅限用于PICO G2、G3、G4、NEO系列VR眼镜上使用, 用途:用于第三方APP(开发者)调用定制播放器播放2D、3D、180、360全景视频。 VR眼镜系统请升级到最新版,可在官网下载,…...

基于51单片机的超声波液位测量与控制系统

基于51单片机液位控制器 &#xff08;仿真&#xff0b;程序&#xff0b;原理图PCB&#xff0b;设计报告&#xff09; 功能介绍 具体功能&#xff1a; 1.使用HC-SR04测量液位&#xff0c;LCD1602显示&#xff1b; 2.当水位高于设定上限的时候&#xff0c;对应声光报警报警&am…...

详细分析Element中的MessageBox基本知识(附Demo)

目录 前言1. 基本知识2. Demo2.1 确认框2.2 警告框2.3 对话框 3. this.$confirm 前言 详细知识推荐阅读&#xff1a;详细分析Element Plus中的ElMessageBox弹窗用法&#xff08;附Demo及模版&#xff09; MessageBox则常用于Vue2 1. 基本知识 MessageBox 是 Element UI 提供…...

音视频开发8 音视频中SDL的使用,SDL 在windows上环境搭建,SDL 使用 以及 常用 API说明,show YUV and play PCM

1.SDL简介 SDL&#xff08;Simple DirectMedia Layer&#xff09;&#xff0c;是一个跨平台的C语言多媒体开发库。 支持Windows、Mac OS X、Linux、iOS、Android 提供对音频、键盘、鼠标、游戏操纵杆、图形硬件的底层访问 很多的视频播放软件、模拟器、受欢迎的游戏都在使用…...

P1003 [NOIP2011 提高组] 铺地毯

题目传送门&#xff1a; P1003 [NOIP2011 提高组] 铺地毯 AC代码&#xff1a; #include<bits/stdc.h>using namespace std;int a[10005],b[10005],g[10005],k[10004];int main() {int n,x,y;cin>>n;for(int i1;i<n;i) cin>>a[i]>>b[i]>>g[…...

C语言学习笔记之指针(一)

目录 什么是指针&#xff1f; 指针和指针类型 指针的类型 指针类型的意义 指针-整数 指针的解引用 指针 - 指针 指针的关系运算 野指针 什么是野指针&#xff1f; 野指针的成因 如何规避野指针&#xff1f; 二级指针 什么是指针&#xff1f; 在介绍指针之前&#…...

化学中的不确定性。

化学中的不确定性TOC 基于元素分析的无机化学的理论大厦应该说早已落成了&#xff0c;但是却仍然存在着一些列的难解甚至是无解问题&#xff0c;这些大多是在使用理论解释现象时遇到的困难&#xff0c;有些则是在生产实践中生产工艺和生产工序设计和优化中发现的问题。于是&…...

AWS容器之Fargate

AWS Fargate是亚马逊提供的一种容器管理服务&#xff0c;它允许开发人员在AWS云中轻松运行容器化应用程序&#xff0c;而无需管理底层的服务器基础架构。Fargate可以自动管理容器的部署、扩展和负载平衡&#xff0c;并提供了与ECS和EKS等AWS容器服务集成的能力。适用于容器的无…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...