【算法笔记】贪心算法

前言： 对于贪心算法的学习主要以增加阅历和经验为主，也就是多做多积累经验，以下通过几个题目来介绍贪心算法的乐趣！

1. 贪心算法基本介绍

• 是一种局部最功利的标准，总是做出在当前看来是最好的选择
• 难点在于证明局部最功利的标准可以得到全局最优解
• 贪心一般跟排序和堆有关
• 贪心算法的难点在于如何证明该标准可行，但是证明往往较难，可以通过对数器来验证最终的方式是否可行

题一：给定一个由字符串组成的数组 strs，必须把所有的字符串拼接起来，返回所有可能的拼接结果中，字典序最小的结果

方法模板： 为了得到字典序最小的结果，我们可以将数组进行排序，使排序后的数组拼接的字符串的字典序最小即可。排序规则为字符串 a 和 字符串 b进行 a + b 和 b + a 的拼接后比比较这两者的字典序大小，如果 a + b 小，则字符串 a 排在 字符串 b 前。

public static class MyComparator implements Comparator<String> {
    @Override
    public int compare(String o1, String o2) {
        return (o1 + o2).compareTo(o2 + o1);
    }
}

public static String lowestString(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    }
    Arrays.sort(strs, new MyComparator());
    String ans = "";
    for (int i = 0; i < strs.length; i++) {
        ans += strs[i];
    }
    return ans;
}

示例代码：

public static void main(String[] args) {
    String[] strs = {"ba", "b", "cda"};
    System.out.println(lowestString(strs));
}
// 结果为：babcda

题二：一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给你每一个项目的开始时间和结束时间，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。返回最多的宣讲场次

结束时间最早

方法模板： 当我们思考该问题时，我们可能会想着使用开始时间最早或者宣讲时间最短来进行验证，但是这种贪心思路是错误的，正确的方法是以结束时间最早来思考这道题。找到第一个结束时间最早的会议，然后删除其余开始时间早于最早结束时间的会议，然后再找第二个结束时间最早的会议…

public static class Program {
    public int begin;
    public int end;

    public Program(int begin, int end) {
        this.begin = begin;
        this.end = end;
    }
}
public static int bestArrange(Program[] programs) {
    Arrays.sort(programs, new MyComparator());
    int timeLine = 0;
    int count = 0;
    for (int i = 0; i < programs.length; i++) {
        if (programs[i].begin >= timeLine) {
            count++;
            timeLine = programs[i].end;
        }
    }
    return count;
}
public static class MyComparator implements Comparator<Program> {
    @Override
    public int compare(Program o1, Program o2) {
        return o1.end - o2.end;
    }
}

示例代码：

public static void main(String[] args) {
    Program[] programs = { new Program(1, 2), new Program(1, 5), new Program(3, 4), new Program(5, 6) };
    System.out.println(bestArrange(programs));
}
// 结果为：3

题三：一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金条，不管怎么切，都需要花费20个铜板。一群人想整分整块金条，怎么分最省铜板？输入一个数组，返回分割的最小代价

举例：

例如，给定数组{10， 20， 30}，代表一共三个人，整块金条长度为60，要将金条分成10，20，30三个部分。

如果先把长度60的金条分成10和50，花费60；再把长度50的金条分成20和30，花费50，一共花费110的铜板

如果先把长度60的金条分成30和30，花费60，再把长度30的金条分成30和10，花费30，一共花费90铜板

方法模板： 思考该题时可能会想到以最大部分的金条长度来切割，但是该贪心思路是错误的（如要分割成长度为97、98、99、100几部分，则要先将金条分成 97+98 和 99+100 两部分）。这里可以建一个小根堆，然后依次弹出堆顶两个元素相加，相加的结果就是这两块金条分割的花费，然后再将该结果入堆，继续以上步骤，直到堆中只剩一个数值

