【数据结构与算法】贪心算法实战入门

1. 前缀树

1.1 说明

前缀树和贪心算法有关系，我们先不说是什么关系。

前缀树又称为Trie，单词查找树等，是一种树形的结构，用于存储大量的字符串。

它的特点在于，是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

1.2 经典前缀树

经典前缀树的字符是存储在通路上的，且每个节点是没有数据的。

1.3 代码定义

1.3.1 节点结构

为了用Trie实现某些特定的功能，实际上会在节点上添加一些数据项。

public class Node {
    // 构建前缀树时,该节点被到达过多少次
    int pass;
    // 该节点是否是某个字符串的结尾节点,如果是,是多少个字符串的结尾节点
    int end;
    // 各个字符的通路
    Node[] nexts; // HashMap<Char, Node> -- TreeMap<Char, Node>

    public Node() {
        this.pass = 0;
        this.end = 0;
        // 假如词典中只有'a'-'z',那么next[26],对应下标0-25
        // 通过下级是否有节点判断是否有路
        // nexts[0]==null表示下级没有存储'a'的路
        // nexts[0]!=null表示下级有存储'a'的路
        nexts = new Node[26];
    }
}
复制代码

注意：

在前缀树中，每一个节点的向下通路是通过挂载下级节点实现的。在代码的实现上是利用了数组的下标，给可以挂载的下级节点编号，从而可以利用下标和字符的一一对应实现每一条边”携带”不同的字符信息。

如果需要存储包含很多种类字符的字符串，那么使用数组来存储挂载节点不太合适，例如Java中就支持6万多种字符，总不能一开始就开辟容量为6万的数组吧。所以在字符种类很多时，可以将数组换成哈希表来存储挂载节点，通过哈希表的key也可以和字符实现一一对应。

将哈希表替换数组后，算法整体不会改变，Coding的细节会发生变化。

但是使用哈希表存储后，通路与通路之间是无序的，如果想要让通路像数组存储那样是有序组织的，可以使用有序表代替哈希表存储。

使用添加过数据项的节点再次存储上文中的字符串：

通过添加过数据项的节点，我们可以方便的解决很多问题，例如：

1. 如何知道Trie中有没有存储 “bck” 这个字符串？

   答：从根节点开始，查看有没有走向 ‘b’ 的路？有；接着有没有走向 ‘c’ 的路？有；再接着有没有走向 ‘k’ 的路？有；然后查看 ‘k’ 路径末尾节点的end，如果end != 0，那么存储了 “bck” ，如果end = 0，没有存储” bck” 。

2. 如何知道在Trie中存储的所有字符串中，有多少字符串的前缀是 “ab” ?

   答：从根节点开始，查看有没有走向 ‘a’ 的路？有；接着有没有走向 ‘b’ 的路？有；然后查看 ‘b’ 路径末尾节点的pass，pass的值就是前缀是 “ab” 的字符串数量。

3. 如何知道Trie中存储了多少个字符串？

   答：查看根节点的pass即可。

4. 如何知道Trie中存储了多少个空串？

   答：查看根节点的end即可。

通过上述问题，我们可以发现，利用节点种的数据项信息，我们可以非常方便的查询Trie中存入的各个字符串，并且查询字符串的代价很低，只需要遍历待查询字符串中字符数量的次数即可。

1.3.2 树结构

public class Trie {
    // 根节点
    private Node root;
    
    public Trie() {
        this.root = new Node();
    }
    
    // 相关操作
    ...
}
复制代码

1.4 基本操作

1.4.1 添加字符串

思路：从根节点开始，沿途节点的pass自增1，字符串末尾节点的end自增1。

代码：

public void insert(String word) {
    if (word == null) {
        return ;
    }
    char[] charSequence = word.toCharArray();
    // 字符串起始节点为根节点
    Node cur = this.root;
    cur.pass ++;
    for (int i = 0; i < charSequence.length; i ++) {
        int index = charSequence[i] - 'a';
        // 该字符对应节点如果没有挂载就挂载上
        if (cur.nexts[index] == null) {
            cur.nexts[index] = new Node();
        }
        // 向下遍历
        cur = cur.nexts[index];
        cur.pass ++;
    }
    // 记录字符串结尾节点
    cur.end ++;
}
复制代码

注意：添加每一个字符串都要从根出发，也就意味着，每一个字符串都是以空串作为前缀的。

1.4.2 删除字符串

思路：如果字符串存在的话，从根节点开始，沿途节点的pass自减1，字符串末尾节点的end自减1。

代码：

