简介

数据结构即数据的存储结构，不同的存储结构存在不同的优劣，数据结构与算法一般而言是密不可分的，因为实现相应的存储结构之后难免会提供相应的算法，几乎每一种存储结构都会提供一些基本的操作，即“增删改查”。

根据是否修改数据结构，所有操作大致分为两类方式：

  • 静态：仅读取，数据结构的内容及组成一般不变：查找
  • 动态：需写入，数据结构的局部或整体将改变：增加、删除

数据结构通常可分为：

  • 线性数据结构：线性表、栈、队列
  • 非线性数据结构：树、图

特别的，线性表又具体分为顺序表和链表，而树也可以理解为半线性数据结构。

也可以按照数据访问方式分为：

  • 寻秩访问（call by rank）：顺序表
  • 寻位置访问（call by position）：链表
  • 寻关键码访问（call by key）：二叉搜索树
  • 寻优先级访问（call by priority）：优先级队列
  • 寻数值访问（call by value）：哈希

常见数据结构的相关操作的时间复杂度：

数据结构顺序表链表二叉树二叉搜索树图哈希表
增加\(O(n)\)\(O(1)\)\(O(logn)\)\(O(logn)\)\(O(n)\)\(O(n)\)
删除\(O(n)\)\(O(1)\)\(O(logn)\)\(O(logn)\)\(O(n)\)\(O(n)\)
修改\(O(1)\)\(O(n)\)\(O(logn)\)\(O(logn)\)\(O(n)\)\(\approx O(1)\)

先修

数学

最大公约数

最大公约数（greatest common divisor，gcd），又称最大公因数（highest common factor，hcf），指能够整除多个整数的最大正整数。而多个整数不能都为零。

例如 8 和 12 的最大公约数为 4。

素数

素数（Prime number），又称质数，指在大于 1 的自然数中，除了 1 和该数自身外，无法被其他自然数整除的数（也可定义为只有 1 与该数本身两个正因数的数）。

如 3、5、7、11、13、17、19、23 等。

更具体来说，素数又可分为两类：

  • 4k + 3：3、7、11、19、23 等
  • 非 4k + 3：5、13、17 等

斐波那契数列

阶乘

正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，计为 \(n!\)。例如：

\(5!=5\times 4\times 3\times 3\times 2\times 1=120\)

特别的，\(1\) 的阶乘 \(1!\) 为 \(1\)、\(0\) 的阶乘 \(0!\) 亦为 \(1\)，其中，\(0\) 的阶乘表示一个空积。

排列组合

从 \(n\) 个元素中取出 \(k\) 个元素，\(k\) 个元素的排列数量为：

\(P_k^n=\frac{n!}{(n-k)!}\)

从 \(n\) 个元素中取出 \(k\) 个元素，\(k\) 个元素的组合数量为：

\(C_k^n=\frac{n!}{k!(n-k)!}\)

级数与时间复杂度

  • 算数级数：与末项平方同阶
  • 幂方级数：比幂次高出一阶
  • 几何级数（a>1）：与末项同阶
  • 收敛级数：\(O(1)\)
  • 调和级数：\(\Theta(logn)\)
  • 对数级数：\(\Theta(nlogn)\)
// 算数级数，O(n^2)
for(int i = 0; i < n; i++)
{
    for(int j = 0; j < n; j++)
    {
        O1Operation(i, j);
    }
}

// 算数级数，O(n^2)
for(int i = 0; i < n; i++)
{
    for(int j = 0; j < i; j++)
    {
        O1Operation(i, j);
    }
}

// 算数级数，O(n^2)
for(int i = 0; i < n; i++)
{
    for(int j = 0; j < i; j += 2013)
    {
        O1Operation(i, j);
    }
}

// 几何级数，O(n)
for(int i = 1; i < n; i <<= 1)
{
    for(int j = 0; j < i; j++)
    {
        O1Operation(i, j);
    }
}

// 几何级数，O(logn*2^logn)
for(int i = 0; i <= n; i++)
{
    for(int j = 1; j < i; j += j)
    {
        O1Operation(i, j);
    }
}

编程语言

位运算

<<

左移 1 位等于乘以 2，即 4 << 1 = 8。

>>

右移 1 位等于除以 2，即 4 >> 1 = 2。

算法分析

所谓算法，即特定计算模型下，旨在解决特定问题的指令序列。具体来说，其包含以下要素：

  • 输入：待处理的信息（问题）
  • 输出：经处理的信息（答案）
  • 正确性：的确可以解决指定的问题
  • 确定性：任一算法都可以描述为一个由基本操作组成的序列
  • 可行性：每一基本操作都可实现，且在常数时间内完成
  • 有穷性：对于任何输入，经有穷次基本操作，都可以得到输出

一个好的算法包含以下特性：

  • 正确：符合语法，能够编译、链接
  • 健壮：能辨别不合法的输入并做适当处理，而不致非正常退出
  • 可读：结构化 + 准确命名 + 注释 + ...
  • 效率：速度尽可能快；存储空间尽可能少

在本系列文章中，我们重点关注效率方面。

算法分析主要包括两个方面：

  • 正确性：算法功能与问题要求一致？
  • 成本：运行时间 + 所需存储空间

通过挖掘算法的不变性和单调性可以证明算法的正确性。

大 O 记号

大 O 记号（big-O notation）：\(T(n) = O(f(n))\) iff \(\exists c > 0\)，当 \(n >> 2\) 后，有 \(T(n) < c \times f(n)\)

根据以上定义，我们可以得出关于大 O 记号的两个重要处理手法：

  • 常系数可忽略：\(O(f(n)) = O(c \times f(n))\)
  • 低次项可忽略：\(O(n^a + n^b) = O(n^a), a > b > 0\)

除此之外，还有以下记号：

  • \(T(n) = \Omega(f(n))\)：\(\exists c > 0\)，当 \(n >> 2\) 后，有 \(T(n) > c \times f(n)\)
  • \(T(n) = \Theta(f(n))\)：\(\exists c_1 > c_2 > 0\)，当 \(n >> 2\) 后，有 \(c_1 \times f(n) > T(n) > c_2 \times f(n)\)

根据大 O 记号，我们可以把时间复杂度分为以下几类：

  • \(O(1)\)：常数（constant function）复杂度，这类算法的效率最高，不含转向（循环、调用、递归等），必顺序执行，即是 \(O(1)\)
  • \(O(logn)\)：对数复杂度，常底数无所谓，常数次幂也无所谓，这类算法非常有效，复杂度无限接近于常数。
  • \(O(n^c)\)：多项式（polynomial function）复杂度，其中一个特例是线性（\(O(n)\)）复杂度，这类算法的效率通常认为已可令人满意。
  • \(O(2^n)\)：指数（exponential function）复杂度，这类算法的计算成本增长极快，通常被认为不可忍受。

从 \(O(n^c)\) 到 \(O(2^n)\)，是从有效算法到无效算法的分水岭。很多问题的 \(O(2^n)\) 算法往往显而易见，然而，设计出 \(O(n^c)\) 算法却极其不易，甚至，有时注定地只能是徒劳无功。

在最好和最坏情况下，相差极其悬殊的算法，叫输入敏感（input-sensitive）的算法，也就是说，它的复杂度具体是多少，与输入时候数据的配置紧密的相关。

封底估算

封底估算即 Back-Of-The-Envelope Calculation。

\(1 天 = 24 hr \times 60 min \times 60 sec \approx 25 \times 4000 = 10^5 sec\)

