JAVA学习-练习试用Java实现“分发糖果”

admin2024-07-08  9

问题:

老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。

需要按照以下要求,帮助老师给这些孩子分发糖果:

每个孩子至少分配到 1 个糖果。

评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

那么这样下来,老师至少需要准备多少颗糖果呢?

示例 1:

输入:[1,0,2]

输出:5

解释:你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:

输入:[1,2,2]

输出:4

解释:你可以分别给这三个孩子分发 1、2、1 颗糖果。

第三个孩子只得到 1 颗糖果,这已满足上述两个条件。

解答思路:

以下是使用 Java 语言解决此问题的代码:

import java.util.ArrayList;

import java.util.List;



public class CandyDistribution {

    public static void main(String[] args) {

        int[] ratings = {1, 0, 2};

        System.out.println(distributeCandies(ratings));

    }



    public static int distributeCandies(int[] ratings) {

        List<Integer> candies = new ArrayList<>();



        for (int i = 0; i < ratings.length; i++) {

            candies.add(1);

        }



        for (int i = 1; i < ratings.length; i++) {

            if (ratings[i] > ratings[i - 1]) {

                candies.set(i, candies.get(i - 1) + 1);

            } else if (ratings[i] < ratings[i - 1]) {

                int j = i;



                while (j > 0 && ratings[j] < ratings[j - 1] && candies.get(j) >= candies.get(j - 1)) {

                    candies.set(j - 1, candies.get(j) + 1);

                    j--;

                }

            }

        }



        int sum = 0;



        for (Integer candy : candies) {

            sum += candy;

        }



        return sum;

    }

}

这段代码首先初始化一个包含每个孩子 1 颗糖果的列表。然后,它遍历评分数组。如果当前孩子的评分高于前一个孩子的评分,它会将当前孩子的糖果数增加 1。如果当前孩子的评分低于前一个孩子的评分,它会从后往前找到第一个评分高于当前孩子的孩子,并将该孩子的糖果数增加 1。最后,它计算并返回糖果总数。

这段代码的时间复杂度为 O(n),其中 n 是孩子的数量,因为它只需要遍历评分数组一次。空间复杂度也为 O(n),因为它需要创建一个新的列表来存储每个孩子的糖果数。

(文章为作者在学习java过程中的一些个人体会总结和借鉴,如有不当、错误的地方,请各位大佬批评指正,定当努力改正,如有侵权请联系作者删帖。)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!