1.前缀树
1.1说明
前缀树和贪心算法有关系哈夫曼编码贪心算法时间复杂度，我们先不说是哪些关系。
前缀树又称为Trie，词组查找树等，是一砍树形的结构，用于储存大量的字符串。
它的特征在于，是空间换时间，借助字符串的公共前缀来增加查询时间的开支以达到提升效率的目的。
1.2精典前缀树
精典前缀树的字符是存贮在通路上的，且每位节点是没有数据的。
1.3代码定义
1.3.1节点结构
为了用Trie实现个别特定的功能，实际上会在节点上添加一些数据项。
注意：
在前缀树中，每一个节点的向上通路是通过挂载下级节点实现的。在代码的实现上是借助了链表的下标，给可以挂载的下级节点编号，因而可以借助下标和字符的一一对应实现每一条边"携带"不同的字符信息。
假如须要储存包含好多种类字符的字符串，这么使用链表来储存挂载节点不太合适，比如Java中就支持6万多种字符，总不能一开始就开辟容量为6万的字段吧。所以在字符种类好多时，可以将字段换成哈希表来储存挂载节点，通过哈希表的key也可以和字符实现一一对应。
将哈希表替换字段后，算法整体不会改变，Coding的细节会发生变化。
并且使用哈希表储存后，通路与通路之间是无序的，假如想要让通路像链表储存那样是有序组织的，可以使用有序表替代哈希表储存。
使用添加过数据项的节点再度储存上文中的字符串：
通过添加过数据项的节点，我们可以便捷的解决好多问题，比如：
怎么晓得Trie中有没有储存"bck"这个字符串？答：从根节点开始，查看有没有迈向'b'的路？有；接着有没有迈向'c'的路？有；再接着有没有迈向'k'的路？有；之后查看'k'路径末尾节点的end，假如end!=0，这么储存了"bck"，假如end=0，没有储存"bck"。
怎么晓得在Trie中储存的所有字符串中，有多少字符串的前缀是"ab"?答：从根节点开始，查看有没有迈向'a'的路？有；接着有没有迈向'b'的路？有；之后查看'b'路径末尾节点的pass，pass的值就是前缀是"ab"的字符串数目。
怎么晓得Trie中储存了多少个字符串？答：查看根节点的pass即可。
怎么晓得Trie中储存了多少个空串？答：查看根节点的end即可。
通过上述问题，我们可以发觉，借助节点种的数据项信息，我们可以十分便捷的查询Trie中存入的各个字符串，但是查询字符串的代价很低，只须要遍历待查询字符串中字符数目的次数即可。
1.3.2树结构
2.贪心算法
2.1概念
在某一个标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫作贪心算法。
也就是说，不从整体最优上加以考虑，所作出的是在某种意义上的局部最优解。
2.2说明
贪心算法虽然是最常用的算法，代码实现也十分短。
好多贪心算法只要求找到优良解，而不是最优解。也就是说，大部份日常中的贪心算法，它的局部最优怎么到整体最优的过程是没办法证明的，或则说证明下来就是错的，由于有时贪心是十分主观的。并且我们日常接触到的贪心算法的题目都是具备确定性的，是能否求出全局最优解的，这时对贪心算法的考察就须要有从局部最优到整体最优的一个证明。
本文不会展示证明的过程，由于每一道题，它局部最优策略怎么推出全局最优的证明都不一样。假如每一道贪心算法题目都去证明的话，在笔试过程中的时间根本不够。下文会介绍一种特别好用的方法，这个方法的前提是须要打算好多模板，而且只须要打算一次。打算以后，之后再做贪心算法的题目时，出答案会既快又准，比证明要快得多。
2.3大会问题
题目：
一些项目要占用一个大会室宣讲，大会室不能同时容纳两个项目的宣讲。给你所有项目和每一个项目开始的时间和结束的时间，你来安排宣讲的日程，要求大会室进行的宣讲的场次最多。返回这个最多的宣讲场次。
剖析：
贪心策略A：开始时间越早的项目越先安排。
不能得到全局最优解，例子如下：
贪心策略B：持续时间越短的项目越先安排。
不能得到全局最优解，例子如下：
贪心策略C：结束时间越早的项目越先安排。
可以得到全局最优解。
策略A例子：
策略B例子：
代码：
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中的实现：
通过生成随机数，可以让测试样本中任何一部份随机，比如：样本大小，测试次数，测试数据。
每一道题目业务逻辑不同，对数器的实现也都不一样，须要自己去根据实际情况实现。
4.笔试题
4.1找寻中位数
题目：
用户使用一种结构逐个储存N个数字，要求随时都能从结构中找出当前储存所有数字的中位数。
规定：质数个数字的中位数就是中间的数字，质数个数字的中位数是中间两个数字的平均数。
剖析：
该题目与贪心算法无关，是一道精典的考察堆应用的题目。
由于贪心算法中会大量运用到堆，所以可以通过此题目熟悉一下对堆的操作。
该算法的时间复杂度很低，由于堆的所有操作都是O(logN)。
流程为：
打算一个大根堆和一个小根堆。
第一个数字步入大根堆。
步入固定迭代流程：
当前输入数字cur是否
