Do something cool!

今天同学群里面讨论了这样一段代码，说是产品出了 bug，现场急着修复。

介绍

动态数组在每次容量用尽时，重新申请 2 倍于当前数组的空间，并将原数组中的内容拷贝到新的空间，然后释放原数组的内存空间。对于动态数组，每次插入的花费有两种情况：

1. 容量够用，我们只需要存储新的元素
2. 容量不够用，创建新的空间，拷贝原数组进新的空间，再存储这个新的元素

分析方法有许多，统称为：amortized analysis（分摊分析）

快速排序算法是一个原理非常简单易懂的算法，但如果现场手写的话又有多少人能写得出来呢？我今天又试了一下，发现还是存在一些认知上的问题。首先我明白快排的核心操作是：选取一个中枢，然后把小于中枢的放到左边，大于中枢的放到右边。但我发现时隔仅仅一年多，我居然已经忘了这个操作的英文名字了。直到我在写这篇文章的时候才突然想起来：partition 操作。

在使用 partition 操作的前提下，递归解决问题就 OK 了。

并查集

什么是并查集

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

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

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

KMP 算法

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

文本匹配例子：

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

不必要的比较：

跳过不必要的比较：

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