Java 贪心算法经典问题解决

分金条

题目

一块金条切成两半，是需要花费和长度数值一样的铜板的。比如 长度为20的 金条，不管切成长度多大的两半，都要花费20个铜 板。一群人想整分整块金 条，怎么分最省铜板？

例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为 10+20+30=60. 金条要分成10,20,30三个部分。 如果， 先把长 度60的金条分成10和50，花费60 再把长度50的金条分成20和30， 花费50 一共花费110铜板。 但是如果， 先把长度60的金条分成30和30，花费60 再把长度30 金条分成10和20，花费30 一共花费90铜板。

输入一个数组，返回分割的最小代价。

思路

哈夫曼树带权路径计算问题，更多了解可参考：哈夫曼树及其应用

1. 先将给定数组进行排序，这里可以使用优先级队列处理【优先级堆结构】，将数组依次丢入优先级队列中；
2. 每次从优先级队列中取出较小的值相加，记录计算结果，同时将结果重新丢入到队列中，直到队列中没有元素；
3. 将过程中的所有计算结果相加，结果即为分割最小代价；

代码实现

   private static int lessMoney(int[] aar) {PriorityQueue<Integer> pQ = new PriorityQueue<>();for (int i = 0; i < aar.length; i++) {pQ.add(aar[i]);}int result = 0;int cur = 0;while (pQ.size() > 1) {cur = pQ.poll() + pQ.poll();result += cur;pQ.add(result);}return result;}

测试用例以及结果输出

  public static void main(String[] args) {int[] aar = new int[]{30, 10, 20};System.out.println(lessMoney(aar));}

输出结果：

90

花费资金做项目最大收益

题目

输入：
参数1，正数数组costs
参数2，正数数组profits
参数3， 正数k
参数4，正数m

其中，costs[i]表示i号项目的花费；profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)；
k表示你不能并行、只能串行的最多做k个项目；
m表示你初始的资金；
说明：你每做完一个项目，马上获得的收益，可以支持你去做下一个 项目。
输出：你最后获得的最大钱数。

思路

基本原则：结合生活中的实际生产，每次选花费最小收益最高的项目去做，最终得到的收益肯定是最大的；

1. 新定义Node类，包含每个项目对应的花费以及收益；
2. 分别定义两个优先级队列，按照最小花费和最大收益优先级取元素；
3. 将根据花费以及收益数组生成的Node数组丢入到最小花费优先级队列中；
4. 进行K次遍历【最多可以做K个项目】，不断从最小花费优先级队列中取出项目，丢入到最大收益优先级队列中【注意资金问题】，在根据最大收益去做项目【即从最大收益队列中取项目做】，计算过程中获取的收益之和；

代码实现

