Summary
- 前缀树 Trie tree
1.1 前缀树定义
1.2 前缀树创建
1.3 查询word之前加入过几次
1.4 所有加入字符串中，有几个是以pre为前缀的
1.5 删除- 贪心 greedy
2.1 贪心算法定义
2.2 贪心解题思路
2.3 贪心常用技巧
2.4 会议室安排会议
2.5 切金条
2.6 最大钱数IPO -- 502 IPO(hard)
2.7 堆的应用--一个数据流中，随时取得中位数 -- 295 Find Median from Data Stream(hard)
1.前缀树 Trie tree
1.1 前缀树定义
在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值
1.2 前缀树创建
思路：
1. 创建TireNode类型，定义pass和end，并创建26条新的空路
2. 遍历时，先看有没有这条路径，若有就pass++，没有就创建新的
3. 每次字符经过一个点时，pass++，到达结尾点时end++
4. 查询前缀是，用pass。查询完整字符串时，用end
public class Trie TrieNode{
public int pass;//经过这个点，pass++
public int end;// 以这个点结尾, end++
public TrieNode[] nexts;// HashMap<Char, Node> nexts;
// or TreeMap<Char, Node> nexts;字符特别多的时候，用哈希表
public TrieNode(){
pass = 0;
end = 0;
//next[0] == null 没有走向“a”的路
//next[25] ！= null 有走向“z”的路
//提前建好26条路，但后面的节点都是空的
nexts = new TrieNode[26]
}
}
public class Trie{
Trie root;//头节点
public Trie{
root = new TrieNode();
}
public void insert(String word){
if(word == null){
return;
}
char[] chs = word.toCharArray();//把word转换成字符类型的数组
TireNode node = root;//node在根节点出发
node.pass++;//根节点p值：加入了多少个字符串或有多少个字符串是空串为前缀
int index = 0;
for (int i = 0; i < chs.length; i++){//从左到右遍历字符
index = chs[i] - 'a';//每个字母减a的ascii码，这样a的index是0，b是1，c是2
if (node.next[index] == null){
node.next[index] = new TrieNode();
}
node = node.nexts[index];
node.pass++;
}
node.end++;
}
}
1.3 查询word之前加入过几次
public int search(String 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.next[index] == null){
return 0;//树中的节点已经到头，但word还没查询完，说明原来没有加入过
}
node = node.next[index];
}
return node.end;//查询完成，全部匹配，end的值就是加入过几次
}
1.4 所有加入字符串中，有几个是以pre为前缀的
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.next[index] == null){
return 0;//树中的节点已经到头，但word还没查询完，说明原来没有加入过
}
node = node.next[index];
}
return node.pass;//查询完成，pre 匹配，看pass有几次
1.5 删除
public void delete(String word){//沿途pass--，最后end--
if(search(word) != 0){//先查询树中有没有加入过此word
char[] chs = word.toCharArray;
TrieNode node = root;
node.pass--;
int index = 0;
for (int i = 0; i < chas.length; i++){
index = chs[i] - 'a';
if(--node.nexts[index].pass == 0){//此处pass减完后为0，不需要遍历后续节点，直接把后面全部删除
//java 中可以，jvm直接把null后面的空间自动释放
//c++ 要遍历
node.nexts[index] = null;
return;
}
node = node.nexts[index];
}
node.end--;
}
}
2. 贪心 greedy
2.1 贪心算法定义
在某一标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，最终的道一个答案的算法。也就是说，不从整体最优考虑，所做出的是在某种意义上的局部最优解
局部最优 -？>整体最优
2.2 贪心解题思路
- 实现一个不依靠贪心的解法X，可以用最暴力的尝试
- 脑补出贪心策略A，B，C
- 用解法X和对数器，验证每一个贪心，用实验的方式得知哪个贪心是正确的
- 不纠结贪心策略的证明
2.3 贪心常用技巧
- 根据某标准建立一个比较器来排序
- 根据某标准建立一个比较器来组成堆
2.4 会议室安排会议
一段时间内，能安排的最多会议
思路：按结束时间安排，先安排结束时间早的，然后删除冲突的，剩下的继续找结束时间早的
public static int bestArrange(Program[] programs, int timePoint) {
Arrays.sort(programs, new ProgramComparator());
int result = 0;
// 依次遍历每一个会议，结束时间早的会议先遍历
for (int i = 0; i < programs.length; i++) {
if (timePoint <= programs[i].start) {
result++;
timePoint = programs[i].end;
}
}
return result;
}
public static class ProgramComparator implements Comparator<Program> {
@Override
public int compare(Program o1, Program o2) {
return o1.end - o2.end;
}
}
2.5 切金条
一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为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铜板。
输入一个数组，返回分割的最小代价.
思路：哈夫曼编码(Huffman Coding)
1. 把数组放入小根堆
2. 选出最小的两个数，结合，把结合后的数重新放入小根堆
3. 重复步骤2，直到小根堆空
public int lessMonry(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;
}
2.6 最大钱数IPO -- 502 IPO(hard)
思路： 堆！
1. 把所有项目按花费放进小根堆(利润无所谓)，called 未解锁
2. 按初始资金，弹出花费<初始资金的所有项目，按利润放入大根堆called 解锁。
3. 按贪心，选利润最大的
4. 重复2-3，直到达到项目上限
class Solution {
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
PriorityQueue<Node> minCostQ = new PriorityQueue<>(new MinCostComparator());
PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
//所有项目都扔进被锁池中，按花费扔小根堆
for(int i = 0; i < profits.length; i++){
minCostQ.add(new Node(profits[i], capital[i]));
}
for(int i = 0; i < k; i++){//进行k轮
//资金够的项目全解锁
while(!minCostQ.isEmpty() && minCostQ.peek().c <= w){
maxProfitQ.add(minCostQ.poll());//按利润放大根堆
}
if (maxProfitQ.isEmpty()){//资金不够解锁项目
return w;
}
w += maxProfitQ.poll().p;
}
return w;
}
public class Node{
public int p;
public int c;
public Node(int p, int c){
this.p = p;
this.c = c;
}
}
public class MinCostComparator implements Comparator<Node>{
@Override
public int compare(Node o1, Node o2){
return o1.c - o2.c;
}
}
public class MaxProfitComparator implements Comparator<Node>{
@Override
public int compare(Node o1, Node o2){
return o2.p - o1.p;
}
}
}
2.7 堆的应用--一个数据流中，随时取得中位数 -- 295 Find Median from Data Stream(hard)
思路：大根堆和小根堆配合 --时间复杂O(log N)
1.first input先进大根堆
2. input 跟大根堆顶比较，input >= 大根堆堆顶，input进小根堆
3. 比较大小根堆的size，如果size相差=2，把数多的堆的堆顶弹出，放入另一个
4.结果：较小1/2在大根堆，较大1/2在小根堆。中位数由两个堆堆顶得出
class MedianFinder {
// To store lower half of data stream eg. 1, 2, 3, 6
PriorityQueue<Integer> lowerHalf;
// To store upper half of data stream eg. 8, 9, 11
PriorityQueue<Integer> upperHalf;
/** initialize your data structure here. */
public MedianFinder() {
lowerHalf = new PriorityQueue<>((a,b) -> b - a); // Max heap : To fetch largest
// element from lower half in O(1) time
upperHalf = new PriorityQueue<>(); // Min heap : To fetch lowest
// element from upper half in O(1) time
}
public void addNum(int num) {
// Insert in lowerHalf is it's empty or if number being inserted is less than the peek of lowerHalf otherwise insert in upperHalf
if(lowerHalf.isEmpty() || num <= lowerHalf.peek()){
lowerHalf.add(num);
}else{
upperHalf.add(num);
}
// We also need to ensure that the halves are balanced i.e. there is no more than a difference of 1 in size of both halves
// Let lowerHalf be the one to hold one extra element if the size of total data stream is odd otherwise be equal to upperHalf
if(upperHalf.size() > lowerHalf.size()){ // If an element added above made upperHalf have one more element than lowerHalf then we poll it and put it into lowerHalf
lowerHalf.add(upperHalf.poll());
} else if(lowerHalf.size() > upperHalf.size() + 1){
// If an element added above, made lowerHalf have 2 more elements then upperHalf then we put one into upperHalf from lowerHalf
upperHalf.add(lowerHalf.poll());
}
}
public double findMedian() {
if(lowerHalf.size() == upperHalf.size()){
return (double)(lowerHalf.peek() + upperHalf.peek())/2;
}else{
return (double)(lowerHalf.peek());
}
}
}