\(1 生 \approx 1 世纪 = 100 yr \times 365 = 3 \times 10^4 day = 3 \times 10^9 sec\)

线性表

线性表具体分为顺序表和链表。

顺序表

顺序表（contiguous list）又称为向量（vector）或数组（array）。

顺序表即物理空间连续的序列，A[i] 的物理地址 = A + i*s，s 为单个元素占用的空间量。

顺序表可分为无序顺序表和有序顺序表。

扩容

相比递增式扩容，采用加倍式扩容，每次扩容的分摊成本仅为 \(O(1)\)，而递增式扩容每次扩容的分摊成本则为 \(O(n)\)。

无序顺序表

无序顺序表要求元素之间至少应该能比较是否相等，我们称作比对操作。

无序顺序表的去重

Python 实现：

def deduplicate(lis):  # 删除重复元素，返回被删除元素数目
    old_size = len(lis)  # 记录原规模
    i = 1  # 从lis[1]开始
    while i < len(lis):  # 自前向后逐一考察各元素lis[i]
        try:
            lis[:i].index(lis[i])  # 在前缀中寻找雷同者
            lis.pop(i)  # 若有雷同则删除雷同者（至多一个？！）
        except ValueError:
            i += 1  # 否则继续考察其后继
    return old_size-len(lis)  # 顺序表规模变化量，即删除元素总数


# 测试
lis = [3, 3, 3, 1, 9, 8, 7, 2, 1, 2]
print(deduplicate(lis))  # 4

对于规模为 n 的顺序表，其最坏时间复杂度为 \(O(n^2)\)。

有序顺序表

有序顺序表要求能够判定任何一对元素孰大孰小，我们称作比较操作。

无序顺序表经预处理转换为有序顺序表之后，相关算法多可优化。

有序性

有序 序列中，任意 一对相邻元素 顺序；无序 序列中，总有 一对相邻元素 逆序。因此，相邻逆序对的数目，可用以度量顺序表的逆序程度。

注意：相邻逆序对即两个相邻的元素 {..i, j..} 且 i>j。而逆序数是逆序对的个数，并不要求二者相邻。

def disordered(lis):  # 返回逆序相邻元素对的总数
    n = 0  # 计数器
    for i in range(1, len(lis)):  # 逐一检查各对相邻元素
        n += (lis[i-1] > lis[i])  # 逆序则计数
    return n  # 向量有序当且仅当n=0


# 测试
lis = [3, 3, 3, 1, 9, 8, 7, 2, 1, 2]
print(disordered(lis))  # 5

若只需判断是否有序，则首次遇到逆序对之后，即可立即终止。

有序顺序表的去重

在有序顺序表中，重复的元素必然相互紧邻构成一个区间，因此，每一区间只需保留单个元素即可。

Python 实现：

def uniquify(lis):
    i = 0
    j = 1  # 各对互异“相邻”元素的秩
    while j < len(lis):  # 逐一扫描，直至末元素
        if lis[i] != lis[j]:  # 跳过雷同者；发现不同元素时，向前移至紧邻于前者右侧
            i += 1
            lis[i] = lis[j]
        j += 1
    i += 1  # 直接截除尾部多余元素
    return j-i  # 顺序表规模变化量，即被删除元素总数


# 测试
lis = [1, 1, 2, 2, 3, 3, 3, 7, 8, 9]
print(uniquify(lis))  # 4

C 语言实现：

int removeDuplicates(int* nums, int numsSize)
{
    if(numsSize == 0)
    {
        return 0;
    }
    int i = 0, j = 0;
    while(++j < numsSize)
    {
        if(nums[i] != nums[j])
        {
            nums[++i] = nums[j];
        }
    }
    return ++i
}

对于规模为 n 的顺序表，其最坏时间复杂度为 \(O(n)\)。

LeetCode：26. 删除排序数组中的重复项

语言实现

在 Python 中可以使用内置的 list 来实现顺序表的功能，如下：

contiguous_list = []
# 增加
contiguous_list.insert(0, 5)
contiguous_list.insert(0, 6)
contiguous_list.insert(2, 9)
contiguous_list.insert(3, 5)
# 删除
contiguous_list.pop(1)
# 查找
contiguous_list[0]
# 去重
contiguous_list = list(set(contiguous_list))
# 反转
contiguous_list.reverse()

链表

链表（linked list）又称为列表（list）。

链表即物理空间不连续的线性序列，其中的元素称作节点（node），各节点通过指针或引用彼此连接，在逻辑上构成一个线性序列。

相邻节点彼此互称前驱（predecessor）或后继（successor），前驱或后继若存在，则必然唯一，没有前驱的唯一节点称作首（first/front）节点，没有后继的唯一节点称作末（last/rear）节点。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class List:
    pass

查找

增加

删除

LeetCode：206. 反转链表

栈

栈（stack）

栈的这种特性也可以被称为后进先出（LIFO，Last In First Out）。

在 Python 中可以使用内置的 list 来实现栈的功能，如下：

stack = []
stack.append(1)  # 入栈 [1]
stack.append(2)  # 入栈 [1, 2]
stack.pop()  # 出栈 [1]
stack.pop()  # 出栈 []

应用

括号匹配

def paren(exp: str) -> bool:
    stack = []  # 使用栈记录已发现但尚未匹配的左括号
    for i in exp:  # 逐一检查当前字符
        if i is '(':  # 遇左括号：则进栈
            stack.append(i)
        elif stack:  # 遇右括号：若栈非空，则弹出左括号
            stack.pop()
        else:  # 否则（遇右括号时栈已空），必不匹配
            return False
    return False if stack else True  # 最终，栈空当且仅当匹配

LeetCode：20. 有效的括号

队列

队列（queue）也是受限的序列，其只能在队尾插入（enqueue），只能在队头删除（dequeue）。

队列的这种特性也可以被称为先进先出（FIFO，First In First Out）。

队列可以基于顺序表或链表实现。

在 Python 中可以使用内置的 collections.deque 来实现队列的功能，如下：

from collections import deque

queue = deque()
queue.append(1)  # 入队 [1]
queue.append(2)  # 入队 [1, 2]
queue.popleft()  # 出队 [2]
queue.popleft()  # 出队 []

LeetCode：剑指 Offer 09. 用两个栈实现队列

树

前面已经介绍了顺序表和链表这两种线性数据结构，我们来对比一下在其上执行操作的时间复杂度：

操作顺序表链表
静态操作：查找\(O(logn)\)\(O(n)\)
动态操作：增加/删除\(O(n)\)\(O(1)\)

树结构则是将顺序表和链表的优势结合起来，可以理解为链表的链表，也可以认为是二维的链表，由于这个原因，可以认为树型结构既不是我们此前所介绍的线性数据结构，同时它也带有一定的线性特征，为了与之后的非线性数据结构 —— 图相区别，我们不妨称其为半线性数据结构。

树是用来按照层次关系组织一系列数据项的一种方式。

定义：递归嵌套

树是特殊的图 \(T=(V, E)\)，节点数（vertex）\(|V|=n\)，边数（edge）\(|E|=e\)。

指定任一节点 \(r\in V\) 作为根后，\(T\) 即称作有根树（rooted tree）。

通过彼此的嵌套，小型的有根树可以逐步地整合为规模更大的有根树。即若 \(T_1,T_2,...T_d\) 为有根树，则 \(T=((\cup V_i) \cup { r } ,)\) 也是。相对于 \(T\)，\(T_i\) 称作以 \(r_i\) 为根的子树（subtree rooted at \(r_i\)），记作 \(T_i=subtree(r_i)\)。\(r_i\) 称作 \(r\) 的孩子（child），\(r_i\) 之间互称兄弟（sibling）。\(r\) 为其父亲（parent），\(d=degree(r)\) 为 \(r\) 的（出）度（degree），即 \(r\) 的孩子的数目。

