算法通关村第十七关|青铜|贪心:无招胜有招

2023-12-14 23:25:26

贪心常见的经典应用场景:

● 排序问题:选择排序,拓扑排序
● 优先队列:堆排序
● 赫夫曼压缩编码
● 图:Prim Fruskal Dijkstra 算法
● 硬币找零问题
● 分数背包问题
● 并查集:按大小或者高度合并问题或者排名
● 任务调度部分场景
● 一些复杂问题的近似算法

1.分发饼干

原题:力扣455.

贪心策略就是将两个数组排序,然后遍历小孩数组,优先用大饼干喂给胃口大的小孩。

这里的 g 是胃口数组, s 是饼干数组

public int findContentChildren(int[] g, int[] s) {
	Arrays.sort(g);
    Arrays.sort(s);
    int count = 0;
    int start = s.length - 1;
    for (int index = g.length - 1; index >= 0; index--) {
        if (start >= 0 && g[index] <= s[start]) {
            start--;
            count++;
        }
    }
    return count;
}

2.柠檬水找零

原题:力扣860.

分析收钱情况:

● 如果给 5 元,直接收下
● 如果给 10 元,收下 10 元,找零 5 元
● 如果给 20 元,收下 20 元,找零 10 元和 5 元或者三个 5 元

第二种情况下必须有 5 元才能找零。

第三种情况下优先找零 10 元,然后再找零 5 元,因为 5 元可以用在第二种和第三种情况,而 10 元只能用在第三种情况下。

代码直接列举情况就好了。

public boolean lemonadeChange(int[] bills) {
    // 记录两种钞票的数目
	int cash_5 = 0;
    int cash_10 = 0;
    for (int i = 0; i < bills.length; i++) {
        if (bills[i] == 5) {
            cash_5++;
        } else if (bills[i] == 10) {
            cash_5--;
            cash_10++;
        } else if (bills[i] == 20) {
            if (cash_10 > 0) {
                cash_10--;
                cash_5--;
            } else {
                cash_5 -= 3;
            }
        }
        if (cash_5 < 0 || cash_10 < 0) {
            return false;
        }
    }
    return true;
}

3.分发糖果

原题:力扣135.

需要注意,相邻的两个孩子的评分相同的时候,就不存在一个比另一个大的情况了,那么就不需要考虑糖果分配,只需给其中一个孩子分配 1 个基本糖果即可。

public int candy(int[] ratings) {
	int[] candyVec = new int[ratings.length];
    candyVec[0] = 1;
    // 先从左到右遍历一次
    for (int i = 1; i < ratings.length; i++) {
        if (rating[i] > ratings[i - 1]) {
            candyVec[i] = candyVec[i - 1] + 1;
        } else {
            // 相等的时候也赋值 1
            candyVec[i] = 1;
        }
    }
    // 再从右向左遍历一次
    for (int i = ratings.length - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
        }
    }
    int ans = 0;
    for (int s : candyVec) {
        ans += s;
    }
    return ans;
}

如果对您有帮助,请点赞关注支持我,谢谢!?
如有错误或者不足之处,敬请指正!?
个人主页:星不易 ?
算法通关村专栏:不易|算法通关村 ?

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