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

分发糖果,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经典算法编程实战。

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

鸿蒙原生应用再添新丁!中国移动 入局鸿蒙

鸿蒙原生应用再添新丁&#xff01;中国移动 入局鸿蒙 来自 HarmonyOS 微博1月2日消息&#xff0c;#中国移动APP启动鸿蒙原生应用开发#&#xff0c;拥有超3亿用户的中国移动APP宣布&#xff0c;正式基于HarmonyOS NEXT启动#鸿蒙原生应用#及元服务开发。#HarmonyOS#系统的分布式…...

一个人能不能快速搭建一套微服务环境

一、背景 大型软件系统的开发现在往往需要多人的协助&#xff0c;特别是前后端分离的情况下下&#xff0c;分工越来越细&#xff0c;那么一个人是否也能快速搭建一套微服务系统呢&#xff1f; 答案是能的。看我是怎么操作的吧。 二、搭建过程 1、首先需要一套逆向代码生成工…...

计算机毕业设计------经贸车协小程序

项目介绍 本项目分为三种用户类型&#xff0c;分别是租赁者&#xff0c;车主&#xff0c;管理员用户&#xff1b; 管理员用户包含以下功能&#xff1a; 管理员登录,个人中心,租赁者管理,车主管理,赛事活动管理,车类别管理,租车管理,租车订单管理,车辆出售管理,购买订单管理,…...

数据结构OJ实验11-拓扑排序与最短路径

A. DS图—图的最短路径&#xff08;无框架&#xff09; 题目描述 给出一个图的邻接矩阵&#xff0c;输入顶点v&#xff0c;用迪杰斯特拉算法求顶点v到其它顶点的最短路径。 输入 第一行输入t&#xff0c;表示有t个测试实例 第二行输入顶点数n和n个顶点信息 第三行起&…...

你的第一个JavaScript程序

JavaScript&#xff0c;即JS&#xff0c;JavaScript是一种具有函数优先的轻量级&#xff0c;解释型或即时编译型的编程语言。虽然它是作为开发Web页面的脚本语言而出名&#xff0c;但是它也被用到了很多非浏览器环境中&#xff0c;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&#xff0c;读取内部温度其他知识 内部温度所在ADC通道 温度计算公式 V25跟Avg_Slope值 参考文档 stm32f103ze.pdf 电压计算公式 Vout Vref * (D / 2^n) 其中Vref代表参考电压&#xff0c; n为ADC的位数&#xff0c; D为ADC输入的数字信号。 实现…...

普中STM32-PZ6806L开发板(使用过程中的问题收集)

Keil使用ST-Link 报错 Internal command error 描述: 在某一次使用过程中&#xff0c;前面都是正常使用, Keil在烧录时报错Internal command error, 试了网上的诸多方式, 例如 升级固件;ST-Link Utility 清除;Keil升级到最新版本;甚至笔者板子的Micro头也换了&#xff0c;因为坏…...

八股文打卡day12——计算机网络(12)

面试题&#xff1a;HTTPS的工作原理&#xff1f;HTTPS是怎么建立连接的&#xff1f; 我的回答&#xff1a; 1.客户端向服务器发起请求&#xff0c;请求建立连接。 2.服务器收到请求之后&#xff0c;向客户端发送其SSL证书&#xff0c;这个证书包含服务器的公钥和一些其他信息…...

自然语言处理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)&#xff0c;专门用来开发游戏。pygame主要为开发、设计2D电子游戏而生&#xff0c;提供图像模块&#xff08;image&#xff09;、声音模块&#xff08;mixer&#xff09;、输入/输出&#xff08;鼠标、键盘、显示屏&#xff09;…...

前端面试

1. 什么是MVVM,MVC&#xff0c;MVP模型&#xff1f; 软件架构模式&#xff1a; MVC: M&#xff1a; 模型&#xff0c;拉取数据的类。 V&#xff1a; 视图&#xff0c;展现给用户的视觉效果。 C&#xff1a; 控制器&#xff0c;通知M拉取数据&#xff0c;并且给V。 > MV…...

Spring Boot快速搭建一个简易商城项目【完成登录功能且优化】

完成登录且优化&#xff1a; 未优化做简单的判断&#xff1a; 全部异常抓捕 优化&#xff1a;返回的是json的格式 BusinessException&#xff1a;所有的错误放到这个容器中&#xff0c;全局异常从这个类中调用 BusinessException&#xff1a; package com.lya.lyaspshop.exce…...

KG+LLM(一)KnowGPT: Black-Box Knowledge Injection for Large Language Models

论文链接&#xff1a;2023.12-https://arxiv.org/pdf/2312.06185.pdf 1.Background & Motivation 目前生成式的语言模型&#xff0c;如ChatGPT等在通用领域获得了巨大的成功&#xff0c;但在专业领域&#xff0c;由于缺乏相关事实性知识&#xff0c;LLM往往会产生不准确的…...

使用anaconda创建爬虫spyder工程

1.由于每个工程使用的环境都可能不一样&#xff0c;因此一个好的习惯就是不同的工程都创建属于自己的环境&#xff0c;在anaconda中默认的环境是base&#xff0c;我们现在来创建一个名为spyder的环境&#xff0c;专门用于爬虫工程&#xff1a; //括号中名字&#xff0c;代表当…...

网络通信(7)-TCP协议解析

目录 一、定义 二、主要特点 三、报文格式 四、工作方式...

win32 WM_MENUSELECT消息学习

之前写了一些win32的程序&#xff0c;处理菜单单击都是处理WM_COMMAND消息&#xff0c;通过 LOWORD(wParam) 获取菜单ID&#xff0c;判断单击的是哪个菜单项&#xff1b; 还有一些其他菜单消息&#xff1b; 当在菜单项中移动光标或鼠标&#xff0c;程序会收到许多WM_MENUSELEC…...

Java学习苦旅(十六)——List

本篇博客将详细讲解Java中的List。 文章目录 预备知识——初识泛型泛型的引入泛型小结 预备知识——包装类基本数据类型和包装类直接对应关系装包与拆包 ArrayList简介ArrayList使用ArrayList的构造ArrayList常见操作ArrayList遍历 结尾 预备知识——初识泛型 泛型的引入 我…...

python爬虫实现获取招聘信息

使用的python版本&#xff1a; 3.12.1 selenium版本&#xff1a;4.8.0 urllib版本&#xff1a;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…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...