public void delete(String word) {
    // 判断是否存储该单词
    if (word == null || search(word) == 0) {
        return ;
    }
    char[] charSequence = word.toCharArray();
    Node cur = this.root;
    cur.pass --;
    for (int i = 0; i < charSequence.length; i ++) {
        int index = charSequence[i] - 'a';
        // 当前节点的下级节点在更新数据后pass为0,意味这没有没有任何一个字符串还通过该节点
        if (-- cur.nexts[index].pass == 0) {
            // 释放掉下级路径的所有节点
            cur.nexts[index] = null;
            return ;
        }
        cur = cur.nexts[index];
    }
    cur.end --;
}
复制代码

注意：如果目标字符串在Trie中只存储了一个，那么在修改节点数据后，需要把多余的节点全部释放掉。在Java中因为有垃圾自动回收，所以当我们第一次遍历到某个节点的pass为0时，就可以直接其置为null，那么该节点的所有下级节点也会自动被回收。如果使用C++实现，那么就要遍历到底，沿途回溯时，再调用析构函数手动释放节点。

1.4.3 查询字符串

思路：如果字符串存在的话，查询字符串末尾节点的end。

代码：

// 查询word这个单词被存储的次数
public int search(String word) {
    if (word == null) {
        return 0;
    }
    char[] charSequence = word.toCharArray();
    Node cur = this.root;
    // 只遍历Trie,不更新数据
    for (int i = 0; i < charSequence.length; i ++) {
        int index = charSequence[i] - 'a';
        // 如果没有挂载节点,说明没有存该字符串
        if (cur.nexts[index] == null) {
            return 0;
        }
        cur = cur.nexts[index];
    }
    // 返回字符串末尾节点的end
    return cur.end;
}
复制代码

1.4.4 查询前缀

思路：如果字符串存在的话，查询前缀字符串末尾节点的pass。

代码：

// Trie存储的字符串中,前缀是pre的字符串个数
public int preFixNumber(String pre) {
    if (pre == null) {
        return 0;
    }
    char[] charSequence = pre.toCharArray();
    Node cur = this.root;
    // 只遍历Trie,不更新数据
    for (int i = 0; i < charSequence.length; i ++) {
        int index = charSequence[i] - 'a';
        // 如果没有挂载节点,说明没有字符串以该子串作为前缀
        if (cur.nexts[index] == null) {
            return 0;
        }
        cur = cur.nexts[index];
    }
    // 返回pre子串末尾节点的pass
    return cur.pass;
}
复制代码

2. 贪心算法

2.1 概念

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

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

2.2 说明

贪心算法其实是最常用的算法，代码实现也非常短。

很多贪心算法只要求找到优良解，而不是最优解。也就是说，大部分日常中的贪心算法，它的局部最优如何到整体最优的过程是没办法证明的，或者说证明出来就是错的，因为有时贪心是非常主观的。但是我们日常接触到的贪心算法的题目都是具备确定性的，是能够求出全局最优解的，这时对贪心算法的考察就需要有从局部最优到整体最优的一个证明。

本文不会展示证明的过程，因为每一道题，它局部最优策略如何推出全局最优的证明都不一样。如果每一道贪心算法题目都去证明的话，在面试过程中的时间根本不够。下文会介绍一种非常好用的技巧，这个技巧的前提是需要准备很多模板，但是只需要准备一次。准备之后，以后再做贪心算法的题目时，出答案会既快又准，比证明要快得多。

2.3 会议问题

题目：

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

分析：

贪心策略A：开始时间越早的项目越先安排。

不能得到全局最优解，反例如下：

贪心策略B：持续时间越短的项目越先安排。

不能得到全局最优解，反例如下：

贪心策略C：结束时间越早的项目越先安排。

可以得到全局最优解。

策略A反例：

策略B反例：

代码：

public class Solution {
 	   
    static class Program {
        // 项目开始时间
        public int begin;
        // 项目结束时间
        public int end;
        public Program(int begin, int end) {
            this.begin = begin;
            this.end = end;
        }
    }

    // 定义Program比较器,按照Program的结束时间来比较
    static class ProgramComparator implements Comparator<Program> {
        @Override
        public int compare(Program program1, Program program2) {
            return program1.end - program2.end;
        }
    }

    public int arrangeProgram(Program[] programs, int currentTime) {
        if (programs == null || programs.length == 0) {
            return 0;
        }
        // 可以安排项目的场数
        int number = 0;
        // 将Program数组按照结束时间早晚来排序,结束早的排前面
        Arrays.sort(programs, new ProgramComparator());
        for (int i = 0; i < programs.length; i ++) {
            // 如果当前时间还没到会议开始时间,安排会议
            if (currentTime < programs[i].begin) {
                number ++;
            }
            // 当前时间来到会议结束
            currentTime = programs[i].end;
        }
        return number;
    }
}
复制代码