可归纳证明：\(e=\sum_{r\in V} degree(r)=n-1=\Theta(n)\)，即任何一棵树中，所含的边数（\(e\)）应该恰好等于其中所有顶点的度数之和，同时也恰好等于顶点总数（\(n\)）减 1，故在衡量相关复杂度时，可以 \(n\) 作为参照。

若指定 \(T_i\) 作为 \(T\) 的第 \(i\) 棵子树，\(r_i\) 作为 \(r\) 的第 \(i\) 个孩子，则 \(T\) 称作有序树（ordered tree）。

定义：连通性+无环性

\(V\) 中的 \(k+1\) 个节点，通过 \(E\) 中 \(k\) 条边依次相联，构成一条路径（path），亦称通路。表示为： \[\pi=\{(v_0, v_1), (v_1, v_2), ..., (v_{k-1}, v_k)\}\]

其中路径长度：\(|\pi|=边数=k\)。在早期文献中，或以节点数为长度。

所谓环路（cycle/loop），即 \(v_k=v_0\)

节点之间均有路径，称作连通图（connected）。不含环路，称作无环图（acyclic）。

所谓的树，其实就是在无环与连通之间达到一个平衡的一种特定的图，因为无环，所以它的边数不会太大，反之，因为连通，所以它的边数又不能太少（无环连通图）；在保证连通的前提下，它的边数能够达到最少（极小连通图）；而在杜绝环路的前提下，它又能够使用尽可能多的边（极大无环图）。

从以上可得，任一节点 \(v\) 与根之间存在唯一路径，即 \(path(v, r)=path(v)\)，因此每一个节点拥有了一个唯一的指标，也就是这条路径的长度。

不致歧义时，路径、节点和子树可相互指代，即 \(path(v)\sim v\sim subtree(v)\)，因此，\(v\) 的深度：\(depth(v)=|path(v)|\)。

此外，\(path(v)\) 上节点，均为 \(v\) 的祖先（ancestor），\(v\) 是它们的后代（descendent），其中，除自身以外，是真（proper）祖先/后代。

所谓的半线性，即在任一深度，\(v\) 的祖先若存在，则必然唯一；\(v\) 的后代若存在，则未必唯一。

根节点是所有节点的公共祖先，深度为 0，没有后代的节点称作叶子（leaf），所有叶子深度中的最大者称作（子）树（根）的高度，即 \(height(v)=height(subtree(v))\)。

特别地，空树的高度取做 -1。

任何一个节点的高度与深度之和绝对不会超过全树的高度，即 \(depth(v)+height(v)\leq height(T)\)。

表示

为兼顾空间性能和时间性能，通常采用长子-兄弟表示法表示一棵树。即每个节点均设两个引用：纵（firstChild()）和横（nextSibling()）。

二叉树

节点度数不超过 2 的树称作二叉树（binary tree）。

同一节点的孩子和子树，均以左、右区分，其中隐含有序。

深度为 \(k\) 的节点，至多 \(2^k\) 个。

含 \(n\) 个节点、高度为 \(h\) 的二叉树中：\(h\lt n\lt 2^{h+1}\)：

  • \(n=h+1\) 时：退化为一条单链
  • \(n=2^{h+1}-1\) 时：即所谓满二叉树（full binary tree）

每个节点的度数都是偶数（或者是 0 或者是 2）的树称作真二叉树（full binary tree）。

二叉树是多叉树的特例，但在有根且有序时，其描述能力却足以覆盖后者。利用长子-兄弟表示法，多叉树均可转化并表示为二叉树。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class BinTree:
    pass

深度优先遍历（DFS）

二叉树的深度优先遍历具体分为：

  • 前序遍历
  • 中序遍历
  • 后序遍历

前序、中序、后序是相对于根的访问顺序确定的。

深度优先遍历一般要依靠栈来实现。

前序遍历

前序遍历（preorder traversal）又称先序遍历，指先访问根，然后访问子树的遍历方式

class Solution:
    def visit_along_left_branch(self, root: TreeNode, stack, result):
        while root:
            result.append(root.val)
            stack.append(root.right)
            root = root.left

    # 迭代实现
    def preorder_traversal(self, root: TreeNode) -> List[int]:
        stack = []
        result = []
        while True:
            self.visit_along_left_branch(root, stack, result)
            if not stack:
                break
            root = stack.pop()
        return result

    # 递归实现
    def preorder_traversal_recursion(self, root: TreeNode) -> List[int]:
        result = []
        if not root:
            return
        result.append(root.val)
        self.preorder_traversal_recursion(root.left)
        self.preorder_traversal_recursion(root.right)
        return result

LeetCode：144. 二叉树的前序遍历

中序遍历

中序遍历（inorder traversal）指先访问左（右）子树，然后访问根，最后访问右（左）子树的遍历方式

如果二叉树画的规范的话，那么它的垂直投影则是中序遍历序列。

class Solution:
    def go_along_left_branch(self, root: TreeNode, stack):
        while root:
            stack.append(root)
            root = root.left

    # 迭代实现
    def inorder_traversal(self, root: TreeNode) -> List[int]:
        stack = []
        result = []
        while True:
            self.go_along_left_branch(root, stack)
            if not stack:
                break
            root = stack.pop()
            result.append(root.val)
            root = root.right
        return result

LeetCode：94. 二叉树的中序遍历

后序遍历

后序遍历（postorder traversal）指先访问子树，然后访问根的遍历方式

class Solution:
    def goto_left_most_leaf(self, stack):
        while (root=stack.pop()):
            stack.append(root)
            root = root.left

    # 迭代实现
    def postorder_traversal(self, root: TreeNode) -> List[int]:
        stack = []
        result = []
        if root:
            stack.append(root)
        while stack:
            if stack.top() != root.parent:
                self.go_along_left_branch(stack)
            root = stack.pop()
            result.append(root.val)
        return result

LeetCode：145. 二叉树的后序遍历

广度优先遍历（BFS）

二叉树的广度优先遍历即层序遍历/层次遍历。

广度优先遍历一般要依靠队列来实现。

from collections import deque


class Solution:
    # 迭代实现
    def level_order_traversal(self, root: TreeNode) -> List[int]:
        result = []
        queue = deque()  # 引入辅助队列
        queue.append(root)  # 根节点入队
        while queue:  # 在队列再次变空之前，反复迭代
            x = queue.popleft()  # 取出队首节点，并随即
            result.append(x.val)  # 访问之
            if x.left:
                queue.append(x.left)  # 左孩子入队
            if x.right:
                queue.append(x.right)  # 右孩子入队
        return result

LeetCode：102. 二叉树的层序遍历

重构

已知 前序遍历与后序遍历之一 以及 中序遍历，可以重构出一棵二叉树。

已知 前序遍历 以及 后序遍历，可以重构出一颗真二叉树。

二叉搜索树

如果说二叉树是对链表的扩充，那么二叉搜索树则可以看作是对有序顺序表的扩充。

在二叉搜索树中，数据项之间，依照各自的关键码（key）彼此区分。因此，这种访问方式不妨称之为寻关键码访问（call-by-key）。

二叉搜索树（Binary Search Tree，BST）相比二叉树拥有以下特性：

  • 顺序性（局部特征）：任一节点均大于其左后代，任一节点均小于其右后代
  • 单调性（全局特征）：BST 的中序遍历序列，必然单调非降

