分发糖果,Java经典算法编程实战。

🏆作者简介,普修罗双战士,一直追求不断学习和成长,在技术的道路上持续探索和实践。
🏆多年互联网行业从业经验,历任核心研发工程师,项目技术负责人。
🎉欢迎 👍点赞✍评论⭐收藏

算法专栏学习
| 题目 | 访问地址 | 专栏 |
|---|---|---|
| 分发糖果 | https://blog.csdn.net/m0_50308467/article/details/135343315 | 算法专栏 |
经典算法题 之 分发糖果

题目如下:
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求,给这些孩子分发糖果:
- 每个孩子至少分配到
1个糖果。 - 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目 。
解答这道题,可以使用
贪心算法进行解决。
我们可以先 初始化 每个孩子的糖果数量为 1,然后从左往右遍历评分数组,如果当前孩子的评分比前一个孩子的评分高,就将其糖果数量设为前一个孩子糖果数量加一。这样可以确保相邻两个评分高的孩子分配到的糖果数量相差至少为1。
但是我们还需要从右往左遍历一遍评分数组,来处理相邻两个评分高的孩子分配到的糖果数量相等的情况。如果当前孩子的评分比后一个孩子的评分高,且当前孩子的糖果数量不大于后一个孩子的糖果数量,就将其糖果数量设为后一个孩子糖果数量加一。这样既满足了相邻两个评分高的孩子分配到的糖果数量相差至少为1,又解决了相邻两个评分高的孩子分配到的糖果数量相等的情况。
最后,我们把每个孩子的糖果数量累加起来,就可以得到需要准备的最少糖果数目。
具体实现逻辑如下:
1. 首先创建一个与评分数组大小相同的糖果数组,初始化为1,表示每个孩子至少分配到一个糖果。
2. 从左到右遍历评分数组,如果当前孩子的评分比前一个孩子高,那么将当前孩子的糖果数目设为前一个孩子糖果数目加1。
3. 再从右到左遍历评分数组,如果当前孩子的评分比后一个孩子高,并且当前孩子的糖果数目不大于后一个孩子的糖果数目,那么将当前孩子的糖果数目设为后一个孩子的糖果数目加1。
4. 最后计算糖果数组的总和,即为最少糖果数目。
以下是一个Java代码实现:
public class DistributeCandies {public static int distributeCandies(int[] ratings) {int n = ratings.length;int[] candies = new int[n];Arrays.fill(candies, 1); // 初始化糖果数组,每个孩子至少分配到一个糖果// 从左到右遍历调整糖果分配for (int i = 1; i < n; i++) {if (ratings[i] > ratings[i-1]) {candies[i] = candies[i-1] + 1;}}// 从右到左遍历调整糖果分配for (int i = n - 2; i >= 0; i--) {if (ratings[i] > ratings[i+1] && candies[i] <= candies[i+1]) {candies[i] = candies[i+1] + 1;}}// 统计总的糖果数int sum = 0;for (int candy : candies) {sum += candy;}return sum;}// 示例调用public static void main(String[] args) {int[] ratings = {1,0,2};System.out.println(distributeCandies(ratings)); // 输出3}
}
在这个示例中,distributeCandies() 方法接收一个评分数组 ratings ,并返回需要准备的最少糖果数目。
首先,我们使用一个长度为 n 的数组 candies 来保存每个孩子的糖果数量,初始值都为 1。
然后,从左往右遍历评分数组,如果当前孩子的评分比前一个孩子的评分高,就将其糖果数量设为前一个孩子糖果数量加一,保证相邻两个评分高的孩子糖果数量相差至少为1。
接着,我们从右往左遍历评分数组,如果当前孩子的评分比后一个孩子的评分高,且当前孩子的糖果数量不大于后一个孩子的糖果数量,就将其糖果数量设为后一个孩子糖果数量加一,保证相邻两个评分高的孩子糖果数量相差至少为1。
最后,我们把每个孩子的糖果数量累加起来,得到需要准备的最少糖果数目。
在 main() 方法中,我们提供了一个简单的测试案例,将评分数组设为 [1,0,2],调用 distributeCandies() 方法进行计算,期望的输出为3。

相关文章:
分发糖果,Java经典算法编程实战。
🏆作者简介,普修罗双战士,一直追求不断学习和成长,在技术的道路上持续探索和实践。 🏆多年互联网行业从业经验,历任核心研发工程师,项目技术负责人。 🎉欢迎 👍点赞✍评论…...
鸿蒙原生应用再添新丁!中国移动 入局鸿蒙
鸿蒙原生应用再添新丁!中国移动 入局鸿蒙 来自 HarmonyOS 微博1月2日消息,#中国移动APP启动鸿蒙原生应用开发#,拥有超3亿用户的中国移动APP宣布,正式基于HarmonyOS NEXT启动#鸿蒙原生应用#及元服务开发。#HarmonyOS#系统的分布式…...
一个人能不能快速搭建一套微服务环境
一、背景 大型软件系统的开发现在往往需要多人的协助,特别是前后端分离的情况下下,分工越来越细,那么一个人是否也能快速搭建一套微服务系统呢? 答案是能的。看我是怎么操作的吧。 二、搭建过程 1、首先需要一套逆向代码生成工…...
计算机毕业设计------经贸车协小程序
项目介绍 本项目分为三种用户类型,分别是租赁者,车主,管理员用户; 管理员用户包含以下功能: 管理员登录,个人中心,租赁者管理,车主管理,赛事活动管理,车类别管理,租车管理,租车订单管理,车辆出售管理,购买订单管理,…...
数据结构OJ实验11-拓扑排序与最短路径
A. DS图—图的最短路径(无框架) 题目描述 给出一个图的邻接矩阵,输入顶点v,用迪杰斯特拉算法求顶点v到其它顶点的最短路径。 输入 第一行输入t,表示有t个测试实例 第二行输入顶点数n和n个顶点信息 第三行起&…...
你的第一个JavaScript程序
JavaScript,即JS,JavaScript是一种具有函数优先的轻量级,解释型或即时编译型的编程语言。虽然它是作为开发Web页面的脚本语言而出名,但是它也被用到了很多非浏览器环境中,JavaScript基于原型编程、多范式的动态脚本语言…...
CMake入门教程【基础篇】列表操作(list)
文章目录 1. 定义列表2. 获取列表长度3. 获取列表元素4. 追加元素到列表末尾5. 插入元素到指定位置6. 移除指定位置的元素7. 移除指定值的元素8. 替换指定位置的元素9. 迭代列表元素 #mermaid-svg-IAjFPWI6IXEGYmuU {font-family:"trebuchet ms",verdana,arial,sans-…...
普中STM32-PZ6806L开发板(HAL库函数实现-读取内部温度)
简介 主芯片STM32F103ZET6,读取内部温度其他知识 内部温度所在ADC通道 温度计算公式 V25跟Avg_Slope值 参考文档 stm32f103ze.pdf 电压计算公式 Vout Vref * (D / 2^n) 其中Vref代表参考电压, n为ADC的位数, D为ADC输入的数字信号。 实现…...
普中STM32-PZ6806L开发板(使用过程中的问题收集)
Keil使用ST-Link 报错 Internal command error 描述: 在某一次使用过程中,前面都是正常使用, Keil在烧录时报错Internal command error, 试了网上的诸多方式, 例如 升级固件;ST-Link Utility 清除;Keil升级到最新版本;甚至笔者板子的Micro头也换了,因为坏…...
八股文打卡day12——计算机网络(12)
面试题:HTTPS的工作原理?HTTPS是怎么建立连接的? 我的回答: 1.客户端向服务器发起请求,请求建立连接。 2.服务器收到请求之后,向客户端发送其SSL证书,这个证书包含服务器的公钥和一些其他信息…...
自然语言处理2——轻松入门情感分析 - Python实战指南
目录 写在开头1.了解情感分析的概念及其在实际应用中的重要性1.1 情感分析的核心概念1.1.1 情感极性1.1.2 词汇和上下文1.1.3 情感强度1.2 实际应用中的重要性 2. 使用情感分析库进行简单的情感分析2.1 TextBlob库的基本使用和优势2.1.1 安装TextBlob库2.1.2 文本情感分析示例2…...
pygame学习(一)——pygame库的导包、初始化、窗口的设置、打印文字
导语 pygame是一个跨平台Python库(pygame news),专门用来开发游戏。pygame主要为开发、设计2D电子游戏而生,提供图像模块(image)、声音模块(mixer)、输入/输出(鼠标、键盘、显示屏)…...
前端面试
1. 什么是MVVM,MVC,MVP模型? 软件架构模式: MVC: M: 模型,拉取数据的类。 V: 视图,展现给用户的视觉效果。 C: 控制器,通知M拉取数据,并且给V。 > MV…...
Spring Boot快速搭建一个简易商城项目【完成登录功能且优化】
完成登录且优化: 未优化做简单的判断: 全部异常抓捕 优化:返回的是json的格式 BusinessException:所有的错误放到这个容器中,全局异常从这个类中调用 BusinessException: package com.lya.lyaspshop.exce…...
KG+LLM(一)KnowGPT: Black-Box Knowledge Injection for Large Language Models
论文链接:2023.12-https://arxiv.org/pdf/2312.06185.pdf 1.Background & Motivation 目前生成式的语言模型,如ChatGPT等在通用领域获得了巨大的成功,但在专业领域,由于缺乏相关事实性知识,LLM往往会产生不准确的…...
使用anaconda创建爬虫spyder工程
1.由于每个工程使用的环境都可能不一样,因此一个好的习惯就是不同的工程都创建属于自己的环境,在anaconda中默认的环境是base,我们现在来创建一个名为spyder的环境,专门用于爬虫工程: //括号中名字,代表当…...
网络通信(7)-TCP协议解析
目录 一、定义 二、主要特点 三、报文格式 四、工作方式...
win32 WM_MENUSELECT消息学习
之前写了一些win32的程序,处理菜单单击都是处理WM_COMMAND消息,通过 LOWORD(wParam) 获取菜单ID,判断单击的是哪个菜单项; 还有一些其他菜单消息; 当在菜单项中移动光标或鼠标,程序会收到许多WM_MENUSELEC…...
Java学习苦旅(十六)——List
本篇博客将详细讲解Java中的List。 文章目录 预备知识——初识泛型泛型的引入泛型小结 预备知识——包装类基本数据类型和包装类直接对应关系装包与拆包 ArrayList简介ArrayList使用ArrayList的构造ArrayList常见操作ArrayList遍历 结尾 预备知识——初识泛型 泛型的引入 我…...
python爬虫实现获取招聘信息
使用的python版本: 3.12.1 selenium版本:4.8.0 urllib版本:1.26.18 from selenium import webdriver from selenium.webdriver import ActionChains import timeimport re import xlwt import urllib.parsedef get_html(url):chrome_drive…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
