在某一个标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫作贪心算法。

也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。

即：从局部最优如何到达整体最优

贪心算法的在笔试时的解题套路**

  1. 实现一个不依靠贪心策略的解法 X，可以用最暴力的尝试
  2. 脑补出贪心策略A、贪心策略B、贪心策略C……
  3. 用解法 X 和对数器，去验证每一个贪心策略，用实验的方式得知哪个贪心策略正确
  4. 不要去纠结贪心策略的证明

技巧：

  1. 根据某标准建立一个比较器来排序
  2. 根据某标准建立一个比较器来组成堆

会议室

一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给你每一个项目开始的时间和结束的时间（给你一个数组，里面是一个个具体的项目），你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。返回这个最多的宣讲场次。

思路：

  • 按照会议开始时间的先后顺序来计算

如果存在会议 A: 7:00 - 8:00、B: 8:30 - 10:00、C: 10:00 - 11:00、D: 6:00 - 13:00
按照开始时间会先先安排 D，这样 A、B、C 就不能使用会议室，显然改策略是不对的

  • 按照会议时间的长短来计算

存在会议 A: 7:00 - 8:40、B: 8:30 - 9:00、C: 8:50 - 11:00
按照时长会优先安排 B，这样 A、C 就不能安排，改策略不合适

  • 按照会议的结束时间先后顺序来计算

如果存在会议 A: 7:00 - 8:00、B: 7:30 - 10:00、C: 10:00 - 11:00、D: 12:00 - 13:00
就会依次安排 A、C、D，这个策略看似可以实现

  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Comparator;
  4. import java.util.List;
  6. public class BestArrange {
  8.     static class Program {
  9.         int start;
  10.         int end;
  12.         public Program(int start, int end) {
  13.             this.start = start;
  14.             this.end = end;
  15.         }
  17.         @Override
  18.         public String toString() {
  19.             return "Program{" + "start=" + start + ", end=" + end + '}';
  20.         }
  21.     }
  23.     public static Program[] bestArrange(Program[] programs, int timePoint) {
  24.         Arrays.sort(programs, Comparator.comparingInt(p -> p.end));
  25.         List<Program> list = new ArrayList<>();
  27.         for (Program program : programs) {
  28.             if (program.start >= timePoint) {
  29.                 list.add(program);
  30.                 timePoint = program.end;
  31.             }
  32.         }
  34.         return list.toArray(new Program[0]);
  35.     }
  37.     public static void main(String[] args) {
  38.         Program[] programs = new Program[]{
  39.                 new Program(6, 8),
  40.                 new Program(7, 9),
  41.                 new Program(8, 10),
  42.                 new Program(9, 12),
  43.                 new Program(14, 15),
  44.                 new Program(15, 17),
  45.                 new Program(16, 20),
  46.                 new Program(18, 19),
  47.         };
  49.         Program[] arrange = bestArrange(programs, 6);
  50.         System.out.println(arrange.length);
  51.         System.out.println(Arrays.toString(arrange));
  52.     }
  54. }

结果

5
[Program{start=6, end=8}, Program{start=8, end=10}, Program{start=14, end=15}, Program{start=15, end=17}, Program{start=18, end=19}]

最低字典序的字符串

给定一个字符串的数组strs，请找到一种拼接顺序，使得所有的字符串拼接起来组成的字符串是所有可能性中字典序最小的，并返回这个字符串
例如：

// 输入
abc
de
// 输出
abcde

// 输入
b
ba
// 输出
bab

思路：

  • 将所有的字符串按照字典序排序，然后依次拼接

输入 b、ba 按照该思路排序后为 b < ba 即 bba 显然不是字典序最小的

  • 比较两字符串拼接后的字典序，选择字典序小的拼接

输入 b、ba 按照该思路排序后为 bab < bba 即 bab

import java.util.Arrays;

public class LowestLexicography {

    static String lowestLexicography(String[] strs) {

        if (strs == null || strs.length == 0) return ""; 

        Arrays.sort(strs, (o1, o2) -> (o1 + o2).compareTo(o2 + o1));

        String res = "";

        for (String str : strs) {
            res += str;
        }

        return res;
    }

    public static void main(String[] args) {
        System.out.println(lowestLexicography(new String[]{"abc", "de"}));
        System.out.println(lowestLexicography(new String[]{"b", "ba"}));
        System.out.println(lowestLexicography(new String[]{"b", "ba", "cd", "dd", "csefd", "dofipws"}));
    }
}

结果

abcde
bab
babcdcsefddddofipws

分割金条

一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为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铜板。

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

思路：

  • 每次都先切最大的

如：
10,20,30 结果就是 60+30 = 90
20,30,35,45 总长 130，顺序为 45>35>30 结果为：130+95+50 = 275，如果顺序为 50>45>30 结果为 130+80+50 = 260

  • 将每次的切的结果画出来

[10,20,30]
image.png image.png
[20,30,35,45]
image.png image.png
把每次分割的结果都看成一个节点，只需要每个非叶子节点的和最小就可以保证最后的结果最小。每次都取最小的两个部分，保证和最小

import java.util.PriorityQueue;

public class LessMoneySplitGold {
    static int lessMoney(int[] arr) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i : arr) {
            queue.add(i);
        }
        int sum = 0;
        while (queue.size() > 1) {
            // 最小的两个部分
            int curSum = queue.poll() + queue.poll();
            sum += curSum;
            queue.add(curSum);
        }
        return sum;
    }

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

利润最大

输入：
正数数组 costs
正数数组 profits
正数 k
正数 m

含义：
costs[i] 表示i号项目的花费
profits[i] 表示i号项目在扣除花费之后还能挣到的钱（利润）
k 表示你只能串行的最多做 k 个项目
m 表示你初始的资金

说明：
你每做完一个项且马上获得的收益，可以支持你去做下一个项目。
你最后获得的最大钱数。

思路：每次都拿在 m 内能获取最大利润的项目

import java.util.Comparator;
import java.util.PriorityQueue;

public class IPO {
    static class Node {
        public int cost;
        public int profit;

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

    static int ipo(int[] costs, int[] profits, int k, int m) {
        // 思路：
        // 每次都拿 花费 <= m 的所有项目中利润最大的

        // 小根堆 花费
        PriorityQueue<Node> minQ = new PriorityQueue<>(Comparator.comparingInt(o -> o.cost));

        // 大根堆 利润
        PriorityQueue<Node> maxQ = new PriorityQueue<>((o1, o2) -> o2.profit - o1.profit);

        for (int i = 0; i < costs.length; i++) {
            minQ.add(new Node(costs[i], profits[i]));
        }

        while (k > 0 && !(minQ.isEmpty() && maxQ.isEmpty())) {
            // 将花费 <= m 的所有项目 放入大根堆中
            while (!minQ.isEmpty() && minQ.peek().cost <= m) {
                maxQ.add(minQ.poll());
            }

            if (maxQ.isEmpty()) return m;

            // 只要利润最大的
            Node node = maxQ.poll();
            m += node.profit;
            k--;
        }
        return m;
    }

    public static void main(String[] args) {
        int[] costs = new int[]{1, 12, 13, 1, 3, 5, 26};
        int[] profits = new int[]{2, 3, 4, 5, 7, 2, 4};
        for (int i = 0; i < costs.length; i++) {
            System.out.println(ipo(costs, profits, i + 1, 1));
        }
        System.out.println(ipo(costs, profits, costs.length + 1, 1));
    }
}

结果

6
13
17
20
22
24
24
24