查找

二叉搜索树的查找运用了减治法的思想，即从根节点出发，逐步地缩小查找范围，直到发现目标（成功），或查找范围缩小至空树（失败）。

对照中序遍历序列可见，整个过程可视作是在仿效有序顺序表的二分查找。

最坏时间复杂度为 \(O(h)\)，\(h\) 为树的高度。

增加

先借助查找算法确定插入位置及方向，再将新节点作为叶子插入。

其时间复杂度主要取决于查找算法，故最坏时间复杂度为 \(O(h)\)，\(h\) 为树的高度。

删除

删除算法稍微复杂，因为这不是简单的删除，还要保证删除后仍然是一棵二叉搜索树，假设要删除的目标节点为 \(x\)，可分以下两种情况考虑：

  • 若 \(x\) 的某一子树为空，则可将其替换为另一子树。
  • 若 \(x\) 有两棵子树，则可化繁为简，令 \(x\) 和它的直接后继互换，此时 \(x\) 将至多有一个右孩子（因为此节点是直接后继，它必然是某条左侧分支的末端），此时可采用上一种情况的方法。

最坏时间复杂度为 \(O(h)\)，\(h\) 为树的高度。

LeetCode：450. 删除二叉搜索树中的节点

平衡二叉搜索树

由前文可知，二叉搜索树的所有操作的时间复杂度为 \(O(h)\)，\(h\) 为树的高度，然而，其平均高度为 \(O(\sqrt n)\)，这并不能令人满意，因此我们要试图降低树的高度。

节点数目固定时，兄弟子树高度越接近（平衡），全树也将倾向于更低。

由 \(n\) 个节点组成的二叉树，高度不低于 \(\lfloor log_2 n \rfloor\) —— 恰为 \(\lfloor log_2 n \rfloor\) 时，称作理想平衡。

完全二叉树、满二叉树都是理想平衡的。

理想平衡出现概率极低、维护成本过高，故须适当地放松标准。

高度渐进地不超过 \(O(logn)\)，即可称作适度平衡。适度平衡的 BST，称作平衡二叉搜索树（Balanced Binary Search Tree，BBST）。

也就是说，BBST 是 BST 的一个子集，如果经过某些操作（一般为动态操作）之后，它不再保持适度平衡，就会游离这个子集之外，此时，我们就需要一整套方法将它重新拉回这个子集之内，这叫做重平衡（rebalance）。不同的 BBST（比如 AVL 树、伸展树、红黑树等），它们的适度平衡的标准不一样，重平衡方法也不一样。无论哪种重平衡方法，本质上来说都是一系列的等价变换。

拓扑结构不尽相同，但中序遍历序列却相同的任何一对 BST，称作相互等价的 BST。等价的 BST 之间，在拓扑结构上虽然不尽相同，但也有其独特的规律：

  • 上下可变：联接关系不尽相同，承袭关系可能颠倒。即等价的 BST 在垂直方向有一定的自由度。
  • 左右不乱：中序遍历序列完全一致，全局单调非降

实际上，任何一对等价 BST 之间的相互转换，都可以视作是由一系列的基本操作串接而成，而这种基本的变换无非两类，彼此对称，即 zig（顺时针旋转）和 zag（逆时针旋转）。

AVL 树

对于二叉树中的任何一个节点 \(v\)，它的平衡因子就是它的左子树高度与右子树高度之差，即：

\(balFac(v)=height(lc(v)) - height(rc(v))\)

所谓 AVL 树就是其中所有节点的平衡因子都不超过 1 也不小于 -1，即：

\(\forall v,|balFac(v)|\leq 1\)

增加

增加算法稍微简单，无非就是单旋或双旋两种情况而已。

其重平衡的时间复杂度为 \(O(1)\)。

删除

因有失衡传播现象，可能需做 \(O(logn)\) 次调整。

伸展树

红黑树

由红、黑两类节点组成的 BST（统一增设外部节点 NULL，使之成为真二叉树）：

  • 树根：必为黑色
  • 外部节点：均为黑色
  • 其余节点：若为红，则只能有黑孩子。即红之子、之父必黑
  • 外部节点到根：途中黑节点数目相等。即黑深度

提升各红节点，使之与其（黑）父亲等高 —— 于是每棵红黑树，都对应于一棵 (2, 4) 树。

增加

删除

B 树

相比二叉搜索树，B 树（B-tree）或称 B-树中每一个节点未必只有两个分叉（实际上，可以拥有更多的分叉），其次，所有底层节点的深度都是完全一致的，从这个意义上讲，它不失为一种理想平衡的搜索树。

从整体上看，B 树会显得更宽、更矮。

由于 B 树也属于平衡搜索树，所以它也具有某种方法来自平衡。

B 树可以理解为是平衡的多路（multi-way）搜索树。

若将多路搜索树中的每一个节点称作超级节点，那么每一个超级节点都可以看成是由若干个二路节点经过适当的合并以后得到的，具体来说：

  • 每 2 代合并：4 路
  • 每 3 代合并：8 路
  • ...
  • 每 \(d\) 代合并：\(m=2^d\) 路，\(m-1\) 个关键码

从上可以看出，B 树在逻辑上与 BBST 完全等价。但 B 树也有其存在的原因，具体来说，多级存储系统中使用 B 树，可针对外部查找，大大减少 I/O 次数。

我们知道，二叉搜索树的查找的逐层递进的，其最坏时间复杂度为 \(O(h)\)，\(h\) 为树的高度，注意这里每访问一层实际上就是一次 I/O 操作，对于平衡二叉搜索树来说，它会适当的降低树的高度，以尽量减小最坏时间复杂度，以 AVL 树为例，若有 \(n=10^9=1G\) 个记录，那么每次查找需要 \(log_2 10^9=30\) 次 I/O 操作，每次只读出一个关键码，得不偿失。

对于以上情况，若使用 B 树，则能充分利用外存对批量访问的高效支持，将此特点转化为优点，每下降一层，都以超级节点为单位，读入一组关键码。

所谓 \(m\) 阶 B 树，即 \(m\) 路平衡搜索树（\(m>=2\)）。

阶次 \(m\) 给出了 B 树中每个超级节点规模的上限和下限（以 \(n\) 来表示节点中所含的关键码数）：

  • 上限：内部节点各有
    • 不超过 \(m\) 个分支：\(A_0,A_1,A_2,...,A_n\)
    • 不超过 \(m-1\) 个关键码：\(K_1<K_2<...<K_n\)
  • 下限：内部节点的分支数 \(n+1\) 也不能太少
    • 其余：\(\lceil m/2\rceil\leq n+1\)
    • 树根：\(2\leq n+1\)

既然如此，我们也用超级节点所拥有分支数的下限和上限来命名 B 树，故亦称作 (\(\lceil m/2\rceil,m\)) 树。比如 \(m=5\) 时，每个节点的分支数自然不得超过 5，同时一般节点所拥有的分支数也不得少于 3，所以我们也可以称之为 (3, 5) 树。特别的，对于 4 阶 B 树而言，自然也可以称之为 (2, 4) 树，(2, 4) 树在 B 树中具有非常独特的作用和地位，(2, 4) 树与红黑树有不解的渊源。

查找

增加

删除

B+ 树

图

相对于此前的线性以及半线性结构，图结构对其中元素的限定更少，因此反过来，它描述应用问题的能力也就更强。

与树类似：

\(G=(V; E)\)

vertex：\(n=|V|\)

