分发糖果,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…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...
数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !
我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...
