考虑到中间继承有几堂课摸鱼了，导致有的知识点没有呈现在代码里，这里先写一点。
- 是什么：类的本质是 “一种具体事物的模板”。
- 比如：
Dog（狗）、Car（汽车）、Student（学生）。
- 比如：
- 特点：
- 类可以 直接创建对象（例如：
Dog myDog = new Dog();）。 - 类中可以包含 属性（数据） 和 方法（行为） 的具体实现。
- 类可以 直接创建对象（例如：
- 是什么：接口的本质是 “一类行为的规范”。
- 比如：
Runnable（可跑的）、Swimmable（可游泳的）、Serializable（可序列化的）。
- 比如：
- 特点：
- 接口 不能直接创建对象（比如不能直接
new Runnable()）。 - 接口只定义 方法的签名（方法名、参数、返回值），但不写具体实现。
- 接口更像一种“合同”：谁实现了这个接口，就必须履行这个合同（实现所有方法）。
- 接口 不能直接创建对象（比如不能直接
这两个术语是语言学和计算机科学中的概念，用来描述 “一般与特殊” 的关系。
- 广义上的类别，代表更抽象、更通用的概念。
- 例如：
- 动物（Animal）是狗（Dog）的超类型。
- 交通工具（Vehicle）是汽车（Car）的超类型。
- 列表（List）是动态数组（ArrayList）的超类型。
- 例如：
-
具体化的类别，代表更具体、更特殊的概念。
- 例如：
- 狗（Dog）是动物（Animal）的子类型。
- 汽车（Car）是交通工具（Vehicle）的子类型。
- 动态数组（ArrayList）是列表（List）的子类型。
简而言之，implements用于继承方法，extends用于继承类
- 例如：
当子类不得不访问父类的方法时，可以用super.function()来直接调用父类方法（此时便可以访问父类私有的一些成员变量），此处的super有点像this。
在调用父类方法前可以写一行super(x);增加代码可读性。x为下面调用方法中需要传入的参数。
如果不写，会自动调用默认的函数（多个重载函数中选无参数传入的）。
在重写父类方法前标记，没有实际用处，相当于注释，但是可以检查下方的拼写错误。
简而言之，编译的时候会根据对象的静态类型进行检查，比如：(maxDog返回值为Dog类，Poodle为Dog子类，意为贵宾犬，下面的两个参数均为贵宾犬的种类)
Dog largerdog = maxDog(frank,franJr);
Poodle largerPoddle = maxDog(frank,franJr);
虽然我们知道frank和franJr都是属于Poodle的，但是在定义maxDog的时候编译器只知道他们是Dog类的，因此会报错。
这里可以通过添加(Poodle)进行强制的类型转换避免报错。
一种数据结构，最终导出的简化版本为树。通过多次查找可以实现路径压缩，进一步简化结构。
对无序集合进行有序排列来简化查找操作。
特殊地，树的高度决定了最坏情况的运行情况。即当树高度为N时(spindly tree)，运行时间为θ(N)，其余情况(bushy tree)为θ(logN)。
TODO: 理解渐进分析、大O记法
为了防止BST过于spindly，允许多个节点（有序的）合并为同一个节点，同时设定一个临界值。当节点内含有节点数目超过临界值后，取中间的节点上升到其父节点位置，大于和小于它的再分开排，最后其父节点将有三个子节点。上限临界值为3时分裂树又叫2-3 树。
用标准的BST来实现B-tree，方法为通过创建一个red虚拟链接把B-tree中同集合的两个节点链接起来。虚拟链接不是真实的链接，只是用来表示连接的两个点本应该在一起。
LLRB tree（左偏红黑树，红色虚拟链接总向左偏，这样的规定方便算法实现）表现为一个普通的BST，可以和一个2-3 tree一一对应（其实就是一种结构的两种表现形式，2-3 tree虽然直观，但是代码上实现难度或许比较大）。LLRB高度容易高于对应的2-3 tree，但不会超过其二倍.渐近分析表明这样的倍数关系对运行效率没有影响。
- 插入时：使用红色链接。
- 如果有一个右倾的“3节点”，左倾违规。
- 向左旋转相应的节点以修复。
- 如果有两个连续的左链接，不正确的4节点违规。
- 向右旋转相应的节点以修复。
- 如果有任何节点有两个红色子节点，临时4节点。
- 颜色翻转节点以模拟分裂操作。
最后一个细节：级联操作。
- 旋转或翻转操作可能会导致需要修复的额外违规。
通过哈希函数把字符串映射到整型变量。举个例子，ASCII码共有128位，可以通过127进制把任意单词转化为数字。
- 用于解决优先队列（PQ）问题
- 表现为完全二叉树，即缺失的节点仅存在于最底层，存在的节点尽可能靠左
- 节点允许重复
- 每个节点必定小于等于其任意子节点
- 值得注意的是，一对兄弟节点之间的大小关系没有要求，不要在实现算法时出现思维惯性
| Name | Storage Operation(s) | Primary Retrieval Operation | Retrieve By: |
|---|---|---|---|
| List | add(key) insert(key, index) |
get(index) |
index |
| Map | put(key, value) |
get(key) |
key identity |
| Set | add(key) |
containsKey(key) |
key identity |
| PQ | add(key) |
getSmallest() |
key order (a.k.a. key size) |
| Disjoint Sets | connect(int1, int2) |
isConnected(int1, int2) |
two int values |
高中学过，此处不再赘述，仅介绍一种新学到的技法。从根节点出发逆时针绕着树的每个节点紧贴着走直至回到根节点，在先序/中序/后序的情况下，在穿过节点左边/底部/右边的时候即视为访问了该节点。
可以认为图是树的父类，树是一种更严格化的图。典型的例子，四个节点呈棱形状相连不是树但是可以是图；同一对节点可以有两个直接相连的边；节点可以和自己相连。
“同一对节点可以有两个直接相连的边；节点可以和自己相连。”去掉这两种情况即可得到简单图。简单图可以分为有向图和无向图，取决于在建模什么，可以在链接的边上添加Edge Labels。
- 深度优先搜索(DFS)：从起始点出发优先探索完子图，再尝试回溯到上一节点探索下一个子图，可以用递归实现。可以帮助我们找到通往每一个顶点的路径。
- 广度优先搜索(BFS)：基于队列实现，将即将探索的节点放到队列尾部，优先探索前面的节点。
显然地，在最短路径中不可能出现循环现象，由此可以推导出结论：最短路径的集合对应的数据结构为树，我们称之为最短路径树。
- 迪杰斯特拉算法(Dijkstra)
基于BFS进行检索，优先检索未被检索过的最近节点，将当前距离和当前最短路径树中该节点对应距离（必须是非负数）进行比较，放弃较长的距离，完成对图的遍历后即可得到最短路径树。
值得注意的是，迪杰斯特拉算法的操作本身耗时为O(N)，而优先队列复杂度为O(logN)。
下面是伪代码：
Dijkstra's:
PQ.add(source, 0)
For other vertices v, PQ.add(v, infinity)
While PQ is not empty:
p=PQ.removeSmallest()
Relax all edges from p
Relaxing an edge p -> q with weight w:
if distTol[p] + w < distTol[q]:
distTol[q] = distTol[p] + w
edgeTo[q] = p
PQ.changePriority(q, distTo[q])
- A*算法 在计算优先级的时候将路径成本和惩罚量（提前给出，又叫启发式评估）相加，减少不必要的探索。
最小（包含最少边/权重最小）的可以接触每个节点、没有循环的树。
- 割边属性：把图的所有节点随机分成两组，可以连接两不同组节点的边中权重最小的边一定在最小生成树中。经过足够多次数的上述操作，可以得到最小生成树。
- Prim's算法：随机选一个起点，将接触过的点和未接触的点分成两组，按照割边属性对最小权重的割边进行探索。循环至找到所有节点。
值得注意的是，Prim's算法中的Relax操作的评估权重为指定节点和当前节点的边权重，无需像Dijkstra算法一样添加当前节点到初始节点的距离权重。即只根据到正在构建的树的距离寻找最近边。
public class PrimMST {
public PrimMST(EdgeWeightedGraph G) {
edgeTo = new Edge[G.V()];
distTo = new double[G.V()];
marked = new boolean[G.V()];
fringe = new specialPQ<Double>(G.V());
distTo[s] = 0.0;
setDistancesToInfinityExceptS(s);
insertAllVertices(fringe);
/* Get vertices in order of distance from tree. */
while (!fringe.isEmpty()) {
int v = fringe.delMin();
scan(G, v);
}
}
}
- 从任意一个顶点开始，逐步扩展最小生成树，每次添加连接树和非树顶点权重最小的边。
- 使用优先队列来有效选择下一个要添加的边。
- 适合稠密图。
- 按照边的权重从小到大排序，然后依次选择边，只要这条边不会与已选择的边形成环。
- 使用并查集数据结构来检测环。
- 适合稀疏图。
public class KruskalMST {
private List<Edge> mst = new ArrayList<Edge>();
public KruskalMST(EdgeWeightedGraph G) {
MinPQ<Edge> pq = new MinPQ<Edge>();
for (Edge e : G.edges()) {
pq.insert(e);
}
WeightedQuickUnionPC uf = new WeightedQuickUnionPC(G.V());
while (!pq.isEmpty() && mst.size() < G.V() - 1) {
Edge e = pq.delMin();
int v = e.from();
int w = e.to();
if (!uf.connected(v, w)) {
uf.union(v, w);
mst.add(e);
}
}
}
}
基于DFS进行探索，堆栈回溯的时候将当前元素推入Postorder，如此迭代后将Postorder反转，得到有向无环图的一个有效排序的拓扑结构。
基于有向无环图生成一个直线向右的拓扑结构，再从最左端进行只向右的探索，可以确保绝对不会探索到已经探索过的节点，从而避免负权重情况下Dijkstra算法无法修改已探索节点路径的问题。
将所有权重改成负数，基于DAG得到的最短路径就是实际上的最长路径。 好天才的想法啊。面对相似但未知的问题，我们可以尝试用已知的知识将其化归(reduce)为可解问题。
多个字符串前缀相同时共用节点进行储存，同时对尾节点进行标注，可以极大地提升查找效率和浪费内存。
浪费内存是因为默认状态下，以ASCII码为例，trie的每个节点下有128个链接（如果用数组储存），然而只有几个链接非空。但是我们可以改用哈希表或红黑树来储存链接，一定程度上减少内存浪费。
常见于搜索引擎或各种IDE的自动补全搜索。
两重循环，每次第二重循环中遍历找到当前最小节点后将其和前面节点交换，直至完成遍历。需要时间O(N^2)。
- 将所有项目塞入一个最小堆中（父节点小于子节点，兄弟节点之间无序，每次弹出的都是最小值），优化选择排序算法。需要时间O(NlogN)，空间复杂度为O(N)。
此处默认以从小到大的升序为例，若为降序则需要最大堆，基本同理。
-
原地堆排序,为了阻止生成一个额外的作为堆的数组产生空间冗余，从底部开始，向上检索，观察有无节点不满足父节点小于子节点，若有，将其与其最小子节点交换。遍历结束后得到最小堆。此时即可堆排序。
-
堆化和删除操作均需要O(NlogN)时间，而空间复杂度为O(1)。
- 合并，将多个有序数组按照同样的顺序合并到一个数组中。时间复杂度为O(N)。
- 归并排序的本质是，将无序大数组拆分成若干个只含一个元素的数组（进行多次的一分为二）后排序，再进行合并，可以减少N增大对时间复杂度增大带来的影响。当小数组被拆分到只含一个元素的时候，算法时间复杂度由O(N^2)降低到O(NlogN)（每次拆分需要N时间单元，一共log2(N)次拆分；合并需要N时间单元）。
- 空间复杂度为O(N)。
- 通过优化后可以不用创建一个额外的输出数组，实际表现为冒泡排序。需要时间O(N^2)，Ω(N)。
- 在数组几乎有序时，插入排序最快。
- 在数组较小时，插入排序最快。