edge|arc：\(e=|E|\)

存在连边的任何两个点都称作是彼此邻接的，那么这样一个关系，也称作邻接（adjancency）关系，而参与定义这种邻接关系的每一个顶点，与这个邻接关系之间的关系，我们也称作关联（jncidence）关系。形象地说，所谓的邻接关系就是顶点与顶点之间的关系，而关联关系实际上是描述顶点以及与它相关的某条边之间的关系。

若同一个节点与自身构成一个邻接关系，则称作自环，本节不讨论这种情况。

若邻接顶点 \(u\) 和 \(v\) 的次序无所谓，则 \((u, v)\) 为无向边（undirected edge）。例：若 \(u\) 是 \(v\) 的好友，则 \(v\) 也必是 \(u\) 的好友。

所有边均无方向的图，即无向图（undigraph）。

反之，有向图（digraph）中均为有向边（directed edge），\(u\)、\(v\) 分别称作边 \((u, v)\) 的尾（tail）、头（head）。例：“\(u\) 欠 \(v\) 的钱”与“\(v\) 欠 \(u\) 的钱”。

在有些情况下，图中的边有的是有向的，而另一部分却可能是无向的，这样的图称之为混合图（mixed graph）

本节重点研究有向图，因为通过有向图，完全可以表示并且实现无向图以及混合图。

与树类似：

路径 \(\pi=<v_0, v_1, ..., v_k>\)，长度 \(|\pi|=k\)

简单路径（simple path）：\(v_i=v_j\) 除非 \(i=j\)

环/环路：\(v_0=v_k\)

如果在一个有向图中，不包含任何的环路，则称之为有向无环图（DAG）。

经过所有的边一次而且恰好一次的环路称作欧拉环路（Eulerian tour）；对称的，经过每一个顶点一次而且恰好一次的环路称作哈密尔顿环路（Hamiltonian tour）。

一笔画问题即要找出欧拉路径。

邻接矩阵

图的表示可以采用邻接矩阵或关联矩阵来表示，本节我们主要采用邻接矩阵。

所谓邻接矩阵就是用以描述顶点之间相互邻接关系的一种形式，具体来说，这是一个方阵，如果图中包含 \(n\) 个顶点，这个矩阵也就是 \(n\times n\) 的，于是矩阵中的任何一个单元，比如对应于第 \(i\) 行第 \(j\) 列的那个单元，都表示顶点 \(i\) 与顶点 \(j\) 之间是否存在一条边（即是否关联）。

如果是无向图，那么它对应的邻接矩阵就应该是对称的，特别的，在该矩阵对角线上的元素都对应于自环。

如果是带权图（即网络），那么每个单元可以存储权值。

对于关联矩阵，如果当前的图有 \(n\) 个节点，那么这个矩阵就有 \(n\) 行，如果图中总共包含 \(e\) 条边，那么这个矩阵就对应的有 \(e\) 列，相应地，矩阵中的任何一个单元表示的也就是对应的顶点与对应的边之间。对于矩阵中的任何一列而言，应该恰好有两个单元的数值为 1，而其余的都是 0。

广度优先搜索

深度优先搜索

哈希表

概念

哈希表（hash table）又称字典（dictionary）、词典或散列表，哈希（hashing）又称散列或杂凑。

当我们需要存储和组织的数据项可能来自于一个相当大的空间（不妨将其数量记为 R），而在任何一个常规的时刻，我们所真正需要存储和组织的数据只是其中非常非常小的一个子集时（不妨将其数量记为 N），为了提升空间效率，就需要使用哈希表。

哈希表中的每一个单元被称为桶（bucket），其可以 直接存放 或 间接指向 一个词条（entry）。因此，哈希表又可称为桶数组（bucket array）。

定址（或哈希）是指根据词条的 key（未必可比较）直接确定哈希表入口。要实现这种定址就需要哈希函数/散列函数。

为方便讨论，我们将哈希表的长度（即容量）记为 M。

已用空间的容量与哈希表总容量之比，即 N/M，称为装填因子（load factor），通常也简记为 \(\lambda\)。

哈希冲突/散列冲突（hash collision），即存在 key1 != key2，但 hash(key1) = hash(key2)。适当的将哈希表的长度增长，可以减少冲突出现的概率。

从理论上讲，哈希可以看作是由一个大空间到小空间的映射，因此绝不可能是单射，即冲突不可避免，但是，近似的单射往往可行，因此，我们需要：

  • 精心设计哈希表及哈希函数，以尽可能降低冲突的概率；
  • 更需要制定可行的预案，以便在发生冲突时，能够尽快予以排解。

下面两节将分别介绍。

哈希函数

一个好的哈希函数有以下特性：

  • 确定（determinism）：同一关键码总是被映射至同一地址
  • 快速（efficiency）：\(expected-O(1)\)
  • 满射（surjection）：尽可能充分地覆盖整个哈希空间
  • 均匀（uniformity）：关键码映射到哈希表各位置的概率尽量接近，可有效避免聚集（clustering）现象。

以下是一些常用的哈希函数：

除余法

\(hash(key) = key \bmod M\)，M 为素数时，数据对哈希表的覆盖最充分，分布最均匀。

除余法的缺陷：

  • 不动点：无论表长 M 取值如何，总有 hash(0) = 0
  • 零阶均匀：[0, k) 的关键码，平均分配至 M 个桶；但相邻关键码的哈希地址也必相邻

MAD 法

MAD 即 multiply-add-divide（乘-加-除），取 M 为素数，\(a > 0\)，\(b > 0\)，\(a \bmod M \neq 0\)，\(hash(key) = (a \times key + b) \bmod M\)。

MAD 法可以解决上述除余法的两个缺陷：

  • b 可以看作是偏移量（offset），可解决不动点问题
  • a 可以看作是步长（step），可以实现一阶均匀，即邻近的关键码，哈希地址不再邻近

当然，特定场合下，未必需要高阶的均匀性。

数字分析法（selecting digits）

抽取 key 中的某几位，构成地址。

比如，取十进制表示的奇数位：\(hash(123456789) = 13579\)

此方法的缺陷在于没有被选用的那一组数位，对最终的哈希地址没有任何影响和贡献，没有足够的体现均匀性的要求。

平方取中法（mid-square）

取 \(key^2\) 的中间若干位，构成地址。

比如：

\(hash(123)=512\)，保留 \(key^2=123^2=15129\) 的中间 3 位

\(hash(1234567)=556\)，保留 \(1234567^2=1524155677489\) 的中间 3 位

平方取中法可以有效的解决上述方法的缺陷，取中间的数位可以使得构成原关键码的各数位能够对最终的哈希地址有尽可能接近的影响。

折叠法（folding）

将 key 分割成等宽的若干段，取其总和作为地址。

位异或法 XOR

将 key 分割成等宽的二进制段，经异或运算得到地址。

总之，哈希函数越是随机，越是没有规律，越好。

排解冲突

哈希表中的冲突无法避免，通过以下方法可以排解冲突：

多槽位

多槽位（multiple slots）：桶单元细分成若干槽位（slot），存放（与同一单元）冲突的词条。

只要槽位数目不多，依然可以保证 \(O(1)\) 的时间效率。

但是，需要为每个桶配备多少个槽，方能保证 \(O(1)\)？若预留过多，则空间浪费；无论预留多少，极端情况下仍有可能不够。

独立链

为了解决以上问题，可以采用独立链法。

独立链（linked-list chaining/separate chaining）：每个桶存放一个指针，冲突的词条，组织成链表。

它存在如下优点与缺点：

