共计 11096 个字符，预计需要花费 28 分钟才能阅读完成。
本教程概述并解释了贪心算法，并附有易于了解的代码和信息图表。你很快就会成为专业人士！
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 反对超过 60000 个字符，所以不能从一开始就关上一个容量为 60000 的数组。因而，当字符类型较多时，能够用哈希表代替数组来存储挂载的节点，哈希表的 key 也能够与字符一一对应。
用数组替换哈希表后，算法整体不会发生变化，Coding 的细节会发生变化。
然而，应用哈希表存储后，门路是无序的。如果你想让门路像数组存储一样组织起来，你能够应用有序表而不是哈希表存储。
应用已增加数据项的节点再次存储上述字符串：
通过增加带有数据项的节点，咱们能够轻松解决很多问题，例如：
我如何晓得字符串“bck”是否存储在 Trie 中？
答：从根节点开始，查看有没有方法 ’b’？是的; 有没有方法 ’c’ 呢？是的; 还有另一种办法能够“k”吗？是的; 而后查看 ’k’ 门路开端的节点的开端，如果 end != 0，则存储“bck”，如果 end = 0，则不存储“bck”。
我如何晓得存储在 Trie 中的所有字符串中有多少字符串以“ab”为前缀？
答：从根节点开始，查看有没有方法到 ’a’？是的; 有没有方法 ’b’ 呢？是的; 而后查看 ’b’ 门路开端节点的 pass。pass 的值是以“ab”为前缀的字符串数。
你怎么晓得 Trie 中存储了多少个字符串？
答：只有查看根节点的 pass 即可。
如何晓得 Trie 中存储了多少个空字符串？
答：只需查看根节点的开端即可。
通过以上问题咱们能够发现，利用节点类型的数据项信息，能够不便的查问 Trie 中存储的每个字符串，而且查问字符串的老本很低，只须要遍历其中的字符数即可要查问的字符串的次数就足够了。
1.3.2 树状构造
public class Trie {
// 根节点
private Node root;
public Trie() {this.root = new Node();
}
// 相干操作
...
}1.4 基本操作
1.4.1 增加字符串
思路：从根节点开始，沿途节点的 pass 加 1，字符串开端的节点加 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，字符串开端的节点减 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 查问字符串
思路：如果字符串存在，则查问字符串开端的节点。
代码：
// 查问 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 是对的，就是靠瞎眼和纯熟瞎眼。
在与贪婪算法相干的问题中，你总会有几种贪婪策略。如果能用反例来颠覆一些贪心的策略，那就再好不过了。然而如果有几个你感觉比拟靠谱的贪婪策略，又不能举反例，那你须要用严格的数学证实吗？你能够私下做问题，但不能在面试中！
贪婪策略的数学证实每道题都不一样，因为每道题都有本人的事，证实的办法也是不堪设想的，考验的是数学能力。
那么，你如何验证你的贪心策略是正确的呢？对数。
解决问题的套路：
要实现不依赖贪心策略的解决方案 X，能够应用最暴力的尝试。
大脑补救了贪心策略 A，贪心策略 B，贪心策略 C ……
用解 X 和对数来验证每个贪婪策略，并用试验来晓得哪个贪婪策略是正确的。
不要放心贪心策略的证实。
筹备：
为蛮力尝试或残缺的代码模板阵列做好筹备。
筹备对数代码模板。
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()); 通过生成随机数，能够使测试样本的任何局部随机化，例如：样本大小、测试次数、测试数据。
每个 topic 的业务逻辑不同，对数的实现也不同。您须要依据理论状况来施行。
4. 面试问题
4.1 求中位数
题目:
用户应用一个构造体将 N 个数字一一存储，并要求随时能够找到以后存储在该构造体中的所有数字的中位数。
规定：奇数位的中位数为两头位，偶数位的中位数为两头两位数的平均值。
剖析：
本课题与贪婪算法无关，是钻研反应堆利用的经典课题。
因为在贪婪算法中宽泛应用了堆，所以能够通过本专题相熟堆的操作。
该算法的工夫复杂度非常低，因为堆上的所有操作都是 O(logN)。
过程是：
筹备一个大根桩和一个小根桩。
第一个数字进入大根桩。
进入固定迭代过程：
以后输出的数字 cur <= 大根桩的顶号，如果是，则 cur 进入大根桩；如果没有，则 cur 进入小根桩。
察看大根桩和小根桩的大小。如果较大的比拟小的多 2 个，则较大的顶部会弹出另一个。
存储所有数字后进行迭代。
较小的 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 块铜板。
输出一个数组并返回拆分的最小老本。
剖析：
这个问题是经典的霍夫曼编码问题。
过程是：
将数组中的所有元素放入小根堆
迭代固定过程：
从小根桩的顶部弹出两个节点并将它们组合成新节点以构建霍夫曼树。
新节点被放回小根堆中。
进行迭代，直到小根堆中只有一个节点。
代码：
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 我的项目布局问题
题目:
你的团队收到了一些我的项目，每个我的项目都会有老本和利润。因为你的团队人很少，你只能按程序做我的项目。假如您团队目前的可摆布资金为 M 个，最多只能做 K 个我的项目，那么最终最大的可摆布资金是多少？
留神：casts[i]、progress[i]、M 和 K 都是负数。
剖析：
过程是：
建设一个小根桩和一个大根桩。小根桩的分类规范是老本，大根桩的分类规范是利润。
将所有物品放入小根堆中。
进入固定迭代过程：
小根堆将所有老本小于或等于 M 的物品弹出到大根堆中。
最赚钱的我的项目呈现了。
M 加上刚刚实现的我的项目的利润。
进行迭代，直到实现的项目数为 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 搁置地位，而后这三个地位顺次 depthwise 优先遍历，并一次又一次地开始。
代码：
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-queen 问题尽管不能从工夫复杂度上优化，然而能够从常数上优化，而且还有很多优化。
能够说工夫复杂度还是这样的工夫复杂度，然而我在实现过程中能够在恒定工夫内把它弄的很低。
它有多低？例如，对于 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;
}获取更多收费材料加群：3907814