public static int lessMoney(int[] arr) {
    Queue<Integer> queue = new PriorityQueue<>();
    for(int num : arr) {
        queue.add(num);
    }
    int money = 0;
    int cur = 0;
    while(queue.size() > 1) {
        cur = queue.poll() + queue.poll();
        money += cur;
        queue.add(cur);
    }
    return money;
}

示例代码：

public static void main(String[] args) {
    int[] arr = {10, 20, 30};
    System.out.println(lessMoney(arr));
}
// 结果为：90

题四：输入：正数数组 costs、正数数组 profits、正数 K、正数 M。cost[i] 表示 i 号项目的花费，profits[i] 表示 i 号项目在扣除花费之后还能挣到的钱，K 表示你只能串行的最多做 K 个项目，M 表示你初始的资金。说明：你没做完一个项目，马上获得的收益，可以支持你去做下一个项目。不能并行的做项目。输出：你最后获得的最大钱数

方法模板： 可以构建一个以项目的花费从低到高的小根堆，并将所有项目入堆，再构建一个以项目的利润从高到低的大根堆，将小根堆中消费少于当前拥有的资金的项目弹出，并加入到大根堆中，取利润最高的项目进行购买，之后依次进行以上步骤

public static class Program {
    public int cost;
    public int profit;

    public Program(int cost, int profit) {
        this.cost = cost;
        this.profit = profit;
    }
}

public static class MinCostComparator implements Comparator<Program>{

    @Override
    public int compare(Program o1, Program o2) {
        return o1.cost - o2.cost;
    }

}

public static class MaxProfitComparator implements Comparator<Program>{

    @Override
    public int compare(Program o1, Program o2) {
        return o2.profit - o1.profit;
    }

}

public static int findMaximizedCapital(int K, int W, int[] profits, int[] capital) {
    Queue<Program> minCostQ = new PriorityQueue<>(new MinCostComparator());
    Queue<Program> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
    for(int i = 0; i < capital.length; i++) {
        Program program = new Program(capital[i], profits[i]);
        minCostQ.add(program);
    }
    while(K > 0) {
        while(minCostQ.size() > 0 && minCostQ.peek().cost <= W) {
            maxProfitQ.add(minCostQ.poll());
        }
        if(maxProfitQ.isEmpty()) {
            break;
        }
        W += maxProfitQ.poll().profit;
        K--;
    }
    return W;
}

示例代码：

public static void main(String[] args) {
    int[] capital = {2,1,6,4};
    int[] profits = {2,3,1,4};
    int K = 3;
    int W = 1;
    System.out.println(findMaximizedCapital(K,W,profits,capital));
}
// 结果为：10

题五： 给定一个字符串 str，只由 ‘X’ 和 ‘.’ 两种字符构成。‘X’ 表示墙，不能放灯，也不需要点亮；’.’ 表示居民点，可以放灯，需要点亮。如果灯放在 i 位置，可以让 i-1、i 和 i+1 三个位置被点亮。返回如果点亮 str 中所有需要点亮的位置，至少需要几盏灯

方法模板： 假设 index 位置是墙时，那么 index = index+1；当 index 位置是居民点时，index+1 位置为墙时，就需要一盏灯，并且 index = index+2；当 index 位置为居民点，index+1 位置为居民点，不论 index+2 位置为居民点还是墙，都需要一盏灯，并且 index = index+3

public static int minLight(String road) {
    char[] str = road.toCharArray();
    int index = 0;
    int light = 0;
    while(index<str.length) {
        if(str[index] == 'X') {
            index++;
        }else {
            light++;
            if(index+1==str.length) {
                break;
            }else {
                if(str[index+1]=='X') {
                    index=index+2;
                }else {
                    index=index+3;
                }
            }
        }
    }
    return light;
}

示例代码：

public static void main(String[] args) {
    String road = "X.XX..X...X....X";
    System.out.println(minLight(road));
}
// 结果为：5