2.4 解题套路

看了2.3，肯定会有疑问，为什么贪心策略C就可以求出最优解呢？别去纠结为什么贪心策略C是对的，就是靠蒙，有技巧的蒙。

在贪心算法相关的题目中，你总会有若干个贪心策略，如果能用举反例的方式推翻几个贪心策略，固然是好。但是如果有几个贪心策略你感觉比较靠谱，但是又举不出反例来，是否需要用严格的数学证明？私下做题时可以，但是面试时千万不行！

贪心策略的数学证明每一道题都不一样，因为每道题都有专属于自己的业务，证明的方式也匪夷所思，及其考验数学能力。

那用什么方式来验证你蒙的贪心策略到底对不对？对数器。

解题套路：

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

准备：

1. 准备暴力尝试或者全排列的代码模板。
2. 准备对数器代码模板。

2.5 面试地位

贪心算法的题目缺乏弹性，在面试中的占比比较低，大概五道题最多考一题。

第一，贪心算法的题目考验不了Coding的技巧，因为代码都及其简单。

第二，贪心算法的题目没有区分度，只要把贪心策略找对，做出来都是一样的，只有0和1的区别。

3. 对数器

3.1 说明

对数器非常好用，可以帮你解决很多问题。

假设现在要测方法A，但是同一个问题可以有很多策略来实现。如果不考虑事件复杂度的好坏，我可以写出一个暴力尝试的解法（例如列出所有的排列组合），我们把不追求时间复杂度优劣，但是很好想又很好写的方法叫做方法B。为什么要测方法A呢？因为可能方法A比较难想或者时间复杂度比较低。

之前，是否每一次测试都需要依赖线上OJ？如果你每一道题目都得依赖OJ，那么你遇到一个陌生的题目还得去OJ上找吗？找不到，你就不练它了吗？其次，线上测试数据也是人想的，那么他准备测试用例的时候，会不会没有让你代码跑出错，但是没有让你过的情况？你就算过了，但是你能保证你的代码就一定对吗？不一定，这时就需要对数器方法了，对数器方法是万无一失的。

3.2 实现

实现一个随机样本发生器，可以控制样本大小，可以控制测试的次数，并且可以生成随机数据。生成的数据在方法A中跑一遍得到res1，再在方法B中跑一遍得到res2，比对res1和res2是否一致。你测它几万组，再改变样本的大小，当你发现res1和res2不一致的时候，那就要不然方法A错了，要不然方法B错了，要不然就都错了。

随机数在Java中的实现：

// [0,1)上所有小数，等概率返回一个，double类型
random = Math.random();
// [0,N)上所有小数，等概率返回一个，double类型
random = N * Math.random();
// [0,N-1]上所有整数，等概率返回一个，int类型
random = (int) (N * Math.random());               
复制代码

通过生成随机数，可以让测试样本中任何一部分随机，例如：样本大小，测试次数，测试数据。

每一道题目业务逻辑不同，对数器的实现也都不一样，需要自己去按照实际情况实现。

4. 面试题

4.1 寻找中位数

题目：

用户使用一种结构挨个存储N个数字，要求随时都能从结构中找出当前存储所有数字的中位数。

规定：奇数个数字的中位数就是中间的数字，偶数个数字的中位数是中间两个数字的平均数。

分析：

该题目与贪心算法无关，是一道经典的考察堆应用的题目。

因为贪心算法中会大量运用到堆，所以可以通过此题目熟悉一下对堆的操作。

该算法的时间复杂度很低，因为堆的所有操作都是O(logN)。

流程为：

1. 准备一个大根堆和一个小根堆。
2. 第一个数字进入大根堆。
3. 进入固定迭代流程：
   1. 当前输入数字cur是否 <= 大根堆堆顶数字，如果是，cur入大根堆；如果不是，cur入小根堆。
   2. 观察大根堆和小根堆的size，如果大的一方比小的一方多2个，大的一方的堆顶弹出进入另一方。
   3. 所有数字存储完停止迭代。
4. 较小的N/2个数字在大根堆里，较大的N/2个数字在小根堆里，通过两个堆的堆顶数字就能求出中位数。

代码：

public class Solution {

