包括常见的基础数据结构、算法，也包含了类似 LeetCode 的刷题技巧。

数据结构 #

这里主要介绍一些常规的数据结构。

树 #

• 基本概念 介绍树的常见术语、遍历方式等概念。
• 自平衡二叉树 按照通过固定的旋转策略保证树的平衡，降低了插入、删除速度，但可以有效提高查询速度。

其它 #

• 优先队列 元素被赋予优先级，通常用栈来实现，每次获取优先级最高或者最低的元素。
• SkipList 随机化数据结构，基于并联的链表，其效率可比拟二叉查找树。
• 并查集 通过数组实现的一个很简单但实用的集合查询。
• 树状数组 Binary Index Tree 最开始用于计算累加频数，目前通常用于高效的计算前缀和、区间和。
• 离散化数组 使用相对大小而非绝对大小来保存数据，这样有些场景下可以提高效率。

常用算法 #

一般如 LeetCode 中，会约束算法完成的时间以及使用内存数，时间就是约束的算法复杂度，通常会用如下的符号进行表示。

$\Theta$ 是上界也是下界 (tight)，等于的意思。 $O$ 上界 (tightness unknown)，小于等于的意思。 $o$ 上界 (not tight)，小于的意思。 $\Omega$ 下界 (tightness unknown)，大于等于的意思。 $\omega$ 下界 (not tight)，大于的意思。

其中 $Ο$ 是渐进上界，$\Omega$ 是渐进下界；$\Theta$ 需要同时满足 $Ο$ 和 $\Omega$，称为确界 (必须同时符合上界和下界)。

在实际使用时，$Ο$ 极其有用，因为它表示了最差性能。

• 基础算法 包括了分治、递归、迭代等基础算法的介绍。

二分查找 #

这是一种高效的查找方法，不过其要求保存的数据必须是顺序存储的，一般是数组，而且所有的元素必须要有序排列，可以支持某个值以及左右边界的查找。

看着简单，但会涉及到很多细节，这里详细介绍其实现。

• 基本介绍 包括了基本的搜索，左边界、右边界搜索。
• 右开区间实现 与上篇文章的实现相似，只是搜索区间有所变化，也导致了一些细节修改。

其它 #

• 排序算法 包含一些基本概念以及常见的排序算法介绍。
• 洗牌算法 如何将数据打散，包括了蓄水池采样。
• 背包问题 很经典或者入门的动态规划问题，包括了基本及其扩展。

参考 #

• The Algorithm Python 一个 130+K 星的经典算法仓库。

其它 #

Bitmap #

常见的 Bitmap 使用比较简单，除此之外还提供了一些扩展。

• BitMap 这里不只是包含 Bitmap 实现，还有相关的优化实现介绍。
• BloomFilter 一种类似 Hash Set 的数据结构，区别是无需保存 Key，通常用于判重。

其它 #

• Huffman 用来提高压缩率，提高传输效率。
• PID 最早发展起来的控制策略之一，算法简单、鲁棒性好和可靠性高。