优点：

  • 无需为每个桶预备多个槽位
  • 任意多次的冲突都可解决
  • 删除操作实现简单、统一

缺点：

  • 指针需要额外空间
  • 节点需要动态申请
  • 空间未必连续分布，系统缓存几乎失效

开放定址

排序

排序是指：给定 n 个整数，将它们按（非降）序排列。

排序算法大致可分为两类：

  • 基于比较的排序（comparison based algorithm，C.B.A.）：归并排序、冒泡排序、快速排序、希尔排序，其时间复杂度的下限为 \(O(nlogn)\)
  • 非基于比较的排序：桶排序、计数排序、基数排序

排序算法的稳定性（stability）指重复元素在输入、输出序列中的相对次序，是否保持不变？

  • 稳定的排序：归并排序、插入排序、冒泡排序
  • 不稳定的排序：快速排序、堆排序

输入含重复元素时，算法的稳定性是更为细致的要求。

排序算法多种多样，对于程序员来说，重点需要熟记归并排序、快速排序、堆排序和插入排序这四种。

各个排序的时间复杂度如下：

排序最坏时间复杂度平均时间复杂度空间复杂度
归并排序\(O(nlogn)\)\(O(nlogn)\)无
快速排序\(O(n^2)\)\(O(nlogn)\)\(O(1)\)
堆排序\(O(nlogn)\)\(O(nlogn)\)无
插入排序\(O(n^2)\)\(O(n^2)\)无
冒泡排序\(O(n^2)\)\(O(n^2)\)无
选择排序\(O(n^2)\)\(O(n^2)\)无
计数排序无无无
桶排序无无无
希尔排序无无无

归并排序

归并排序（merge sort）是分治策略的一种实现，具体来说，它将序列一分为二，分别的对子序列递归排序，最后合并有序子序列。

归并排序的核心是合并（merge）操作，即二路归并（2-way merge），指将两个有序序列合并为一个有序序列：S[lo, hi) = S[lo, mi) + S[mi, hi)。

合并时只需比较两个有序序列的第一个元素的大小即可。

