Trie 树
- 每个节点储存一个字母
- 每个节点可以被多个 key 共享
- Trie 树的节点也可以是个 Map
何时找不到 key
- 从 Trie 树上掉落
- 最后的节点是白色的 （染色法，给单词最后字母的节点染成蓝色），如果节点是 Map,则最后的节点有值
Trie API
字符串排序
最小生成树算法
- 有向图
- DFS
- BFS
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| - 无向图 |
- 哈希表
- 二叉搜索树
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class BinarySearch { | |
| /* | |
| * 在已排序数组中找到 key 的 index,如果找不到则返回小于 key 的个数 | |
| * @param a 已排序数组 | |
| * @param key 目标值 | |
| */ | |
| public static int binarySearchRecursion(int[] a,int key) { | |
| return binarySearchRecursionHelper(a,key,0,a.length-1); | |
| } |
收集一些元素,从N个元素中找到M个最大或最小元素
优先队列 MAXPQ
- 两个重要操作： 删除最大元素
delMax()和插入元素insert
二叉堆实现优先级队列
- 二叉堆的每个元素要大于两个特定位置的元素
- k 的上一层是 k/2, k 的下一层是 2k、2k+1 (a[0] 作为哨兵节点可以简化这个的实现)
- 两个帮助方法，上浮
swim(int k),下沉sink(int k)
- 上浮实现： while 反复比较 k 和 k/2 的大小