Do something cool!

并查集

什么是并查集

并查集的核心是parent指针，一个结点可以找到自己所属的结点。从而把结点归类。有两个核心操作：

• Union（用来合并两个并查集）
• Find（用于查找一个结点的parent）

所以并查集可以叫做：union-find data structure。

KMP 算法

KMP 算法用来在一个文本中查找模式串，如下图所示：

文本匹配例子：

我们把上面那个长字符串的称为文本，下面这个短的称为模式串。我们的目的是查看ABADABAD是否出现在文本中。

不必要的比较：

跳过不必要的比较：

KMP 算法的核心作用在于帮助模式串顺利的跳过很多不必要的比较（模式串没有任何前缀与文本匹配），直接后移到一部分前缀已经匹配的位置，开始下一次的比较。更准确的讲是移动到：最长真前后缀匹配的位置，如上图所示的ABA。

蓄水池算法(Reservoir Sampling)

这个算法真的很奇妙，它的核心是一个数学证明。外延，或者说应用场景是：

1. $C_n^k$，也就是从大小为 n 的样本集中随机取 k 个不同的样本
2. 流式数据，或者说无法直接根据索引拿到数据（更加不可能一遍加载到内存）

高数中的第一个证明，可能就是这个$\lim\limits_{x\rightarrow 0} \frac{\sin x}{x} = 1$的证明了。下面给出这个极限的证明，用到了解析几何（作图法）。

通用快捷键

1. 格式化代码（reformat code）:
   win: ctrl+alt+L
   mac: command+option+L
2. 在一行的任意位置使用： shift + enter，新建下一行并跳到下一行。
3. 善用代码自动补全功能，变量名和方法名等可以用 enter 补全。导入包可以用 alt + enter。
4. 上下移动代码，ctrl+shift+上下键
5. Android Studio 生成函数注释：你在方法前输入/**然后一回车，自动帮你生成方法和参数的注释。