散列表

直接寻址表

散列表

散列函数

开放寻址法

线性探查

二次探查

双重散列

二叉搜索树

递归查找：

1
2
3
4
5
6
7

tree_search(root, k)
	if root == null or k == root.key
		return root
	if k < root.key
		return tree_search(root.left, k)
	else
		return tree_search(root.right, k)

红黑树

旋转：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

left_rotate(T, root)
	rChild = root.right
	root.right = rChild.left
	if rChild.left != T.null
		rChild.left.parent = root
	rChild.parent = root.parent
	if root.parent == T.null
		T.root = rChild
	elif root == root.parent.left
		root.parent.left = rChild
	else
		root.parent.right = rChild
	rChild.left = root
	root.parent = rChild

插入：

观察者模式（Observer）

定义了对象之间的一对多依赖，当一个对象改变状态时，它的所有依赖者都会收到通知并自动更新。

初识

我们先来了解一下报纸和杂志的订阅是怎么回事：

1. 报社的业务就是出版报纸、杂志等各种出版物。
2. 如果我想看报社的 A 报纸和 B 杂志，那么就向报社订阅 A 报纸和 B 杂志。
3. 当他们有新的 A 报纸或 B 杂志出版时，就会向你派送，只要你是他们的订户，你就会一直收到新报纸，新杂志。
4. 如果你不想看 B 杂志了，取消订阅，他们就不会再送新的 B 杂志给你了。但不会影响你订阅的 A 报纸。
5. 只要报社还在运营，就会一直有人向他们订阅或取消报纸等出版物。

在观察者模式中，出版者报社 = 主题（subject），而我们订阅者 = 观察者（observer）。

排序和顺序统计量

堆排序

（二叉）堆是一个数组，它可以被看成一个近似的完全二叉树（除了最底层，该树是完全满的，而且是从左到右填充）。

表示堆的数组 A 包括两个属性：

• A.length（通常）给出数组元素的个数。
• A.heap_size 表示有多少个堆元素存储在该数组中。
  也就是说，虽然 A[A.length] 可能都存有数据，但只有 A[A.heap_size] 中存放的是堆的有效元素。（0 <= heap_size <= length）

前言

对白很有趣，业务情景营造地很有氛围，如果还不会设计模式的话是值得一读的。

本笔记当然不会有那些有趣的图片和氛围，内容也会尽量浓缩。

策略模式（Strategy）

定义了算法族，分别封装起来，让它们之间可以互相替换，此模式让算法的变化独立于使用算法的客户。

前言

系统地过一遍《算法导论》，理清之前做题时的混乱思路。

伪代码均以类似 Python 的形式书写。

分治策略

最大子数组问题

假设让你买一支股票，并且你已经知道未来 17 天的走势，要求最大化收益。

什么时候收益最大？当然是最低价买进，最高价卖出。如果这种策略有效的话，那么确定最大化收益的方法就是：

1. 找到最高和最低价。
2. 从最高价开始向左找最低价，从最低价开始向右找最高价。
3. 取两对价格中差值最大的。