并查集

定义：并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

核心思想

• 以一颗有根树代表每个集合。
• 每个节点维护一个指向其父节点的链接。
• 对于每个集合根节点为该集合的代表。
• 例如： 集合{x,y,z}和{a,b,c,d}。

Priority Queue

普通队列是一种先进先出（FIFO）的数据结构。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高优先先出（first in，lagest out）的行为特征。

实现方案

使用排序和数组可以简单的实现Priority Queue，插入到列表的时间复杂度为𝑂（𝑛），排序列表的时间复杂度为𝑂(𝑛log𝑛)。更优的方式是使用大顶堆（小顶堆），以大顶堆（小顶堆）实现的Priority Queue的出队、入队时间复杂度均为𝑂(log 𝑛)。

举个栗子

考虑一个car类，有个brake（制动）方法，多个汽车模型可能拥有几种不同的制动行为。
方案一：由于制动行为在模型间频繁变化，通常的方法是通过继承来实现，在子类中实现这些行为。这种方法有很大的缺点：

1. 必须在每个模型中实现制动行为，各个汽车模型之间存在大量重复代码（不同汽车模型的制动行为可能是一样的）。
2. 汽车的模型与制动行为的实现耦合在一起，如果某种制动行为发生变化或新增一个制动行为，那么对应的所有汽车模型就要修改，不符合“封装变化原则”与“开闭原则”。
3. 随着汽车模型数量的增加，管理制动行为的成本大大增加。如，对于所有x种汽车模型都要稍微修改一下制动行为。
   我们发现，当涉及到“维护”时，以复用为目的的继承，解决并不完美。

方案二：将制动行为封装进一组行为类中，通过组合动态设定汽车模型对应的制动行为。当有制动行为修改或有新的制动行为我们可以操纵行为类，将行为类的实现与汽车模型分离，减少耦合度。

上述方案即为策略模式，让行为（算法）和对象分开来，使得行为（算法）可以独立于它的客户的变化。

队列

队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中的元素进出是按先进先出的原则进行（FIFO–First In First Out）。

栈

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。栈中元素的进出是按后进先出的原则进行，这是栈的重要特征（LIFO–Last In First Out）。

斐波那契数列

斐波那契数列又称黄金分割数列，这个数列从第三项开始，每一项都等于前两项之和。

递推公式

F(0) = 1;
F(1) = 1;
F(n) = F(n-1) + F(n-1);

扩展欧几里德算法

定义： 扩展欧几里德算法，是欧几里德算法的扩展。已知整数a、b，扩展欧几里德算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式:

ax + by = gcd(a,b).     

有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。

欧几里德算法（辗转相除法）

定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。
公式：gcd(a,b) = gcd(b,a mod b) (设 a > b )

两个欧几里得的重要结论

gcd(a,b) = gcd(b,a mod b)
gcd(a,0) = a

数学公式归纳