    // 大根堆比较器
    static class BigComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer num1, Integer num2) {
            return num2 - num1;
        }
    }

    public static int findMedian(int[] input) {
        if (input == null || input.length == 0) {
            return 0;
        }
        PriorityQueue<Integer> bigRootHeap = new PriorityQueue<>(new BigComparator());
        PriorityQueue<Integer> smallRootHeap = new PriorityQueue<>();
        // 第一个数先入大根堆
        bigRootHeap.add(input[0]);
        for (int i = 1; i < input.length; i ++) {
            if (input[i] <= bigRootHeap.peek()) {
                bigRootHeap.add(input[i]);
            } else {
                smallRootHeap.add(input[i]);
            }
            if (Math.abs(bigRootHeap.size() - smallRootHeap.size()) == 2) {
                if (bigRootHeap.size() > smallRootHeap.size()) {
                    smallRootHeap.add(bigRootHeap.poll());
                } else {
                    bigRootHeap.add(smallRootHeap.poll());
                }
            }
        }
        // 判断输入数字个数是奇数还是偶数
        if (input.length % 2 != 0) {
            return smallRootHeap.peek();
        }
        return (bigRootHeap.peek() + smallRootHeap.peek()) / 2;
    }
}
复制代码

4.2 金条问题

题目：

一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为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. 迭代固定流程：
   1. 从小根堆顶弹出两个节点，组合成新节点构建哈夫曼树。
   2. 新节点重新放入小根堆。
   3. 直到小根堆只有一个节点时停止迭代。

代码：

public int leastMoney(int[] parts) {
    PriorityQueue<Integer> smallRootHeap = new PriorityQueue<>();
    // 需要花费的最少钱数
    int money = 0;
    // 将节点全部放入小根堆
    for (int i = 0; i < parts.length; i ++) {
        smallRootHeap.add(parts[i]);
    }
    // 直到堆中只有一个节点时停止
    while (smallRootHeap.size() != 1) {
        // 每次堆顶弹两个算累加和
        int cur = smallRootHeap.poll() + smallRootHeap.poll();
        money += cur;
        // 累加和的新节点入堆
        smallRootHeap.add(cur);
    }
    return money;
}
复制代码

4.3 项目规划问题

题目：

你们团队接到了一些项目，每个项目都会有花费casts和利润profits。由于你的团队人很少，只能串行的去做项目。在你们团队目前可支配资金为M，最多只能做K个项目的情况下，最终可支配资金最多是多少？

注意：casts[i]，profits[i]，M，K都是正数。

分析：

流程为：

1. 构建一个小根堆和一个大根堆。小根堆的排序标准是花费，大根堆的排序标准是利润。
2. 将所有的项目放入小根堆。
3. 进入固定迭代流程：
   1. 小根堆弹出所有花费小于等于M的项目进入大根堆。
   2. 大根堆弹出利润最大的项目做。
   3. M加上刚做完的项目的利润。
   4. 直到已做项目数量为K时停止迭代。

代码：

public class Solution {

    static class Project {
        int cost;
        int profit;
        public Project(int cost, int profit) {
            this.cost = cost;
            this.profit = profit;
        }
    }

    static class minCostComparator implements Comparator<Project> {
        @Override
        public int compare(Project p1, Project p2) {
            return p1.cost - p2.cost;
        }
    }

    static class maxProfitComparator implements Comparator<Project> {
        @Override
        public int compare(Project p1, Project p2) {
            return p2.profit - p1.profit;
        }
    }

    public static int findMaximumFund(int M, int K, int[] costs, int[] profits) {
        if (M == 0 || K == 0) {
            return 0;
        }
        // 通过花费构建小根堆
        PriorityQueue<Project> costSmallRootHeap = new PriorityQueue<>(new minCostComparator());
        // 通过利润构建大根堆
        PriorityQueue<Project> profitBigRootHeap = new PriorityQueue<>(new maxProfitComparator());
        // 将所有项目全部放入小根堆
        for (int i = 0; i < costs.length; i ++) {
            costSmallRootHeap.add(new Project(costs[i], profits[i]));
        }
        // 一共只能做K个项目
        for (int i = 0; i < K; i ++) {
            // 将小根堆中当前可以做的项目放入大根堆
            while (!costSmallRootHeap.isEmpty() && costSmallRootHeap.peek().cost <= M) {
                profitBigRootHeap.add(costSmallRootHeap.poll());
            }
            // 没有可以做的项目
            if (profitBigRootHeap.isEmpty()) {
                return M;
            }
            // 从大根堆中选选取利润最大的做
            Project cur = profitBigRootHeap.poll();
            M += cur.profit;
        }
        return M;
    }
}
复制代码

4.4 N皇后问题

题目：

