西安自助建站做网站,钟祥网站制作,行政机关网站建设,英雄联盟网站设计#x1f3c6;作者简介#xff0c;普修罗双战士#xff0c;一直追求不断学习和成长#xff0c;在技术的道路上持续探索和实践。 #x1f3c6;多年互联网行业从业经验#xff0c;历任核心研发工程师#xff0c;项目技术负责人。 #x1f389;欢迎 #x1f44d;点赞✍评论… 作者简介普修罗双战士一直追求不断学习和成长在技术的道路上持续探索和实践。 多年互联网行业从业经验历任核心研发工程师项目技术负责人。 欢迎 点赞✍评论⭐收藏 算法专栏学习
题目访问地址专栏分发糖果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[i1] candies[i] candies[i1]) {candies[i] candies[i1] 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。
