介绍前缀树：

何为前缀树？ 如何生成前缀树？ 例子： 一个字符串类型的数组arr1，另一个字符串类型的数组arr2

每一个字母填在路上，不是填在点上的，前缀树（try树）的加法：

 用处：给N个字符串，问所有的字符串中是否有以某几个字符（BE）开头的；

+：若问加的字符串中是否包含BE，不好找是否新加进去的含有还是不含有，所以在数据项上加上有几个字符是以这个值结尾的，就是在节点上加上值，因此扩充了功能。

+：给一个字符串，有多少个字符串以它作为前缀，加一个数据项，每个节点被划过几次

查询的代价为树划过的长度

package zuoshen7; public class Code_01_TrieTree { public static class TrieNode { public int path;//经过这个节点的字符串数量 public int end;//以这个节点结尾的字符串的数量 public TrieNode[] nexts;//路 //这里也可以用哈希map， //public HashMap<char,TrieNode> public TrieNode() {//初始化 path = 0; end = 0; nexts = new TrieNode[26];//若是字母就是26，若是0-256，那就256 //检查一条路下一个节点是否为空来判断是否存在这条路 } } public static class Trie { private TrieNode root; public Trie() { root = new TrieNode();//首先就要有一个根结点 } public void insert(String word) {//插入 if (word == null) { return; } char[] chs = word.toCharArray();//将这个字符转成char类型的数组 TrieNode node = root;//从头节点开始 int index = 0;//当前位置index为0 for (int i = 0; i < chs.length; i++) { index = chs[i] - 'a'; if (node.nexts[index] == null) {//当前位置有没有走向这个值的路 node.nexts[index] = new TrieNode();//没有就建出这个节点来 } node = node.nexts[index];//若有，就往下跳一个 node.path++;//path+1 } node.end++;//循环结束，这个节点是结尾了，end+1 } public void delete(String word) { if (search(word) != 0) { char[] chs = word.toCharArray(); TrieNode node = root; int index = 0; for (int i = 0; i < chs.length; i++) { index = chs[i] - 'a'; if (--node.nexts[index].path == 0) { node.nexts[index] = null; return; } node = node.nexts[index]; } node.end--; } } public int search(String word) {//查一个word在其中出现几次 if (word == null) { return 0; } char[] chs = word.toCharArray(); TrieNode node = root; int index = 0; for (int i = 0; i < chs.length; i++) { index = chs[i] - 'a'; if (node.nexts[index] == null) { return 0; } node = node.nexts[index]; } return node.end; } public int prefixNumber(String pre) {//查某一个字符串前缀数量是多少，怎么插入的怎么找 if (pre == null) { return 0; } char[] chs = pre.toCharArray(); TrieNode node = root; int index = 0; for (int i = 0; i < chs.length; i++) { index = chs[i] - 'a'; if (node.nexts[index] == null) { return 0; } node = node.nexts[index]; } return node.path;//就是查出现了多少次 } } public static void main(String[] args) { Trie trie = new Trie(); System.out.println(trie.search("zuo")); trie.insert("zuo"); System.out.println(trie.search("zuo")); trie.delete("zuo"); System.out.println(trie.search("zuo")); trie.insert("zuo"); trie.insert("zuo"); trie.delete("zuo"); System.out.println(trie.search("zuo")); trie.delete("zuo"); System.out.println(trie.search("zuo")); trie.insert("zuoa"); trie.insert("zuoac"); trie.insert("zuoab"); trie.insert("zuoad"); trie.delete("zuoa"); System.out.println(trie.search("zuoa")); System.out.println(trie.prefixNumber("zuo")); } }

题目七：问题：给一个字符串类型的数组，目的是将所有的字符串拼起来，会得到很多种拼接的结果，找到拼接出的所有中字典序最小的结果。

贪心问题，没太听懂这里

堆往往就是用来解决贪心的问题，定义一个比较器，可以按照比较器定义的规则进行比较计算

字典序概念：哪个字母出现在前面，若长度一样，把字符串想成一个26进制的数，比较字面值大小

                                                         若长度不一样，就用0将短的补成一样长度的，扩长度

给定一个字符串类型的数组strs，找到一种拼接方式，使得把所 有字 符串拼起来之后形成的字符串具有最低的字典序。

题目四  ： 一块金条切成两半，是需要花费和长度数值一样的铜板的。

比如 长度为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铜板。 输入一个数组，返回分割的最小代价。

哈夫曼编码经典问题：

所有非叶子节点的和是代价；子节点合并在一起的代价是加起来的和；

过程是把所有非叶节点合并，代价就是这两个的和；

eg：若有一堆数：1.2.6.4.3.7.1.8

先把这些数加到一个小根堆里去，每一次从小根堆拿出两个数，1.1，产生代价为2，把2仍回到堆，再拿出两个最小，2.2，代价为4，4扔回去，再拿两个最小的，4，3，代价为7，7扔回去。。。。直到堆里只剩一个数，停。

切割的顺序就是堆从上往下，哈夫曼编码是和的过程，切割是分的过程。

package class_07; import java.util.Comparator; import java.util.PriorityQueue; public class Code_02_Less_Money { public static int lessMoney(int[] arr) { PriorityQueue<Integer> pQ = new PriorityQueue<>(); for (int i = 0; i < arr.length; i++) { pQ.add(arr[i]); } int sum = 0; int cur = 0; while (pQ.size() > 1) { cur = pQ.poll() + pQ.poll(); sum += cur; pQ.add(cur); } return sum; } public static class MinheapComparator implements Comparator<Integer> { @Override public int compare(Integer o1, Integer o2) { return o1 - o2; // < 0 o1 < o2 负数 } } public static class MaxheapComparator implements Comparator<Integer> { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; // < o2 < o1 } } public static void main(String[] args) { // solution int[] arr = { 6, 7, 8, 9 }; System.out.println(lessMoney(arr)); int[] arrForHeap = { 3, 5, 2, 7, 0, 1, 6, 4 }; // min heap PriorityQueue<Integer> minQ1 = new PriorityQueue<>(); for (int i = 0; i < arrForHeap.length; i++) { minQ1.add(arrForHeap[i]); } while (!minQ1.isEmpty()) { System.out.print(minQ1.poll() + " "); } System.out.println(); // min heap use Comparator PriorityQueue<Integer> minQ2 = new PriorityQueue<>(new MinheapComparator()); for (int i = 0; i < arrForHeap.length; i++) { minQ2.add(arrForHeap[i]); } while (!minQ2.isEmpty()) { System.out.print(minQ2.poll() + " "); } System.out.println(); // max heap use Comparator PriorityQueue<Integer> maxQ = new PriorityQueue<>(new MaxheapComparator()); for (int i = 0; i < arrForHeap.length; i++) { maxQ.add(arrForHeap[i]); } while (!maxQ.isEmpty()) { System.out.print(maxQ.poll() + " "); } } }

题目五  :

输入： 参数1，正数数组costs 参数2，正数数组profits 参数3， 正数k 参数4，正数m costs[i]表示i号项目的花费 profits[i]表示i号项目在扣除花 费之后还能挣到的钱(利润) k表示你不能并行、只能串行的最多 做k个项目 m表示你初始的资金 说明：你每做完一个项目，马上获得的收益，可以支持你去做下 一个 项目。 输出： 你最后获得的最大钱数。

1.首先建立一个小根堆，花费小的在顶部，所有花费小于初始资金的（可解锁的），从小根堆里边出来，进入大根堆，谁的收益高谁在顶部。

2.第一个项目OK之后，初始资金变化，新的初始资金解锁新的项目，进入大根堆；如果不能解锁新的项目，就还在之前的大根堆再选一个。

3.一直做K个，结束。

小根堆中就是待解锁的项目，大根堆是已经解锁的项目。

package class_07; import java.util.Comparator; import java.util.PriorityQueue; public class Code_03_IPO { public static class Node { public int p; public int c; public Node(int p, int c) { this.p = p; this.c = c; } } public static class MinCostComparator implements Comparator<Node> { @Override public int compare(Node o1, Node o2) { return o1.c - o2.c; } } public static class MaxProfitComparator implements Comparator<Node> { @Override public int compare(Node o1, Node o2) { return o2.p - o1.p; } } public static int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) { Node[] nodes = new Node[Profits.length]; for (int i = 0; i < Profits.length; i++) { nodes[i] = new Node(Profits[i], Capital[i]); } PriorityQueue<Node> minCostQ = new PriorityQueue<>(new MinCostComparator()); PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator()); for (int i = 0; i < nodes.length; i++) { minCostQ.add(nodes[i]); } for (int i = 0; i < k; i++) { while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) { maxProfitQ.add(minCostQ.poll()); } if (maxProfitQ.isEmpty()) { return W; } W += maxProfitQ.poll().p; } return W; } }

题目八  : 

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

分析：不能按照哪个项目早开始，哪个项目时间短来安排。

找哪个项目早结束，然后淘汰掉因为这个项目而淘汰掉的项目，然后看下一个早结束的项目，按照这样安排，安排的项目是最多的。

package class_07; import java.util.Arrays; import java.util.Comparator; public class Code_06_BestArrange { public static class Program { public int start; public int end; public Program(int start, int end) { this.start = start; this.end = end; } } public static class ProgramComparator implements Comparator<Program> { @Override public int compare(Program o1, Program o2) { return o1.end - o2.end; } } public static int bestArrange(Program[] programs, int start) { Arrays.sort(programs, new ProgramComparator()); int result = 0; for (int i = 0; i < programs.length; i++) { if (start <= programs[i].start) { result++; start = programs[i].end; } } return result; } public static void main(String[] args) { } }