N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列，也不在同一条斜线上。

给定一个整数n，返回n皇后的摆法有多少种。

例如：

n=1，返回1。

n=2或3，返回0。（2皇后和3皇后问题无论怎么摆都不行）

n=8，返回92。

分析：

该题是一道经典问题，最优解非常复杂，属于有后效性的动态规划问题。

如果不是写论文的，在面试过程中最优解就是：利用深度优先的思想，每一行依次放皇后，使用暴力递归将每一列的可能性都尝试一遍。

这种解的时间复杂度指标依旧非常高。

因为，第一行有N种选择，第二行有N种选择，第三行也有N种选择，……，一共有N行，所以时间复杂度为O(N^N)。

假设，record[0] = 2，record[1] = 4，当深度优先遍历到 i = 2时，图示在第三行有3种Queen的合理摆放位置，这三个位置再依次进行深度优先遍历，周而复始。

代码：

public static int nQueen(int n) {
    if (n < 1) {
        return 0;
    }
    int[] record = new int[n];
    // 从第0行开始
    return process(0, n, record);
}

/**
 * @param i 当前遍历第几行
 * @param n 一共多少行
 * @param record [0,i-1]行已经摆放的Queen的位置,record[1]=2表示第1行第2列已摆放一个Queen
 * @return n行n列棋盘中摆n个Queen的合理的摆法总数
 */
public static int process(int i, int n, int[] record) {
    // 遍历到最后一行的下一行结束递归,说明这条摆放方案合理
    if (i == n) {
        return 1;
    }
    // 记录[i,n-1]行合理的摆法总数
    int result = 0;
    // 尝试第i行的[0,n-1]列进行深度优先遍历
    for (int j = 0; j < n; j ++) {
        // 判断在第i行第j列的位置上是否能放Queen
        if (isValid(i, j, record)) {
            record[i] = j;
            // 遍历下一行
            result += process(i + 1, n, record);
        }
    }
    return result;
}

// 检查第i行第j列能不能放Queen
public static boolean isValid(int i, int j, int[] record) {
    // 遍历[0,i-1]行放过的所有Queen,检查是否和当前位置有冲突
    for (int k = 0; k < i; k ++) {
        // 判断是否是同一列或者是否共斜线(不可能共行)
        if (record[k] == j || Math.abs(k - i) == Math.abs(record[k] - j)) {
            return false;
        }
    }
    return true;
}
复制代码

4.5 N皇后问题(优化)

虽然N皇后问题在时间复杂度指标上无法优化了，但是可以在常数上进行优化，而且优化的还很多。

可以这么说，时间复杂度还是这么个时间复杂度，但是我可以让它在实现过程中常数时间变的非常低。

有多低，比方说，一个14皇后问题，使用4.4的解法会跑5s，用4.5优化后的解法会跑0.2s。一个15皇后问题，使用4.4解法会跑1分钟，用4.5优化后的解法会跑1.5s。

分析：

使用位运算来加速。位运算加速是非常常用的技巧，建议掌握。

既然使用位运算，那么和代码中变量的存储形式有关系，本代码中变量的类型为32位的int，所以不能解决32皇后以上的问题。

如果要解决32皇后以上的问题，那么可以把参数类型改为long。

代码：

public static int nQueen(int n) {
    if (n < 1 || n > 32) {
        return 0;
    }
    int limit = n == 32 ? -1 : (1 << n) - 1;
    return process(limit, 0, 0, 0);
}

/**
 * @param n 一共多少行
 * @param colLim 列的限制，1的位置不能放皇后，0的位置可以
 * @param leftDiaLim 左斜线的限制，1的位置不能放皇后，0的位置可以
 * @param rightDiaLim 右斜线的限制，1的位置不能放皇后，0的位置可以
 * @return  n行n列棋盘中摆n个Queen的合理的摆法总数
 */
public static int process(int n, int colLim, int leftDiaLim, int rightDiaLim) {
    // 皇后是否填满
    if (colLim == n) {
        return 1;
    }
    int mostRightOne = 0;
    // 所有后选皇后的列都在pos的位信息上
    int pos = n & (~ (colLim | leftDiaLim | rightDiaLim));
    int res = 0;
    while (pos != 0) {
        // 提取出候选皇后中最右侧的1
        mostRightOne = pos & (~ pos + 1);
        pos = pos - mostRightOne;
        // 更新限制，进入递归
        res += process(n, colLim | mostRightOne,
                       (leftDiaLim | mostRightOne) << 1,
                       (rightDiaLim | mostRightOne) >>> 1);
    }
    return res;
}
复制代码