贪心是一个经验性的东西,要不断积累,找一个你认为对的贪心策略,要能举出反例证明一个策略是否是正确的
1.哈夫曼编码问题
用一个优先级队列表示堆
import java.util.Comparator; import java.util.PriorityQueue; public class Solution { public static int lessMoney(int[] arr){ PriorityQueue<Integer> pq = new PriorityQueue<>(new MinHeapComparator()); for(int i = 0; i < arr.length; i++){ pq.add(arr[i]); } int sum = 0; int cur = 0; while(pq.size() > 1){ cur = pq.poll() + pq.poll(); sum += cur; pq.add(cur); } return sum; } public static class MinHeapComparator implements Comparator<Integer>{ @Override public int compare(Integer o1, Integer o2){ return o1 - o2; } } }
2.leetcode502 :IPO
import java.util.Comparator; import java.util.PriorityQueue; public class IPO { public static class Node{ public int p; //profit public int c; //capital public Node(int p, int c){ this.p = p; this.c = c; } } public static class minCostComparaor implements Comparator<Node>{ @Override public int compare(Node o1, Node o2) { return o1.c - o2.c; } } public static class maxProfitComparator implements Comparator<Node>{ @Override public int compare(Node o1, Node o2) { return o2.p - o1.p; } } public static int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {//k项目个数//w资本 Node[] nodes = new Node[Profits.length]; for(int i = 0; i < Profits.length; i++){ nodes[i] = new Node(Profits[i], Capital[i]); } PriorityQueue<Node> minCostQ = new PriorityQueue<>(new minCostComparaor());//小根堆 PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new maxProfitComparator());//大根堆 for(int i = 0; i < nodes.length; i++){ minCostQ.add(nodes[i]); } for(int i = 0; i < k; i++){ while(!minCostQ.isEmpty() && minCostQ.peek().c <= W){ maxProfitQ.add(minCostQ.poll()); } if(maxProfitQ.isEmpty()) return W; W += maxProfitQ.poll().p; } return W; } }
3.
和leetcode 253 : 会议室II差不多,形式上有些变化
import java.util.Arrays; import java.util.Comparator; public class BestArrange { public static class Program{ public int start; public int end; public Program(int start, int end){ this.start = start; this.end = end; } } public static int bestArrange(Program[] programs, int cur){ //贪心策略:按照每个项目结束的时间排序 Arrays.sort(programs, new Comparator<Program>() { @Override public int compare(Program o1, Program o2) { return o1.end - o2.end; } }); int res = 0; for(int i = 0; i < programs.length; i++){ if(cur <= programs[i].start) res ++; cur = programs[i].end; } return res; } }