def merge(left, right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    if left:
        result += left
    if right:
        result += right
    return result


def mergesort(lis):  # [lo, hi)
    if len(lis) < 2:  # 单元素区间自然有序，否则...
        return lis
    mi = len(lis) >> 1  # 以中点为界
    left = mergesort(lis[:mi])  # 对前半段排序
    right = mergesort(lis[mi:])  # 对后半段排序
    return merge(left, right)  # 归并


# 测试
lis = [4, 3, 8, 7, 1, 9, 6]
print(mergesort(lis))  # [1, 3, 4, 6, 7, 8, 9]

归并排序的最坏时间复杂度为 \(O(nlogn)\)。

LeetCode：21. 合并两个有序链表

快速排序

快速排序（quick sort）同样是分治策略的一种体现，它的思想为将序列分为两个子序列，且前一个子序列的数都不大于后一个子序列，在子序列分别递归地排序之后，原序列自然有序。

由此可见，归并排序的计算量和难点在于合，而快速排序在于分。

要实现以上所述的那种子序列的划分，其关键在于寻找轴点（pivot），轴点左侧的元素均不比它更大，轴点右侧的元素均不比它更小。

显然，轴点必定已然就位。但坏消息是，在原始序列中，轴点未必存在。比如，在乱排（derangement）序列中，轴点就不存在。特别地，在有序序列中，所有元素皆为轴点，反之亦然。从这个角度来看，所谓的快速排序无非就是将所有元素逐个转换为轴点的过程。具体来说，通过适当交换，可使任一元素转换为轴点。

任何一个有序序列只要经过一次循环移位就可得到一个乱排序列，比如 [2, 3, 4, ..., n, 1]。

def partition(lis):
    pivot = lis[0]
    mi = 0
    for k in range(1, len(lis)+1):
        if lis[k] < pivot:
            mi += 1
            lis[mi], lis[k] = lis[k], lis[mi]
    lis[0], lis[mi] = lis[mi], lis[0]
    return mi


def quicksort(lis):
    if len(lis) < 2:  # 单元素区间自然有序，否则...
        return lis
    mi = partition(lis)  # 先构造轴点，再
    quicksort(lis[:mi])  # 对前半段排序
    quicksort(lis[mi:])  # 对后半段排序


# 测试
lis = [4, 3, 8, 7, 1, 9, 6]
print(quicksort(lis))  # [1, 3, 4, 6, 7, 8, 9]

快速排序是不稳定（unstable）的，lo/hi 的移动方向相反，左/右侧的大/小重复元素可能前/后颠倒。

快速排序是就地（in-place）的，只需 \(O(1)\) 的附加空间。

最好情况下，每次划分都（接近）平均，轴点总是（接近）中央，此时时间复杂度为 \(O(nlogn)\)。

最坏情况下，每次划分都极不均衡，比如，轴点总是最小或最大元素，此时时间复杂度为 \(O(n^2)\)，与冒泡排序相当！即便采用随机选取、（Unix）三者取中之类的策略，也只能降低最坏情况的概率，而无法杜绝。

随机选取：不再是每次都固定的将首元素作为候选轴点，而是在整个序列中，随机的选择其一。

三者取中：每次都是在整个序列中，随机的抽取三个元素，然后将其中数值居中的那个作为候选轴点。

以均匀独立分布为例，在平均情况下，其时间复杂度为 \(O(nlogn)\)，特别的，\(n\) 约等于 1.39。

堆排序

from heapq import heappush, heappop


def heapsort(iterable):
    h = []
    for value in iterable:
        heappush(h, value)
    return [heappop(h) for i in range(len(h))]


lis = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
print(heapsort(lis))

插入排序

冒泡排序

冒泡排序（bubble sort）又称起泡排序。它主要基于以下观察：

  • 有序序列中，任意一对相邻元素顺序
  • 无序序列中，总有一对相邻元素逆序

为此，要执行扫描交换，即依次比较每一对相邻元素，如有必要，交换之；若整趟扫描都没有进行交换，则排序完成；否则，再做一趟扫描交换。

Python 实现：

C 实现：

void bubblesort(int A[], int n)
{
    for(bool sorted = false; sorted = !sorted; n--)  // 逐趟扫描交换，直至完全有序
    {
        for(int i = 1; i < n; i++)  // 自左向右，逐对检查A[0, n)内各相邻元素
        {
            if(A[i-1] > A[i])  // 若逆序，则
            {
                swap(A[i-1], A[i]);  // 令其互换，同时
                sorted = false;  // 清除（全局）有序标志
            }
        }
    }
}

冒泡排序是稳定的排序，这是因为，在冒泡排序中，元素 a 和 b 的相对位置发生变化，只有一种可能：经分别与其他元素的交换，二者相互接近直至相邻，在接下来一轮扫描交换中，二者因逆序而交换位置。

选择排序

计数排序

def countingsort(lis):
    length = max(lis)-min(lis)+1
    count = [0]*length
    for i in lis:
        count[i] += 1
    for index in range(0, len(count)):
        count[index] += count[index-1]
    return count


lis = [6, 3, 8, 4, 2, 6, 3, 7, 3]
sorted_list = countingsort(lis)
print(sorted_list)

LeetCode：1122. 数组的相对排序

桶排序

LeetCode：164. 最大间距

希尔排序

查找

二分查找

二分查找是减治策略的一种体现。

以任一元素 x = S[mi] 为界，都可将待查找区间分为 2 部分，即 S[lo, mi) <= S[mi, hi)，其中 S[mi] 称作轴点，只需将目标元素 e 与 x 做一比较，即可分 2 种情况进一步处理：

  1. e < x：则 e 若存在必属于左侧子区间 S[lo, mi)，故可递归深入
  2. x <= e：则 e 若存在必属于右侧子区间 S[mi, hi)，亦可递归深入

二分（折半）策略：轴点 mi 总是取作中点，则查找每深入一层，问题规模也缩减一半。

此外，为了语义约定，查找的返回值为不大于 e 的最后一个元素。

def bin_search(A, e, lo, hi):  # 在有序向量区间[lo, hi)内查找元素e
    while lo < hi:  # 不变性：A[0, lo) <= e < A[hi, n)
        mi = (lo+hi) >> 1  # 以中点为轴点，经比较后确定深入
        if e < A[mi]:
            hi = mi  # 深入前半段[lo, mi)继续查找
        else:
            lo = mi + 1  # 深入后半段(mi, hi)
    return lo-1  # 出口时，A[lo=hi]为大于e的最小元素，故lo-1即不大于e的元素的最大秩


# 测试
lis = [2, 5, 6, 9, 10, 12, 13]
print(bin_search(lis, 12, 0, len(lis)))  # 5
print(bin_search(lis, 11, 0, len(lis)))  # 4

其平均时间复杂度约为 \(O(1.5\times logn)\)。

LeetCode：704. 二分查找

Fibonacci 查找

二分查找和 Fibonacci 查找都有一个通用策略，即对于任何的 A[0, n)，总是选取 \(A[\lambda n]\) 作为轴点，其中 \(0\leq\lambda<1\)。

具体来说，二分查找对应于 \(\lambda=0.5\)，Fibonacci 查找对应于 \(\lambda=\phi=0.6180339...\)。

比如，若设 n=fib(k)-1，则可取 mi=fib(k-1)-1，于是，前、后子向量的长度分别为 fib(k-1)-1、fib(k-2)-1。

def fib_search(A, e, lo, hi):
    Fib fib(hi-lo)
    while lo < hi:
        while hi-lo<fib.get():
            fib.prev()
        mi = lo + fib.get() - 1  # 按黄金比例切分
        if e < A[mi]:
            hi = mi  # 深入前半段[lo, mi)继续查找
        elif A[mi] < e:
            lo = mi + 1  # 深入后半段(mi, hi)
        else:
            return mi  # 在mi处命中
    return -1

其平均时间复杂度约为 \(O(1.44\times logn)\)。

插值查找

假设已知有序向量中各元素随机分布的规律，比如均匀且独立的随机分布，于是 [lo, hi) 内各元素应大致按照线性趋势增长，即 \(\frac{mi-lo}{hi-lo}\approx\frac{e-A[lo]}{A[hi]-A[lo]}\)，因此，通过猜测轴点 mi，可以极大地提高收敛速度，即 \(mi\approx lo+(hi-lo)\times\frac{e-A[lo]}{A[hi]-A[lo]}\)。

例如，在英文词典中，binary 大致位于 \(\frac{2}{26}\) 处，search 大致位于 \(\frac{19}{26}\) 处。

按照姚期智先生早期的证明，在插值查找算法中，每经过一次比较，查找规模 n 缩至 \(\sqrt{n}\)。

通过以上定理可以计算得出其平均时间复杂度约为 \(O(loglogn)\)。

在实际中，插值算法通常优势不明显 —— 除非查找区间宽度极大，或者比较操作成本极高；此外，其易受小扰动的干扰和“蒙骗”；在具体实现时须引入乘法、除法运算，这也造成其实现成本较高。

所以，实际可行的方法是：首先通过插值查找，将查找范围缩小到一定的范围，然后再进行二分查找。

字符串匹配

字符串的具体实现并不难，借助之前的线性表数据结构即可轻松实现，在本节我们重点讨论字符串的相关算法。

概念

字符串简称为 串，是指由 字母表 \(\sum\) 的字符所组成的 有限序列，即 \(S=a_0a_1a_2...a_{n-1} \in \sum^*\)。

字符串与常规的线性表又有些许不同，通常，字符的种类不多，而\(串长=n \gg |\sum|\)。

一般地，如果一个名为 S 的字符串由 n 个字符构成，我们就将所有的字符从前至后编号为 0 至 n-1，并按照我们的惯例，记作 S[0, n)，而串中秩为 k 的字符，也相应地记作 S[k]。

两个字符串相等是指 S[0, n) = T[0, m)，即长度相等（n = m），且对应的字符均相同（S[i] = T[i]）。

对于任何一个字符串 S 而言，由 i 和 k 所指定的那个子串，也就是从秩为 i 的那个字符开始，连续的 k 个字符。

所谓的前缀（prefix）是子串的一个特例，具体来说，所谓长度为 k 的前缀，也就是起始于首字符的前 k 个字符。

对称的，所谓长度为 k 的后缀（suffix），也就是终止于末元素的最靠后的 k 个字符。

不难验证，所谓起始于 i，长度为 k 的子串，也就是在长度为 i+k 的前缀中，长度为 k 的后缀。

对于串长 n 为 0 的串称之为空串，空串与由空格组成的串并不是一回事，空串是任何串的子串、前缀、后缀。

此外，任何串也是其自身的子串、前缀、后缀。反过来，长度严格小于原串的子串、前缀、后缀也称作真子串、真前缀、真后缀。

注意，从上面可以看出子串和子序列不是一回事，子串是连续的，子序列则未必连续。

串匹配

字符串匹配具体指在文本串 T 中找到模式串 P 的过程。记 \(n=|T|\) 和 \(m=|P|\)，通常有 \(n\gg m\gg 2\)。

字符串匹配又称模式匹配（pattern matching），其可以分为 4 个层次：

  1. detection：P 是否 出现？
  2. location：首次 在哪里 出现？
  3. counting：共有 几次 出现？
  4. enumeration：各出现 在哪里？

我们本节重点讨论第 2 个层次。

暴力匹配

暴力匹配（Brute Force，BF）又称为蛮力匹配或朴素匹配算法，自左向右，以字符为单位，依次移动模式串，直到在某个位置，发现匹配。

def match(P, T):
    n = len(T)  # T[i]与P[0]对齐
    m = len(P)  # T[i+j]与P[j]对齐
    for i in range(n-m+1):  # T从第i个字符起，与
        for j in range(m):  # P中对应的字符逐个比对
            if T[i+j] != P[j]:  # 若失配，P整体右移一个字符，重新比对
                break
        if j == m-1:  # 找到匹配子串
            break
    return i


# 测试
P = '1011'
T = '1001101101'
print(match(P, T))

暴力匹配的最坏时间复杂度为 \(O(n\times m)\)，\(|\sum|\) 越小，最坏情况出现的概率越高，\(m\) 越大，最坏情况的后果更加严重。

KMP

KMP（D.E.Knuth, J.H.Morris, V.R.Pratt）算法可以看作是对暴力匹配的一种改进，具体来说，在每一次失败之后，应该将模式串中的某一个字符与文本串中刚才失败的那个字符彼此重新对齐。

比如：

T = 'ZHREGRETBA'
P =   'REGROW'
P =      'REGROW'

当 T 中的 E 与 P 中的 O 失配后，我们应将 P 中的 E 重新与 T 中的 E 进行比较，此时 P 向后移动了 3 位。

如何确定模式串中要进行对齐的那个继任字符呢？我们需要借助 next 查询表，由此可见 KMP 算法的核心在于构造 next 查询表。

构造查询表 next[0, m)：在任一位置 P[j] 处失败之后，将 j 替换为 next[j]。

所谓 next[j]，即是在 P[0, j) 中，最大自匹配的真前缀和真后缀的长度。

比如，P = 'chinchilla'：

  • next[0]，即 P[0, 0) == ''：设为 -1
  • next[1]，即 P[0, 1) == 'c'：真前缀为空串，真后缀也为空串，最大自匹配长度为 0
  • next[2]，即 P[0, 2) == 'ch'：真前缀只有 'c'，真后缀只有 'h'，最大自匹配长度为 0
  • next[3]，即 P[0, 3) == 'chi'：真前缀有 ['c', 'ch']，真后缀有 ['i', 'hi']，最大自匹配长度为 0
  • next[4]，即 P[0, 4) == 'chin'：真前缀有 ['c', 'ch', 'chi']，真后缀有 ['n', 'in', 'hin']，最大自匹配长度为 0
  • next[5]，即 P[0, 5) == 'chinc'：真前缀有 ['c', 'ch', 'chi', 'chin']，真后缀有 ['c', 'nc', 'inc', 'hinc']，最大自匹配为 'c'，长度为 1
  • next[6]，即 P[0, 6) == 'chinch'：真前缀有 ['c', 'ch', 'chi', 'chin', 'chinc']，真后缀有 ['h', 'ch', 'nch', 'inch', 'hinch']，最大自匹配为 'ch'，长度为 2
  • next[7]，即 P[0, 7) == 'chinchi'：真前缀有 ['c', 'ch', 'chi', 'chin', 'chinc', 'chinch']，真后缀有 ['i', 'hi', 'chi', 'nchi', 'inchi', 'hinchi']，最大自匹配为 'chi'，长度为 3
  • next[8]，即 P[0, 8) == 'chinchil'：真前缀有 ['c', 'ch', 'chi', 'chin', 'chinc', 'chinch', 'chinchi']，真后缀有 ['l', 'il', 'hil', 'chil', 'nchil', 'inchil', 'hinchil']，最大自匹配长度为 0
  • next[9]，即 P[0, 9) == 'chinchill'：真前缀有 ['c', 'ch', 'chi', 'chin', 'chinc', 'chinch', 'chinchi', 'chinchil']，真后缀有 ['l', 'll', 'ill', 'hill', 'chill', 'nchill', 'inchill', 'hinchill']，最大自匹配长度为 0

则其 next 表为 [-1, 0, 0, 0, 0, 1, 2, 3, 0, 0]。

KMP 算法实现如下：

def build_next(P):  # 构造模式串P的next[]表
    m = len(P)
    j = 0  # “主”串指针
    N = [-1]  # next[]表
    t = N[0]  # 模式串指针（P[-1]通配符）
    while j < m-1:
        if t < 0 or P[j] == P[t]:  # 匹配
            j += 1
            N.append(t+1)
        else:  # 失配
            t = N[t]
    return N


def match(P, T):
    next = build_next(P)  # 构造next表
    n = len(T)
    i = 0  # 文本串指针
    m = len(P)
    j = 0  # 模式串指针
    while j < m and i < n:  # 自左向右，逐个比对字符
        if j < 0 or T[i] == P[j]:  # 若匹配
            i += 1  # 则携手共进
            j += 1
        else:  # 否则，P右移，T不回退
            j = next[j]
    del next  # 释放next表
    return i-j


# 测试
T = '1001101101'
P = '1011'
print(match(P, T))  # 4

在最坏情况下，其时间复杂度为 \(O(n)\)，具体来说，对于长度为 \(n\) 的文本串和长度为 \(m\) 的模式串，其时间复杂度为 \(O(n+m)\)

参考

BM

参考

Rabin–Karp

Rabin–Karp 又称 Karp-Rabin

策略

贪心

减治

减治（Decrease-and-conquer）又称减而治之，为求解一个大规模的问题，可以将其划分为两个子问题：其一平凡，另一规模缩减，分别求解子问题，由子问题的解，得到原问题的解。

典型的算法有二分查找等。

分治

分治（Divide-and-conquer）又称分而治之，为求解一个大规模的问题，可以将其划分为若干（通常两个）子问题，规模大体相当，分别求解子问题，由子问题的解，得到原问题的解。

典型算法有归并排序、快速排序等。

动态规划

动态规划实际上是把原来递归的过程倒过来实现。

def fib(n):
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n-2)


