分发糖果,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…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...
wpf在image控件上快速显示内存图像
wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像(比如分辨率3000*3000的图像)的办法,尤其是想把内存中的裸数据(只有图像的数据,不包…...