/*** 计算最大收益** @param k       表示能做K个项目* @param m       表示启动资金* @param profits 表示做每个项目去除花费后的利润* @param costs   表示做每个项目对应的花费* @return*/private static int getMaxProfit(int k, int m, int[] profits, int[] costs) {//将项目对应花费以及收益包装成Node类,添加到Node[]数组中Node[] nodes = new Node[costs.length];for (int i = 0; i < costs.length; i++) {nodes[i] = new Node(costs[i], profits[i]);}// 最小花费优先级队列PriorityQueue<Node> minConstQ = new PriorityQueue<>(new MinComparator());// 最大收益优先级队列PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MaxComparator());//添加到最小花费优先级队列中for (int i = 0; i < nodes.length; i++) {minConstQ.add(nodes[i]);}// k表示最多可以做k个项目for (int i = 0; i < k; i++) {//只要花费不超过启动资金，按照最小花费不断从队列中取，丢入到收益队列中while (!minConstQ.isEmpty() && minConstQ.peek().cost <= m) {maxProfitQ.add(minConstQ.poll());}//如果收益队列为空，就返回最终资金，否则每次从收益队列中取最大收益的项目去做；if (maxProfitQ.isEmpty()) {return m;}m = m + maxProfitQ.poll().profit;}return m;}private static class Node {/*** 花费*/public int cost;/*** 利润*/public int profit;public Node(int cost, int profit) {this.cost = cost;this.profit = profit;}}/*** 花费最小排序*/private static class MinComparator implements Comparator<Node> {@Overridepublic int compare(Node o1, Node o2) {return o1.cost - o2.cost; //>0表示o1>o2}}/*** 利润最大排序*/private static class MaxComparator implements Comparator<Node> {@Overridepublic int compare(Node o1, Node o2) {return o2.profit - o1.profit; // >0 表示o2>o1}}

测试用例以及结果输出

   public static void main(String[] args) {int k = 3;int m = 5;int[] profits = new int[]{1, 3, 4, 6, 8};int[] costs = new int[]{3, 6, 4, 2, 6};System.out.println(getMaxProfit(k, m, profits, costs));}

输出结果：

23

预定会议室

题目

一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。

给你每一个项目开始的时间和结束的时间(给你一个数组，里面是一个个具体的项目)，你来安排宣讲的日程，

要求会议室进行的宣讲的场次最多，返回这个最多的宣讲场次。

思路

优先做最早结束的项目，保证开始时间小于或等于要做项目的开始时间即可；

代码实现

 private static int getMaxProgram(Program[] program, int start) {Arrays.sort(program, new ProgramComparator());int result = 0;for (int i = 0; i < program.length; i++) {if (start <= program[i].start) {result++;start = program[i].end;}}return result;}/*** 定义项目会议  包含开始和结束时间*/private static class Program {public int start;public int end;public Program(int start, int end) {this.start = start;this.end = end;}}/*** 按哪个项目先结束排序*/private static class ProgramComparator implements Comparator<Program> {@Overridepublic int compare(Program o1, Program o2) {return o1.end - o2.end;}}

测试用例以及结果输出

    public static void main(String[] args) {Program p1 = new Program(6, 10);Program p2 = new Program(7, 8);Program p3 = new Program(11, 13);Program p4 = new Program(13, 15);Program[] programs = new Program[]{p1, p2, p3, p4};System.out.println(getMaxProgram(programs, 6));}

输出结果：

3

取中位数

题目

一个数据流中，随时可以取得中位数；

思路

分别定义大根堆和小根堆，以下述逻辑进行存放和调整；

1. 当大根堆为空时，元素直接添加到大根堆中；
2. 当大根堆不为空时，如果元素小于或等于大根堆堆顶元素，则添加到大根堆中，否则添加到小根堆中；
3. 当大根堆和小根堆元素个数相差为2时，需要进行堆调整，将元素个数多的堆堆顶元素放入元素个数少的堆中；
4. 计算中位数，当大根堆和小根堆元素个数相等，则中位数为取两个堆的堆顶元素之和除以2，如果元素个数不相等，则中位数为元素个数多的堆的堆顶元素；

下面以以图进行举例说明，这里简单以队列表示大小根堆：

可以理解成通过堆对元素进行排序，只不过利用大小根队的性质，保证中位数可以通过堆顶数据进行计算得出，也避免了每次添加元素时进行排序问题，时间复杂度更低；

代码实现

    private static class MedianHelper {private PriorityQueue<Integer> minQ = new PriorityQueue<>(new MinComparator());private PriorityQueue<Integer> maxQ = new PriorityQueue<>(new MaxComparator());public int getMedian() {int maxQSize = maxQ.size();int minQSize = minQ.size();if (maxQSize == 0) {return 0;}//元素个数相等，取两者堆顶元素/2if (maxQSize == minQSize) {return (maxQ.peek() + minQ.peek()) / 2;}//元素个数不相等，取元素多的堆顶元素return maxQSize > minQSize ? maxQ.peek() : minQ.peek();}//插入元素public void addNum(int num) {if (maxQ.isEmpty()) {maxQ.add(num);} else {if (maxQ.peek() >= num) {maxQ.add(num);} else {minQ.add(num);}}modifyQSize();}/*** 调整两个堆的大小 一旦发现两个堆数据个数相差为2，则取多的丢到少的里面*/private void modifyQSize() {int minQSize = minQ.size();int maxQSize = maxQ.size();if (minQSize - maxQSize == 2) {maxQ.add(minQ.poll());}if (maxQSize - minQSize == 2) {minQ.add(maxQ.poll());}}}

测试用例以及结果输出

    public static void main(String[] args) {int[] aar = new int[]{8, 6, 13, 10, 11, 19};MedianHelper helper = new MedianHelper();for (int i : aar) {helper.addNum(i);}System.out.println(helper.getMedian());}

输出结果：

10

最低字典序

题目

给定一个字符串类型的数组strs，找到一种拼接方式，使得把所有字符串拼起来之后形成的字符串具有最低的字典序。

思路

保证每次拼接后的字符串都是最低字典序的即可；

代码实现

 private static String lowestString(String[] strs) {if (strs == null || strs.length == 0) {return "";}Arrays.sort(strs, new LowestComparator());StringBuilder result = new StringBuilder();for (int i = 0; i < strs.length; i++) {result.append(strs[i]);}return result.toString();}/*** 定义两个字符拼接最小字典序比较器*/private static class LowestComparator implements Comparator<String> {@Overridepublic int compare(String o1, String o2) {return (o1 + o2).compareTo(o2 + o1);}}

测试用例以及结果输出

    public static void main(String[] args) {String[] strs2 = {"b", "ab", "ac"};System.out.println(lowestString(strs2));}

结果输出：

abacb

结语

如果以上文章对您有一点点帮助，希望您不要吝啬的点个赞加个关注，您每一次小小的举动都是我坚持写作的不懈动力！ღ( ´･ᴗ･` )