介绍前缀树

经典的前缀树，字符都是在路上的，节点是为了边的存在而存在的，有路就可以复用。

那么前缀树对应的数据结构是什么样的呢？
对于节点构建结构，设置一个int pass（表示路径途径这个节点的次数），一个int end（表示路径在这个点结束了），其中边以一个【26】大小的数组存在，使得具备延伸出26条路径的潜力。

那么我们知道了前缀树，我们怎么知道一个指定的字符串前缀树中有没有呢？那就是怎么加的怎么查，就是照着这个字符串，从头结点开始，走到最后一个，看end是不是>1，是就有，并且end就是出现的次数。反之没有。

同时我们可以查看这个字符串集合的前缀使用情况。一样，就是搜前缀，走完前缀的节点之后，pass就是结果。

前缀树构建的具体实现

每一个字符串，开始按字符遍历，查看每一个字符，有没有走过这个路径对应的节点，如果没有走过，那就是得创建一个新的。然后节点下移，下一节点的pass++。

从而分析：根节点的pass就是总的字符串的数量（或者说是空串作为前缀的字符串的个数，显然全部）。如果是空串输入呢？根节点pass++，end++。

那如果我们这里的字符串不讲武德，不限制26的英文字母的时候怎么办呢，到时候一个字符种类数组就要多留一个，那就很费空间，所以可以使用map哈希表的结构，这样更加直观和好理解。

那我们想要删除一个前缀树中的字符串，可以吗？

当然可以，我们需要注意的是先查看输入的字符串是否存在，存在，就往下走，沿途pass–，结果的end–。
看起来很easy？但是万一我们这个时候删完了，有一条路都要删掉，也就是pass减到0了，那就需要整个删掉。这里使用C++的话，就得走到底之后，一个节点一个节点的手动设置next=null删除

md还是JAVA好啊，第一个删除，后面自动删，不用管的

C++的实现思路，我们需要设置节点和int变量，存储第一个不再用到的点已经对应的要删路径的编号，然后设置一个set存储后面的节点，这里不进行删除，就是pass–，最后end–。循环出来了，再遍历set把这些节点删了

贪心算法

最常用的算法。
就是优先考虑当前最好的。
但是这只是一个局部最优的问题，如果要用的话，我们就是要确定局部最优可以转化为整体最优

最经典的应该就是会议安排问题了

就是找合法的，结束时间最最早的会议给他们安排会议室

但是我怎么知道贪心的思路对不对呢？

1.我们可以实现一个不依靠贪心策略的解法，这个可以非常的暴力。
2.接下来我们开始脑补贪心策略A，B，C
3.用粗暴解法和对数器去验证我们每一个贪心的策略。只要都没错，那这个贪心就是对的。
4.之所以这样，是因为贪心的数学证明确实很麻烦，临场不好做

比如，字典序的比较方法（abk

如果我们要字符串拼接出来，要最小的字典序的话，怎么做呢？
如果我们按字典序排列拼接的话，这是一个传统贪心，但是‘b’,'ba’就是一个反例
我们重新设置比较器，对于字符串a和字符串b,对于ab和ba，选择字典序更小的那个。这样其实就对了

首先，我们需要确定一个真实有效的比较策略。这个比较的策略需要具备传递性（1<2 并且 2<5所以1<5，类似这样）。
不过光是这个传递性就很不好证明了，我们对于这一道题，可以把字符串当做是一个26进制的数字，通过不等式转换二合一证明可以传递。

然后证明了传递性之后，我们还要证明如果不满足我们的比较策略的话，他为什么就是不是最优的。这里就是证明+数学归纳法，真的超级麻烦

哈夫曼编码树也是一种贪心算法

使用STL的话哈夫曼编码巨简单，就是使用map就可以了，先拿最小的两个合起来，再放进去。

样例一

项目提供花费和利润，我们有一个明确的起始资金，问完成k个项目之后，我们最多能获得多少？
这就是一个非常自然思维的贪心方法。
先做一个按照花费的小根堆，按照我们的金钱选择满足的项目都拿出来，这些项目再按照利润做一个大根堆。

样例二

对于一个数据流，我们始终获得中位数怎么办呢？这也是一个堆的使用技巧
第一个数字，直接进大根堆，之后数字看是不是小于大根堆堆顶，小于就是进大堆反之进小根堆，如果进完之后两个堆的size差了2，那就多的那个堆的堆顶弹出，进入另一个堆。
这样是为了小的一半在大根堆里，大的一半在小根堆里，两个堆顶一定出中位数。
logn搞定一切

n皇后问题

这个就是经典的没有太好的方法就是暴力尝试的一个题目
经典的单皇后问题还是比较简单的，就是设置一个单数组存这，然后递归填数就可以了
然后一行行check下来
这个就是最最好的了，虽然N!真的很烂就是了。指标是改不了了，不过我们可以用位运算把常数时间优化很多很多，不过位运算的话，只好解决32皇后问题，毕竟位运算，int32位到头了。
比如说八皇后问题，
我第一行选择00001000
那么第二行是不是列限制为00001000
左斜线限制：00010000
右斜线限制：00000100
然后三个或运算即可
然后再下一行的时候左右斜线限制移位即可。
这里还需要一个limit为24位0+8位1.这个是为了防止前面的部分也被尝试，那是没必要的。
可以把limit和或运算的结果进行与运算，结果就是所有可以放皇后的位置。
结束条件就是列限制=11111111，就可以结束了

也可以算得上是非常优雅了