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

2024-01-02 18:40:28

在这里插入图片描述

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

在这里插入图片描述

算法专栏学习

题目访问地址专栏
分发糖果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。

在这里插入图片描述

文章来源:https://blog.csdn.net/m0_50308467/article/details/135343315
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。