五大常用算法——贪心算法
汇总几个常见的贪心算法实现的问题
- 概述
- IPO（最大投资收益）
- 金砖最小分割代价
- 会议室相关问题
- 分发糖果
- 柠檬水找零
- 分发饼干
概述
这里主要总结一些涉及贪心算法的题目，对于贪心算法原理不作阐述。简单罗列一下搜集的资料。
贪心算法的定义：
贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
解题的一般步骤是：
1.建立数学模型来描述问题；
2.把求解的问题分成若干个子问题；
3.对每一子问题求解，得到子问题的局部最优解；
4.把子问题的局部最优解合成原来问题的一个解。
以上较为官方的一些阐述，那么个人认为贪心最大的工作就是尝试，在稿子上尝试写出几个简单示例的贪心策略，验证成功直接coding即可。
IPO问题
假设 力扣（LeetCode）即将开始其 IPO。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。
给定若干个项目。对于每个项目 i，它都有一个纯利润 Pi，并且需要最小的资本 Ci 来启动相应的项目。最初，你有 W 资本。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。
总而言之，从给定项目中选择最多 k 个不同项目的列表，以最大化最终资本，并输出最终可获得的最多资本。
- 贪心策略思考：每次选择项目的时候，都在现有的资本可以实现的象中选取利润最大的项目。也就是说必须满足(cur)W >= Ci, choose = Max(Ci - Pi);
- 实现: 首先将资本Ci构建成为一个小顶堆，所需资本小的放在前面，然后遍历这个小顶堆，将满足投资要求的项目扔进由利润值构建的大顶堆中去，那么每次选择项目时，就取出大顶堆的堆顶项目投资即可。
- 代码：
/*
-----------------------------------创建Node辅助贪心算法----------------------------------
*/
// 创建项目类
class Node {
int c; // 资本
int p; // 利润
public Node(int c, int p) {
this.c = c;
this.p = p;
}
}
public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
// 首先创建大小堆
PriorityQueue<Node> cHeap = new PriorityQueue<Node>(new MinCapitalComparator());
PriorityQueue<Node> pHeap = new PriorityQueue<Node>(new MaxProfitComparator());
// 将capitalHeap构造成为资本的小顶堆
for (int i = 0; i < Capital.length; i++) {
cHeap.add(new Node(Capital[i], Profits[i]));
}
int ans = W;
// 遍历k,进行k次交易
for (int j = 0; j < k; j++) {
while (!cHeap.isEmpty() && cHeap.peek().c <= ans) {
pHeap.add(cHeap.poll());
}
if (pHeap.isEmpty()) return ans;
ans += pHeap.poll().p;
}
// 返回利润
return ans;
}
// 小顶堆改造
public class MinCapitalComparator implements Comparator<Node> {
@Override
public int compare(Node o1, Node o2) {
return o1.c - o2.c;
}
}
// 大顶堆改造
public class MaxProfitComparator implements Comparator<Node> {
@Override
public int compare(Node o1, Node o2) {
return o2.p - o1.p;
}
}
金砖最小分割代价
题目：
一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的 金条，不管切成长度多大的两半，都要花费20个铜板。一群人想整分整块金 条，怎么分最省铜板？例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为10+20+30=60. 金条要分成10,20,30三个部分。 如果， 先把长度60的金条分成10和50，花费50 再把长度50的金条分成20和30，花费50 一共花费110铜板。但是如果， 先把长度60的金条分成30和30，花费60 再把长度30金条分成10和20，花费30 一共花费90铜板。输入一个数组，返回分割的最小代价.
- 贪心策略： 根据题意可知，如果当前的金砖总价较高，那么分割代价肯定较高，所以考虑优先挑选数组最小的两个元素分割，各分代价就是两个元素的和，求出和之和再扔进数组继续分割
- 实现方法： 同样借用优先级队列，构造一个小顶堆，元素升序排列。
- 实现思想，不断累加数组数种两个最小元素的分割代价。
- 代码“
public static int lessMoney(int[] arr) {
//创建一个优先级队列（默认情况下按照升序进行排列）
PriorityQueue<Integer> PQ = new PriorityQueue<Integer>();
for (int i = 0; i < arr.length; i++) {
PQ.add(arr[i]);
}
int res = 0;
int sum = 0;
while(PQ.size() > 1) {
sum = PQ.poll() + PQ.poll(); // 弹出两个最小值求和
res += sum;
PQ.add(sum); // 累加sum之后再扔回堆中
}
return res;
}
会议室相关问题
一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。 给你每一个项目开始的时间和结束的时间(给你一个数组，里面 是一个个具体的项目)，你来安排宣讲的日程，要求会议室进行 的宣讲的场次最多。返回这个最多的宣讲场次。
- 分析： 只有一个会议室，所以每个项目的开始时间和结束时间必须要错开，保证不会有两个项目同时使用一个会议室的冲突。
- 贪心策略：优先选取最早结束时间的项目，然后从开始时间在此处后面项目中再选最长结束时间的项目。
- 实现方法： 优先级队列，创建一个队列，以每个项目的最早结束时间升序排列，依次遍历查看队列中元素，如果最迟时间为0或者当前的最早时间大于等于最迟时间，ans加1。
- 代码如下：
// 创建项目的实体类
public static class Program{
int start; //项目开始时间
int end; //项目结束时间
public Program(int start, int end){
this.start = start;
this.end = end;
}
}
// 创建一个项目按照结束时间从小到大的排列顺序
public static class MinEndTimeComparator implements Comparator<Program> {
@Override
public int compare(Program o1, Program o2) {
return o1.end - o2.end;
}
}
/**
* 主函数入口
* @param programs 给定项目的数组（包含项目的开始时间和结束时间）
* @param start 会议室可以使用的开始时间
* @return 最多会议室的使用次数
*/
public static int bestArrange(Program[] programs, int start) {
PriorityQueue<Program> queue = new PriorityQueue<>(new MinEndTimeComparator());
for (int i = 0; i < programs.length; i++) {
queue.add(programs[i]);
}
int res = 0;
while(!queue.isEmpty()){
if(start <= queue.peek().start) {
res++;
start = queue.poll().end;
}else{
queue.poll();
}
}
return res;
}
LintCode920——会议室
给定一系列的会议时间间隔，包括起始和结束时间[[s1,e1]，[s2,e2]，…(si < ei)，确定一个人是否可以参加所有会议。
思路： 类似上一题（使用优先级队列）
/**
* Definition of Interval:
* public class Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
/**
* @param intervals: an array of meeting time intervals
* @return: if a person could attend all meetings
*/
public boolean canAttendMeetings(List<Interval> intervals) {
// Write your code here
if(intervals.size() < 2) return true;
PriorityQueue<Interval> heap = new PriorityQueue<Interval>(new MyConparator());
for(Interval pro: intervals){
heap.add(pro);
}
// h构建小顶堆结束，遍历检查后一项的start是否>=前一项的end
int end = heap.poll().end;
while(!heap.isEmpty()){
if(heap.peek().start < end){
return false;
}
end = heap.poll().end;
}
return true;
}
// n比较器，按照开始时间排序
class MyConparator implements Comparator<Interval> {
@Override
public int compare(Interval o1, Interval o2){
return o1.start - o2.start;
}
}
}
LeeCode1353. 最多可以参加的会议数目(经典)
给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于startDayi ，结束于 endDayi 。
你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。
请你返回你可以参加的 最大 会议数目
- 思路分析： 这题跟一个会议室供多个项目使用有区别。对于某一天我可以参加的所有会议中，我肯定会选择最早结束的那个，因此贪心的思想就出现了：每次在可以进行的会议中选择拥有最早结束时间的会议来实现。
- 代码如下：
public int maxEvents(int[][] events) {
// 首先将所有会议按照会议开始时间进行排序
Arrays.sort(events, new Comparator<int[]>(){
@Override
public int compare(int[] a, int[] b){
return a[0] - b[0];
}
});
// 创建优先级队列
PriorityQueue<Integer> queue = new PriorityQueue<>();
int cur = 0; // 当前处于第0天
int index = 0; // 会议按照最早开始时间存储的编号
int n = events.length; // 会议总数
int ans = 0; // 结果集
// 循环结束条件
while(index < n || !queue.isEmpty()){
// 如果队列为空，将当前的项目结束时间扔进去，day调整为当前的时间
if(queue.isEmpty()){
queue.add(events[index][1]);
cur = events[index++][0];
}
// 遍历后面的会议。如果开始时间在day时间之间，都将他们入独对列
while(index < n && events[index][0] <= cur){
queue.add(events[index++][1]);
}
// 如果当前会议可以进行
if(queue.peek() >= cur){
cur++;
ans++;
}
//弹出会议
queue.poll();
}
return ans;
}
分发糖果
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。那么这样下来，老师至少需要准备多少颗糖果呢？
思路分析：（贪心策略）
- 首先保证每个孩子手上有一颗糖
- 从左到右遍历数组，如果当前孩子比他左边的孩子分数高，则这个孩子再给一颗糖。即
ratings[i] > ratings[i-1] 的时候，i孩子在前一个孩子的基础上再给一颗糖。一次遍历之后只考虑了左孩子的情况，那么现在还要考虑右孩子。从以同样的方式从到左再来一遍 - 从右到左遍历数组，如果当前孩子比他右边的孩子分数高，则这个孩子再给一颗糖。即
ratings[i] > ratings[i+1] 的时候，i孩子在后一个孩子的基础上再给一颗糖。 - 代码如下：
class Solution {
// 贪心算法求解
public int candy(int[] ratings) {
if (ratings.length == 1) return 1;
int n = ratings.length;
int[] candy = new int[n];
Arrays.fill(candy,1);// 首先需要保证每个孩子手上有一颗糖
// 从左至右遍历数组
for (int i = 1; i < n; i++) {
if(ratings[i] > ratings[i - 1]){
candy[i] = candy[i - 1] + 1;
}
}
// 从右到左再来一遍
for (int i = n - 2; i >= 0; i--) {
if(ratings[i] > ratings[i + 1] && candy[i] <= candy[i + 1]){
candy[i] = candy[i + 1] + 1;
}
}
// 返回结果集
int ans = 0;
for (int c : candy) {
ans += c;
}
return ans;
}
}
柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
思路：只会收到5，10，20三种面个的货币，20无论如何都不会用作找零的面额不考虑。没后每次找零的时候优先用大额面额(5,10) , 如果找零后5元成负数，则一定不可能找零。
代码：
class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0; // 代表5元面额
int ten = 0; // 代表10元面额
//遍历数组
for(int m : bills){
if(m == 5){
five++;
continue;
}
if(m == 10){
five--;
ten++;
}else{
if(ten != 0){
five--;
ten--;
}else{
five -= 3;
}
}
// 每次找零之后，如果five变成了负，则无法找零
if(five < 0) return false;
}
return true;
}
}
分发饼干
LeeCode455. 分发饼干
难度简单145假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
思路： 典型贪心策略，尽可能的用小饼干喂饱胃口小的孩子
- 首先将两个数组分别排序
- 遍历两个数组，如果当前饼干喂不饱当前的小孩，那么后面所有的小孩肯定也喂不饱，所以直接查看下一个饼干能否喂饱当前的小孩。
- 如果当前的饼干可以喂饱当前的小孩，那么小孩和饼干都从列表中移除，结果集加1.
- 代码如下:
class Solution {
public int findContentChildren(int[] g, int[] s) {
// 首先将两个数组进行排序
Arrays.sort(g);
Arrays.sort(s);
int i = 0, j = 0, ans = 0;
while(i < g.length && j < s.length){
// 满足了一个小孩，s和g均后移，ans加1
if(s[j] >= g[i]){
i++;
ans++;
}
// 不管当前饼干是否可以满足此小孩，指针都向后移
j++;
}
return ans;
}
}
