Leetcode 135. 分发糖果（Java实现 超详细注释！）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Leetcode 135. 分发糖果（Java实现 超详细注释！），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2248字，纯文字阅读大概需要4分钟。

内容图文

Leetcode 135. 分发糖果

这道题考察对贪心思想的实际运用能力，读懂题目并转换为解答方案是解决问题的第一步！加了详细的注释，方便日后复习，也希望能帮到其他小伙伴，如有错误，欢迎指正！

Java实现：

class Solution {
    public int candy(int[] ratings) {
        /**
        这道题的思路：先从左往右遍历，右边的分值比左边大，那右边的糖果就多分一个；再从右往左遍历，左边的分值比右边大，那左边的糖果就多分一个；
        如果同时满足上述两个条件，那么肯定满足相邻的孩子中，评分高的孩子必须获得更多的糖果，这里是贪心的思想，所以我们把两次遍历的结果取并集，也就是每个孩子必须都得到这两种情况中更大的那个糖果数量，这样也就能保证分发的总糖果数量尽量小;
        此外，为了满足每个孩子至少分配到 1 个糖果，我们左边和右边遍历的第一个孩子都必须给一个糖果；
        */

        方法1：
        // 先初始化两个数组
        int n = ratings.length;
        int[] left_to_right = new int[n];
        int[] right_to_left = new int[n];
        // 为了满足每个孩子至少分配到 1 个糖果，我们左边和右边遍历的第一个孩子都必须给一个糖果
        left_to_right[0] = 1;
        right_to_left[n - 1] = 1;
        // 从左向右遍历，右边比左边分高就给右边的孩子多分一个糖果，否则就只给右边的孩子分一个糖果
        for (int i = 1; i < n; i++){
            if (ratings[i] > ratings[i - 1]){
                left_to_right[i] = left_to_right[i - 1] + 1;
            }else{
                left_to_right[i] = 1;
            }
        }
        // 从右向左遍历，左边比右边分高就给左边的孩子多分一个糖果，否则就只给左边的孩子分一个糖果
        for (int j = n - 2; j >= 0; j--){
            if (ratings[j] > ratings[j + 1]){
                right_to_left[j] = right_to_left[j + 1] + 1;
            }else{
                right_to_left[j] = 1;
            }
        }
        // 统计最少的总糖果数
        int sum_candy = 0;
        // 我们把两次遍历的结果取并集并累加，也就是每个孩子必须都得到这两种情况中更大的那个糖果数量，这样也就能保证分发的总糖果数量尽量小;
        for (int c = 0; c < n; c++){
            sum_candy += Math.max(left_to_right[c],right_to_left[c]);
        }
        return sum_candy;
    }


    // 方法2：和第一种方法几乎一样，只是不需要写else，用Arrays.fill提前把所有的小朋友都发一个糖
    int n = ratings.length;
        int[] left_to_right = new int[n];
        int[] right_to_left = new int[n];
        Arrays.fill(left_to_right,1);
        Arrays.fill(right_to_left,1);

        for (int i = 1; i < n; i++){
            if (ratings[i] > ratings[i - 1]){
                left_to_right[i] = left_to_right[i - 1] + 1;
            }
        }

        for (int j = n - 2; j >= 0; j--){
            if (ratings[j] > ratings[j + 1]){
                right_to_left[j] = right_to_left[j + 1] + 1;
            }
        }
        int sum_candy = 0;
        for (int c = 0; c < n; c++){
            sum_candy += Math.max(left_to_right[c],right_to_left[c]);
        }
        return sum_candy;
    }
}

内容总结

以上是互联网集市为您收集整理的Leetcode 135. 分发糖果（Java实现 超详细注释！）全部内容，希望文章能够帮你解决Leetcode 135. 分发糖果（Java实现 超详细注释！）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端