# Memoization 记忆化
def fib_a(n):
    M = []
    if n < 2:
        return n
    else:
        if not M[n]:
            M[n] = fib(n-1) + fib(n-2)
    return M[n]

滑动窗口

滑动窗口一般用于解决从数组或字符串中找出连续的子数组或子串的问题。

给定一个数组，找出数组中连续 3 个数的最大值。如 [1, 4, 2, 6, 4, 5, 3] 中最大值是 15，即 [6, 4, 5]。

nums = [1, 4, 2, 6, 4, 5, 3]


def brute(nums):
    max_value = 0
    for i in nums:
        max_value = max(max_value, sum(nums[i:i+3]))
    return max_value


def sliding_window(nums):
    start = 1
    end = 3
    max_value = sum(nums[0:2])
    while end < len(nums):
        max_value = max(max_value, max_value-nums[start-1]+nums[end])
        end += 1
        start += 1
    return max_value


brute(nums)
sliding_window(nums)

LeetCode：

常用算法

LRU

from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity  # cache的容量
        self.visited = OrderedDict()  # python内置的OrderDict具备排序的功能

    def get(self, key: int) -> int:
        if key not in self.visited:
            return -1
        self.visited.move_to_end(key)  # 最近访问的放到链表最后，维护好顺序
        return self.visited[key]

    def put(self, key: int, value: int) -> None:
        if key not in self.visited and len(self.visited) == self.capacity:
            # last=False时，按照FIFO顺序弹出键值对
            # 因为我们将最近访问的放到最后，所以最远访问的就是最前的，也就是最first的，故要用FIFO顺序
            self.visited.popitem(last=False)
        self.visited[key] = value
        self.visited.move_to_end(key)    # 最近访问的放到链表最后，维护好顺序

LeetCode：146. LRU 缓存机制

并查集

LeetCode：

常考题型

刷题总结

套路

题目中有 最大 或 最小 的，一般都可以先通过排序再解决。

Python

max 函数获取一个列表的最大值：

a = [1, 0, 3]
print(max(a))  # 3

bin 函数用于生成一个数值的二进制形式：

a = 55
bin(a)  # '0b110111'

统计序列中某元素出现的次数：

a = [1, 0, 0]
a.count(0)  # 2

集合的交集、并集、差集：

a = {1, 2, 3}
b = {1, 2, 3, 4, 5}
a & b  # 交集，输出 {1, 2, 3}
a | b  # 并集，输出 {1, 2, 3, 4, 5}
b - a  # 差集，输出 {4, 5}

collections 模块里的 Counter 对象可以很方便的统计元素出现的次数，如下：

from collections import Counter
dict(Counter('gallahad'))  # {'g': 1, 'a': 3, 'l': 2, 'h': 1, 'd': 1}
dict(Counter('gallahad').most_common())  # {'a': 3, 'l': 2, 'g': 1, 'h': 1, 'd': 1}

itertools 模块里提供有排列组合的相关函数，如下：

from itertools import permutations, combinations
nums = [1, 2, 3]
# 排列，输出 [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
list(permutations(nums, 3))
# 组合，输出 [(1, 2), (1, 3), (2, 3)]
list(combinations(nums, 2))