526互联

代码随想录贪心专题-day1

发布时间 2023-07-21 22:37:42作者: KU做人

35. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

思路：

本题这种要同时满足左右两种情况的题目，我们一般不直接处理左右两边，而是前处理一边，再处理另一边。回到本题来，我们可以先从前到后枚举右孩子大于左孩子的情况，再从后往前枚举左孩子大于右孩子的情况，注意计算左孩子大于右孩子的情况的时候，还需要满足情况1，所以我们取两次的最大值。

代码：

class Solution {
    // 2023-7-21
    // 二刷 这种要考虑两边的题目，一般来说先确定一边
    // 再确定另一边
    // 两次遍历 
    // 一次遍历右孩子大于左孩子 从前往后
    // 一次左孩子大于右孩子 必须从后往前，才能利用上一次的结果
    public int candy(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] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        return Arrays.stream(candies).sum();
    }
}

860. 柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

思路：

本题贪心的点在于面对20的时候我们该如何找零，我们可以找零的方式无非就是两种：1.找10+5；2.找5+5+5。显然我们认为5元更有用，因为他还能找10元滴，所以我们优先用方式1找零。

代码：

class Solution {
    // 2023-7-21
    // 代码随想录 二刷
    // 每杯柠檬水 5 美元
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0; // 因为最大的面值为20，所以20元的钞票不在找零的范围内

        for (int bill : bills) {
            if (bill == 5) five ++;
            else if (bill == 10) {
                if (five == 0) return false; // 没有5美元的
                five --;
                ten ++;
            } else if (bill == 20){ // 优先用10 + 5 找钱，因为5比较万能
                if (five != 0 && ten != 0) {
                    five --;
                    ten --;
                } else if (five >= 3){
                    five -=3;
                } else return false;
            }
        }

        return true;
    }
}

406.根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

思路

本题类似135，同样需要安装两个规则来排序，我们分析后可知，如果先按k排序，并不能满足。所以我们先安装h排序，将身高高的放前面，再遍历将元素插入到对应的k位置上即可。

代码

class Solution {
    // 复习2023-4-20
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1]; // 身高一样的比较k，k小的在前 a - b是升序
            return b[0] - a[0]; // 身高不一样的比较身高，高的在前 b - a是降序
        });

        LinkedList<int[]> que = new LinkedList<>();
        for (int[] p : people) {
            que.add(p[1], p); // 把p插入到p[1] 及k的位置上
        }

        return que.toArray(new int[people.length][]);
    }
}