算法初阶笔记——贪心策略

贪心是一个经验性的东西，要不断积累，找一个你认为对的贪心策略，要能举出反例证明一个策略是否是正确的
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;
    }
}