本篇文章主要参考了GitHub的 Hello 算法

数组

「数组 array」是一种线性数据结构，其将相同类型元素存储在连续的内存空间中。我们将元素在数组中的位置称为该元素的「索引 index」

数组常用操作

初始化数组

我们可以根据需求选用数组的两种初始化方式：无初始值和给定初始值。在未指定初始值的情况下，大多数编程语言会将数组元素初始化为0

1
2
int[] arr = new int[5]; // { 0, 0, 0, 0, 0 }
int[] nums = { 1, 3, 2, 5, 4 };

访问元素

数组元素被存储在连续的内存空间中，这意味着计算数组元素的内存地址非常容易。给定数组内存地址（即首元素内存地址）和某个元素的索引，我们可以使用如图所示的公式计算得到该元素的内存地址，从而直接访问此元素（元素内存地址 = 数组内存地址（即首元素地址） + 元素长度 ×; 元素索引）。索引的含义本质上是内存地址的偏移量

1
2
3
4
5
6
7
int randomAccess(int[] nums) {
    // 在区间 [0, nums.length) 中随机抽取一个数字
    int randomIndex = ThreadLocalRandom.current().nextInt(0, nums.length);
    // 获取并返回随机元素
    int randomNum = nums[randomIndex];
    return randomNum;
}

插入元素

数组元素在内存中是"紧挨着的"，它们之间没有空间再存放任何数据。如图所示，如果想要在数组中间插入一个元素，则需要将该元素之后的所有元素都向后移动一位，之后再把元素赋值给该索引

1
2
3
4
5
6
7
8
void insert(int[] nums, int num, int index) {
    // 把索引 index 以及之后的所有元素向后移动一位
    for (int i = nums.length - 1; i > index; i--) {
        nums[i] = nums[i - 1];
    }
    // 将 num 赋给 index 处元素
    nums[index] = num;
}

删除元素

和插入元素一样想要删除索引i处的元素，则需要把索引i之后的元素都向前移动一位。注意：删除元素完成后，原先末尾的元素变得"无意义"了，所以我们无须特意去修改它

1
2
3
4
5
6
void remove(int[] nums, int index) {
    // 把索引 index 之后的所有元素向前移动一位
    for (int i = index; i < nums.length - 1; i++) {
        nums[i] = nums[i + 1];
    }
}

总的来看，数组的插入与删除操作有以下缺点：

  • 时间复杂度高：数组的插入和删除的平均时间复杂度均为 $O(n)$，其中n为数组长度
  • 丢失元素：由于数组的长度不可变，因此在插入元素后，超出数组长度范围的元素会丢失
  • 内存浪费：我们可以初始化一个比较长的数组，只用前面一部分，这样在插入数据时，丢失的末尾元素都是无意义的，但这样做也会造成部分内存空间的浪费

遍历数组

在大多数编程语言中，我们既可以通过索引遍历数组，也可以直接遍历获取数组中的每个元素

1
2
3
4
5
6
7
8
9
10
11
void traverse(int[] nums) {
    int count = 0;
    // 通过索引遍历数组
    for (int i = 0; i < nums.length; i++) {
        count += nums[i];
    }
    // 直接遍历数组元素
    for (int num : nums) {
        count += num;
    }
}

查找元素

在数组中查找指定元素需要遍历数组，每轮判断元素值是否匹配，若匹配则输出对应索引。因为数组是线性数据结构，所以上述查找操作被称为"线性查找"

1
2
3
4
5
6
7
8
int find(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target)；；
            return i;
    }
    return -1;
}

扩容数组

在复杂的系统环境中，程序难以保证数组之后的内存空间是可用的，从而无法安全地扩展数组容量。因此在大多数编程语言中，数组的长度是不可变的。如果我们希望扩容数组，则需重新建立一个更大的数组，然后把原数组元素依次拷贝到新数组。这是一个 $O(n)$ 的操作，在数组很大的情况下是非常耗时的

1
2
3
4
5
6
7
8
9
10
int[] extend(int[] nums, int enlarge) {
    // 初始化一个扩展长度后的数组
    int[] res = new int[nums.length + enlarge];
    // 将原数组中的所有元素复制到新数组
    for (int i = 0; i < nums.length; i++) {
        res[i] = nums[i];
    }
    // 返回扩展后的新数组
    return res;
}

数组优点与局限性

数组存储在连续的内存空间内，且元素类型相同。这种做法包含丰富的先验信息，系统可以利用这些信息来优化数据结构的操作效率

  • 空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销
  • 支持随机访问：数组允许在 $O(1)$ 时间内访问任何元素
  • 缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度

连续空间存储是一把双刃剑，其存在以下缺点：

  • 插入与删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素
  • 长度不可变: 数组在初始化后长度就固定了，扩容数组需要将所有数据复制到新数组，开销很大
  • 空间浪费: 如果数组分配的大小超过了实际所需，那么多余的空间就被浪费了

数组典型应用

数组是一种基础且常见的数据结构，既频繁应用在各类算法之中，也可用于实现各种复杂数据结构

  • 随机访问：如果我们想要随机抽取一些样本，那么可以用数组存储，并生成一个随机序列，根据索引实现样本的随机抽取
  • 排序和搜索：数组是排序和搜索算法最常用的数据结构。快速排序，归并排序，二分查找等都主要在数组上进行
  • 查找表：当我们需要快速查找一个元素或者需要查找一个元素的对应关系时，可以使用数组作为查找表。假如我们想要实现字符到 ASCII 码的映射，则可以将字符的 ASCII 码值作为索引，对应的元素存放在数组中的对应位置
  • 机器学习：神经网络中大量使用了向量，矩阵，张量之间的线性代数运算，这些数据都是以数组的形式构建的。数组是神经网络编程中最常使用的数据结构
  • 数据结构实现：数组可以用于实现栈，队列，哈希表，堆，图等数据结构。例如，图的邻接矩阵表示实际上是一个二维数组

链表

内存空间是所有程序的公共资源，在一个复杂的系统运行环境下，空闲的内存空间可能散落在内存各处。我们知道，存储数组的内存空间必须是连续的，而当数组非常大时，内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了

「链表 linked list」是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过"引用"相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。链表的设计使得各个节点可以被分散存储在内存各处，它们的内存地址是无须连续的。链表的组成单位是「节点 node」对象。每个节点都包含两项数据：节点的"值"和指向下一节点的"引用"

  • 链表的首个节点被称为"头节点"，最后一个节点被称为"尾节点"
  • 尾节点指向的是"空"，它在 Java，C++ 和 Python 中分别被记为 null，nullptr，None
  • 在 C，C++，Go 和 Rust 等支持指针的语言中，上述的"引用"应被替换为"指针"

如以下代码所示，链表节点 ListNode 除了包含值，还需额外保存一个引用（指针）。因此在相同数据量下，链表比数组占用更多的内存空间：

1
2
3
4
5
class ListNode {
    int val;        // 节点值
    ListNode next;  // 指向下一节点的引用
    ListNode(int x) { val = x; }  // 构造函数
}

链表常用操作

初始化链表

建立链表分为两步，第一步是初始化各个节点对象，第二步是构建引用指向关系。初始化完成后，我们就可以从链表的头节点出发，通过引用指向 next 依次访问所有节点

1
2
3
4
5
6
7
8
// 初始化链表 1 -> 3 -> 2
ListNode n0 = new ListNode(1);
ListNode n1 = new ListNode(3);
ListNode n2 = new ListNode(2);
// 构建引用指向
n0.next = n1;
n1.next = n2;
n2.next = n3;

数组整体是一个变量，比如数组 nums 包含元素 nums[0] 和 nums[1] 等，而链表是由多个独立的节点对象组成的。我们通常将头节点当作链表的代称，比如以上代码中的链表可被记做链表n0

插入节点

在链表中插入节点非常容易。假设我们想在相邻的两个节点 n0 和 n1 之间插入一个新节点 P ，则只需要改变两个节点引用（指针）即可，时间复杂度为 $O(1)$。相比之下，在数组中插入元素的时间复杂度为 $O(n)$，在大数据量下的效率较低

1
2
3
4
5
void insert(ListNode n0, ListNode P) {
    ListNode n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

删除节点

在链表中删除节点也非常方便，只需改变一个节点的引用（指针）即可。

注意：尽管在删除操作完成后节点 P 仍然指向 n1 ，但实际上遍历此链表已经无法访问到 P ，这意味着 P 已经不再属于该链表了

1
2
3
4
5
6
7
8
void remove(ListNode n0) {
    if (n0.next == null)
        return;
    // n0 -> P -> n1
    ListNode P = n0.next;
    ListNode n1 = P.next;
    n0.next = n1;
}

访问节点

在链表访问节点的效率较低。我们可以在 $O(1)$ 时间下访问数组中的任意元素。链表则不然，程序需要从头节点出发，逐个向后遍历，直至找到目标节点。也就是说，访问链表的第i个节点需要循环i - 1轮，时间复杂度为 $O(n)$

1
2
3
4
5
6
7
8
9
ListNode access(ListNode head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == null)
            return null;
        head = head.next;
    }
    return head;
}

查找节点

遍历链表，查找链表内值为 target 的节点，输出节点在链表中的索引。此过程也属于线性查找

1
2
3
4
5
6
7
8
9
10
int find(ListNode head, int target) {
    int index = 0;
    while (head != null) {
        if (head.val == target)
            return index;
        head = head.next;
        index++;
    }
    return -1;
}

数组 VS 链表

数组 链表
存储方式 连续内存空间 分散内存空间
缓存局部性 友好 不友好
容量扩展 长度不可变 可灵活扩展
内存效率 占用内存少，浪费部分空间 占用内存多
访问元素 $O(1)$ $O(n)$
添加元素 $O(n)$ $O(1)$
删除元素 $O(n)$ $O(1)$

常见链表类型

单向链表通常用于实现栈，队列，哈希表和图等数据结构

  • 单向链表：即上述介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空
  • 环形链表：如果我们令单向链表的尾节点指向头节点（即首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点
  • 双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间

链表典型应用

  • 栈与队列：当插入和删除操作都在链表的一端进行时，它表现出先进后出的的特性，对应栈；当插入操作在链表的一端进行，删除操作在链表的另一端进行，它表现出先进先出的特性，对应队列
  • 哈希表：链地址法是解决哈希冲突的主流方案之一，在该方案中，所有冲突的元素都会被放到一个链表中
  • 图：邻接表是表示图的一种常用方式，在其中，图的每个顶点都与一个链表相关联，链表中的每个元素都代表与该顶点相连的其他顶点

双向链表常被用于需要快速查找前一个和下一个元素的场景

  • 高级数据结构：比如在红黑树，B 树中，我们需要访问节点的父节点，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表
  • 浏览器历史：在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单
  • LRU 算法：在缓存淘汰算法（LRU）中，我们需要快速找到最近最少使用的数据，以及支持快速地添加和删除节点。这时候使用双向链表就非常合适

循环链表常被用于需要周期性操作的场景，比如操作系统的资源调度

  • 时间片轮转调度算法：在操作系统中，时间片轮转调度算法是一种常见的 CPU 调度算法，它需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环的操作就可以通过循环链表来实现
  • 数据缓冲区：在某些数据缓冲区的实现中，也可能会使用到循环链表。比如在音频、视频播放器中，数据流可能会被分成多个缓冲块并放入一个循环链表，以便实现无缝播放

列表

「列表 list」是一个抽象的数据结构概念，它表示元素的有序集合，支持元素访问、修改、添加、删除和遍历等操作，无需使用者考虑容量限制的问题。列表可以基于链表或数组实现

  • 链表天然可以被看作是一个列表，其支持元素增删查改操作，并且可以灵活动态扩容
  • 数组也支持元素增删查改，但由于其长度不可变，因此只能被看作是一个具有长度限制的列表

当使用数组实现列表时，长度不可变的性质会导致列表的实用性降低。这是因为我们通常无法事先确定需要存储多少数据，从而难以选择合适地列表长度。若长度过小，则很可能无法满足使用需求；若长度过大，则会造成内存空间的浪费

为解决此问题，我们可以使用「动态数组 dynamic array」来实现列表。它继承了数组的各项优点，并且可以在程序运行过程中进行动态扩容

实际上，许多编程语言中的标准库提供的列表都是基于动态数组实现的，例如 Python 中的 list，Java 中的 ArrayList ，C++ 中的 vector 和 C# 中的 List 等。在接下来的讨论中，我们将把"列表"和"动态数组"视为等同的概念

列表常用操作

初始化列表

我们通常使用"无初始值"和"有初始值"这两种初始化方法

1
2
3
4
5
// 无初始值
List<Integer> nums1 = new ArrayList<>();
// 有初始值（注意数组的元素类型需为 int[] 的包装类 Integer[]）
Integer[] numbers = new Integer[] { 1, 3, 2, 5, 4 };
List<Integer> nums = new ArrayList<>(Arrays.asList(numbers));

访问元素

列表本质上是数组，因此可以在 $O(1)$ 时间内访问和更新元素，效率很高

1
2
int num = nums.get(1);  // 访问索引 1 处的元素
nums.set(1, 0);  // 将索引 1 处的元素更新为 0

插入与删除元素

相较于数组，列表可以自由地添加与删除元素。在列表尾部添加元素的时间复杂度为 $O(1)$，但插入和删除元素的效率仍与数组相同，时间复杂度为 $O(n)$ 

1
2
3
4
nums.clear(); // 清空列表
nums.add(1); // 尾部添加元素
nums.add(3, 6);  // 在索引 3 处插入数字 6
nums.remove(3);  // 删除索引 3 处的元素

遍历列表

与数组一样，列表可以根据索引遍历，也可以直接遍历各元素

1
2
3
4
5
6
7
8
9
10
// 通过索引遍历列表
int count = 0;
for (int i = 0; i < nums.size(); i++) {
    count += nums.get(i);
}

// 直接遍历列表元素
for (int num : nums) {
    count += num;
}

拼接列表

给定一个新列表 nums1 ，我们可以将该列表拼接到原列表的尾部

1
2
List<Integer> nums1 = new ArrayList<>(Arrays.asList(new Integer[] { 6, 8, 7, 10, 9 }));
nums.addAll(nums1);  // 将列表 nums1 拼接到 nums 之后

排序列表

完成列表排序后，我们便可以使用在数组类算法题中经常考察的"二分查找"和"双指针"算法

1
Collections.sort(nums);  // 排序后，列表元素从小到大排列

列表实现

为了加深对列表工作原理的理解，我们尝试实现一个简易版列表，包括以下三个重点设计：

  • 初始容量：选取一个合理的数组初始容量。这里我们选择 10 作为初始容量
  • 数量记录：声明一个变量 size ，用于记录列表当前元素数量，并随着元素插入和删除实时更新。根据此变量，我们可以定位列表尾部，以及判断是否需要扩容
  • 扩容机制：若插入元素时列表容量已满，则需要进行扩容。首先根据扩容倍数创建一个更大的数组，再将当前数组的所有元素依次移动至新数组。这里我们规定每次将数组扩容至之前的 2 倍
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// 列表类简易实现
class MyList {
    private int[] arr; // 数组（存储列表元素）
    private int capacity = 10; // 列表容量
    private int size = 0; // 列表长度（即当前元素数量）
    private int extendRatio = 2; // 每次列表扩容的倍数

    // 构造方法
    public MyList() {
        arr = new int[capacity];
    }

    // 获取列表长度（即当前元素数量）
    public int size() {
        return size;
    }

    // 获取列表容量
    public int capacity() {
        return capacity;
    }

    // 访问元素
    public int get(int index) {
        // 索引如果越界则抛出异常，下同
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("索引越界");
        return arr[index];
    }

    // 更新元素
    public void set(int index, int num) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("索引越界");
        arr[index] = num;
    }

    // 尾部添加元素
    public void add(int num) {
        // 元素数量超出容量时，触发扩容机制
        if (size == capacity())
            extendCapacity();
        arr[size] = num;
        // 更新元素数量
        size++;
    }

    // 中间插入元素
    public void insert(int index, int num) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("索引越界");
        // 元素数量超出容量时，触发扩容机制
        if (size == capacity())
            extendCapacity();
        // 将索引 index 以及之后的元素都向后移动一位
        for (int j = size - 1; j >= index; j--) {
            arr[j + 1] = arr[j];
        }
        arr[index] = num;
        // 更新元素数量
        size++;
    }

    // 删除元素
    public int remove(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("索引越界");
        int num = arr[index];
        // 将索引 index 之后的元素都向前移动一位
        for (int j = index; j < size - 1; j++) {
            arr[j] = arr[j + 1];
        }
        // 更新元素数量
        size--;
        // 返回被删除元素
        return num;
    }

    // 列表扩容
    public void extendCapacity() {
        // 新建一个长度为原数组 extendRatio 倍的新数组，并将原数组拷贝到新数组
        arr = Arrays.copyOf(arr, capacity() * extendRatio);
        // 更新列表容量
        capacity = arr.length;
    }

    // 将列表转换为数组
    public int[] toArray() {
        int size = size();
        // 仅转换有效长度范围内的列表元素
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = get(i);
        }
        return arr;
    }
}

Q & A

数组存储在栈上和存储在堆上，对时间效率和空间效率是否有影响？

存储在栈上和堆上的数组都被存储在连续内存空间内，数据操作效率是基本一致的。然而，栈和堆具有各自的特点，从而导致以下不同点

  1. 分配和释放效率：栈是一块较小的内存，分配由编译器自动完成；而堆内存相对更大，可以在代码中动态分配，更容易碎片化。因此，堆上的分配和释放操作通常比栈上的慢
  2. 大小限制：栈内存相对较小，堆的大小一般受限于可用内存。因此堆更加适合存储大型数组
  3. 灵活性：栈上的数组的大小需要在编译时确定，而堆上的数组的大小可以在运行时动态确定

为什么数组要求相同类型的元素，而在链表中却没有强调同类型呢？

链表由节点组成，节点之间通过引用（指针）连接，各个节点可以存储不同类型的数据，例如 int，double，string，object 等

相对地，数组元素则必须是相同类型的，这样才能通过计算偏移量来获取对应元素位置。例如，数组同时包含 int 和 long 两种类型，单个元素分别占用 4 bytes 和 8 bytes ，此时就不能用以下公式计算偏移量了，因为数组中包含了两种长度的元素。

1
// 元素内存地址 = 数组内存地址 + 元素长度 * 元素索引

删除节点后，是否需要把 P.next 设为NULL呢？

不修改 P.next 也可以。从该链表的角度看，从头节点遍历到尾节点已经不会遇到 P 了。这意味着节点 P 已经从链表中删除了，此时节点 P 指向哪里都不会对该链表产生影响。

从垃圾回收的角度看，对于 Java、Python、Go 等拥有自动垃圾回收机制的语言来说，节点 P 是否被回收取决于是否仍存在指向它的引用，而不是 P.next 的值。在 C 和 C++ 等语言中，我们需要手动释放节点内存

在链表中插入和删除操作的时间复杂度是 $O(1)$。但是增删之前都需要 $O(n)$ 的时间查找元素，那为什么时间复杂度不是 $O(n)$ 呢？

如果是先查找元素、再删除元素，时间复杂度确实是 $O(n)$。然而，链表的 $O(1)$ 增删的优势可以在其他应用上得到体现。例如，双向队列适合使用链表实现，我们维护一个指针变量始终指向头节点、尾节点，每次插入与删除操作都是 $O(1)$

在列表末尾添加元素是否时时刻刻都为 $O(1)$？

如果添加元素时超出列表长度，则需要先扩容列表再添加。系统会申请一块新的内存，并将原列表的所有元素搬运过去，这时候时间复杂度就会是 $O(n)$

"列表的出现极大地提高了数组的实用性，但可能导致部分内存空间浪费"，这里的空间浪费是指额外增加的变量如容量，长度，扩容倍数所占的内存吗？

这里的空间浪费主要有两方面含义：一方面，列表都会设定一个初始长度，我们不一定需要用这么多；另一方面，为了防止频繁扩容，扩容一般会乘以一个系数，比如 × 1.5。这样一来，也会出现很多空位，我们通常不能完全填满它们

初始化列表 res = [0] * self.size() 操作，会导致 res 的每个元素引用相同的地址吗？

不会。但二维数组会有这个问题，例如初始化二维列表 res = [[0] * self.size()] ，则多次引用了同一个列表 [0] 。

在删除节点中，需要断开该节点与其后继节点之间的引用指向吗？

从数据结构与算法（做题）的角度看，不断开没有关系，只要保证程序的逻辑是正确的就行。从标准库的角度看，断开更加安全、逻辑更加清晰。如果不断开，假设被删除节点未被正常回收，那么它也会影响后继节点的内存回收

栈

栈如同叠猫猫，而队列就像猫猫排队。两者分别代表着先入后出和先入先出的逻辑关系

「栈 stack」是一种遵循先入后出的逻辑的线性数据结构。我们可以将栈类比为桌面上的一摞盘子，如果需要拿出底部的盘子，则需要先将上面的盘子依次取出。我们将盘子替换为各种类型的元素（如整数、字符、对象等），就得到了栈数据结构。我们把堆叠元素的顶部称为栈顶，底部称为栈底。将把元素添加到栈顶的操作叫做入栈，删除栈顶元素的操作叫做出栈

栈常用操作

栈的常用操作如下表所示，具体的方法名需要根据所使用的编程语言来确定。在此，我们以常见的 push()，pop()，peek() 命名为例

方法 描述 事件复杂度
push() 元素入栈（添加至栈顶） $O(1)$
pop() 栈顶元素出栈 $O(1)$
peek() 访问栈顶元素 $O(1)$

通常情况下，我们可以直接使用编程语言内置的栈类。然而，某些语言可能没有专门提供栈类，这时我们可以将该语言的数组或链表视作栈来使用，并在程序逻辑上忽略与栈无关的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 初始化栈
Stack<Integer> stack = new Stack<>();

// 元素入栈
stack.push(1);
stack.push(3);
stack.push(2);
stack.push(5);
stack.push(4);

// 访问栈顶元素
int peek = stack.peek();

// 元素出栈
int pop = stack.pop();

// 获取栈的长度
int size = stack.size();

// 判断是否为空
boolean isEmpty = stack.isEmpty();

栈的实现

栈遵循先入后出的原则，因此我们只能在栈顶添加或删除元素。然而，数组和链表都可以在任意位置添加和删除元素，因此栈可以被视为一种受限制的数组或链表。换句话说，我们可以"屏蔽"数组或链表的部分无关操作，使其对外表现的逻辑符合栈的特性

基于链表的实现

使用链表来实现栈时，我们可以将链表的头节点视为栈顶，尾节点视为栈底。对于入栈操作，我们只需将元素插入链表头部，这种节点插入方法被称为"头插法"。而对于出栈操作，只需将头节点从链表中删除即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// 基于链表实现的栈
class LinkedListStack {
    private ListNode stackPeek; // 将头节点作为栈顶
    private int stkSize = 0; // 栈的长度

    public LinkedListStack() {
        stackPeek = null;
    }

    // 获取栈的长度
    public int size() {
        return stkSize;
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return size() == 0;
    }

    // 入栈
    public void push(int num) {
        ListNode node = new ListNode(num);
        node.next = stackPeek;
        stackPeek = node;
        stkSize++;
    }

    // 出栈
    public int pop() {
        int num = peek();
        stackPeek = stackPeek.next;
        stkSize--;
        return num;
    }

    // 访问栈顶元素
    public int peek() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return stackPeek.val;
    }

    // 将 List 转化为 Array 并返回
    public int[] toArray() {
        ListNode node = stackPeek;
        int[] res = new int[size()];
        for (int i = res.length - 1; i >= 0; i--) {
            res[i] = node.val;
            node = node.next;
        }
        return res;
    }
}

基于数组的实现

使用数组实现栈时，我们可以将数组的尾部作为栈顶。入栈与出栈操作分别对应在数组尾部添加元素与删除元素，时间复杂度都为 $O(1)$。由于入栈的元素可能会源源不断地增加，因此我们可以使用动态数组，这样就无须自行处理数组扩容问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 基于数组实现的栈
class ArrayStack {
    private ArrayList<Integer> stack;

    public ArrayStack() {
        // 初始化列表（动态数组）
        stack = new ArrayList<>();
    }

    // 获取栈的长度
    public int size() {
        return stack.size();
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return size() == 0;
    }

    // 入栈
    public void push(int num) {
        stack.add(num);
    }

    // 出栈
    public int pop() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return stack.remove(size() - 1);
    }

    // 访问栈顶元素
    public int peek() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return stack.get(size() - 1);
    }

    // 将 List 转化为 Array 并返回
    public Object[] toArray() {
        return stack.toArray();
    }
}

两种实现对比

  • 支持操作

两种实现都支持栈定义中的各项操作。数组实现额外支持随机访问，但这已超出了栈的定义范畴，因此一般不会用到

  • 时间效率

在基于数组的实现中，入栈和出栈操作都是在预先分配好的连续内存中进行，具有很好的缓存本地性，因此效率较高。然而，如果入栈时超出数组容量，会触发扩容机制，导致该次入栈操作的时间复杂度变为 $O(n)$

在链表实现中，链表的扩容非常灵活，不存在上述数组扩容时效率降低的问题。但是，入栈操作需要初始化节点对象并修改指针，因此效率相对较低。不过，如果入栈元素本身就是节点对象，那么可以省去初始化步骤，从而提高效率

综上所述，当入栈与出栈操作的元素是基本数据类型时，例如 int 或 double ，我们可以得出以下结论：

  1. 基于数组实现的栈在触发扩容时效率会降低，但由于扩容是低频操作，因此平均效率更高
  2. 基于链表实现的栈可以提供更加稳定的效率表现
  • 空间效率

在初始化列表时，系统会为列表分配"初始容量"，该容量可能超过实际需求。并且，扩容机制通常是按照特定倍率（例如 2 倍）进行扩容，扩容后的容量也可能超出实际需求。因此，基于数组实现的栈可能造成一定的空间浪费。然而，由于链表节点需要额外存储指针，因此链表节点占用的空间相对较大。综上，我们不能简单地确定哪种实现更加节省内存，需要针对具体情况进行分析

栈典型应用

  1. 浏览器中的后退与前进，软件中的撤销与反撤销。每当我们打开新的网页，浏览器就会将上一个网页执行入栈，这样我们就可以通过后退操作回到上一页面。后退操作实际上是在执行出栈。如果要同时支持后退和前进，那么需要两个栈来配合实现
  2. 程序内存管理。每次调用函数时，系统都会在栈顶添加一个栈帧，用于记录函数的上下文信息。在递归函数中，向下递推阶段会不断执行入栈操作，而向上回溯阶段则会执行出栈操作

队列

「队列 queue」是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列的尾部，而位于队列头部的人逐个离开。我们将队列的头部称为队首，尾部称为队尾，将把元素加入队尾的操作称为入队，删除队首元素的操作称为出队

队列常用操作

队列的常见操作如下表所示。需要注意的是，不同编程语言的方法名称可能会有所不同。我们在此采用与栈相同的方法命名

方法名 描述 时间复杂度
push() 元素入队，即将元素添加至队尾 $O(1)$
pop() 队首元素出队 $O(1)$
peek() 访问队首元素 $O(1)$ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 初始化队列
Queue<Integer> queue = new LinkedList<>();

// 元素入队
queue.offer(1);
queue.offer(3);
queue.offer(2);
queue.offer(5);
queue.offer(4);

// 访问队首元素
int peek = queue.peek();

// 元素出队
int pop = queue.poll();

// 获取队列的长度
int size = queue.size();

// 判断队列是否为空
boolean isEmpty = queue.isEmpty();

队列实现

为了实现队列，我们需要一种数据结构，可以在一端添加元素，并在另一端删除元素。因此，链表和数组都可以用来实现队列

基于链表的实现

我们可以将链表的头节点和尾节点分别视为队首和队尾，规定队尾仅可添加节点，队首仅可删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 基于链表实现的队列
class LinkedListQueue {
    private ListNode front, rear; // 头节点 front ，尾节点 rear
    private int queSize = 0;

    public LinkedListQueue() {
        front = null;
        rear = null;
    }

    // 获取队列的长度
    public int size() {
        return queSize;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return size() == 0;
    }

    // 入队
    public void push(int num) {
        // 尾节点后添加 num
        ListNode node = new ListNode(num);
        // 如果队列为空，则令头、尾节点都指向该节点
        if (front == null) {
            front = node;
            rear = node;
        // 如果队列不为空，则将该节点添加到尾节点后
        } else {
            rear.next = node;
            rear = node;
        }
        queSize++;
    }

    // 出队
    public int pop() {
        int num = peek();
        // 删除头节点
        front = front.next;
        queSize--;
        return num;
    }

    // 访问队首元素
    public int peek() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return front.val;
    }

    // 将链表转化为 Array 并返回
    public int[] toArray() {
        ListNode node = front;
        int[] res = new int[size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = node.val;
            node = node.next;
        }
        return res;
    }
}

基于数组的实现

由于数组删除首元素的时间复杂度为 $O(n)$，这会导致出队操作效率较低。然而，我们可以采用以下巧妙方法来避免这个问题

们可以使用一个变量 front 指向队首元素的索引，并维护一个变量 size 用于记录队列长度。定义 rear = front + size ，这个公式计算出的 rear 指向队尾元素之后的下一个位置，基于此设计，数组中包含元素的有效区间为[front, rear - 1]。可以看到，入队和出队操作都只需进行一次操作，时间复杂度均为 $O(1)$

  • 入队操作：将输入元素赋值给 rear 索引处，并将 size 增加 1
  • 出队操作：只需将 front 增加 1 ，并将 size 减少 1

在不断进行入队和出队的过程中，front 和 rear 都在向右移动，当它们到达数组尾部时就无法继续移动了。为解决此问题，我们可以将数组视为首尾相接的"环形数组"。对于环形数组，我们需要让 front 或 rear 在越过数组尾部时，直接回到数组头部继续遍历。这种周期性规律可以通过"取余操作"来实现，代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// 基于环形数组实现的队列
class ArrayQueue {
    private int[] nums; // 用于存储队列元素的数组
    private int front; // 队首指针，指向队首元素
    private int queSize; // 队列长度

    public ArrayQueue(int capacity) {
        nums = new int[capacity];
        front = queSize = 0;
    }

    // 获取队列的容量
    public int capacity() {
        return nums.length;
    }

    // 获取队列的长度
    public int size() {
        return queSize;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return queSize == 0;
    }

    // 入队
    public void push(int num) {
        if (queSize == capacity()) {
            System.out.println("队列已满");
            return;
        }
        // 计算尾指针，指向队尾索引 + 1
        // 通过取余操作，实现 rear 越过数组尾部后回到头部
        int rear = (front + queSize) % capacity();
        // 将 num 添加至队尾
        nums[rear] = num;
        queSize++;
    }

    // 出队
    public int pop() {
        int num = peek();
        // 队首指针向后移动一位，若越过尾部则返回到数组头部
        front = (front + 1) % capacity();
        queSize--;
        return num;
    }

    // 访问队首元素
    public int peek() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return nums[front];
    }

    // 返回数组
    public int[] toArray() {
        // 仅转换有效长度范围内的列表元素
        int[] res = new int[queSize];
        for (int i = 0, j = front; i < queSize; i++, j++) {
            res[i] = nums[j % capacity()];
        }
        return res;
    }
}

以上实现的队列仍然具有局限性，即其长度不可变。然而，这个问题不难解决，我们可以将数组替换为动态数组，从而引入扩容机制

队列典型应用

  • 淘宝订单：购物者下单后，订单将加入队列中，系统随后会根据顺序依次处理队列中的订单。在双十一期间，短时间内会产生海量订单，高并发成为工程师们需要重点攻克的问题
  • 各类待办事项：任何需要实现"先来后到"功能的场景，例如打印机的任务队列、餐厅的出餐队列等。队列在这些场景中可以有效地维护处理顺序

双向队列

在队列中，我们仅能在头部删除或在尾部添加元素。「双向队列 double-ended queue」提供了更高的灵活性，允许在头部和尾部执行元素的添加或删除操作

双向队列常用操作

双向队列的常用操作如下表所示，具体的方法名称需要根据所使用的编程语言来确定

方法名 描述 时间复杂度
pushFirst() 将元素添加至队首 $O(1)$
pushLast() 将元素添加至队尾 $O(1)$
popFirst() 删除队首元素 $O(1)$
popLast() 删除队尾元素 $O(1)$
peekFirst() 访问队首元素 $O(1)$
peekLast() 访问队尾元素 $O(1)$

同样地，我们可以直接使用编程语言中已实现的双向队列类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 初始化双向队列
Deque<Integer> deque = new LinkedList<>();

// 元素入队
deque.offerLast(2);   // 添加至队尾
deque.offerLast(5);
deque.offerLast(4);
deque.offerFirst(3);  // 添加至队首
deque.offerFirst(1);

// 访问元素
int peekFirst = deque.peekFirst();  // 队首元素
int peekLast = deque.peekLast();    // 队尾元素

// 元素出队
int popFirst = deque.pollFirst();  // 队首元素出队
int popLast = deque.pollLast();    // 队尾元素出队

// 获取双向队列的长度
int size = deque.size();

// 判断双向队列是否为空
boolean isEmpty = deque.isEmpty();

双向队列实现

双向队列的实现与队列类似，可以选择链表或数组作为底层数据结构

  • 基于双向链表的实现

对于双向队列而言，头部和尾部都可以执行入队和出队操作。换句话说，双向队列需要实现另一个对称方向的操作。为此，我们采用"双向链表"作为双向队列的底层数据结构。我们将双向链表的头节点和尾节点视为双向队列的队首和队尾，同时实现在两端添加和删除节点的功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
// 双向链表节点
class ListNode {
    int val; // 节点值
    ListNode next; // 后继节点引用
    ListNode prev; // 前驱节点引用

    ListNode(int val) {
        this.val = val;
        prev = next = null;
    }
}

// 基于双向链表实现的双向队列
class LinkedListDeque {
    private ListNode front, rear; // 头节点 front ，尾节点 rear
    private int queSize = 0; // 双向队列的长度

    public LinkedListDeque() {
        front = rear = null;
    }

    // 获取双向队列的长度
    public int size() {
        return queSize;
    }

    // 判断双向队列是否为空
    public boolean isEmpty() {
        return size() == 0;
    }

    // 入队操作
    private void push(int num, boolean isFront) {
        ListNode node = new ListNode(num);
        // 若链表为空，则令 front, rear 都指向 node
        if (isEmpty())
            front = rear = node;
        // 队首入队操作
        else if (isFront) {
            // 将 node 添加至链表头部
            front.prev = node;
            node.next = front;
            front = node; // 更新头节点
        // 队尾入队操作
        } else {
            // 将 node 添加至链表尾部
            rear.next = node;
            node.prev = rear;
            rear = node; // 更新尾节点
        }
        queSize++; // 更新队列长度
    }

    // 队首入队
    public void pushFirst(int num) {
        push(num, true);
    }

    // 队尾入队
    public void pushLast(int num) {
        push(num, false);
    }

    // 出队操作
    private int pop(boolean isFront) {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        int val;
        // 队首出队操作
        if (isFront) {
            val = front.val; // 暂存头节点值
            // 删除头节点
            ListNode fNext = front.next;
            if (fNext != null) {
                fNext.prev = null;
                front.next = null;
            }
            front = fNext; // 更新头节点
        // 队尾出队操作
        } else {
            val = rear.val; // 暂存尾节点值
            // 删除尾节点
            ListNode rPrev = rear.prev;
            if (rPrev != null) {
                rPrev.next = null;
                rear.prev = null;
            }
            rear = rPrev; // 更新尾节点
        }
        queSize--; // 更新队列长度
        return val;
    }

    // 队首出队
    public int popFirst() {
        return pop(true);
    }

    // 队尾出队
    public int popLast() {
        return pop(false);
    }

    // 访问队首元素
    public int peekFirst() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return front.val;
    }

    // 访问队尾元素
    public int peekLast() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return rear.val;
    }

    // 返回数组用于打印
    public int[] toArray() {
        ListNode node = front;
        int[] res = new int[size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = node.val;
            node = node.next;
        }
        return res;
    }
}
  • 基于数组的实现

与基于数组实现队列类似，我们也可以使用环形数组来实现双向队列。在队列的实现基础上，仅需增加队首入队和队尾出队的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
// 基于环形数组实现的双向队列
class ArrayDeque {
    private int[] nums; // 用于存储双向队列元素的数组
    private int front; // 队首指针，指向队首元素
    private int queSize; // 双向队列长度

    // 构造方法
    public ArrayDeque(int capacity) {
        this.nums = new int[capacity];
        front = queSize = 0;
    }

    // 获取双向队列的容量
    public int capacity() {
        return nums.length;
    }

    // 获取双向队列的长度
    public int size() {
        return queSize;
    }

    // 判断双向队列是否为空
    public boolean isEmpty() {
        return queSize == 0;
    }

    // 计算环形数组索引
    private int index(int i) {
        // 通过取余操作实现数组首尾相连
        // 当 i 越过数组尾部后，回到头部
        // 当 i 越过数组头部后，回到尾部
        return (i + capacity()) % capacity();
    }

    // 队首入队
    public void pushFirst(int num) {
        if (queSize == capacity()) {
            System.out.println("双向队列已满");
            return;
        }
        // 队首指针向左移动一位
        // 通过取余操作，实现 front 越过数组头部后回到尾部
        front = index(front - 1);
        // 将 num 添加至队首
        nums[front] = num;
        queSize++;
    }

    // 队尾入队
    public void pushLast(int num) {
        if (queSize == capacity()) {
            System.out.println("双向队列已满");
            return;
        }
        // 计算尾指针，指向队尾索引 + 1
        int rear = index(front + queSize);
        // 将 num 添加至队尾
        nums[rear] = num;
        queSize++;
    }

    // 队首出队
    public int popFirst() {
        int num = peekFirst();
        // 队首指针向后移动一位
        front = index(front + 1);
        queSize--;
        return num;
    }

    // 队尾出队
    public int popLast() {
        int num = peekLast();
        queSize--;
        return num;
    }

    // 访问队首元素
    public int peekFirst() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return nums[front];
    }

    // 访问队尾元素
    public int peekLast() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        // 计算尾元素索引
        int last = index(front + queSize - 1);
        return nums[last];
    }

    // 返回数组用于打印
    public int[] toArray() {
        // 仅转换有效长度范围内的列表元素
        int[] res = new int[queSize];
        for (int i = 0, j = front; i < queSize; i++, j++) {
            res[i] = nums[index(j)];
        }
        return res;
    }
}

双向队列应用

双向队列兼具栈与队列的逻辑，因此它可以实现这两者的所有应用场景，同时提供更高的自由度。我们知道，软件的撤销功能通常使用栈来实现：系统将每次更改操作 push 到栈中，然后通过 pop 实现撤销。然而，考虑到系统资源的限制，软件通常会限制撤销的步数（例如仅允许保存50步）。当栈的长度超过50时，软件需要在栈底（即队首）执行删除操作。但栈无法实现该功能，此时就需要使用双向队列来替代栈。

撤销的核心逻辑仍然遵循栈的先入后出原则，只是双向队列能够更加灵活地实现一些额外逻辑

Q & A

浏览器的前进后退是否是双向链表实现？

浏览器的前进后退功能本质上是"栈"的体现。当用户访问一个新页面时，该页面会被添加到栈顶；当用户点击后退按钮时，该页面会从栈顶弹出。使用双向队列可以方便实现一些额外操作，这个在双向队列章节有提到

在出栈后，是否需要释放出栈节点的内存？

如果后续仍需要使用弹出节点，则不需要释放内存。若之后不需要用到，Java 和 Python 等语言拥有自动垃圾回收机制，因此不需要手动释放内存；在 C 和 C++ 中需要手动释放内存

双向队列像是两个栈拼接在了一起，它的用途是什么？

双向队列就像是栈和队列的组合，或者是两个栈拼在了一起。它表现的是栈 + 队列的逻辑，因此可以实现栈与队列的所有应用，并且更加灵活

撤销（undo）和反撤销（redo）具体是如何实现的？

使用两个堆栈，栈 A 用于撤销，栈 B 用于反撤销

  1. 每当用户执行一个操作，将这个操作压入栈 A ，并清空栈 B
  2. 当用户执行撤销时，从栈 A 中弹出最近的操作，并将其压入栈 B
  3. 当用户执行反撤销时，从栈 B 中弹出最近的操作，并将其压入栈 A

堆

堆就像是山川的峰峦，它们层叠起伏、形态各异。每一座山峰都有其高低之分，而最高的山峰总是最先映入眼帘

「堆 heap」是一种满足特定条件的完全二叉树，主要可分为两种类型：

  • 「大顶堆 max heap」：任意节点的值$\geq$其子节点的值
  • 「小顶堆 min heap」：任意节点的值$\leq$其子节点的值

堆作为完全二叉树的一个特例，具有以下特性：

  • 最底层节点靠左填充，其他层的节点都被填满
  • 我们将二叉树的根节点称为"堆顶"，将底层最靠右的节点称为"堆底"
  • 对于大顶堆（小顶堆），堆顶元素（即根节点）的值分别是最大（最小）的

堆常用操作

需要指出的是，许多编程语言提供的是「优先队列 priority queue」，这是一种抽象数据结构，定义为具有优先级排序的队列。实际上，堆通常用作实现优先队列，大顶堆相当于元素按从大到小顺序出队的优先队列。从使用角度来看，我们可以将优先队列和堆看作等价的数据结构

方法名 描述 时间复杂度
push() 元素入堆 $O(logn)$
pop() 堆顶元素出堆 $O(logn)$
peek() 访问堆顶元素（大/小顶堆分别为最大/小值） $O(1)$
size() 获取堆的元素数量 $O(1)$
isEmpty() 判断堆是否为空 $O(1)$ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 初始化小顶堆
Queue<Integer> minHeap = new PriorityQueue<>();
// 初始化大顶堆（使用 lambda 表达式修改 Comparator 即可）
Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

// 元素入堆
maxHeap.offer(1);
maxHeap.offer(3);
maxHeap.offer(2);
maxHeap.offer(5);
maxHeap.offer(4);

// 获取堆顶元素
int peek = maxHeap.peek(); // 5

// 堆顶元素出堆
// 出堆元素会形成一个从大到小的序列
peek = maxHeap.poll(); // 5
peek = maxHeap.poll(); // 4
peek = maxHeap.poll(); // 3
peek = maxHeap.poll(); // 2
peek = maxHeap.poll(); // 1

// 获取堆大小
int size = maxHeap.size();

// 判断堆是否为空
boolean isEmpty = maxHeap.isEmpty();

// 输入列表并建堆
minHeap = new PriorityQueue<>(Arrays.asList(1, 3, 2, 5, 4));

堆的实现

堆的存储与表示

由于堆正是一种完全二叉树，我们将采用数组来存储堆。当使用数组表示二叉树时，元素代表节点值，索引代表节点在二叉树中的位置。节点指针通过索引映射公式来实现。给定索引i，其左子节点索引为2i + 1，右子节点索引为2i + 2，父节点索引为(i - 1) / 2（向下取整）。当索引越界时，表示空节点或节点不存在。我们可以将索引映射公式封装成函数，方便后续使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 获取左子节点索引
int left(int i) {
    return 2 * i + 1;
}

// 获取右子节点索引
int right(int i) {
    return 2 * i + 2;
}

// 获取父节点索引
int parent(int i) {
    return (i - 1) / 2; // 向下整除
}

访问堆顶元素

堆顶元素即为二叉树的根节点，也就是列表的首个元素

1
2
3
4
// 访问堆顶元素
int peek() {
    return maxHeap.get(0);
}

元素入堆

给定元素 val ，我们首先将其添加到堆底。添加之后，由于 val 可能大于堆中其他元素，堆的成立条件可能已被破坏。因此，需要修复从插入节点到根节点的路径上的各个节点，这个操作被称为「堆化 heapify」。考虑从入堆节点开始，从底至顶执行堆化。我们比较插入节点与其父节点的值，如果插入节点更大，则将它们交换。然后继续执行此操作，从底至顶修复堆中的各个节点，直至越过根节点或遇到无须交换的节点时结束。设节点总数为n，则树的高度为$O(logn)$。由此可知，堆化操作的循环轮数最多为$O(logn)$，元素入堆操作的时间复杂度为$O(logn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 元素入堆
void push(int val) {
    // 添加节点
    maxHeap.add(val);
    // 从底至顶堆化
    siftUp(size() - 1);
}

// 从节点 i 开始，从底至顶堆化
void siftUp(int i) {
    while (true) {
        // 获取节点 i 的父节点
        int p = parent(i);
        // 当越过根节点或节点无须修复时，结束堆化
        if (p < 0 || maxHeap.get(i) <= maxHeap.get(p))
            break;
        // 交换两节点
        swap(i, p);
        // 循环向上堆化
        i = p;
    }
}

堆顶元素出堆

堆顶元素是二叉树的根节点，即列表首元素。如果我们直接从列表中删除首元素，那么二叉树中所有节点的索引都会发生变化，这将使得后续使用堆化修复变得困难。为了尽量减少元素索引的变动，我们采用以下操作步骤：

  • 交换堆顶元素与堆底元素（即交换根节点与最右叶节点）
  • 交换完成后，将堆底从列表中删除（注意，由于已经交换，实际上删除的是原来的堆顶元素）
  • 从根节点开始，从顶至底执行堆化

从顶至底堆化的操作方向与从底至顶堆化相反，我们将根节点的值与其两个子节点的值进行比较，将最大的子节点与根节点交换。然后循环执行此操作，直到越过叶节点或遇到无须交换的节点时结束。与元素入堆操作相似，堆顶元素出堆操作的时间复杂度也为$O(logn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 元素出堆
int pop() {
    // 判空处理
    if (isEmpty())
        throw new IndexOutOfBoundsException();
    // 交换根节点与最右叶节点（即交换首元素与尾元素）
    swap(0, size() - 1);
    // 删除节点
    int val = maxHeap.remove(size() - 1);
    // 从顶至底堆化
    siftDown(0);
    // 返回堆顶元素
    return val;
}

// 从节点 i 开始，从顶至底堆化
void siftDown(int i) {
    while (true) {
        // 判断节点 i, l, r 中值最大的节点，记为 ma
        int l = left(i), r = right(i), ma = i;
        if (l < size() && maxHeap.get(l) > maxHeap.get(ma))
            ma = l;
        if (r < size() && maxHeap.get(r) > maxHeap.get(ma))
            ma = r;
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if (ma == i)
            break;
        // 交换两节点
        swap(i, ma);
        // 循环向下堆化
        i = ma;
    }
}

堆常见应用

  • 优先队列：堆通常作为实现优先队列的首选数据结构，其入队和出队操作的时间复杂度均为$O(logn)$，而建队操作为 $O(n)$，这些操作都非常高效
  • 堆排序：给定一组数据，我们可以用它们建立一个堆，然后不断地执行元素出堆操作，从而得到有序数据。
  • 获取最大k个元素：这是一个经典的算法问题，同时也是一种典型应用，例如选择热度前 10 的新闻作为微博热搜，选取销量前 10 的商品等

建堆操作

在某些情况下，我们希望使用一个列表的所有元素来构建一个堆，这个过程被称为"建堆操作"

借助入堆操作实现

我们首先创建一个空堆，然后遍历列表，依次对每个元素执行"入堆操作"，即先将元素添加至堆的尾部，再对该元素执行"从底至顶"堆化。每当一个元素入堆，堆的长度就加一。由于节点是从顶到底依次被添加进二叉树的，因此堆是"自上而下"地构建的。设元素数量为，每个元素的入堆操作使用$O(logn)$时间，因此该建堆方法的时间复杂度为 $O(nlogn)$

通过遍历堆化实现

实际上，我们可以实现一种更为高效的建堆方法，共分为两步：

  • 将列表所有元素原封不动添加到堆中，此时堆的性质尚未得到满足
  • 倒序遍历堆（即层序遍历的倒序），依次对每个非叶节点执行"从顶至底堆化"

每当堆化一个节点后，以该节点为根节点的子树就形成一个合法的子堆。而由于是倒序遍历，因此堆是自下而上地被构建的。之所以选择倒序遍历，是因为这样能够保证当前节点之下的子树已经是合法的子堆，这样堆化当前节点才是有效的。值得说明的是，叶节点没有子节点，天然就是合法的子堆，因此无需堆化。如以下代码所示，最后一个非叶节点是最后一个节点的父节点，我们从它开始倒序遍历并执行堆化

1
2
3
4
5
6
7
8
9
// 构造方法，根据输入列表建堆
MaxHeap(List<Integer> nums) {
    // 将列表元素原封不动添加进堆
    maxHeap = new ArrayList<>(nums);
    // 堆化除叶节点以外的其他所有节点
    for (int i = parent(size() - 1); i >= 0; i--) {
        siftDown(i);
    }
}

复杂度分析

下面，我们来尝试推算第二种建堆方法的时间复杂度

  • 假设完全二叉树的节点数量为n，则叶节点数量为(n + 1) / 2，其中/为向下整除。因此需要堆化的节点数量为(n - 1) / 2
  • 在从顶至底堆化的过程中，每个节点最多堆化到叶节点，因此最大迭代次数为二叉树高度$logn$

将上述两者相乘，可得到建堆过程的时间复杂度为 $O(nlogn)$。但这个估算结果并不准确，因为我们没有考虑到二叉树底层节点数量远多于顶层节点的性质。接下来我们来进行更为准确的计算。为了减小计算难度，假设给定一个节点数量为n，高度为$h$的完美二叉树，该假设不会影响计算结果的正确性。节点从顶至底堆化的最大迭代次数等于该节点到叶节点的距离，而该距离正是节点高度。因此，我们可以将各层的节点数量×节点高度求和，从而得到所有节点的堆化迭代次数的总和：

化简上式需要借助中学的数列知识，先对 $T(h)$ 乘以2，得到：

使用错位相减法，用下式 $2T(h)$ 减去上式$T(h)$，可得：

观察上式，发现 $T(h)$ 是一个等比数列，可直接使用求和公式，得到时间复杂度为：

进一步地，高度为$h$的完美二叉树的节点数量为$n$ = $2^{h + 1}$ - 1，易得复杂度为$O(2^h)$ = $O(n)$。以上推算表明，输入列表并建堆的时间复杂度为 $O(n)$，非常高效

Top-K 问题

给定一个长度为n无序数组nums ，请返回数组中前k大的元素

对于该问题，我们先介绍两种思路比较直接的解法，再介绍效率更高的堆解法

方法一：遍历选择

我们可以进行k轮遍历，分别在每轮中提取第1, 2, ......，k大的元素，时间复杂度为$O(nk)$。此方法只适用于k $\leq$ n的情况，因为当k与n比较接近时，其时间复杂度趋向于 $O(n^2)$，非常耗时

当k == n时，我们可以得到完整的有序序列，此时等价于"选择排序"算法

方法二：排序

我们可以先对数组 nums 进行排序，再返回最右边的k个元素，时间复杂度为 $O(nlogn)$。显然，该方法超额完成任务了，因为我们只需要找出最大的k个元素即可，而不需要排序其他元素

方法三：堆

我们可以基于堆更加高效地解决 Top-K 问题：

  1. 始化一个小顶堆，其堆顶元素最小
  2. 先将数组的前k个元素依次入堆
  3. 从第k + 1个元素开始，若当前元素大于堆顶元素，则将堆顶元素出堆，并将当前元素入堆
  4. 遍历完成后，堆中保存的就是最大的k个元素

总共执行了n轮入堆和出堆，堆的最大长度为k，因此时间复杂度为 $O(nlogn)$。该方法的效率很高，当k较小时，时间复杂度趋向 $O(n)$；当k较大时，时间复杂度不会超过 $O(nlogn)$。另外，该方法适用于动态数据流的使用场景。在不断加入数据时，我们可以持续维护堆内的元素，从而实现最大k个元素的动态更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 基于堆查找数组中最大的 k 个元素
Queue<Integer> topKHeap(int[] nums, int k) {
    // 初始化小顶堆
    Queue<Integer> heap = new PriorityQueue<Integer>();
    // 将数组的前 k 个元素入堆
    for (int i = 0; i < k; i++) {
        heap.offer(nums[i]);
    }
    // 从第 k+1 个元素开始，保持堆的长度为 k
    for (int i = k; i < nums.length; i++) {
        // 若当前元素大于堆顶元素，则将堆顶元素出堆、当前元素入堆
        if (nums[i] > heap.peek()) {
            heap.poll();
            heap.offer(nums[i]);
        }
    }
    return heap;
}

Q & A

数据结构的"堆"与内存管理的"堆"是同一个概念吗？

两者不是同一个概念，只是碰巧都叫堆。计算机系统内存中的堆是动态内存分配的一部分，程序在运行时可以使用它来存储数据。程序可以请求一定量的堆内存，用于存储如对象和数组等复杂结构。当这些数据不再需要时，程序需要释放这些内存，以防止内存泄漏。相较于栈内存，堆内存的管理和使用需要更谨慎，使用不当可能会导致内存泄漏和野指针等问题

树

参天大树充满生命力，其根深叶茂，分枝扶疏。它为我们展现了数据分治的生动形态

「二叉树 binary tree」是一种非线性数据结构，代表着祖先与后代之间的派生关系，体现着一分为二的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含：值，左子节点引用，右子节点引用

1
2
3
4
5
6
7
/* 二叉树节点类 */
class TreeNode {
    int val;         // 节点值
    TreeNode left;   // 左子节点引用
    TreeNode right;  // 右子节点引用
    TreeNode(int x) { val = x; }
}

每个节点都有两个引用（指针），分别指向「左子节点 left-child node」和「右子节点 right-child node」，该节点被称为这两个子节点的「父节点 parent node」。当给定一个二叉树的节点时，我们将该节点的左子节点及其以下节点形成的树称为该节点的「左子树 left subtree」，同理可得「右子树 right subtree」。在二叉树中，除叶节点外，其他所有节点都包含子节点和非空子树

二叉树常见术语

  • 「根节点 root node」：位于二叉树顶层的节点，没有父节点
  • 「叶节点 leaf node」：没有子节点的节点，其两个指针均指向 None
  • 「边 edge」：连接两个节点的线段，即节点引用（指针）
  • 节点所在的「层 level」：从顶至底递增，根节点所在层为 1
  • 节点的「度 degree」：节点的子节点的数量。在二叉树中，度的取值范围是 0，1，2
  • 二叉树的「高度 height」：从根节点到最远叶节点所经过的边的数量
  • 节点的「深度 depth」：从根节点到该节点所经过的边的数量
  • 节点的「高度 height」：从距离该节点最远的叶节点到该节点所经过的边的数量

请注意，我们通常将高度和深度定义为走过边的数量，但有些题目或教材可能会将其定义为走过节点的数量。在这种情况下，高度和深度都需要加 1

二叉树基本操作

初始化二叉树

与链表类似，首先初始化节点，然后构建引用（指针）

1
2
3
4
5
6
7
8
9
10
11
// 初始化节点
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
// 构建引用指向（即指针）
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

插入与删除节点

与链表类似，在二叉树中插入与删除节点可以通过修改指针来实现

1
2
3
4
5
6
TreeNode P = new TreeNode(0);
// 在 n1 -> n2 中间插入节点 P
n1.left = P;
P.left = n2;
// 删除节点 P
n1.left = n2;

常见二叉树类型

完美二叉树

「完美二叉树 perfect binary tree」所有层的节点都被完全填满。在完美二叉树中，叶节点的度为0，其余所有节点的度都为2；若树高度为h，则节点总数为$2^{h + 1} - 1$，呈现标准的指数级关系，反映了自然界中常见的细胞分裂现象

请注意，在中文社区中，完美二叉树常被称为「满二叉树」

完全二叉树

「完全二叉树 complete binary tree」只有最底层的节点未被填满，且最底层节点尽量靠左填充

完满二叉树

「完满二叉树 full binary tree」除了叶节点之外，其余所有节点都有两个子节点（所有节点的度都为0或2）

平衡二叉树

「平衡二叉树 balanced binary tree」中任意节点的左子树和右子树的高度之差的绝对值不超过 1 （设节点的左子树高度 - 右子树高度 = d，则平衡二叉树中所有节点都满足| d | $\leq$ 1）

二叉树的退化

当二叉树的每层节点都被填满时，达到完美二叉树；而当所有节点都偏向一侧时，二叉树退化为链表

  • 完美二叉树是理想情况，可以充分发挥二叉树"分治"的优势
  • 链表则是另一个极端，各项操作都变为线性操作，时间复杂度退化至 $O(n)$

在最佳和最差结构下，二叉树的叶节点数量，节点总数，高度等达到极大或极小值

完美二叉树 链表
第 i 层节点数量 $2^{h - 1}$ 1
高度 h 树的叶节点数量 $2^h$ 1
高度 h 的节点总数 $2^{h + 1} - 1$ h + 1
节点总数 n 树的高度 $log_2^{n + 1} - 1$ n - 1

二叉树遍历

从物理结构的角度来看，树是一种基于链表的数据结构，因此其遍历方式是通过指针逐个访问节点。然而，树是一种非线性数据结构，这使得遍历树比遍历链表更加复杂，需要借助搜索算法来实现。二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等

层序遍历

「层序遍历 level-order traversal」从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。层序遍历本质上属于「广度优先遍历 breadth-first traversal」，它体现了一种一圈一圈向外扩展的逐层遍历方式

广度优先遍历通常借助队列来实现。队列遵循先进先出的规则，而广度优先遍历则遵循逐层推进的规则，两者背后的思想是一致的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 层序遍历
List<Integer> levelOrder(TreeNode root) {
    // 初始化队列，加入根节点
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    // 初始化一个列表，用于保存遍历序列
    List<Integer> list = new ArrayList<>();
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // 队列出队
        list.add(node.val);           // 保存节点值
        if (node.left != null)
            queue.offer(node.left);   // 左子节点入队
        if (node.right != null)
            queue.offer(node.right);  // 右子节点入队
    }
    return list;
}
  • 时间复杂度 $O(n)$：所有节点被访问一次，使用 $O(n)$ 时间，其中n为节点数量
  • 空间复杂度 $O(n)$：在最差情况下，即满二叉树时，遍历到最底层之前，队列中最多同时存在(n + 1) / 2个节点，占用 $O(n)$ 空间

前序，中序，后序遍历

相应地，前序、中序和后序遍历都属于「深度优先遍历 depth-first traversal」，它体现了一种先走到尽头，再回溯继续的遍历方式。深度优先遍历就像是绕着整个二叉树的外围走一圈，在每个节点都会遇到三个位置，分别对应前序遍历、中序遍历和后序遍历

  • 前序遍历：对于每一棵子树，先访问该节点，然后是左子树，最后是右子树
  • 中序遍历：对于每一棵子树，先访问左子树，然后是该节点，最后是右子树
  • 后序遍历：对于每一棵子树，先访问左子树，然后是右子树，最后是该节点

深度优先搜索通常基于递归实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 前序遍历
void preOrder(TreeNode root) {
    if (root == null)
        return;
    // 访问优先级：根节点 -> 左子树 -> 右子树
    list.add(root.val);
    preOrder(root.left);
    preOrder(root.right);
}

// 中序遍历
void inOrder(TreeNode root) {
    if (root == null)
        return;
    // 访问优先级：左子树 -> 根节点 -> 右子树
    inOrder(root.left);
    list.add(root.val);
    inOrder(root.right);
}

// 后序遍历
void postOrder(TreeNode root) {
    if (root == null)
        return;
    // 访问优先级：左子树 -> 右子树 -> 根节点
    postOrder(root.left);
    postOrder(root.right);
    list.add(root.val);
}
  • 时间复杂度 $O(n)$：所有节点被访问一次，使用 $O(n)$ 时间
  • 空间复杂度 $O(n)$：在最差情况下，即树退化为链表时，递归深度达到n，系统占用 $O(n)$ 栈帧空间

二叉树数组表示

表示完美二叉树

给定一个完美二叉树，我们将所有节点按照层序遍历的顺序存储在一个数组中，则每个节点都对应唯一的数组索引。根据层序遍历的特性，我们可以推导出父节点索引与子节点索引之间的"映射公式"：若节点的索引为i，则该节点的左子节点索引为2i + 1，右子节点索引为2i + 2。映射公式的角色相当于链表中的指针。给定数组中的任意一个节点，我们都可以通过映射公式来访问它的左（右）子节点

表示任意二叉树

完美二叉树是一个特例，在二叉树的中间层通常存在许多None。由于层序遍历序列并不包含这些None，因此我们无法仅凭该序列来推测None的数量和分布位置。这意味着存在多种二叉树结构都符合该层序遍历序列。为了解决此问题，我们可以考虑在层序遍历序列中显式地写出所有None。这样处理后，层序遍历序列就可以唯一表示二叉树了。

1
2
// 二叉树的数组表，使用 int 的包装类 Integer ，就可以使用 null 来标记空位
Integer[] tree = { 1, 2, 3, 4, null, 6, 7, 8, 9, null, null, 12, null, null, 15 };

值得说明的是，完全二叉树非常适合使用数组来表示。回顾完全二叉树的定义，只出现在最底层且靠右的位置，因此所有None一定出现在层序遍历序列的末尾。这意味着使用数组表示完全二叉树时，可以省略存储所有None，非常方便。以下代码实现了一个基于数组表示的二叉树，包括以下几种操作：

  • 给定某节点，获取它的值、左（右）子节点、父节点
  • 获取前序遍历、中序遍历、后序遍历、层序遍历序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// 数组表示下的二叉树类
class ArrayBinaryTree {
    private List<Integer> tree;

    // 构造方法
    public ArrayBinaryTree(List<Integer> arr) {
        tree = new ArrayList<>(arr);
    }

    // 节点数量
    public int size() {
        return tree.size();
    }

    // 获取索引为 i 节点的值
    public Integer val(int i) {
        // 若索引越界，则返回 null ，代表空位
        if (i < 0 || i >= size())
            return null;
        return tree.get(i);
    }

    // 获取索引为 i 节点的左子节点的索引
    public Integer left(int i) {
        return 2 * i + 1;
    }

    // 获取索引为 i 节点的右子节点的索引
    public Integer right(int i) {
        return 2 * i + 2;
    }

    // 获取索引为 i 节点的父节点的索引
    public Integer parent(int i) {
        return (i - 1) / 2;
    }

    // 层序遍历
    public List<Integer> levelOrder() {
        List<Integer> res = new ArrayList<>();
        // 直接遍历数组
        for (int i = 0; i < size(); i++) {
            if (val(i) != null)
                res.add(val(i));
        }
        return res;
    }

    // 深度优先遍历
    private void dfs(Integer i, String order, List<Integer> res) {
        // 若为空位，则返回
        if (val(i) == null)
            return;
        // 前序遍历
        if (order == "pre")
            res.add(val(i));
        dfs(left(i), order, res);
        // 中序遍历
        if (order == "in")
            res.add(val(i));
        dfs(right(i), order, res);
        // 后序遍历
        if (order == "post")
            res.add(val(i));
    }

    // 前序遍历
    public List<Integer> preOrder() {
        List<Integer> res = new ArrayList<>();
        dfs(0, "pre", res);
        return res;
    }

    // 中序遍历
    public List<Integer> inOrder() {
        List<Integer> res = new ArrayList<>();
        dfs(0, "in", res);
        return res;
    }

    // 后序遍历
    public List<Integer> postOrder() {
        List<Integer> res = new ArrayList<>();
        dfs(0, "post", res);
        return res;
    }
}

优势与局限性

二叉树的数组表示主要有以下优点：

  • 数组存储在连续的内存空间中，对缓存友好，访问与遍历速度较快
  • 不需要存储指针，比较节省空间
  • 允许随机访问节点

然而，数组表示也存在一些局限性：

  • 数组存储需要连续内存空间，因此不适合存储数据量过大的树
  • 增删节点需要通过数组插入与删除操作实现，效率较低
  • 当二叉树中存在大量None时，数组中包含的节点数据比重较低，空间利用率较低

二叉搜索树

「二叉搜索树 binary search tree」满足以下条件：

  1. 对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值
  2. 任意节点的左，右子树也是二叉搜索树，即同样满足条件 1.

二叉搜索树的操作

我们将二叉搜索树封装为一个类 BinarySearchTree ，并声明一个成员变量 root ，指向树的根节点

  • 查找节点

给定目标节点值 num ，可以根据二叉搜索树的性质来查找。我们声明一个节点 cur ，从二叉树的根节点 root 出发，循环比较节点值 cur.val 和 num 之间的大小关系

  • 若 cur.val < num ，说明目标节点在 cur 的右子树中，因此执行 cur = cur.right
  • 若 cur.val > num ，说明目标节点在 cur 的左子树中，因此执行 cur = cur.left
  • 若 cur.val = num ，说明找到目标节点，跳出循环并返回该节点

二叉搜索树的查找操作与二分查找算法的工作原理一致，都是每轮排除一半情况。循环次数最多为二叉树的高度，当二叉树平衡时，使用$O(logn)$时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 查找节点
TreeNode search(int num) {
    TreeNode cur = root;
    // 循环查找，越过叶节点后跳出
    while (cur != null) {
        // 目标节点在 cur 的右子树中
        if (cur.val < num)
            cur = cur.right;
        // 目标节点在 cur 的左子树中
        else if (cur.val > num)
            cur = cur.left;
        // 找到目标节点，跳出循环
        else
            break;
    }
    // 返回目标节点
    return cur;
}
  • 插入节点
  1. 查找插入位置：与查找操作相似，从根节点出发，根据当前节点值和 num 的大小关系循环向下搜索，直到越过叶节点（遍历至None）时跳出循环
  2. 在该位置插入节点：初始化节点 num ，将该节点置于None的位置

在代码实现中，需要注意以下两点：

  • 二叉搜索树不允许存在重复节点，否则将违反其定义。因此，若待插入节点在树中已存在，则不执行插入，直接返回
  • 为了实现插入节点，我们需要借助节点 pre 保存上一轮循环的节点。这样在遍历至None时，我们可以获取到其父节点，从而完成节点插入操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 插入节点
void insert(int num) {
    // 若树为空，则初始化根节点
    if (root == null) {
        root = new TreeNode(num);
        return;
    }
    TreeNode cur = root, pre = null;
    // 循环查找，越过叶节点后跳出
    while (cur != null) {
        // 找到重复节点，直接返回
        if (cur.val == num)
            return;
        pre = cur;
        // 插入位置在 cur 的右子树中
        if (cur.val < num)
            cur = cur.right;
        // 插入位置在 cur 的左子树中
        else
            cur = cur.left;
    }
    // 插入节点
    TreeNode node = new TreeNode(num);
    if (pre.val < num)
        pre.right = node;
    else
        pre.left = node;
}

与查找节点相同，插入节点使用$O(logn)$时间

  • 删除节点

先在二叉树中查找到目标节点，再将其从二叉树中删除。与插入节点类似，我们需要保证在删除操作完成后，二叉搜索树的左子树 < 根节点 < 右子树的性质仍然满足。因此，我们需要根据目标节点的子节点数量，共分为 0，1 和 2 这三种情况，执行对应的删除节点操作。当待删除节点的度为0时，表示该节点是叶节点，可以直接删除。当待删除节点的度为1时，将待删除节点替换为其子节点即可。当待删除节点的度为2时，我们无法直接删除它，而需要使用一个节点替换该节点。由于要保持二叉搜索树左<根<右的性质，因此这个节点可以是右子树的最小节点或左子树的最大节点。假设我们选择右子树的最小节点（即中序遍历的下一个节点），则删除操作流程：

  1. 找到待删除节点在中序遍历序列中的下一个节点，记为 tmp
  2. 将 tmp 的值覆盖待删除节点的值，并在树中递归删除节点 tmp

删除节点操作同样使用$O(logn)$时间，其中查找待删除节点需要$O(logn)$时间，获取中序遍历后继节点需要$O(logn)$时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 删除节点
void remove(int num) {
    // 若树为空，直接提前返回
    if (root == null)
        return;
    TreeNode cur = root, pre = null;
    // 循环查找，越过叶节点后跳出
    while (cur != null) {
        // 找到待删除节点，跳出循环
        if (cur.val == num)
            break;
        pre = cur;
        // 待删除节点在 cur 的右子树中
        if (cur.val < num)
            cur = cur.right;
        // 待删除节点在 cur 的左子树中
        else
            cur = cur.left;
    }
    // 若无待删除节点，则直接返回
    if (cur == null)
        return;
    // 子节点数量 = 0 or 1
    if (cur.left == null || cur.right == null) {
        // 当子节点数量 = 0 / 1 时， child = null / 该子节点
        TreeNode child = cur.left != null ? cur.left : cur.right;
        // 删除节点 cur
        if (cur != root) {
            if (pre.left == cur)
                pre.left = child;
            else
                pre.right = child;
        } else {
            // 若删除节点为根节点，则重新指定根节点
            root = child;
        }
    }
    // 子节点数量 = 2
    else {
        // 获取中序遍历中 cur 的下一个节点
        TreeNode tmp = cur.right;
        while (tmp.left != null) {
            tmp = tmp.left;
        }
        // 递归删除节点 tmp
        remove(tmp.val);
        // 用 tmp 覆盖 cur
        cur.val = tmp.val;
    }
}
  • 中序遍历有序

二叉树的中序遍历遵循左 -> 根 -> 右的遍历顺序，而二叉搜索树满足左子节点 < 根节点 < 右子节点的大小关系。这意味着在二叉搜索树中进行中序遍历时，总是会优先遍历下一个最小节点，从而得出一个重要性质：二叉搜索树的中序遍历序列是升序的。利用中序遍历升序的性质，我们在二叉搜索树中获取有序数据仅需 $O(n)$ 时间，无须进行额外的排序操作，非常高效

二叉搜索树的效率

给定一组数据，我们考虑使用数组或二叉搜索树存储。二叉搜索树的各项操作的时间复杂度都是对数阶，具有稳定且高效的性能表现。只有在高频添加、低频查找删除的数据适用场景下，数组比二叉搜索树的效率更高

无序数组 二叉搜索树
查找元素 $O(n)$ $O(logn)$
插入元素 $O(1)$ $O(logn)$
删除元素 $O(n)$ $O(logn)$

在理想情况下，二叉搜索树是平衡的，这样就可以在$logn$轮循环内查找任意节点。然而，如果我们在二叉搜索树中不断地插入和删除节点，可能导致二叉树退化为链表，这时各种操作的时间复杂度也会退化为 $O(n)$

二叉搜索树常见应用

  • 用作系统中的多级索引，实现高效的查找，插入，删除操作
  • 作为某些搜索算法的底层数据结构
  • 用于存储数据流，以保持其有序状态

AVL 树

在二叉搜索树章节中，我们提到了在多次插入和删除操作后，二叉搜索树可能退化为链表。这种情况下，所有操作的时间复杂度将从$O(logn)$恶化为$O(logn)$。G. M. Adelson-Velsky 和 E. M. Landis 在其 1962 年发表的论文 An algorithm for the organization of information 中提出了「AVL 树」。论文中详细描述了一系列操作，确保在持续添加和删除节点后，AVL 树不会退化，从而使得各种操作的时间复杂度保持在$O(logn)$级别。换句话说，在需要频繁进行增删查改操作的场景中，AVL 树能始终保持高效的数据操作性能，具有很好的应用价值。

AVL 树常见术语

AVL 树既是二叉搜索树也是平衡二叉树，同时满足这两类二叉树的所有性质，因此也被称为「平衡二叉搜索树 balanced binary search tree」

  • 节点高度

由于 AVL 树的相关操作需要获取节点高度，因此我们需要为节点类添加 height 变量

1
2
3
4
5
6
7
8
// AVL 树节点类
class TreeNode {
    public int val;        // 节点值
    public int height;     // 节点高度
    public TreeNode left;  // 左子节点
    public TreeNode right; // 右子节点
    public TreeNode(int x) { val = x; }
}

"节点高度"是指从该节点到其最远叶节点的距离，即所经过的"边"的数量。需要特别注意的是，叶节点的高度为 0 ，而空节点的高度为 -1 。我们将创建两个工具函数，分别用于获取和更新节点的高度

1
2
3
4
5
6
7
8
9
10
11
// 获取节点高度
int height(TreeNode node) {
    // 空节点高度为 -1 ，叶节点高度为 0
    return node == null ? -1 : node.height;
}

// 更新节点高度
void updateHeight(TreeNode node) {
    // 节点高度等于最高子树高度 + 1
    node.height = Math.max(height(node.left), height(node.right)) + 1;
}
  • 节点平衡因子

节点的「平衡因子 balance factor」定义为节点左子树的高度减去右子树的高度，同时规定空节点的平衡因子为 0 。我们同样将获取节点平衡因子的功能封装成函数，方便后续使用

1
2
3
4
5
6
7
8
// 获取平衡因子
int balanceFactor(TreeNode node) {
    // 空节点平衡因子为 0
    if (node == null)
        return 0;
    // 节点平衡因子 = 左子树高度 - 右子树高度
    return height(node.left) - height(node.right);
}

设平衡因子为f，则一棵 AVL 树的任意节点的平衡因子皆满足 -1 $\leq$ f $\leq$ -1

AVL 树旋转

AVL 树的特点在于旋转操作，它能够在不影响二叉树的中序遍历序列的前提下，使失衡节点重新恢复平衡。换句话说，旋转操作既能保持二叉搜索树的性质，也能使树重新变为平衡二叉树。我们将平衡因子绝对值 > 1 的节点称为失衡节点。根据节点失衡情况的不同，旋转操作分为四种：右旋，左旋，先右旋后左旋，先左旋后右旋

  • 右旋
1
2
3
4
5
6
7
8
9
10
11
12
13
// 右旋操作
TreeNode rightRotate(TreeNode node) {
    TreeNode child = node.left;
    TreeNode grandChild = child.right;
    // 以 child 为原点，将 node 向右旋转
    child.right = node;
    node.left = grandChild;
    // 更新节点高度
    updateHeight(node);
    updateHeight(child);
    // 返回旋转后子树的根节点
    return child;
}
  • 左旋

右旋和左旋操作在逻辑上是镜像对称的，它们分别解决的两种失衡情况也是对称的。基于对称性，我们只需将右旋地实现代码中的所有的 left 替换为 right ，将所有的 right 替换为 left ，即可得到左旋地实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
// 左旋操作
TreeNode leftRotate(TreeNode node) {
    TreeNode child = node.right;
    TreeNode grandChild = child.left;
    // 以 child 为原点，将 node 向左旋转
    child.left = node;
    node.right = grandChild;
    // 更新节点高度
    updateHeight(node);
    updateHeight(child);
    // 返回旋转后子树的根节点
    return child;
}
  • 旋转的选择

我们通过判断失衡节点的平衡因子以及较高一侧子节点的平衡因子的正负号，来确定失衡节点属于哪种情况

失衡节点的平衡因子 子节点的平衡因子 应采用的旋转方法
> 1（即左偏树） $\leq$ 0 右旋
> 1（即左偏树） < 0 先左旋后右旋
< -1（即右偏树） $\geq$ 0 左旋
< -1（即右偏树） > 0 先右旋后左旋

为了便于使用，我们将旋转操作封装成一个函数。有了这个函数，我们就能对各种失衡情况进行旋转，使失衡节点重新恢复平衡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 执行旋转操作，使该子树重新恢复平衡
TreeNode rotate(TreeNode node) {
    // 获取节点 node 的平衡因子
    int balanceFactor = balanceFactor(node);
    // 左偏树
    if (balanceFactor > 1) {
        if (balanceFactor(node.left) >= 0) {
            // 右旋
            return rightRotate(node);
        } else {
            // 先左旋后右旋
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
    }
    // 右偏树
    if (balanceFactor < -1) {
        if (balanceFactor(node.right) <= 0) {
            // 左旋
            return leftRotate(node);
        } else {
            // 先右旋后左旋
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
    }
    // 平衡树，无须旋转，直接返回
    return node;
}

AVL 树常用操作

  • 插入节点

AVL 树的节点插入操作与二叉搜索树在主体上类似。唯一的区别在于，在 AVL 树中插入节点后，从该节点到根节点的路径上可能会出现一系列失衡节点。因此，我们需要从这个节点开始，自底向上执行旋转操作，使所有失衡节点恢复平衡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 插入节点
void insert(int val) {
    root = insertHelper(root, val);
}

// 递归插入节点（辅助方法）
TreeNode insertHelper(TreeNode node, int val) {
    if (node == null)
        return new TreeNode(val);
    // 1. 查找插入位置，并插入节点
    if (val < node.val)
        node.left = insertHelper(node.left, val);
    else if (val > node.val)
        node.right = insertHelper(node.right, val);
    else
        return node; // 重复节点不插入，直接返回
    updateHeight(node); // 更新节点高度
    // 2. 执行旋转操作，使该子树重新恢复平衡
    node = rotate(node);
    // 返回子树的根节点
    return node;
}
  • 删除节点

类似地，在二叉搜索树的删除节点方法的基础上，需要从底至顶地执行旋转操作，使所有失衡节点恢复平衡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 删除节点
void remove(int val) {
    root = removeHelper(root, val);
}

// 递归删除节点（辅助方法）
TreeNode removeHelper(TreeNode node, int val) {
    if (node == null)
        return null;
    // 1. 查找节点，并删除之
    if (val < node.val)
        node.left = removeHelper(node.left, val);
    else if (val > node.val)
        node.right = removeHelper(node.right, val);
    else {
        if (node.left == null || node.right == null) {
            TreeNode child = node.left != null ? node.left : node.right;
            // 子节点数量 = 0 ，直接删除 node 并返回
            if (child == null)
                return null;
            // 子节点数量 = 1 ，直接删除 node
            else
                node = child;
        } else {
            // 子节点数量 = 2 ，则将中序遍历的下个节点删除，并用该节点替换当前节点
            TreeNode temp = node.right;
            while (temp.left != null) {
                temp = temp.left;
            }
            node.right = removeHelper(node.right, temp.val);
            node.val = temp.val;
        }
    }
    updateHeight(node); // 更新节点高度
    // 2. 执行旋转操作，使该子树重新恢复平衡
    node = rotate(node);
    // 返回子树的根节点
    return node;
}

AVL 树典型应用

  • 组织和存储大型数据，适用于高频查找、低频增删的场景
  • 用于构建数据库中的索引系统
  • 红黑树在许多应用中比 AVL 树更受欢迎。这是因为红黑树的平衡条件相对宽松，在红黑树中插入与删除节点所需的旋转操作相对较少，其节点增删操作的平均效率更高

红黑树

红黑树也是一种自平衡的二叉搜索树，较之AVL，插入和删除时旋转次数更少。红黑树的特性：

  • 所有节点都有两种颜色：红与黑
  • 所有NULL视为黑色
  • 红色节点不能相邻
  • 根节点是黑色
  • 从根节点到任意一个叶子节点，路径中的黑色节点数一样（黑色完美平衡）

B树

树和平衡二叉树的不同之处是：B树属于多叉树又名平衡多路查找树（查找路径不止两个），数据库索引技术里大量使用着B树和B+树的数据结构

注意: 有文章把B树和B-tree理解成了两种不同类别的树，其实这两个是同一种树

构建规则

  1. 排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则
  2. 子节点数：非叶节点（根节点和枝节点）的子节点数 > 1，且子节点数量 <= M，且 M >= 2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M = M路,当M = 2则是2叉树,M = 3则是3叉）
  3. 关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M - 1个（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2)
  4. 所有叶子节点均在同一层，叶子节点除了包含了关键字和关键字记录的指针外，也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子

查询流程

  1. 获取根节点的关键字进行比较，当前根节点关键字为M，E < M（26个字母顺序），所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点，右边放大于当前节点值的子节点）
  2. 拿到关键字D和G，D < E < G 所以直接找到D和G中间的节点
  3. 拿到E和F，因为E = E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回NULL）

插入节点

定义一个5阶树（平衡5路查找树），现在我们要把3，8，31，11，23，29，50，28，53 这些数字构建出一个5阶树出来。

  • 节点拆分规则：当前是要组成一个5路查找树，那么此时m = 5，关键字数必须 <= 5 - 1（这里关键字数 > 4就要进行节点拆分）
  • 排序规则：满足节点本身比左边节点大，比右边节点小的排序规则
    1. 首先插入 3，8，31，11
    2. 然后插入23，29
    3. 最后插入50，28，53

删除节点

  1. 节点合并规则：当前是要组成一个5路查找树，那么此时m = 5，关键字数必须大于等于 ceil(m/2)-1（所以这里关键字数 < 2就要进行节点合并）
  2. 满足节点本身比左边节点大，比右边节点小的排序规则
  3. 关键字数小于二时先从子节点取，子节点没有符合条件时就向父节点取，取中间值往父节点放

总结

B树相对平衡二叉树在节点空间的利用率上进行改进，B树在每个节点保存更多的数据，减少了树的高度，从而提升了查找的性能，在数据库应用中，B树的每个节点存储的数据量大约为4K, 这是因为考虑到磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次对磁盘进行IO数据读取时，同一个磁盘块的数据会被一次性读取出来，所以每一次磁盘IO都可以读取到B树中一个节点的全部数据

Q & A

对于只有一个节点的二叉树，树的高度和根节点的深度都是0吗？

是的，因为高度和深度通常定义为"经过的边的数量"

二叉树中的插入与删除一般由一套操作配合完成，这里的"一套操作"指什么呢？可以理解为资源的子节点的资源释放吗？

拿二叉搜索树来举例，删除节点操作要分三种情况处理，其中每种情况都需要进行多个步骤的节点操作

为什么 DFS 遍历二叉树有前，中，后三种顺序，分别有什么用呢？

与顺序和逆序遍历数组类似，前序,中序，后序遍历是三种二叉树遍历方法，我们可以使用它们得到一个特定顺序的遍历结果。例如在二叉搜索树中，由于节点大小满足 左子节点值 < 根节点值 < 右子节点值 ，因此我们只要按照 左 < 根 < 右 的优先级遍历树，就可以获得有序的节点序列

右旋操作是处理失衡节点 node，child，grand_child 之间的关系，那 node 的父节点和 node 原来的连接不需要维护吗？右旋操作后岂不是断掉了？

我们需要从递归的视角来看这个问题。右旋操作 right_rotate(root) 传入的是子树的根节点，最终 return child 返回旋转之后的子树的根节点。子树的根节点和其父节点的连接是在该函数返回后完成的，不属于右旋操作的维护范围

如何从一组输入数据构建一棵二叉搜索树？根节点的选择是不是很重要？

是的，构建树的方法已在二叉搜索树代码中的 build_tree() 方法中给出。至于根节点的选择，我们通常会将输入数据排序，然后将中点元素作为根节点，再递归地构建左右子树。这样做可以最大程度保证树的平衡性

在 Java 中，字符串对比是否一定要用 equals() 方法？

在 Java 中，对于基本数据类型，== 用于对比两个变量的值是否相等。对于引用类型，两种符号的工作原理是不同的

  1. == ：用来比较两个变量是否指向同一个对象，即它们在内存中的位置是否相同
  2. equals()：用来对比两个对象的值是否相等

因此，如果要对比值，我们应该使用 equals() 。然而，通过 String a = "hi"; String b = "hi"; 初始化的字符串都存储在字符串常量池中，它们指向同一个对象，因此也可以用 a == b 来比较两个字符串的内容

广度优先遍历到最底层之前，队列中的节点数量是$2^h$吗？

是的，例如高度 h = 2 的满二叉树，其节点总数 n = 7，则底层节点数量 4 = (n + 1) / 2

哈希表

「哈希表 hash table」，又称「散列表」，其通过建立键 key 与值 value 之间的映射，实现高效的元素查询。具体而言，我们向哈希表输入一个键 key ，则可以在 $O(1)$ 时间内获取对应的值 value 。除哈希表外，数组和链表也可以实现查询功能，它们的效率对比如下表所示：

  • 添加元素：仅需将元素添加至数组（链表）的尾部即可，使用 $O(1)$ 时间
  • 查询元素：由于数组（链表）是乱序的，因此需要遍历其中的所有元素，使用 $O(n)$ 时间
  • 删除元素：需要先查询到元素，再从数组（链表）中删除，使用 $O(n)$ 时间
数组 链表 哈希表
查找元素 $O(n)$ $O(n)$ $O(1)$
添加元素 $O(1)$ $O(1)$ $O(1)$
删除元素 $O(n)$ $O(n)$ $O(1)$

哈希表常用操作

哈希表的常见操作包括：初始化，查询操作，添加键值对和删除键值对等，示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 初始化哈希表
Map<Integer, String> map = new HashMap<>();

// 添加操作
map.put(12836, "小哈");   
map.put(15937, "小啰");   
map.put(16750, "小算");   
map.put(13276, "小法");
map.put(10583, "小鸭");

// 查询操作
String name = map.get(15937);

// 删除操作
map.remove(10583);

哈希表有三种常用的遍历方式：遍历键值对，遍历键和遍历值。示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
// 遍历键值对 key->value
for (Map.Entry <Integer, String> kv: map.entrySet()) {
    System.out.println(kv.getKey() + " -> " + kv.getValue());
}
// 单独遍历键 key
for (int key: map.keySet()) {
    System.out.println(key);
}
// 单独遍历值 value
for (String val: map.values()) {
    System.out.println(val);
}

哈希表简单实现

我们先考虑最简单的情况，仅用一个数组来实现哈希表。在哈希表中，我们将数组中的每个空位称为「桶 bucket」，每个桶可存储一个键值对。因此，查询操作就是找到 key 对应的桶，并在桶中获取 value 。

那么，如何基于 key 定位对应的桶呢？这是通过「哈希函数 hash function」实现的。哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间。在哈希表中，输入空间是所有 key ，输出空间是所有桶（数组索引）。换句话说，输入一个 key ，我们可以通过哈希函数得到该 key 对应的键值对在数组中的存储位置。输入一个 key ，哈希函数的计算过程分为以下两步：

  1. 通过某种哈希算法 hash() 计算得到哈希值。
  2. 将哈希值对桶数量（数组长度）capacity 取模，从而获取该 key 对应的数组索引 index = hash(key) % capacity
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
// 键值对
class Pair {
    public int key;
    public String val;

    public Pair(int key, String val) {
        this.key = key;
        this.val = val;
    }
}

// 基于数组实现的哈希表
class ArrayHashMap {
    private List<Pair> buckets;

    public ArrayHashMap() {
        // 初始化数组，包含 100 个桶
        buckets = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            buckets.add(null);
        }
    }

    // 哈希函数
    private int hashFunc(int key) {
        int index = key % 100;
        return index;
    }

    // 查询操作
    public String get(int key) {
        int index = hashFunc(key);
        Pair pair = buckets.get(index);
        if (pair == null)
            return null;
        return pair.val;
    }

    // 添加操作
    public void put(int key, String val) {
        Pair pair = new Pair(key, val);
        int index = hashFunc(key);
        buckets.set(index, pair);
    }

    // 删除操作
    public void remove(int key) {
        int index = hashFunc(key);
        // 置为 null ，代表删除
        buckets.set(index, null);
    }

    // 获取所有键值对
    public List<Pair> pairSet() {
        List<Pair> pairSet = new ArrayList<>();
        for (Pair pair : buckets) {
            if (pair != null)
                pairSet.add(pair);
        }
        return pairSet;
    }

    // 获取所有键
    public List<Integer> keySet() {
        List<Integer> keySet = new ArrayList<>();
        for (Pair pair : buckets) {
            if (pair != null)
                keySet.add(pair.key);
        }
        return keySet;
    }

    // 获取所有值
    public List<String> valueSet() {
        List<String> valueSet = new ArrayList<>();
        for (Pair pair : buckets) {
            if (pair != null)
                valueSet.add(pair.val);
        }
        return valueSet;
    }

    // 打印哈希表
    public void print() {
        for (Pair kv : pairSet()) {
            System.out.println(kv.key + " -> " + kv.val);
        }
    }
}

哈希冲突与扩容

从本质上看，哈希函数的作用是将所有 key 构成的输入空间映射到数组所有索引构成的输出空间，而输入空间往往远大于输出空间。因此，理论上一定存在多个输入对应相同输出的情况。对于上述示例中的哈希函数，当输入的 key 后两位相同时，哈希函数的输出结果也相同。例如，查询学号为 12836 和 20336 的两个学生时，我们得到：

1
2
12836 % 100 = 36
20336 % 100 = 36

两个学号指向了同一个姓名，这显然是不对的。我们将这种多个输入对应同一输出的情况称为「哈希冲突 hash collision」。容易想到，哈希表容量n越大，多个 key 被分配到同一个桶中的概率就越低，冲突就越少。因此，我们可以通过扩容哈希表来减少哈希冲突

类似于数组扩容，哈希表扩容需将所有键值对从原哈希表迁移至新哈希表，非常耗时；并且由于哈希表容量 capacity 改变，我们需要通过哈希函数来重新计算所有键值对的存储位置，这进一步提高了扩容过程的计算开销。为此，编程语言通常会预留足够大的哈希表容量，防止频繁扩容

「负载因子 load factor」是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希冲突的严重程度，也常作为哈希表扩容的触发条件。在 Java 中，当负载因子超过0.75时，系统会将哈希表扩容至原先的2倍

哈希冲突会导致查询结果错误，严重影响哈希表的可用性。为解决该问题，我们可以每当遇到哈希冲突就进行哈希表扩容，直至冲突消失为止。此方法简单粗暴且有效，但效率太低，因为哈希表扩容需要进行大量的数据搬运与哈希值计算。为了提升效率，我们可以采用以下策略:

  • 改良哈希表数据结构，使得哈希表可以在出现哈希冲突时正常工作
  • 仅在必要时，即当哈希冲突比较严重时，才执行扩容操作

哈希表的结构改良方法主要包括链式地址和开放寻址

链式地址

在原始哈希表中，每个桶仅能存储一个键值对。「链式地址 separate chaining」将单个元素转换为链表，将键值对作为链表节点，将所有发生冲突的键值对都存储在同一链表中。基于链式地址实现的哈希表的操作方法发生了以下变化：

  • 查询元素：输入 key ，经过哈希函数得到桶索引，即可访问链表头节点，然后遍历链表并对比 key 以查找目标键值对
  • 添加元素：首先通过哈希函数访问链表头节点，然后将节点（键值对）添加到链表中
  • 删除元素：根据哈希函数的结果访问链表头部，接着遍历链表以查找目标节点并将其删除

链式地址存在以下局限性：

  • 占用空间增大，链表包含节点指针，它相比数组更加耗费内存空间
  • 查询效率降低，因为需要线性遍历链表来查找对应元素

以下代码给出了链式地址哈希表的简单实现，需要注意两点：

  • 使用列表（动态数组）代替链表，从而简化代码。在这种设定下，哈希表（数组）包含多个桶，每个桶都是一个列表
  • 以下实现包含哈希表扩容方法。当负载因子超过2/3时，我们将哈希表扩容至原先的2倍
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
// 链式地址哈希表
class HashMapChaining {
    int size; // 键值对数量
    int capacity; // 哈希表容量
    double loadThres; // 触发扩容的负载因子阈值
    int extendRatio; // 扩容倍数
    List<List<Pair>> buckets; // 桶数组

    // 构造方法
    public HashMapChaining() {
        size = 0;
        capacity = 4;
        loadThres = 2.0 / 3.0;
        extendRatio = 2;
        buckets = new ArrayList<>(capacity);
        for (int i = 0; i < capacity; i++) {
            buckets.add(new ArrayList<>());
        }
    }

    // 哈希函数
    int hashFunc(int key) {
        return key % capacity;
    }

    // 负载因子
    double loadFactor() {
        return (double) size / capacity;
    }

    // 查询操作
    String get(int key) {
        int index = hashFunc(key);
        List<Pair> bucket = buckets.get(index);
        // 遍历桶，若找到 key 则返回对应 val
        for (Pair pair : bucket) {
            if (pair.key == key) {
                return pair.val;
            }
        }
        // 若未找到 key 则返回 null
        return null;
    }

    // 添加操作
    void put(int key, String val) {
        // 当负载因子超过阈值时，执行扩容
        if (loadFactor() > loadThres) {
            extend();
        }
        int index = hashFunc(key);
        List<Pair> bucket = buckets.get(index);
        // 遍历桶，若遇到指定 key ，则更新对应 val 并返回
        for (Pair pair : bucket) {
            if (pair.key == key) {
                pair.val = val;
                return;
            }
        }
        // 若无该 key ，则将键值对添加至尾部
        Pair pair = new Pair(key, val);
        bucket.add(pair);
        size++;
    }

    // 删除操作
    void remove(int key) {
        int index = hashFunc(key);
        List<Pair> bucket = buckets.get(index);
        // 遍历桶，从中删除键值对
        for (Pair pair : bucket) {
            if (pair.key == key) {
                bucket.remove(pair);
                size--;
                break;
            }
        }
    }

    // 扩容哈希表
    void extend() {
        // 暂存原哈希表
        List<List<Pair>> bucketsTmp = buckets;
        // 初始化扩容后的新哈希表
        capacity *= extendRatio;
        buckets = new ArrayList<>(capacity);
        for (int i = 0; i < capacity; i++) {
            buckets.add(new ArrayList<>());
        }
        size = 0;
        // 将键值对从原哈希表搬运至新哈希表
        for (List<Pair> bucket : bucketsTmp) {
            for (Pair pair : bucket) {
                put(pair.key, pair.val);
            }
        }
    }

    // 打印哈希表
    void print() {
        for (List<Pair> bucket : buckets) {
            List<String> res = new ArrayList<>();
            for (Pair pair : bucket) {
                res.add(pair.key + " -> " + pair.val);
            }
            System.out.println(res);
        }
    }
}

值得注意的是，当链表很长时，查询效率 $O(n)$ 很差。此时可以将链表转换为AVL树或红黑树，从而将查询操作的时间复杂度优化至 $O(logn)$

开放寻址

「开放寻址 open addressing」不引入额外的数据结构，而是通过多次探测来处理哈希冲突，探测方式主要包括线性探测，平方探测，多次哈希等。下面以线性探测为例，介绍开放寻址哈希表的工作机制

  • 线性探测

线性探测采用固定步长的线性搜索来进行探测，其操作方法与普通哈希表有所不同

  1. 插入元素：通过哈希函数计算桶索引，若发现桶内已有元素，则从冲突位置向后线性遍历（步长通常为1），直至找到空桶，将元素插入其中
  2. 查找元素：若发现哈希冲突，则使用相同步长向后线性遍历，直到找到对应元素，返回 value 即可；如果遇到空桶，说明目标元素不在哈希表中，返回NULL

然而，线性探测容易产生聚集现象。具体来说，数组中连续被占用的位置越长，这些连续位置发生哈希冲突的可能性越大，从而进一步促使该位置的聚堆生长，形成恶性循环，最终导致增删查改操作效率劣化。值得注意的是，我们不能在开放寻址哈希表中直接删除元素。这是因为删除元素会在数组内产生一个空桶NULL，而当查询元素时，线性探测到该空桶就会返回，因此在该空桶之下的元素都无法再被访问到，程序可能误判这些元素不存在

为了解决该问题，我们可以采用「懒删除 lazy deletion」机制：它不直接从哈希表中移除元素，而是利用一个常量 TOMBSTONE 来标记这个桶。在该机制下，NULL和 TOMBSTONE 都代表空桶，都可以放置键值对。但不同的是，线性探测到 TOMBSTONE 时应该继续遍历，因为其之下可能还存在键值对

然而，懒删除可能会加速哈希表的性能退化。这是因为每次删除操作都会产生一个删除标记，随着 TOMBSTONE 的增加，搜索时间也会增加，因为线性探测可能需要跳过多个 TOMBSTONE 才能找到目标元素

为此，考虑在线性探测中记录遇到的首个 TOMBSTONE 的索引，并将搜索到的目标元素与该 TOMBSTONE 交换位置。这样做的好处是当每次查询或添加元素时，元素会被移动至距离理想位置（探测起始点）更近的桶，从而优化查询效率

以下代码实现了一个包含懒删除的开放寻址（线性探测）哈希表。为了更加充分地使用哈希表的空间，我们将哈希表看作一个"环形数组"，当越过数组尾部时，回到头部继续遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
// 开放寻址哈希表
class HashMapOpenAddressing {
    private int size; // 键值对数量
    private int capacity = 4; // 哈希表容量
    private final double loadThres = 2.0 / 3.0; // 触发扩容的负载因子阈值
    private final int extendRatio = 2; // 扩容倍数
    private Pair[] buckets; // 桶数组
    private final Pair TOMBSTONE = new Pair(-1, "-1"); // 删除标记

    // 构造方法
    public HashMapOpenAddressing() {
        size = 0;
        buckets = new Pair[capacity];
    }

    // 哈希函数
    private int hashFunc(int key) {
        return key % capacity;
    }

    // 负载因子
    private double loadFactor() {
        return (double) size / capacity;
    }

    // 搜索 key 对应的桶索引
    private int findBucket(int key) {
        int index = hashFunc(key);
        int firstTombstone = -1;
        // 线性探测，当遇到空桶时跳出
        while (buckets[index] != null) {
            // 若遇到 key ，返回对应桶索引
            if (buckets[index].key == key) {
                // 若之前遇到了删除标记，则将键值对移动至该索引
                if (firstTombstone != -1) {
                    buckets[firstTombstone] = buckets[index];
                    buckets[index] = TOMBSTONE;
                    return firstTombstone; // 返回移动后的桶索引
                }
                return index; // 返回桶索引
            }
            // 记录遇到的首个删除标记
            if (firstTombstone == -1 && buckets[index] == TOMBSTONE) {
                firstTombstone = index;
            }
            // 计算桶索引，越过尾部返回头部
            index = (index + 1) % capacity;
        }
        // 若 key 不存在，则返回添加点的索引
        return firstTombstone == -1 ? index : firstTombstone;
    }

    // 查询操作
    public String get(int key) {
        // 搜索 key 对应的桶索引
        int index = findBucket(key);
        // 若找到键值对，则返回对应 val
        if (buckets[index] != null && buckets[index] != TOMBSTONE) {
            return buckets[index].val;
        }
        // 若键值对不存在，则返回 null
        return null;
    }

    // 添加操作
    public void put(int key, String val) {
        // 当负载因子超过阈值时，执行扩容
        if (loadFactor() > loadThres) {
            extend();
        }
        // 搜索 key 对应的桶索引
        int index = findBucket(key);
        // 若找到键值对，则覆盖 val 并返回
        if (buckets[index] != null && buckets[index] != TOMBSTONE) {
            buckets[index].val = val;
            return;
        }
        // 若键值对不存在，则添加该键值对
        buckets[index] = new Pair(key, val);
        size++;
    }

    // 删除操作
    public void remove(int key) {
        // 搜索 key 对应的桶索引
        int index = findBucket(key);
        // 若找到键值对，则用删除标记覆盖它
        if (buckets[index] != null && buckets[index] != TOMBSTONE) {
            buckets[index] = TOMBSTONE;
            size--;
        }
    }

    // 扩容哈希表
    private void extend() {
        // 暂存原哈希表
        Pair[] bucketsTmp = buckets;
        // 初始化扩容后的新哈希表
        capacity *= extendRatio;
        buckets = new Pair[capacity];
        size = 0;
        // 将键值对从原哈希表搬运至新哈希表
        for (Pair pair : bucketsTmp) {
            if (pair != null && pair != TOMBSTONE) {
                put(pair.key, pair.val);
            }
        }
    }

    // 打印哈希表
    public void print() {
        for (Pair pair : buckets) {
            if (pair == null) {
                System.out.println("null");
            } else if (pair == TOMBSTONE) {
                System.out.println("TOMBSTONE");
            } else {
                System.out.println(pair.key + " -> " + pair.val);
            }
        }
    }
}
  • 平方探测

平方探测与线性探测类似，都是开放寻址的常见策略之一。当发生冲突时，平方探测不是简单地跳过一个固定的步数，而是跳过"探测次数的平方"的步数，即1，4，9…步

平方探测主要具有以下优势：

  1. 平方探测通过跳过平方的距离，试图缓解线性探测的聚集效应
  2. 平方探测会跳过更大的距离来寻找空位置，有助于数据分布得更加均匀

然而，平方探测也并不是完美的：

  1. 仍然存在聚集现象，即某些位置比其他位置更容易被占用
  2. 由于平方的增长，平方探测可能不会探测整个哈希表，这意味着即使哈希表中有空桶，平方探测也可能无法访问到它
  • 多次哈希

顾名思义，多次哈希方法使用多个哈希函数进行探测

  1. 插入元素：若哈希函数$f_1(x)$出现冲突，则尝试$f_2(x)$，以此类推，直到找到空桶后插入元素
  2. 查找元素：在相同的哈希函数顺序下进行查找，直到找到目标元素时返回；若遇到空桶或已尝试所有哈希函数，说明哈希表中不存在该元素，则返回NULL

开放寻址（线性探测，平方探测和多次哈希）哈希表都存在不能直接删除元素的问题

哈希算法

键值对的分布情况由哈希函数决定。回忆哈希函数的计算步骤，先计算哈希值，再对数组长度取模：index = hash(key) % capacity观察以上公式，当哈希表容量 capacity 固定时，哈希算法 hash() 决定了输出值，进而决定了键值对在哈希表中的分布情况。这意味着，为了降低哈希冲突的发生概率，我们应当将注意力集中在哈希算法 hash() 的设计上

哈希算法的目标

为了实现"既快又稳"的哈希表数据结构，哈希算法应具备以下特点：

  • 确定性：对于相同地输入，哈希算法应始终产生相同地输出。这样才能确保哈希表是可靠的
  • 效率高：计算哈希值的过程应该足够快。计算开销越小，哈希表的实用性越高
  • 均匀分布：哈希算法应使得键值对均匀分布在哈希表中。分布越均匀，哈希冲突的概率就越低

实际上，哈希算法除了可以用于实现哈希表，还广泛应用于其他领域中

  • 密码存储：为了保护用户密码的安全，系统通常不会直接存储用户的明文密码，而是存储密码的哈希值。当用户输入密码时，系统会对输入的密码计算哈希值，然后与存储的哈希值进行比较。如果两者匹配，那么密码就被视为正确
  • 数据完整性检查：数据发送方可以计算数据的哈希值并将其一同发送；接收方可以重新计算接收到的数据的哈希值，并与接收到的哈希值进行比较。如果两者匹配，那么数据就被视为完整

对于密码学的相关应用，为了防止从哈希值推导出原始密码等逆向工程，哈希算法需要具备更高等级的安全特性：

  • 单向性：无法通过哈希值反推出关于输入数据的任何信息
  • 抗碰撞性：应当极难找到两个不同的输入，使得它们的哈希值相同
  • 雪崩效应：输入的微小变化应当导致输出的显著且不可预测的变化

均匀分布与抗碰撞性是两个独立的概念，满足均匀分布不一定满足抗碰撞性。例如，在随机输入 key 下，哈希函数 key % 100 可以产生均匀分布的输出。然而该哈希算法过于简单，所有后两位相等的 key 的输出都相同，因此我们可以很容易地从哈希值反推出可用的 key ，从而破解密码

哈希算法的设计

哈希算法的设计是一个需要考虑许多因素的复杂问题。然而对于某些要求不高的场景，我们也能设计一些简单的哈希算法

  • 加法哈希：对输入的每个字符的 ASCII 码进行相加，将得到的总和作为哈希值。
  • 乘法哈希：利用乘法的不相关性，每轮乘以一个常数，将各个字符的 ASCII 码累积到哈希值中。
  • 异或哈希：将输入数据的每个元素通过异或操作累积到一个哈希值中。
  • 旋转哈希：将每个字符的 ASCII 码累积到一个哈希值中，每次累积之前都会对哈希值进行旋转操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 加法哈希
int addHash(String key) {
    long hash = 0;
    final int MODULUS = 1000000007;
    for (char c : key.toCharArray()) {
        hash = (hash + (int) c) % MODULUS;
    }
    return (int) hash;
}

// 乘法哈希
int mulHash(String key) {
    long hash = 0;
    final int MODULUS = 1000000007;
    for (char c : key.toCharArray()) {
        hash = (31 * hash + (int) c) % MODULUS;
    }
    return (int) hash;
}

// 异或哈希
int xorHash(String key) {
    int hash = 0;
    final int MODULUS = 1000000007;
    for (char c : key.toCharArray()) {
        hash ^= (int) c;
    }
    return hash & MODULUS;
}

// 旋转哈希
int rotHash(String key) {
    long hash = 0;
    final int MODULUS = 1000000007;
    for (char c : key.toCharArray()) {
        hash = ((hash << 4) ^ (hash >> 28) ^ (int) c) % MODULUS;
    }
    return (int) hash;
}

观察发现，每种哈希算法的最后一步都是对大质数1000000007取模，以确保哈希值在合适的范围内。值得思考的是，为什么要强调对质数取模，或者说对合数取模的弊端是什么？这是一个有趣的问题。因为使用大质数作为模数，可以最大化地保证哈希值的均匀分布。因为质数不与其他数字存在公约数，可以减少因取模操作而产生的周期性模式，从而避免哈希冲突。

常见哈希算法

不难发现，以上介绍的简单哈希算法都比较"脆弱"，远远没有达到哈希算法的设计目标。例如，由于加法和异或满足交换律，因此加法哈希和异或哈希无法区分内容相同但顺序不同的字符串，这可能会加剧哈希冲突，并引起一些安全问题

在实际中，我们通常会用一些标准哈希算法，例如 MD5，SHA-1，SHA-2，SHA-3 等。它们可以将任意长度的输入数据映射到恒定长度的哈希值。

近一个世纪以来，哈希算法处在不断升级与优化的过程中。一部分研究人员努力提升哈希算法的性能，另一部分研究人员和黑客则致力于寻找哈希算法的安全性问题。下表展示了在实际应用中常见的哈希算法：

  • MD5 和 SHA-1 已多次被成功攻击，因此它们被各类安全应用弃用。
  • SHA-2 系列中的 SHA-256 是最安全的哈希算法之一，仍未出现成功的攻击案例，因此常用在各类安全应用与协议中。
  • SHA-3 相较 SHA-2 的实现开销更低、计算效率更高，但目前使用覆盖度不如 SHA-2 系列
MD5 SHA-1 SHA-2 SHA-3
推出时间 1992 1995 2002 2008
输出长度 128 bits 160 bits 256/512 bits 224/256/384/512 bits
哈希冲突 较多 较多 很少 很少
安全等级 低，已被成功攻击 低，已被成功攻击 高 高
应用 已被弃用 已被弃用 加密货币交易验证，数字签名等 可用于替代 SHA-2

Q & A

哈希表的时间复杂度为什么不是 $O(n)$？

当哈希冲突比较严重时，哈希表的时间复杂度会退化至 $O(n)$。当哈希函数设计得比较好，容量设置比较合理，冲突比较平均时，时间复杂度是 $O(1)$。我们使用编程语言内置的哈希表时，通常认为时间复杂度是 $O(1)$

为什么不使用哈希函数$f(x) = x$呢？这样就不会有冲突了

在$f(x) = x$哈希函数下，每个元素对应唯一的桶索引，这与数组等价。然而，输入空间通常远大于输出空间（数组长度），因此哈希函数的最后一步往往是对数组长度取模。换句话说，哈希表的目标是将一个较大的状态空间映射到一个较小的空间，并提供 $O(1)$ 的查询效率

哈希表底层实现是数组，链表，二叉树，但为什么效率可以比它们更高呢？

首先，哈希表的时间效率变高，但空间效率变低了。哈希表有相当一部分内存未使用

其次，只是在特定使用场景下时间效率变高了。如果一个功能能够在相同的时间复杂度下使用数组或链表实现，那么通常比哈希表更快。这是因为哈希函数计算需要开销，时间复杂度的常数项更大

最后，哈希表的时间复杂度可能发生劣化。例如在链式地址中，我们采取在链表或红黑树中执行查找操作，仍然有退化至 $O(n)$ 时间的风险

多次哈希有不能直接删除元素的缺陷吗？标记为已删除的空间还能再次使用吗？

多次哈希是开放寻址的一种，开放寻址法都有不能直接删除元素的缺陷，需要通过标记删除。标记为已删除的空间可以再次使用。当将新元素插入哈希表，并且通过哈希函数找到标记为已删除的位置时，该位置可以被新元素使用。这样做既能保持哈希表的探测序列不变，又能保证哈希表的空间使用率

为什么在线性探测中，查找元素的时候会出现哈希冲突呢？

查找的时候通过哈希函数找到对应的桶和键值对，发现 key 不匹配，这就代表有哈希冲突。因此，线性探测法会根据预先设定的步长依次向下查找，直至找到正确的键值对或无法找到跳出为止

为什么哈希表扩容能够缓解哈希冲突？

哈希函数的最后一步往往是对数组长度n取余，让输出值落在数组索引范围内；在扩容后，数组长度n发生变化，而 key 对应的索引也可能发生变化。原先落在同一个桶的多个 key ，在扩容后可能会被分配到多个桶中，从而实现哈希冲突的缓解

搜索

搜索是一场未知的冒险，我们或许需要走遍神秘空间的每个角落，又或许可以快速锁定目标

二分查找

「二分查找 binary search」是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止

给定一个长度为 n 的数组 nums ，元素按从小到大的顺序排列且不重复。请查找并返回元素 target 在该数组中的索引。若数组不包含该元素，则返回 1

我们先初始化指针 i = 0 和 j = n - 1，分别指向数组首元素和尾元素，代表搜索区间 [0, n - 1]。请注意，中括号表示闭区间，其包含边界值本身。接下来，循环执行以下两步：

  1. 计算中点索引 (i + j) >>> 1，其中 >>> 表示右移一位
  2. 判断 nums[m] 和 target 的大小关系，分为以下三种情况：
    • 当 nums[m] < target 时，说明 target 在区间 [m + 1, j] 中，因此执行 i = m + 1
    • 当 nums[m] > target 时，说明 target 在区间 [i, m - 1] 中，因此执行 j = m - 1
    • 当 nums[m] = target 时，说明找到 target，因此返回索引 m

若数组不包含目标元素，搜索区间最终会缩小为空。此时返回 -1。值得注意的是，由于 i 和 j 都是 int 类型，因此 i + j 可能会超出 int 类型的取值范围。为了避免大数越界，我们通常采用公式 m = (i + j) >>> 2 来计算中点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 二分查找（双闭区间）
int binarySearch(int[] nums, int target) {
    // 初始化双闭区间 [0, n-1] ，即 i, j 分别指向数组首元素、尾元素
    int i = 0, j = nums.length - 1;
    // 循环，当搜索区间为空时跳出（当 i > j 时为空）
    while (i <= j) {
        int m = (i + j) >>> 2; // 计算中点索引 m
        if (nums[m] < target) // 此情况说明 target 在区间 [m+1, j] 中
            i = m + 1;
        else if (nums[m] > target) // 此情况说明 target 在区间 [i, m-1] 中
            j = m - 1;
        else // 找到目标元素，返回其索引
            return m;
    }
    // 未找到目标元素，返回 -1
    return -1;
}
  • 时间复杂度 $O(logn)$：在二分循环中，区间每轮缩小一半，循环次数为 $log_2^n$
  • 空间复杂度 $O(1)$：指针 i 和 j 使用常数大小空间

区间表示方法

除了上述双闭区间外，常见的区间表示还有左闭右开区间，定义为 [0, n)，即左边界包含自身，右边界不包含自身。在该表示下，区间 [i, j] 在 i = j 时为空。我们可以基于该表示实现具有相同功能的二分查找算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 二分查找（左闭右开区间）
int binarySearchLCRO(int[] nums, int target) {
    // 初始化左闭右开区间 [0, n) ，即 i, j 分别指向数组首元素、尾元素+1
    int i = 0, j = nums.length;
    // 循环，当搜索区间为空时跳出（当 i = j 时为空）
    while (i < j) {
        int m = (i + j) >>> 2; // 计算中点索引 m
        if (nums[m] < target) // 此情况说明 target 在区间 [m+1, j) 中
            i = m + 1;
        else if (nums[m] > target) // 此情况说明 target 在区间 [i, m) 中
            j = m;
        else // 找到目标元素，返回其索引
            return m;
    }
    // 未找到目标元素，返回 -1
    return -1;
}

由于"双闭区间"表示中的左右边界都被定义为闭区间，因此通过指针 i 和指针 j 缩小区间的操作也是对称的。这样更不容易出错，因此一般建议采用双闭区间的写法

优点与局限性

二分查找在时间和空间方面都有较好的性能

  • 二分查找的时间效率高。在大数据量下，对数阶的时间复杂度具有显著优势。例如，当数据大小 n = $2^20$ 时，线性查找需要 1048576 轮循环，而二分查找仅需 20 轮循环
  • 二分查找无须额外空间。相较于需要借助额外空间的搜索算法（例如哈希查找），二分查找更加节省空间

然而，二分查找并非适用于所有情况，主要有以下原因：

  • 二分查找仅适用于有序数据。若输入数据无序，为了使用二分查找而专门进行排序，得不偿失。因为排序算法的时间复杂度通常为 $O()nlogn$，比线性查找和二分查找都更高。对于频繁插入元素的场景，为保持数组有序性，需要将元素插入到特定位置，时间复杂度为 $O(n)$，也是非常昂贵的
  • 二分查找仅适用于数组。二分查找需要跳跃式（非连续地）访问元素，而在链表中执行跳跃式访问的效率较低，因此不适合应用在链表或基于链表实现的数据结构。
  • 小数据量下，线性查找性能更佳。在线性查找中，每轮只需 1 次判断操作；而在二分查找中，需要 1 次加法、1 次除法、1 ~ 3 次判断操作、1 次加法（减法），共 4 ~ 6 个单元操作；因此，当数据量 n 较小时，线性查找反而比二分查找更快。

二分查找插入点

二分查找不仅可用于搜索目标元素，还可用于解决许多变种问题，比如搜索目标元素的插入位置

无重复元素的情况

给定一个长度为 n 的有序数组 nums 和一个元素 target ，数组不存在重复元素。现将 target 插入数组 nums 中，并保持其有序性。若数组中已存在元素 target ，则插入到其左方。请返回插入后 target 在数组中的索引

如果想复用二分查找的代码，则需要回答以下两个问题：

问题一：当数组中包含 target 时，插入点的索引是否是该元素的索引？

题目要求将 target 插入到相等元素的左边，这意味着新插入的 target 替换了原来 target 的位置。也就是说，当数组包含 target 时，插入点的索引就是该 target 的索引

题二：当数组中不存在 target 时，插入点是哪个元素的索引？

进一步思考二分查找过程：当 nums[m] < target 时移动，这意味着指针 i 在向大于等于 target 的元素靠近。同理，指针 j 始终在向小于等于 target 的元素靠近。

因此二分结束时一定有：i 指向首个大于 target 的元素，j 指向首个小于 target 的元素。易得当数组不包含 target 时，插入索引为 i。代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 二分查找插入点（无重复元素）
int binarySearchInsertionSimple(int[] nums, int target) {
    int i = 0, j = nums.length - 1; // 初始化双闭区间 [0, n-1]
    while (i <= j) {
        int m = (i + j) >>> 2; // 计算中点索引 m
        if (nums[m] < target) {
            i = m + 1; // target 在区间 [m+1, j] 中
        } else if (nums[m] > target) {
            j = m - 1; // target 在区间 [i, m-1] 中
        } else {
            return m; // 找到 target ，返回插入点 m
        }
    }
    // 未找到 target ，返回插入点 i
    return i;
}

存在重复元素的情况

假设数组中存在多个 target ，则普通二分查找只能返回其中一个 target 的索引，而无法确定该元素的左边和右边还有多少 target。题目要求将目标元素插入到最左边，所以我们需要查找数组中最左一个 target 的索引

  1. 执行二分查找，得到任意一个 target 的索引，记为 k
  2. 从索引 k 开始，向左进行线性遍历，当找到最左边的 target 时返回。

此方法虽然可用，但其包含线性查找，因此时间复杂度为 $O(n)$。当数组中存在很多重复的 target 时，该方法效率很低。现考虑拓展二分查找代码。整体流程保持不变，每轮先计算中点索引，再判断 target 和 nums[m] 的大小关系，分为以下几种情况：

  1. 当 nums[m] < target 或 nums[m] > target 时，说明还没有找到 target ，因此采用普通二分查找的缩小区间操作，从而使指针 i 和 j 向 target 靠近
  2. 当 nums[m] == target 时，说明小于 target 的元素在区间 [i, m -1] 中，因此采用 j = m - 1 来缩小区间，从而使指针 j 向小于 target 的元素靠近

循环完成后，i 指向最左边的 target，j 指向首个小于 target 的元素，因此索引 i 就是插入点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 二分查找插入点（存在重复元素）
int binarySearchInsertion(int[] nums, int target) {
    int i = 0, j = nums.length - 1; // 初始化双闭区间 [0, n-1]
    while (i <= j) {
        int m = (i + j) >>> 2; // 计算中点索引 m
        if (nums[m] < target) {
            i = m + 1; // target 在区间 [m+1, j] 中
        } else if (nums[m] > target) {
            j = m - 1; // target 在区间 [i, m-1] 中
        } else {
            j = m - 1; // 首个小于 target 的元素在区间 [i, m-1] 中
        }
    }
    // 返回插入点 i
    return i;
}

二分查找边界

查找左边界

给定一个长度为 n 的有序数组 nums ，其中可能包含重复元素。请返回数组中最左一个元素 target 的索引。若数组中不包含该元素，则返回 -1

回忆二分查找插入点的方法，搜索完成后 i 指向最左一个 target ，因此查找插入点本质上是在查找最左一个 target 的索引。考虑通过查找插入点的函数实现查找左边界。请注意，数组中可能不包含 target ，这种情况可能导致以下两种结果：

  • 插入点的索引 i 越界
  • 元素 nums[i] 与 target 不相等。

当遇到以上两种情况时，直接返回 -1 即可。代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
// 二分查找最左一个 target
int binarySearchLeftEdge(int[] nums, int target) {
    // 等价于查找 target 的插入点
    int i = binary_search_insertion.binarySearchInsertion(nums, target);
    // 未找到 target ，返回 -1
    if (i == nums.length || nums[i] != target) {
        return -1;
    }
    // 找到 target ，返回索引 i
    return i;
}

查找右边界

实际上，我们可以利用查找最左元素的函数来查找最右元素，具体方法为：将查找最右一个 target 转化为查找最左一个 target + 1。查找完成后，指针 i 指向最左一个 target +1（如果存在），而 j 指向最右一个 target ，因此返回 j 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
// 二分查找最右一个 target
int binarySearchRightEdge(int[] nums, int target) {
    // 转化为查找最左一个 target + 1
    int i = binary_search_insertion.binarySearchInsertion(nums, target + 1);
    // j 指向最右一个 target ，i 指向首个大于 target 的元素
    int j = i - 1;
    // 未找到 target ，返回 -1
    if (j == -1 || nums[j] != target) {
        return -1;
    }
    // 找到 target ，返回索引 j
    return j;
}

哈希优化策略

在算法题中，我们常通过将线性查找替换为哈希查找来降低算法的时间复杂度

给定一个整数数组 nums 和一个目标元素 target ，请在数组中搜索和为 target 的两个元素，并返回它们的数组索引。返回任意一个解即可

线性查找：以时间换空间

考虑直接遍历所有可能的组合。我们开启一个两层循环，在每轮中判断两个整数的和是否为 target ，若是，则返回它们的索引

1
2
3
4
5
6
7
8
9
10
11
12
// 方法一：暴力枚举
int[] twoSumBruteForce(int[] nums, int target) {
    int size = nums.length;
    // 两层循环，时间复杂度为 O(n^2)
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            if (nums[i] + nums[j] == target)
                return new int[] { i, j };
        }
    }
    return new int[0];
}

此方法的时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$，在大数据量下非常耗时

哈希查找：以空间换时间

考虑借助一个哈希表，键值对分别为数组元素和元素索引。循环遍历数组

  1. 判断数字 target - nums[i] 是否在哈希表中，若是，则直接返回这两个元素的索引。
  2. 将键值对 nums[i] 和索引 i 添加进哈希表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 方法二：辅助哈希表
int[] twoSumHashTable(int[] nums, int target) {
    int size = nums.length;
    // 辅助哈希表，空间复杂度为 O(n)
    Map<Integer, Integer> dic = new HashMap<>();
    // 单层循环，时间复杂度为 O(n)
    for (int i = 0; i < size; i++) {
        if (dic.containsKey(target - nums[i])) {
            return new int[] { dic.get(target - nums[i]), i };
        }
        dic.put(nums[i], i);
    }
    return new int[0];
}

此方法通过哈希查找将时间复杂度从 $O(n^2)$ 降至 $O(n)$，大幅提升运行效率。由于需要维护一个额外的哈希表，因此空间复杂度为 $O(n)$。尽管如此，该方法的整体时空效率更为均衡，因此它是本题的最优解法。

排序

「排序算法 sorting algorithm」用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用，因为有序数据通常能够被更高效地查找，分析和处理。排序算法中的数据类型可以是整数，浮点数，字符或字符串等。排序的判断规则可根据需求设定，如数字大小，字符 ASCII 码顺序或自定义规则

选择排序

「选择排序 selection sort」的工作原理非常简单：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 选择排序
void selectionSort(int[] nums) {
    int n = nums.length;
    // 外循环：未排序区间为 [i, n-1]
    for (int i = 0; i < n - 1; i++) {
        // 内循环：找到未排序区间内的最小元素
        int k = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[k])
                k = j; // 记录最小元素的索引
        }
        // 将该最小元素与未排序区间的首个元素交换
        int temp = nums[i];
        nums[i] = nums[k];
        nums[k] = temp;
    }
}

冒泡排序

「冒泡排序 bubble sort」通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样，因此得名冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 冒泡排序
void bubbleSort(int[] nums) {
    // 外循环：未排序区间为 [0, i]
    for (int i = nums.length - 1; i > 0; i--) {
        // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // 交换 nums[j] 与 nums[j + 1]
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
            }
        }
    }
}

我们发现，如果某轮"冒泡"中没有执行任何交换操作，说明数组已经完成排序，可直接返回结果。因此，可以增加一个标志位 flag 来监测这种情况，一旦出现就立即返回。经过优化，冒泡排序的最差时间复杂度和平均时间复杂度仍为 $O(n^2)$；但当输入数组完全有序时，可达到最佳时间复杂度 $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 冒泡排序（标志优化）
void bubbleSortWithFlag(int[] nums) {
    // 外循环：未排序区间为 [0, i]
    for (int i = nums.length - 1; i > 0; i--) {
        boolean flag = false; // 初始化标志位
        // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // 交换 nums[j] 与 nums[j + 1]
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
                flag = true; // 记录交换元素
            }
        }
        if (!flag)
            break; // 此轮冒泡未交换任何元素，直接跳出
    }
}

插入排序

「插入排序 insertion sort」是一种简单的排序算法，它的工作原理与手动整理一副牌的过程非常相似。具体来说，我们在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
// 插入排序
void insertionSort(int[] nums) {
    // 外循环：已排序元素数量为 1, 2, ..., n
    for (int i = 1; i < nums.length; i++) {
        int base = nums[i], j = i - 1;
        // 内循环：将 base 插入到已排序部分的正确位置
        while (j >= 0 && nums[j] > base) {
            nums[j + 1] = nums[j]; // 将 nums[j] 向右移动一位
            j--;
        }
        nums[j + 1] = base;        // 将 base 赋值到正确位置
    }
}

插入排序的时间复杂度为 $O(n^2)$，而我们即将学习的快速排序的时间复杂度为 $O(nlogn)$。尽管插入排序的时间复杂度更高，但在数据量较小的情况下，插入排序通常更快。

这个结论与线性查找和二分查找的适用情况的结论类似。快速排序这类 $O(nlogn)$ 的算法属于基于分治策略的排序算法，往往包含更多单元计算操作。而在数据量较小时，$n^2$ 和 $nlogn$ 的数值比较接近，复杂度不占主导地位；每轮中的单元操作数量起到决定性作用。

虽然冒泡排序、选择排序和插入排序的时间复杂度都为 $O(n^2)$，但在实际情况中，插入排序的使用频率显著高于冒泡排序和选择排序，主要有以下原因。

  • 冒泡排序基于元素交换实现，需要借助一个临时变量，共涉及 3 个单元操作；插入排序基于元素赋值实现，仅需 1 个单元操作。因此，冒泡排序的计算开销通常比插入排序更高。
  • 选择排序在任何情况下的时间复杂度都为 $O(n^2)$。如果给定一组部分有序的数据，插入排序通常比选择排序效率更高。
  • 选择排序不稳定，无法应用于多级排序。

快速排序

「快速排序 quick sort」是一种基于分治策略的排序算法，运行高效，应用广泛。快速排序的核心操作是"哨兵划分"，其目标是：选择数组中的某个元素作为"基准数"，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧

哨兵划分的实质是将一个较长数组的排序问题简化为两个较短数组的排序问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 元素交换
void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

// 哨兵划分
int partition(int[] nums, int left, int right) {
    // 以 nums[left] 为基准数
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--;          // 从右向左找首个小于基准数的元素
        while (i < j && nums[i] <= nums[left])
            i++;          // 从左向右找首个大于基准数的元素
        swap(nums, i, j); // 交换这两个元素
    }
    swap(nums, i, left);  // 将基准数交换至两子数组的分界线
    return i;             // 返回基准数的索引
}

从名称上就能看出，快速排序在效率方面应该具有一定的优势。尽管快速排序的平均时间复杂度与归并排序和堆排序相同，但通常快速排序的效率更高，主要有以下原因：

  • 出现最差情况的概率很低：虽然快速排序的最差时间复杂度为 $O(n^2)$，没有归并排序稳定，但在绝大多数情况下，快速排序能在 $O(nlogn)$ 的时间复杂度下运行。
  • 缓存使用效率高：在执行哨兵划分操作时，系统可将整个子数组加载到缓存，因此访问元素的效率较高。而像堆排序这类算法需要跳跃式访问元素，从而缺乏这一特性。
  • 复杂度的常数系数小：在上述三种算法中，快速排序的比较，赋值，交换等操作的总数量最少。这与插入排序比冒泡排序更快的原因类似

基准数优化

快速排序在某些输入下的时间效率可能降低。举一个极端例子，假设输入数组是完全倒序的，由于我们选择最左端元素作为基准数，那么在哨兵划分完成后，基准数被交换至数组最右端，导致左子数组长度为 n - 1，右子数组长度为 0。如此递归下去，每轮哨兵划分后的右子数组长度都为 0，分治策略失效，快速排序退化为冒泡排序

为了尽量避免这种情况发生，我们可以优化哨兵划分中的基准数的选取策略。例如，我们可以随机选取一个元素作为基准数。然而，如果运气不佳，每次都选到不理想的基准数，效率仍然不尽如人意。需要注意的是，编程语言通常生成的是"伪随机数"。如果我们针对伪随机数序列构建一个特定的测试样例，那么快速排序的效率仍然可能劣化。

为了进一步改进，我们可以在数组中选取三个候选元素（通常为数组的首，尾，中点元素），并将这三个候选元素的中位数作为基准数。这样一来，基准数"既不太小也不太大"的概率将大幅提升。当然，我们还可以选取更多候选元素，以进一步提高算法的稳健性。采用这种方法后，时间复杂度劣化至 $O(n^2)$ 的概率大大降低。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 选取三个元素的中位数
int medianThree(int[] nums, int left, int mid, int right) {
    // 此处使用异或运算来简化代码
    // 异或规则为 0 ^ 0 = 1 ^ 1 = 0, 0 ^ 1 = 1 ^ 0 = 1
    if ((nums[left] < nums[mid]) ^ (nums[left] < nums[right]))
        return left;
    else if ((nums[mid] < nums[left]) ^ (nums[mid] < nums[right]))
        return mid;
    else
        return right;
}

// 哨兵划分（三数取中值）
int partition(int[] nums, int left, int right) {
    // 选取三个候选元素的中位数
    int med = medianThree(nums, left, (left + right) / 2, right);
    // 将中位数交换至数组最左端
    swap(nums, left, med);
    // 以 nums[left] 为基准数
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--;          // 从右向左找首个小于基准数的元素
        while (i < j && nums[i] <= nums[left])
            i++;          // 从左向右找首个大于基准数的元素
        swap(nums, i, j); // 交换这两个元素
    }
    swap(nums, i, left);  // 将基准数交换至两子数组的分界线
    return i;             // 返回基准数的索引
}

尾递归优化

在某些输入下，快速排序可能占用空间较多。以完全倒序的输入数组为例，设递归中的子数组长度为 m，每轮哨兵划分操作都将产生长度为 0 的左子数组和长度为 m - 1 的右子数组，这意味着每一层递归调用减少的问题规模非常小（只减少一个元素），递归树的高度会达到 n - 1，此时需要占用 $O(n)$ 大小的栈帧空间。

为了防止栈帧空间的累积，我们可以在每轮哨兵排序完成后，比较两个子数组的长度，仅对较短的子数组进行递归。由于较短子数组的长度不会超过 n / 2，因此这种方法能确保递归深度不超过 logn，从而将最差空间复杂度优化至 $O(logn)$。代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 快速排序（尾递归优化）
void quickSort(int[] nums, int left, int right) {
    // 子数组长度为 1 时终止
    while (left < right) {
        // 哨兵划分操作
        int pivot = partition(nums, left, right);
        // 对两个子数组中较短的那个执行快速排序
        if (pivot - left < right - pivot) {
            quickSort(nums, left, pivot - 1); // 递归排序左子数组
            left = pivot + 1; // 剩余未排序区间为 [pivot + 1, right]
        } else {
            quickSort(nums, pivot + 1, right); // 递归排序右子数组
            right = pivot - 1; // 剩余未排序区间为 [left, pivot - 1]
        }
    }
}

归并排序

「归并排序 merge sort」是一种基于分治策略的排序算法，包含"划分"和"合并"阶段。

  1. 划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题
  2. 合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 合并左子数组和右子数组
void merge(int[] nums, int left, int mid, int right) {
    // 左子数组区间 [left, mid], 右子数组区间 [mid+1, right]
    // 创建一个临时数组 tmp ，用于存放合并后的结果
    int[] tmp = new int[right - left + 1];
    // 初始化左子数组和右子数组的起始索引
    int i = left, j = mid + 1, k = 0;
    // 当左右子数组都还有元素时，比较并将较小的元素复制到临时数组中
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
            tmp[k++] = nums[i++];
        else
            tmp[k++] = nums[j++];
    }
    // 将左子数组和右子数组的剩余元素复制到临时数组中
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
    for (k = 0; k < tmp.length; k++) {
        nums[left + k] = tmp[k];
    }
}

// 归并排序
void mergeSort(int[] nums, int left, int right) {
    // 终止条件
    if (left >= right)
        return; // 当子数组长度为 1 时终止递归
    // 划分阶段
    int mid = (left + right) / 2; // 计算中点
    mergeSort(nums, left, mid); // 递归左子数组
    mergeSort(nums, mid + 1, right); // 递归右子数组
    // 合并阶段
    merge(nums, left, mid, right);
}

堆排序

「堆排序 heap sort」是一种基于堆数据结构实现的高效排序算法。我们可以利用已经学过的"建堆操作"和"元素出堆操作"实现堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 堆的长度为 n ，从节点 i 开始，从顶至底堆化
void siftDown(int[] nums, int n, int i) {
    while (true) {
        // 判断节点 i, l, r 中值最大的节点，记为 ma
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma])
            ma = l;
        if (r < n && nums[r] > nums[ma])
            ma = r;
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if (ma == i)
            break;
        // 交换两节点
        int temp = nums[i];
        nums[i] = nums[ma];
        nums[ma] = temp;
        // 循环向下堆化
        i = ma;
    }
}

// 堆排序
void heapSort(int[] nums) {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for (int i = nums.length / 2 - 1; i >= 0; i--) {
        siftDown(nums, nums.length, i);
    }
    // 从堆中提取最大元素，循环 n-1 轮
    for (int i = nums.length - 1; i > 0; i--) {
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        int tmp = nums[0];
        nums[0] = nums[i];
        nums[i] = tmp;
        // 以根节点为起点，从顶至底进行堆化
        siftDown(nums, i, 0);
    }
}

桶排序

「桶排序 bucket sort」是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 桶排序
void bucketSort(float[] nums) {
    // 初始化 k = n/2 个桶，预期向每个桶分配 2 个元素
    int k = nums.length / 2;
    List<List<Float>> buckets = new ArrayList<>();
    for (int i = 0; i < k; i++) {
        buckets.add(new ArrayList<>());
    }
    // 1. 将数组元素分配到各个桶中
    for (float num : nums) {
        // 输入数据范围为 [0, 1)，使用 num * k 映射到索引范围 [0, k-1]
        int i = (int) (num * k);
        // 将 num 添加进桶 i
        buckets.get(i).add(num);
    }
    // 2. 对各个桶执行排序
    for (List<Float> bucket : buckets) {
        // 使用内置排序函数，也可以替换成其他排序算法
        Collections.sort(bucket);
    }
    // 3. 遍历桶合并结果
    int i = 0;
    for (List<Float> bucket : buckets) {
        for (float num : bucket) {
            nums[i++] = num;
        }
    }
}

桶排序的时间复杂度理论上可以达到$O(n)$，关键在于将元素均匀分配到各个桶中，因为实际数据往往不是均匀分布的。例如，我们想要将淘宝上的所有商品按价格范围平均分配到 10 个桶中，但商品价格分布不均，低于 100 元的非常多，高于 1000 元的非常少。若将价格区间平均划分为 10 个，各个桶中的商品数量差距会非常大。

为实现平均分配，我们可以先设定一条大致的分界线，将数据粗略地分到 3 个桶中。分配完毕后，再将商品较多的桶继续划分为 3 个桶，直至所有桶中的元素数量大致相等。

计数排序

「计数排序 counting sort」通过统计元素数量来实现排序，通常应用于整数数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 计数排序，简单实现，无法用于排序对象
void countingSortNaive(int[] nums) {
    // 1. 统计数组最大元素 m
    int m = 0;
    for (int num : nums) {
        m = Math.max(m, num);
    }
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    int[] counter = new int[m + 1];
    for (int num : nums) {
        counter[num]++;
    }
    // 3. 遍历 counter ，将各元素填入原数组 nums
    int i = 0;
    for (int num = 0; num < m + 1; num++) {
        for (int j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}

从桶排序的角度看，我们可以将计数排序中的计数数组 counter 的每个索引视为一个桶，将统计数量的过程看作将各个元素分配到对应的桶中。本质上，计数排序是桶排序在整型数据下的一个特例

基数排序

「基数排序 radix sort」的核心思想与计数排序一致，也通过统计个数来实现排序。在此基础上，基数排序利用数字各位之间的递进关系，依次对每一位进行排序，从而得到最终的排序结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 获取元素 num 的第 k 位，其中 exp = 10^(k-1)
int digit(int num, int exp) {
    // 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算
    return (num / exp) % 10;
}

// 计数排序（根据 nums 第 k 位排序）
void countingSortDigit(int[] nums, int exp) {
    // 十进制的位范围为 0~9 ，因此需要长度为 10 的桶数组
    int[] counter = new int[10];
    int n = nums.length;
    // 统计 0~9 各数字的出现次数
    for (int i = 0; i < n; i++) {
        int d = digit(nums[i], exp); // 获取 nums[i] 第 k 位，记为 d
        counter[d]++;                // 统计数字 d 的出现次数
    }
    // 求前缀和，将出现个数转换为数组索引
    for (int i = 1; i < 10; i++) {
        counter[i] += counter[i - 1];
    }
    // 倒序遍历，根据桶内统计结果，将各元素填入 res
    int[] res = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        int d = digit(nums[i], exp);
        int j = counter[d] - 1; // 获取 d 在数组中的索引 j
        res[j] = nums[i];       // 将当前元素填入索引 j
        counter[d]--;           // 将 d 的数量减 1
    }
    // 使用结果覆盖原数组 nums
    for (int i = 0; i < n; i++)
        nums[i] = res[i];
}

// 基数排序
void radixSort(int[] nums) {
    // 获取数组的最大元素，用于判断最大位数
    int m = Integer.MIN_VALUE;
    for (int num : nums)
        if (num > m)
            m = num;
    // 按照从低位到高位的顺序遍历
    for (int exp = 1; exp <= m; exp *= 10)
        // 对数组元素的第 k 位执行计数排序
        // k = 1 -> exp = 1
        // k = 2 -> exp = 10
        // 即 exp = 10^(k-1)
        countingSortDigit(nums, exp);
}

为什么从最低位开始排序？

在连续的排序轮次中，后一轮排序会覆盖前一轮排序的结果。举例来说，如果第一轮排序结果 a < b，而第二轮排序结果 a > b，那么第二轮的结果将取代第一轮的结果。由于数字的高位优先级高于低位，因此应该先排序低位再排序高位

图

「图 graph」是一种非线性数据结构，由「顶点 vertex」和「边 edge」组成。如果将顶点看作节点，将边看作连接各个节点的引用（指针），我们就可以将图看作一种从链表拓展而来的数据结构。相较于线性关系（链表）和分治关系（树），网络关系（图）的自由度更高，因而更为复杂

图常见类型与术语

根据边是否具有方向，可分为「无向图 undirected graph」和「有向图 directed graph」

  1. 在无向图中，边表示两顶点之间的双向连接关系，例如微信或 QQ 中的"好友关系"
  2. 在有向图中，边具有方向性，即 A -> B 和 B -> A 两个方向的边是相互独立的，例如微博或抖音上的"关注"与"被关注"关系

根据所有顶点是否连通，可分为「连通图 connected graph」和「非连通图 disconnected graph」

  1. 对于连通图，从某个顶点出发，可以到达其余任意顶点
  2. 对于非连通图，从某个顶点出发，至少有一个顶点无法到达

我们还可以为边添加权重变量，从而得到「有权图 weighted graph」。例如在王者荣耀等手游中，系统会根据共同游戏时间来计算玩家之间的亲密度，这种亲密度网络就可以用有权图来表示。图数据结构包含以下常用术语：

  • 「邻接 adjacency」：当两顶点之间存在边相连时，称这两顶点邻接
  • 「路径 path」：从顶点 A 到顶点 B 经过的边构成的序列被称为从 A 到 B 的路径
  • 「度 degree」：一个顶点拥有的边数。对于有向图，「入度 in-degree」表示有多少条边指向该顶点，「出度 out-degree」表示有多少条边从该顶点指出

图的表示

图的常用表示方式包括"邻接矩阵"和"邻接表"

邻接矩阵

设图的顶点数量为n，「邻接矩阵 adjacency matrix」使用一个 n × n 大小的矩阵来表示图，每一行（列）代表一个顶点，矩阵元素代表边，用 1 或 0 表示两个顶点之间是否存在边。邻接矩阵具有以下特性：

  • 顶点不能与自身相连，因此邻接矩阵主对角线元素没有意义
  • 对于无向图，两个方向的边等价，此时邻接矩阵关于主对角线对称
  • 将邻接矩阵的元素从 1 和 0 替换为权重，则可表示有权图

使用邻接矩阵表示图时，我们可以直接访问矩阵元素以获取边，因此增删查改操作的效率很高，时间复杂度均为 $O(1)$。然而，矩阵的空间复杂度为 $O(n^2)$，内存占用较多

邻接表

「邻接表 adjacency list」使用 n 个链表来表示图，链表节点表示顶点。第 i 个链表对应顶点 i ，其中存储了该顶点的所有邻接顶点（与该顶点相连的顶点）。邻接表仅存储实际存在的边，而边的总数通常远小于 $n^2$ ，因此它更加节省空间。然而，在邻接表中需要通过遍历链表来查找边，因此其时间效率不如邻接矩阵。邻接表结构与哈希表中的链式地址非常相似，因此我们也可以采用类似的方法来优化效率。比如当链表较长时，可以将链表转化为 AVL 树或红黑树，从而将时间效率从 $O(n)$ 优化至 $O(logn)$；还可以把链表转换为哈希表，从而将时间复杂度降至 $O(1)$

图基础操作

图的基础操作可分为对"边"的操作和对顶点"的操作。在"邻接矩阵"和"邻接表"两种表示方法下，实现方式有所不同

基于邻接矩阵的实现

给定一个顶点数量为 n 的无向图：

  • 添加或删除边：直接在邻接矩阵中修改指定的边即可，使用 %O(1)% 时间。而由于是无向图，因此需要同时更新两个方向的边
  • 添加顶点：在邻接矩阵的尾部添加一行一列，并全部填 0 即可，使用 $O(n)$ 时间
  • 删除顶点：在邻接矩阵中删除一行一列。当删除首行首列时达到最差情况，需要将 $(n - 1)^2$ 个元素向左上移动，从而使用 $O(n^2)$ 时间
  • 初始化：传入 n 个顶点，初始化长度为 n 的顶点列表 vertices ，使用 $O(n)$ 时间；初始化 n × n 大小的邻接矩阵 adjMat ，使用 $O(n^2)$ 时间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// 基于邻接矩阵实现的无向图类
class GraphAdjMat {
    List<Integer> vertices; // 顶点列表，元素代表顶点值，索引代表顶点索引
    List<List<Integer>> adjMat; // 邻接矩阵，行列索引对应顶点索引

    // 构造方法
    public GraphAdjMat(int[] vertices, int[][] edges) {
        this.vertices = new ArrayList<>();
        this.adjMat = new ArrayList<>();
        // 添加顶点
        for (int val : vertices) {
            addVertex(val);
        }
        // 添加边
        // 请注意，edges 元素代表顶点索引，即对应 vertices 元素索引
        for (int[] e : edges) {
            addEdge(e[0], e[1]);
        }
    }

    // 获取顶点数量
    public int size() {
        return vertices.size();
    }

    // 添加顶点
    public void addVertex(int val) {
        int n = size();
        // 向顶点列表中添加新顶点的值
        vertices.add(val);
        // 在邻接矩阵中添加一行
        List<Integer> newRow = new ArrayList<>(n);
        for (int j = 0; j < n; j++) {
            newRow.add(0);
        }
        adjMat.add(newRow);
        // 在邻接矩阵中添加一列
        for (List<Integer> row : adjMat) {
            row.add(0);
        }
    }

    // 删除顶点
    public void removeVertex(int index) {
        if (index >= size())
            throw new IndexOutOfBoundsException();
        // 在顶点列表中移除索引 index 的顶点
        vertices.remove(index);
        // 在邻接矩阵中删除索引 index 的行
        adjMat.remove(index);
        // 在邻接矩阵中删除索引 index 的列
        for (List<Integer> row : adjMat) {
            row.remove(index);
        }
    }

    // 添加边
    // 参数 i, j 对应 vertices 元素索引
    public void addEdge(int i, int j) {
        // 索引越界与相等处理
        if (i < 0 || j < 0 || i >= size() || j >= size() || i == j)
            throw new IndexOutOfBoundsException();
        // 在无向图中，邻接矩阵关于主对角线对称，即满足 (i, j) == (j, i)
        adjMat.get(i).set(j, 1);
        adjMat.get(j).set(i, 1);
    }

    // 删除边
    // 参数 i, j 对应 vertices 元素索引
    public void removeEdge(int i, int j) {
        // 索引越界与相等处理
        if (i < 0 || j < 0 || i >= size() || j >= size() || i == j)
            throw new IndexOutOfBoundsException();
        adjMat.get(i).set(j, 0);
        adjMat.get(j).set(i, 0);
    }

    // 打印邻接矩阵
    public void print() {
        System.out.print("顶点列表 = ");
        System.out.println(vertices);
        System.out.println("邻接矩阵 =");
        PrintUtil.printMatrix(adjMat);
    }
}

基于邻接表的实现

设无向图的顶点总数为 n ，边总数为 m

  • 添加边：在顶点对应链表的末尾添加边即可，使用 $O(1)$ 时间。因为是无向图，所以需要同时添加两个方向的边
  • 删除边：在顶点对应链表中查找并删除指定边，使用 $O(m)$ 时间。在无向图中，需要同时删除两个方向的边
  • 添加顶点：在邻接表中添加一个链表，并将新增顶点作为链表头节点，使用 $O(1)$ 时间
  • 删除顶点：需遍历整个邻接表，删除包含指定顶点的所有边，使用 $O(m + 1)$ 时间
  • 初始化：在邻接表中创建 n 个顶点和 2m 条边，使用 $O(n + m)$ 时间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// 基于邻接表实现的无向图类
class GraphAdjList {
    // 邻接表，key：顶点，value：该顶点的所有邻接顶点
    Map<Vertex, List<Vertex>> adjList;

    // 构造方法
    public GraphAdjList(Vertex[][] edges) {
        this.adjList = new HashMap<>();
        // 添加所有顶点和边
        for (Vertex[] edge : edges) {
            addVertex(edge[0]);
            addVertex(edge[1]);
            addEdge(edge[0], edge[1]);
        }
    }

    // 获取顶点数量
    public int size() {
        return adjList.size();
    }

    // 添加边
    public void addEdge(Vertex vet1, Vertex vet2) {
        if (!adjList.containsKey(vet1) || !adjList.containsKey(vet2) || vet1 == vet2)
            throw new IllegalArgumentException();
        // 添加边 vet1 - vet2
        adjList.get(vet1).add(vet2);
        adjList.get(vet2).add(vet1);
    }

    // 删除边
    public void removeEdge(Vertex vet1, Vertex vet2) {
        if (!adjList.containsKey(vet1) || !adjList.containsKey(vet2) || vet1 == vet2)
            throw new IllegalArgumentException();
        // 删除边 vet1 - vet2
        adjList.get(vet1).remove(vet2);
        adjList.get(vet2).remove(vet1);
    }

    // 添加顶点
    public void addVertex(Vertex vet) {
        if (adjList.containsKey(vet))
            return;
        // 在邻接表中添加一个新链表
        adjList.put(vet, new ArrayList<>());
    }

    // 删除顶点
    public void removeVertex(Vertex vet) {
        if (!adjList.containsKey(vet))
            throw new IllegalArgumentException();
        // 在邻接表中删除顶点 vet 对应的链表
        adjList.remove(vet);
        // 遍历其他顶点的链表，删除所有包含 vet 的边
        for (List<Vertex> list : adjList.values()) {
            list.remove(vet);
        }
    }

    // 打印邻接表
    public void print() {
        System.out.println("邻接表 =");
        for (Map.Entry<Vertex, List<Vertex>> pair : adjList.entrySet()) {
            List<Integer> tmp = new ArrayList<>();
            for (Vertex vertex : pair.getValue())
                tmp.add(vertex.val);
            System.out.println(pair.getKey().val + ": " + tmp + ",");
        }
    }
}

效率对比

设图中共有 n 个顶点和 m 条边，下表对比了邻接矩阵和邻接表的时间效率和空间效率

邻接矩阵 邻接表（链表） 邻接表（哈希表）
判断是否邻接 $O(1)$ $O(m)$ $O(1)$
添加边 $O(1)$ $O(1)$ $O(1)$
删除边 $O(1)$ $O(m)$ $O(1)$
添加顶点 $O(n)$ $O(1)$ $O(1)$
删除顶点 $O(n^2)$ $O(n + m)$ $O(n)$
内存空间占用 $O(n^2)$ $O(n + m)$ $O(n + m)$

似乎邻接表（哈希表）的时间效率与空间效率最优。但实际上，在邻接矩阵中操作边的效率更高，只需一次数组访问或赋值操作即可。综合来看，邻接矩阵体现了以空间换时间的原则，而邻接表体现了以时间换空间的原则。

图的遍历

树代表的是一对多的关系，而图则具有更高的自由度，可以表示任意的多对多关系。因此，我们可以把树看作图的一种特例。显然，树的遍历操作也是图的遍历操作的一种特例

图和树都需要应用搜索算法来实现遍历操作。图的遍历方式可分为两种：「广度优先遍历 breadth-first traversal」和「深度优先遍历 depth-first traversal」。它们也常被称为「广度优先搜索 breadth-first search」和「深度优先搜索 depth-first search」，简称 BFS 和 DFS

广度优先遍历

广度优先遍历是一种由近及远的遍历方式，从某个节点出发，始终优先访问距离最近的顶点，并一层层向外扩张。从左上角顶点出发，首先遍历该顶点的所有邻接顶点，然后遍历下一个顶点的所有邻接顶点，以此类推，直至所有顶点访问完毕。BFS 通常借助队列来实现，代码如下所示。队列具有先入先出的性质，这与 BFS 的由近及远的思想异曲同工

  • 将遍历起始顶点 startVet 加入队列，并开启循环
  • 在循环的每轮迭代中，弹出队首顶点并记录访问，然后将该顶点的所有邻接顶点加入到队列尾部
  • 循环步骤 2. ，直到所有顶点被访问完毕后结束
  • 为了防止重复遍历顶点，我们需要借助一个哈希表 visited 来记录哪些节点已被访问。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 广度优先遍历 BFS
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
List<Vertex> graphBFS(GraphAdjList graph, Vertex startVet) {
    // 顶点遍历序列
    List<Vertex> res = new ArrayList<>();
    // 哈希表，用于记录已被访问过的顶点
    Set<Vertex> visited = new HashSet<>();
    visited.add(startVet);
    // 队列用于实现 BFS
    Queue<Vertex> que = new LinkedList<>();
    que.offer(startVet);
    // 以顶点 vet 为起点，循环直至访问完所有顶点
    while (!que.isEmpty()) {
        Vertex vet = que.poll(); // 队首顶点出队
        res.add(vet);            // 记录访问顶点
        // 遍历该顶点的所有邻接顶点
        for (Vertex adjVet : graph.adjList.get(vet)) {
            if (visited.contains(adjVet))
                continue;        // 跳过已被访问的顶点
            que.offer(adjVet);   // 只入队未访问的顶点
            visited.add(adjVet); // 标记该顶点已被访问
        }
    }
    // 返回顶点遍历序列
    return res;
}

广度优先遍历的序列是否唯一？

不唯一。广度优先遍历只要求按由近及远的顺序遍历，而多个相同距离的顶点的遍历顺序允许被任意打乱

  • 时间复杂度：所有顶点都会入队并出队一次，使用 $O(|V|)$ 时间；在遍历邻接顶点的过程中，由于是无向图，因此所有边都会被访问 2 次，使用 $O(2|E|)$ 时间；总体使用 $O(|V| + |E|)$ 时间
  • 空间复杂度：列表 res ，哈希表 visited ，队列 que 中的顶点数量最多为 $|V|$，使用 $O(|V|)$ 空间

深度优先遍历

深度优先遍历是一种优先走到底，无路可走再回头的遍历方式。从左上角顶点出发，访问当前顶点的某个邻接顶点，直到走到尽头时返回，再继续走到尽头并返回，以此类推，直至所有顶点遍历完成。这种"走到尽头再返回"的算法范式通常基于递归来实现。与广度优先遍历类似，在深度优先遍历中，我们也需要借助一个哈希表 visited 来记录已被访问的顶点，以避免重复访问顶点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 深度优先遍历 DFS 辅助函数
void dfs(GraphAdjList graph, Set<Vertex> visited, List<Vertex> res, Vertex vet) {
    res.add(vet);     // 记录访问顶点
    visited.add(vet); // 标记该顶点已被访问
    // 遍历该顶点的所有邻接顶点
    for (Vertex adjVet : graph.adjList.get(vet)) {
        if (visited.contains(adjVet))
            continue; // 跳过已被访问的顶点
        // 递归访问邻接顶点
        dfs(graph, visited, res, adjVet);
    }
}

// 深度优先遍历 DFS
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
List<Vertex> graphDFS(GraphAdjList graph, Vertex startVet) {
    // 顶点遍历序列
    List<Vertex> res = new ArrayList<>();
    // 哈希表，用于记录已被访问过的顶点
    Set<Vertex> visited = new HashSet<>();
    dfs(graph, visited, res, startVet);
    return res;
}

深度优先遍历的序列是否唯一？

与广度优先遍历类似，深度优先遍历序列的顺序也不是唯一的。给定某顶点，先往哪个方向探索都可以，即邻接顶点的顺序可以任意打乱，都是深度优先遍历。以树的遍历为例，根 -> 左 -> 右，左 -> 根 -> 右，左 -> 右 -> 根分别对应前序，中序，后序遍历，它们展示了三种遍历优先级，然而这三者都属于深度优先遍历

  • 时间复杂度：所有顶点都会被访问 1 次，使用 $O(|V|)$ 时间；所有边都会被访问 2 次，使用 $O(2|E|)$ 时间；总体使用 $O(|V| + |E|)$ 时间
  • 空间复杂度：列表 res ，哈希表 visited 顶点数量最多为，递归深度最大为 $|V|$，因此使用 $O(|V|)$ 空间

Q & A

路径的定义是顶点序列还是边序列？

维基百科上不同语言版本的定义不一致：英文版是路径是一个边序列，而中文版是路径是一个顶点序列。以下是英文版原文：In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices. 在本文中，路径被视为一个边序列，而不是一个顶点序列。这是因为两个顶点之间可能存在多条边连接，此时每条边都对应一条路径

非连通图中是否会有无法遍历到的点？

在非连通图中，从某个顶点出发，至少有一个顶点无法到达。遍历非连通图需要设置多个起点，以遍历到图的所有连通分量

在邻接表中，"与该顶点相连的所有顶点"的顶点顺序是否有要求？

可以是任意顺序。但在实际应用中，可能需要按照指定规则来排序，比如按照顶点添加的次序，或者按照顶点值大小的顺序等，这样有助于快速查找带有某种极值的顶点

贪心

贪心策略在一轮轮的简单选择中，逐步导向最佳答案

贪心算法

「贪心算法 greedy algorithm」是一种常见的解决优化问题的算法，其基本思想是在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部最优的决策，以期获得全局最优解。贪心算法简洁且高效，在许多实际问题中有着广泛的应用。

贪心算法和动态规划都常用于解决优化问题。它们之间存在一些相似之处，比如都依赖最优子结构性质，但工作原理不同。

  • 动态规划会根据之前阶段的所有决策来考虑当前决策，并使用过去子问题的解来构建当前子问题的解。
  • 贪心算法不会考虑过去的决策，而是一路向前地进行贪心选择，不断缩小问题范围，直至问题被解决。

给定 n 种硬币，第 i 种硬币的面值为 coins[i - 1]，目标金额为 amt，每种硬币可以重复选取，问能够凑出目标金额的最少硬币数量。如果无法凑出目标金额则返回 -1

给定目标金额，我们贪心地选择不大于且最接近它的硬币，不断循环该步骤，直至凑出目标金额为止。实现代码如下所示。你可能会不由地发出感叹：So clean ！贪心算法仅用约十行代码就解决了零钱兑换问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 零钱兑换：贪心
int coinChangeGreedy(int[] coins, int amt) {
    // 假设 coins 列表有序
    int i = coins.length - 1;
    int count = 0;
    // 循环进行贪心选择，直到无剩余金额
    while (amt > 0) {
        // 找到小于且最接近剩余金额的硬币
        while (i > 0 && coins[i] > amt) {
            i--;
        }
        // 选择 coins[i]
        amt -= coins[i];
        count++;
    }
    // 若未找到可行方案，则返回 -1
    return amt == 0 ? count : -1;
}

贪心的优点与局限性

贪心算法不仅操作直接、实现简单，而且通常效率也很高。在以上代码中，记硬币最小面值为 min(coins)，则贪心选择最多循环 amt / min(coins) 次，时间复杂度为 $O(amt / min(coins))$。这比动态规划解法的时间复杂度 $O(n \times amt)$ 提升了一个数量级。然而，对于某些硬币面值组合，贪心算法并不能找到最优解：

  • 正例 coins = [1, 5, 10, 20, 50, 100]：在该硬币组合下，给定任意 amt，贪心算法都可以找到最优解
  • 反例 coins = [1, 20, 50]：假设 amt = 60，贪心算法只能找到 50 + 1 × 10 的兑换组合，共计 11 枚硬币，但动态规划可以找到最优解 20 + 20 + 20，仅需 3 枚硬币
  • 反例 coins = [1, 49, 50]：假设 amt = 98，贪心算法只能找到 50 + 1 × 48 的兑换组合，共计 49 枚硬币，但动态规划可以找到最优解 49 + 49，仅需 2 枚硬币

也就是说，对于零钱兑换问题，贪心算法无法保证找到全局最优解，并且有可能找到非常差的解。它更适合用动态规划解决。一般情况下，贪心算法的适用情况分以下两种：

  1. 可以保证找到最优解：贪心算法在这种情况下往往是最优选择，因为它往往比回溯、动态规划更高效。
  2. 可以找到近似最优解：贪心算法在这种情况下也是可用的。对于很多复杂问题来说，寻找全局最优解非常困难，能以较高效率找到次优解也是非常不错的。

贪心算法特性

那么问题来了，什么样的问题适合用贪心算法求解呢？或者说，贪心算法在什么情况下可以保证找到最优解？相较于动态规划，贪心算法的使用条件更加苛刻，其主要关注问题的两个性质：

  • 贪心选择性质：只有当局部最优选择始终可以导致全局最优解时，贪心算法才能保证得到最优解。
  • 最优子结构：原问题的最优解包含子问题的最优解。

有一篇论文给出了一个 $O(n^3)$ 时间复杂度的算法，用于判断一个硬币组合能否使用贪心算法找出任意金额的最优解。
Pearson, David. A polynomial-time algorithm for the change-making problem. Operations Research Letters 33.3 (2005): 231-234.

贪心解题步骤

贪心问题的解决流程大体可分为以下三步：

  1. 问题分析：梳理与理解问题特性，包括状态定义、优化目标和约束条件等。这一步在回溯和动态规划中都有涉及
  2. 确定贪心策略：确定如何在每一步中做出贪心选择。这个策略能够在每一步减小问题的规模，并最终解决整个问题
  3. 正确性证明：通常需要证明问题具有贪心选择性质和最优子结构。这个步骤可能需要用到数学证明，例如归纳法或反证法等

确定贪心策略是求解问题的核心步骤，但实施起来可能并不容易，主要有以下原因：

  • 不同问题的贪心策略的差异较大。对于许多问题来说，贪心策略比较浅显，我们通过一些大概的思考与尝试就能得出。而对于一些复杂问题，贪心策略可能非常隐蔽，这种情况就非常考验个人的解题经验与算法能力了
  • 某些贪心策略具有较强的迷惑性。当我们满怀信心设计好贪心策略，写出解题代码并提交运行，很可能发现部分测试样例无法通过。这是因为设计的贪心策略只是“部分正确”的，上文介绍的零钱兑换就是一个典型案例

为了保证正确性，我们应该对贪心策略进行严谨的数学证明，通常需要用到反证法或数学归纳法。然而，正确性证明也很可能不是一件易事。如若没有头绪，我们通常会选择面向测试用例进行代码调试，一步步修改与验证贪心策略

贪心典型例题

贪心算法常常应用在满足贪心选择性质和最优子结构的优化问题中，以下列举了一些典型的贪心算法问题：

  • 硬币找零问题：在某些硬币组合下，贪心算法总是可以得到最优解
  • 区间调度问题：假设你有一些任务，每个任务在一段时间内进行，你的目标是完成尽可能多的任务。如果每次都选择结束时间最早的任务，那么贪心算法就可以得到最优解
  • 分数背包问题：给定一组物品和一个载重量，你的目标是选择一组物品，使得总重量不超过载重量，且总价值最大。如果每次都选择性价比最高（价值 / 重量）的物品，那么贪心算法在一些情况下可以得到最优解
  • 股票买卖问题：给定一组股票的历史价格，你可以进行多次买卖，但如果你已经持有股票，那么在卖出之前不能再买，目标是获取最大利润
  • 霍夫曼编码：霍夫曼编码是一种用于无损数据压缩的贪心算法。通过构建霍夫曼树，每次选择出现频率最低的两个节点合并，最后得到的霍夫曼树的带权路径长度（编码长度）最小
  • Dijkstra 算法：它是一种解决给定源顶点到其余各顶点的最短路径问题的贪心算法

分数背包问题

给定 n 个物品，第 i 个物品的重量为 wgt[i - 1]、价值为 val[i - 1]，和一个容量为 cap 的背包。每个物品只能选择一次，但可以选择物品的一部分，价值根据选择的重量比例计算，问在限定背包容量下背包中物品的最大价值

分数背包问题和 0-1 背包问题整体上非常相似，状态包含当前物品 i 和容量 c，目标是求限定背包容量下的最大价值。不同点在于，本题允许只选择物品的一部分。我们可以对物品任意地进行切分，并按照重量比例来计算相应价值：

  1. 对于物品 i ，它在单位重量下的价值为 val[i - 1] / wgt[i - 1]，简称单位价值
  2. 假设放入一部分物品 i，重量为 w，则背包增加的价值为 w × val[i - 1] / wgt[i - 1]

贪心策略确定

最大化背包内物品总价值，本质上是最大化单位重量下的物品价值。由此便可推理出贪心策略

  1. 将物品按照单位价值从高到低进行排序。
  2. 遍历所有物品，每轮贪心地选择单位价值最高的物品。
  3. 若剩余背包容量不足，则使用当前物品的一部分填满背包。

代码实现

我们建立了一个物品类 Item ，以便将物品按照单位价值进行排序。循环进行贪心选择，当背包已满时跳出并返回解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 物品
class Item {
    int w; // 物品重量
    int v; // 物品价值

    public Item(int w, int v) {
        this.w = w;
        this.v = v;
    }
}

// 分数背包：贪心
double fractionalKnapsack(int[] wgt, int[] val, int cap) {
    // 创建物品列表，包含两个属性：重量、价值
    Item[] items = new Item[wgt.length];
    for (int i = 0; i < wgt.length; i++) {
        items[i] = new Item(wgt[i], val[i]);
    }
    // 按照单位价值 item.v / item.w 从高到低进行排序
    Arrays.sort(items, Comparator.comparingDouble(item -> -((double) item.v / item.w)));
    // 循环贪心选择
    double res = 0;
    for (Item item : items) {
        if (item.w <= cap) {
            // 若剩余容量充足，则将当前物品整个装进背包
            res += item.v;
            cap -= item.w;
        } else {
            // 若剩余容量不足，则将当前物品的一部分装进背包
            res += (double) item.v / item.w * cap;
            // 已无剩余容量，因此跳出循环
            break;
        }
    }
    return res;
}

在最差情况下，需要遍历整个物品列表，因此时间复杂度为 $O(n)$，其中 n 为物品数量。由于初始化了一个 Item 对象列表，因此空间复杂度为 $O(n)$

正确性证明

采用反证法。假设物品 x 是单位价值最高的物品，使用某算法求得最大价值为 res ，但该解中不包含物品 x。现在从背包中拿出单位重量的任意物品，并替换为单位重量的物品 x。由于物品 x 的单位价值最高，因此替换后的总价值一定大于 res 。这与 res 是最优解矛盾，说明最优解中必须包含物品 x。对于该解中的其他物品，我们也可以构建出上述矛盾。总而言之，单位价值更大的物品总是更优选择，这说明贪心策略是有效的

最大容量问题

输入一个数组 ht，其中的每个元素代表一个垂直隔板的高度。数组中的任意两个隔板，以及它们之间的空间可以组成一个容器。容器的容量等于高度和宽度的乘积（面积），其中高度由较短的隔板决定，宽度是两个隔板的数组索引之差。请在数组中选择两个隔板，使得组成的容器的容量最大，返回最大容量

容器由任意两个隔板围成，因此本题的状态为两个隔板的索引记为[i, j]。根据题意，容量等于高度乘以宽度，其中高度由短板决定，宽度是两隔板的数组索引之差。设容量为 cap[i, j]，则可得计算公式：

设数组长度为 n，两个隔板的组合数量（状态总数）为 $C_n^2 = \frac{n(n - 1)}{2}$ 个。最直接地，我们可以穷举所有状态，从而求得最大容量，时间复杂度为 $O(n^2)$

贪心策略确定

这道题还有更高效率的解法。现选取一个状态[i, j]，其满足索引 i < j 且高度 ht[i] < ht[j]，即 i 为短板、j 为长板。若此时将长板 j 向短板 i 靠近，则容量一定变小。这是因为在移动长板 j 后，宽度 j - i 肯定变小；而高度由短板决定，因此高度只可能不变（i 仍为短板）或变小（移动后的 j 成为短板）。

反向思考，我们只有向内收缩短板 i，才有可能使容量变大。因为虽然宽度一定变小，但高度可能会变大（移动后的短板 i 可能会变长）。由此便可推出本题的贪心策略：初始化两指针分列容器两端，每轮向内收缩短板对应的指针，直至两指针相遇

  1. 初始状态下，指针 i 和 j 分列与数组两端
  2. 计算当前状态的容量 cap[i, j]，并更新最大容量
  3. 比较板 i 和板 j 的高度，并将短板向内移动一格
  4. 循环执行第 2. 步和第 3. 步，直至 i 和 j 相遇时结束

代码实现

代码循环最多 n 轮，因此时间复杂度为 $O(n)$。变量 i、j、res 使用常数大小的额外空间，因此空间复杂度为 $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 最大容量：贪心
int maxCapacity(int[] ht) {
    // 初始化 i, j 分列数组两端
    int i = 0, j = ht.length - 1;
    // 初始最大容量为 0
    int res = 0;
    // 循环贪心选择，直至两板相遇
    while (i < j) {
        // 更新最大容量
        int cap = Math.min(ht[i], ht[j]) * (j - i);
        res = Math.max(res, cap);
        // 向内移动短板
        if (ht[i] < ht[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
}

正确性证明

之所以贪心比穷举更快，是因为每轮的贪心选择都会"跳过"一些状态。比如在状态 cap[i, j]下，i 为短板、j 为长板。若贪心地将短板 i 向内移动一格，这意味着之后无法验证这些状态的容量大小。

观察发现，这些被跳过的状态实际上就是将长板 j 向内移动的所有状态。前面我们已经证明内移长板一定会导致容量变小。也就是说，被跳过的状态都不可能是最优解，跳过它们不会导致错过最优解。以上分析说明，移动短板的操作是“安全”的，贪心策略是有效的

最大切分乘积问题

给定一个正整数 n，将其切分为至少两个正整数的和，求切分后所有整数的乘积最大是多少？

假设我们将 n 切分为 m 个整数因子，其中第 i 个因子记为 $n_i$，我们需要思考的是：切分数量 m 应该多大，每个 $n_i$ 应该是多少？

贪心策略确定

根据经验，两个整数的乘积往往比它们的加和更大。假设从 n 中分出一个因子 2，则它们的乘积为 2(n - 1)。我们将该乘积与 n 作比较：

当 n $\geq$ 4 时，切分出一个 2 后乘积会变大，这说明大于等于 4 的整数都应该被切分。

贪心策略一

如果切分方案中包含 $\geq$ 4 的因子，那么它就应该被继续切分。最终的切分方案只应出现 1、2、3 这三种因子。接下来思考哪个因子是最优的。在 1、2、3 这三个因子中，显然 1 是最差的，因为 1 × (n - 1) < n 恒成立，即切分出 1 反而会导致乘积减小。当 n = 6 时，有 3 × 3 > 2 × 2 × 2。这意味着切分出 3 比切分出 2 更优

贪心策略二

在切分方案中，最多只应存在两个 2。因为三个 2 总是可以替换为两个 3，从而获得更大的乘积。综上所述，可推理出以下贪心策略：

  1. 输入整数 n，从其不断地切分出因子 3，直至余数为 0、1、2
  2. 当余数为 0 时，代表 n 是 3 的倍数，因此不做任何处理
  3. 当余数为 2 时，不继续划分，保留之
  4. 当余数为 1 时，由于 2 × 2 > 1 × 3，因此应将最后一个 3 替换为 2

代码实现

我们无须通过循环来切分整数，而可以利用向下整除运算得到 3 的个数 a，用取模运算得到余数 b，此时有：n = 3a + b。请注意，对于 n $\leq$ 3 的边界情况，必须拆分出一个 1，乘积为 1 × (n - 1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 最大切分乘积：贪心
int maxProductCutting(int n) {
    // 当 n <= 3 时，必须切分出一个 1
    if (n <= 3) {
        return 1 * (n - 1);
    }
    // 贪心地切分出 3 ，a 为 3 的个数，b 为余数
    int a = n / 3;
    int b = n % 3;
    if (b == 1) {
        // 当余数为 1 时，将一对 1 * 3 转化为 2 * 2
        return (int) Math.pow(3, a - 1) * 2 * 2;
    }
    if (b == 2) {
        // 当余数为 2 时，不做处理
        return (int) Math.pow(3, a) * 2;
    }
    // 当余数为 0 时，不做处理
    return (int) Math.pow(3, a);
}

正确性证明

使用反证法，只分析 n $\geq$ 3 的情况

  1. 所有因子 $\leq$ 3 ：假设最优切分方案中存在 $\geq$ 4 的因子 x ，那么一定可以将其继续划分为 2(x - 2)，从而获得更大的乘积。这与假设矛盾
  2. 切分方案不包含 1：假设最优切分方案中存在一个因子 1，那么它一定可以合并入另外一个因子中，以获得更大的乘积。这与假设矛盾
  3. 切分方案最多包含两个 2：假设最优切分方案中包含三个 2，那么一定可以替换为两个 3，乘积更大。这与假设矛盾

动态规划

初探动态规划

「动态规划 dynamic programming」是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。在本节中，我们从一个经典例题入手，先给出它的暴力回溯解法，观察其中包含的重叠子问题，再逐步导出更高效的动态规划解法

给定一个共有 n 阶的楼梯，你每步可以上 1 阶或者 2 阶，请问有多少种方案可以爬到楼顶？

本题的目标是求解方案数量，我们可以考虑通过回溯来穷举所有可能性。具体来说，将爬楼梯想象为一个多轮选择的过程：从地面出发，每轮选择上 1 阶或 2 阶，每当到达楼梯顶部时就将方案数量加 1，当越过楼梯顶部时就将其剪枝。代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 回溯
void backtrack(List<Integer> choices, int state, int n, List<Integer> res) {
    // 当爬到第 n 阶时，方案数量加 1
    if (state == n)
        res.set(0, res.get(0) + 1);
    // 遍历所有选择
    for (Integer choice : choices) {
        // 剪枝：不允许越过第 n 阶
        if (state + choice > n)
            continue;
        // 尝试：做出选择，更新状态
        backtrack(choices, state + choice, n, res);
        // 回退
    }
}

// 爬楼梯：回溯
int climbingStairsBacktrack(int n) {
    List<Integer> choices = Arrays.asList(1, 2); // 可选择向上爬 1 阶或 2 阶
    int state = 0; // 从第 0 阶开始爬
    List<Integer> res = new ArrayList<>();
    res.add(0); // 使用 res[0] 记录方案数量
    backtrack(choices, state, n, res);
    return res.get(0);
}

方法一：暴力搜索

回溯算法通常并不显式地对问题进行拆解，而是将求解问题看作一系列决策步骤，通过试探和剪枝，搜索所有可能的解。

我们可以尝试从问题分解的角度分析这道题。设爬到第 i 阶共有 dp[i] 种方案，那么 dp[i] 就是原问题，其子问题包括：

由于每轮只能上 1 阶或 2 阶，因此当我们站在第 i 阶楼梯上时，上一轮只可能站在第 i - 1 阶或第 i - 2 阶上。换句话说，我们只能从第 i - 1 阶或第 i - 2 阶迈向第 i 阶。由此便可得出一个重要推论：爬到第 i - 1 阶的方案数加上爬到第 i - 2 阶的方案数就等于爬到第 i 阶的方案数。公式如下：

这意味着在爬楼梯问题中，各个子问题之间存在递推关系，原问题的解可以由子问题的解构建得来。我们可以根据递推公式得到暴力搜索解法。以 dp[n] 为起始点，递归地将一个较大问题拆解为两个较小问题的和，直至到达最小子问题 dp[1] 和 dp[2] 时返回。其中，最小子问题的解是已知的，即 dp[1] = 1、dp[2] = 2，表示爬到第 1、2 阶分别有 1、2 种方案。观察以下代码，它和标准回溯代码都属于深度优先搜索，但更加简洁：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 搜索
int dfs(int i) {
    // 已知 dp[1] 和 dp[2] ，返回之
    if (i == 1 || i == 2)
        return i;
    // dp[i] = dp[i-1] + dp[i-2]
    int count = dfs(i - 1) + dfs(i - 2);
    return count;
}

// 爬楼梯：搜索
int climbingStairsDFS(int n) {
    return dfs(n);
}

对于问题 dp[n]，其递归树的深度为 n，时间复杂度为 $O(2^n)$。指数阶属于爆炸式增长，如果我们输入一个比较大的 n，则会陷入漫长的等待之中。指数阶的时间复杂度是重叠子问题导致的。例如 dp[9] 被分解为 dp[8] 和 dp[7]，dp[8] 被分解为 dp[7] 和 dp[6]，两者都包含子问题 dp[7]。以此类推，子问题中包含更小的重叠子问题，子子孙孙无穷尽也。绝大部分计算资源都浪费在这些重叠的问题上。

方法二：记忆化搜索

为了提升算法效率，我们希望所有的重叠子问题都只被计算一次。为此，我们声明一个数组 mem 来记录每个子问题的解，并在搜索过程中将重叠子问题剪枝

  1. 当首次计算 dp[i] 时，我们将其记录至 mem[i] ，以便之后使用
  2. 当再次需要计算 dp[i] 时，我们便可直接从 mem[i] 中获取结果，从而避免重复计算该子问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 记忆化搜索
int dfs(int i, int[] mem) {
    // 已知 dp[1] 和 dp[2] ，返回之
    if (i == 1 || i == 2)
        return i;
    // 若存在记录 dp[i] ，则直接返回之
    if (mem[i] != -1)
        return mem[i];
    // dp[i] = dp[i-1] + dp[i-2]
    int count = dfs(i - 1, mem) + dfs(i - 2, mem);
    // 记录 dp[i]
    mem[i] = count;
    return count;
}

// 爬楼梯：记忆化搜索
int climbingStairsDFSMem(int n) {
    // mem[i] 记录爬到第 i 阶的方案总数，-1 代表无记录
    int[] mem = new int[n + 1];
    Arrays.fill(mem, -1);
    return dfs(n, mem);
}

经过记忆化处理后，所有重叠子问题都只需计算一次，时间复杂度优化至 $O(n)$，这是一个巨大的飞跃

方法三：动态规划

记忆化搜索是一种"从顶至底"的方法：我们从原问题（根节点）开始，递归地将较大子问题分解为较小子问题，直至解已知的最小子问题（叶节点）。之后，通过回溯逐层收集子问题的解，构建出原问题的解。

与之相反，动态规划是一种"从底至顶"的方法：从最小子问题的解开始，迭代地构建更大子问题的解，直至得到原问题的解。

由于动态规划不包含回溯过程，因此只需使用循环迭代实现，无须使用递归。在以下代码中，我们初始化一个数组 dp 来存储子问题的解，它起到了与记忆化搜索中数组 mem 相同的记录作用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 爬楼梯：动态规划
int climbingStairsDP(int n) {
    if (n == 1 || n == 2)
        return n;
    // 初始化 dp 表，用于存储子问题的解
    int[] dp = new int[n + 1];
    // 初始状态：预设最小子问题的解
    dp[1] = 1;
    dp[2] = 2;
    // 状态转移：从较小子问题逐步求解较大子问题
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

与回溯算法一样，动态规划也使用"状态"概念来表示问题求解的特定阶段，每个状态都对应一个子问题以及相应的局部最优解。例如，爬楼梯问题的状态定义为当前所在楼梯阶数 i。根据以上内容，我们可以总结出动态规划的常用术语：

  • 将数组 dp 称为「 dp 表」，dp[i] 表示状态 i 对应子问题的解
  • 将最小子问题对应的状态（第 1 阶和第 2 阶楼梯）称为「初始状态」
  • 将递推公式 dp[i] = dp[i - 1] + dp[i - 2] 称为「状态转移方程」

空间优化

由于 dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关，因此我们无须使用一个数组 dp 来存储所有子问题的解，而只需两个变量滚动前进即可。代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
// 爬楼梯：空间优化后的动态规划
int climbingStairsDPComp(int n) {
    if (n == 1 || n == 2)
        return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        int tmp = b;
        b = a + b;
        a = tmp;
    }
    return b;
}

观察以上代码，由于省去了数组 dp 占用的空间，因此空间复杂度从 $O(n)$ 降至 $O(1)$。在动态规划问题中，当前状态往往仅与前面有限个状态有关，这时我们可以只保留必要的状态，通过"降维"来节省内存空间。这种空间优化技巧被称为滚动变量或滚动数组

DP问题特性

在上一节中，我们学习了动态规划是如何通过子问题分解来求解原问题的。实际上，子问题分解是一种通用的算法思路，在分治、动态规划、回溯中的侧重点不同

  • 分治算法递归地将原问题划分为多个相互独立的子问题，直至最小子问题，并在回溯中合并子问题的解，最终得到原问题的解
  • 动态规划也对问题进行递归分解，但与分治算法的主要区别是，动态规划中的子问题是相互依赖的，在分解过程中会出现许多重叠子问题
  • 回溯算法在尝试和回退中穷举所有可能的解，并通过剪枝避免不必要的搜索分支。原问题的解由一系列决策步骤构成，我们可以将每个决策步骤之前的子序列看作一个子问题

实际上，动态规划常用来求解最优化问题，它们不仅包含重叠子问题，还具有另外两大特性：最优子结构、无后效性

最优子结构

给定一个楼梯，你每步可以上 1 阶或者 2 阶，每一阶楼梯上都贴有一个非负整数，表示你在该台阶所需要付出的代价。给定一个非负整数数组 cost，其中 cost[i] 表示在第 i 个台阶需要付出的代价，cost[0] 为地面（起始点）。请计算最少需要付出多少代价才能到达顶部？

设 dp[i] 为爬到第 i 阶累计付出的代价，由于第 i 阶只可能从 i - 1 阶或 i - 2 阶走来，因此 dp[i] 只可能等于 dp[i - 1] + cost[i] 或 dp[i - 2] + cost[i]。为了尽可能减少代价，我们应该选择两者中较小的那一个：dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]。这便可以引出最优子结构的含义：原问题的最优解是从子问题的最优解构建得来的。本题显然具有最优子结构：我们从两个子问题最优解 dp[i - 1] 和 dp[i - 2] 中挑选出较优的那一个，并用它构建出原问题 do[i] 的最优解。根据状态转移方程，以及初始状态 dp[1] = cost[1] 和 dp[2] = cost[2]，我们就可以得到动态规划代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 爬楼梯最小代价：动态规划
int minCostClimbingStairsDP(int[] cost) {
    int n = cost.length - 1;
    if (n == 1 || n == 2)
        return cost[n];
    // 初始化 dp 表，用于存储子问题的解
    int[] dp = new int[n + 1];
    // 初始状态：预设最小子问题的解
    dp[1] = cost[1];
    dp[2] = cost[2];
    // 状态转移：从较小子问题逐步求解较大子问题
    for (int i = 3; i <= n; i++) {
        dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    return dp[n];
}

本题也可以进行空间优化，将一维压缩至零维，使得空间复杂度从 $O(n)$ 降至 $O(1)$：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 爬楼梯最小代价：空间优化后的动态规划
int minCostClimbingStairsDPComp(int[] cost) {
    int n = cost.length - 1;
    if (n == 1 || n == 2)
        return cost[n];
    int a = cost[1], b = cost[2];
    for (int i = 3; i <= n; i++) {
        int tmp = b;
        b = Math.min(a, tmp) + cost[i];
        a = tmp;
    }
    return b;
}

无后效性

无后效性是动态规划能够有效解决问题的重要特性之一，其定义为：给定一个确定的状态，它的未来发展只与当前状态有关，而与过去经历的所有状态无关。

以爬楼梯问题为例，给定状态 i，它会发展出状态 i + 1 和状态 i + 2，分别对应跳 1 步和跳 2 步。在做出这两种选择时，我们无须考虑状态 i 之前的状态，它们对状态 i 的未来没有影响。然而，如果我们给爬楼梯问题添加一个约束，情况就不一样了

给定一个共有 n 阶的楼梯，你每步可以上 1 阶或者 2 阶，但不能连续两轮跳 1 阶，请问有多少种方案可以爬到楼顶？

在该问题中，如果上一轮是跳 1 阶上来的，那么下一轮就必须跳 2 阶。这意味着，下一步选择不能由当前状态（当前所在楼梯阶数）独立决定，还和前一个状态（上轮所在楼梯阶数）有关。

不难发现，此问题已不满足无后效性，状态转移方程 dp[i] = do[i - 1] + dp[i - 2] 也失效了，因为 dp[i - 1] 代表本轮跳 1 阶，但其中包含了许多"上一轮是跳 1 阶上来的"方案，而为了满足约束，我们就不能将 dp[i - 1] 直接计入 dp[i] 中

为此，我们需要扩展状态定义：状态 [i, j] 表示处在第 i 阶并且上一轮跳了 j 阶，其中 j $\in$ {1, 2}。此状态定义有效地区分了上一轮跳了 1 阶还是 2 阶，我们可以据此来判断当前状态是从何而来的。

  • 当上一轮跳了 1 阶时，上上一轮只能选择跳 2 阶，即 dp[i, 1] 只能从 dp[i - 1, 2] 转移过来
  • 当上一轮跳了 2 阶时，上上一轮可选择跳 1 阶或跳 2 阶，即 dp[i, 2] 可以从 dp[i - 2, 1] 或 dp[i - 2, 2] 转移过来

在该定义下，dp[i, j] 表示状态 [i, j] 对应的方案数。此时状态转移方程为：1. dp[i, 1] = dp[i - 1, 2]，2. dp[i, 2] = dp[i - 2, 1] + dp[i - 2, 2]。最终，返回 dp[n, 1] + dp[n, 2] 即可，两者之和代表爬到第 n 阶的方案总数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 带约束爬楼梯：动态规划
int climbingStairsConstraintDP(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    // 初始化 dp 表，用于存储子问题的解
    int[][] dp = new int[n + 1][3];
    // 初始状态：预设最小子问题的解
    dp[1][1] = 1;
    dp[1][2] = 0;
    dp[2][1] = 0;
    dp[2][2] = 1;
    // 状态转移：从较小子问题逐步求解较大子问题
    for (int i = 3; i <= n; i++) {
        dp[i][1] = dp[i - 1][2];
        dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
    }
    return dp[n][1] + dp[n][2];
}

在上面的案例中，由于仅需多考虑前面一个状态，因此我们仍然可以通过扩展状态定义，使得问题重新满足无后效性。然而，某些问题具有非常严重的有后效性。

给定一个共有 n 阶的楼梯，你每步可以上 1 阶或者 2 阶。规定当爬到第 i 阶时，系统自动会在第 2i 阶上放上障碍物，之后所有轮都不允许跳到第 2i 阶上。例如，前两轮分别跳到了第 2、3 阶上，则之后就不能跳到第 4、6 阶上。请问有多少种方案可以爬到楼顶？

在这个问题中，下次跳跃依赖过去所有的状态，因为每一次跳跃都会在更高的阶梯上设置障碍，并影响未来的跳跃。对于这类问题，动态规划往往难以解决

实际上，许多复杂的组合优化问题（例如旅行商问题）不满足无后效性。对于这类问题，我们通常会选择使用其他方法，例如启发式搜索、遗传算法、强化学习等，从而在有限时间内得到可用的局部最优解

DP解题思路

问题判断

总的来说，如果一个问题包含重叠子问题、最优子结构，并满足无后效性，那么它通常适合用动态规划求解。然而，我们很难从问题描述中直接提取出这些特性。因此我们通常会放宽条件，先观察问题是否适合使用回溯（穷举）解决。适合用回溯解决的问题通常满足决策树模型，这种问题可以使用树形结构来描述，其中每一个节点代表一个决策，每一条路径代表一个决策序列。换句话说，如果问题包含明确的决策概念，并且解是通过一系列决策产生的，那么它就满足决策树模型，通常可以使用回溯来解决。在此基础上，动态规划问题还有一些判断的"加分项"：

  • 问题包含最大（小）或最多（少）等最优化描述
  • 问题的状态能够使用一个列表、多维矩阵或树来表示，并且一个状态与其周围的状态存在递推关系

相应地，也存在一些"减分项"：

  • 问题的目标是找出所有可能的解决方案，而不是找出最优解
  • 问题描述中有明显的排列组合的特征，需要返回具体的多个方案

如果一个问题满足决策树模型，并具有较为明显的"加分项"，我们就可以假设它是一个动态规划问题，并在求解过程中验证它

问题求解步骤

动态规划的解题流程会因问题的性质和难度而有所不同，但通常遵循以下步骤：描述决策，定义状态，建立 dp 表，推导状态转移方程，确定边界条件等。为了更形象地展示解题步骤，我们使用一个经典问题最小路径和来举例：

给定一个 n × m 的二维网格 grid ，网格中的每个单元格包含一个非负整数，表示该单元格的代价。机器人以左上角单元格为起始点，每次只能向下或者向右移动一步，直至到达右下角单元格。请返回从左上角到右下角的最小路径和

  • 第一步：思考每轮的决策，定义状态，从而得到 dp 表

本题的每一轮的决策就是从当前格子向下或向右走一步。设当前格子的行列索引为 [i, j]，则向下或向右走一步后，索引变为 [i + 1, j] 或 [i, j + 1]。因此，状态应包含行索引和列索引两个变量，记为 [i, j]。状态 [i, j] 对应的子问题为：从起始点 [0, 0] 走到 [i, j] 的最小路径和，解记为 dp[i, j]

动态规划和回溯过程可以描述为一个决策序列，而状态由所有决策变量构成。它应当包含描述解题进度的所有变量，其包含了足够的信息，能够用来推导出下一个状态
每个状态都对应一个子问题，我们会定义一个 dp 表来存储所有子问题的解，状态的每个独立变量都是 dp 表的一个维度。从本质上看，dp 表是状态和子问题的解之间的映射

  • 第二步：找出最优子结构，进而推导出状态转移方程

对于状态 [i, j]，它只能从上边格子 [i - 1, j] 和左边格子 [i, j - 1] 转移而来。因此最优子结构为：到达 [i, j] 的最小路径和由 [i, j - 1] 的最小路径和与 [i - 1, j] 的最小路径和中较小的那一个决定。根据以上分析，可推出状态转移方程：dp[i, j] = min(dp[i - 1, j], dp[i, j - 1]) + grid[i, j]

根据定义好的 dp 表，思考原问题和子问题的关系，找出通过子问题的最优解来构造原问题的最优解的方法，即最优子结构。一旦我们找到了最优子结构，就可以使用它来构建出状态转移方程

  • 第三步：确定边界条件和状态转移顺序

在本题中，处在首行的状态只能从其左边的状态得来，处在首列的状态只能从其上边的状态得来，因此首行 i = 0 和首列 j = 0 是边界条件。由于每个格子是由其左方格子和上方格子转移而来，因此我们使用循环来遍历矩阵，外循环遍历各行，内循环遍历各列

边界条件在动态规划中用于初始化 dp 表，在搜索中用于剪枝。状态转移顺序的核心是要保证在计算当前问题的解时，所有它依赖的更小子问题的解都已经被正确地计算出来

根据以上分析，我们已经可以直接写出动态规划代码。然而子问题分解是一种从顶至底的思想，因此按照暴力搜索 -> 记忆化搜索 -> 动态规划的顺序实现更加符合思维习惯

方法一：暴力搜索

从状态 [i, j] 开始搜索，不断分解为更小的状态 [i - 1, j] 和 [i, j - 1]，递归函数包括以下要素：

  • 递归参数：状态 [i, j]
  • 返回值：从 [0, 0] 到 [i, j] 的最小路径和 dp[i, j]
  • 终止条件：当 i = 0 且 j = 0 时，返回代价 grid[0, 0]
  • 剪枝：当 i < 0 时或 j < 0 时索引越界，此时返回代价+∞，代表不可行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 最小路径和：暴力搜索
int minPathSumDFS(int[][] grid, int i, int j) {
    // 若为左上角单元格，则终止搜索
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // 若行列索引越界，则返回 +∞ 代价
    if (i < 0 || j < 0) {
        return Integer.MAX_VALUE;
    }
    // 计算从左上角到 (i - 1, j) 和 (i, j - 1) 的最小路径代价
    int up = minPathSumDFS(grid, i - 1, j);
    int left = minPathSumDFS(grid, i, j - 1);
    // 返回从左上角到 (i, j) 的最小路径代价
    return Math.min(left, up) + grid[i][j];
}

每个状态都有向下和向右两种选择，从左上角走到右下角总共需要 m + n - 2 步，所以最差时间复杂度为 $O(2^{m+n})$。请注意，这种计算方式未考虑临近网格边界的情况，当到达网络边界时只剩下一种选择，因此实际的路径数量会少一些

方法二：记忆化搜索

我们引入一个和网格 grid 相同尺寸的记忆列表 mem ，用于记录各个子问题的解，并将重叠子问题进行剪枝：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 最小路径和：记忆化搜索
int minPathSumDFSMem(int[][] grid, int[][] mem, int i, int j) {
    // 若为左上角单元格，则终止搜索
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // 若行列索引越界，则返回 +∞ 代价
    if (i < 0 || j < 0) {
        return Integer.MAX_VALUE;
    }
    // 若已有记录，则直接返回
    if (mem[i][j] != -1) {
        return mem[i][j];
    }
    // 左边和上边单元格的最小路径代价
    int up = minPathSumDFSMem(grid, mem, i - 1, j);
    int left = minPathSumDFSMem(grid, mem, i, j - 1);
    // 记录并返回左上角到 (i, j) 的最小路径代价
    mem[i][j] = Math.min(left, up) + grid[i][j];
    return mem[i][j];
}

在引入记忆化后，所有子问题的解只需计算一次，因此时间复杂度取决于状态总数，即网格尺寸 $O(nm)$

方法三：动态规划

基于迭代实现动态规划解法，代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 最小路径和：动态规划
int minPathSumDP(int[][] grid) {
    int n = grid.length, m = grid[0].length;
    // 初始化 dp 表
    int[][] dp = new int[n][m];
    dp[0][0] = grid[0][0];
    // 状态转移：首行
    for (int j = 1; j < m; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    // 状态转移：首列
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    // 状态转移：其余行和列
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
        }
    }
    return dp[n - 1][m - 1];
}

时间复杂度为 $O(nm)$。数组 dp 大小为 n × m，因此空间复杂度为 $O(nm)$

空间优化

由于每个格子只与其左边和上边的格子有关，因此我们可以只用一个单行数组来实现 dp 表。请注意，因为数组 dp 只能表示一行的状态，所以我们无法提前初始化首列状态，而是在遍历每行时更新它：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 最小路径和：空间优化后的动态规划
int minPathSumDPComp(int[][] grid) {
    int n = grid.length, m = grid[0].length;
    // 初始化 dp 表
    int[] dp = new int[m];
    // 状态转移：首行
    dp[0] = grid[0][0];
    for (int j = 1; j < m; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    // 状态转移：其余行
    for (int i = 1; i < n; i++) {
        // 状态转移：首列
        dp[0] = dp[0] + grid[i][0];
        // 状态转移：其余列
        for (int j = 1; j < m; j++) {
            dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
        }
    }
    return dp[m - 1];
}

0-1 背包问题

背包问题是一个非常好的动态规划入门题目，是动态规划中最常见的问题形式。其具有很多变种，例如 0-1 背包问题、完全背包问题、多重背包问题等

给定 n 个物品，第 i 个物品的重量为 wgt[i - 1]、价值为 val[i - 1]，和一个容量为 cap 的背包。每个物品只能选择一次，问在限定背包容量下能放入物品的最大价值？

由于物品编号 i 从 1 开始计数，数组索引从 0 开始计数，因此物品 i 对应重量 wgt[i - 1] 和价值 val[i - 1]。我们可以将 0-1 背包问题看作一个由 n 轮决策组成的过程，对于每个物体都有不放入和放入两种决策，因此该问题满足决策树模型。该问题的目标是求解在限定背包容量下能放入物品的最大价值，因此较大概率是一个动态规划问题

  • 第一步：思考每轮的决策，定义状态，从而得到 dp 表

对于每个物品来说，不放入背包，背包容量不变；放入背包，背包容量减小。由此可得状态定义：当前物品编号 i 和剩余背包容量 c，记为 [i, c]。状态 [i, c] 对应的子问题为：前 i 个物品在剩余容量为 c 的背包中的最大价值，记为 dp[i, c]。待求解的是 dp[n, cap]，因此需要一个尺寸为 (n + 1) × (cap + 1) 的二维 dp 表

  • 第二步：找出最优子结构，进而推导出状态转移方程

当我们做出物品 i 的决策后，剩余的是前 i - 1 个物品的决策，可分为以下两种情况

  • 不放入物品 i：背包容量不变，状态变化为 [i - 1, c]
  • 放入物品 i：背包容量减少 wgt[i - 1]，价值增加 val[i - 1]，状态变化为[i - 1, c - wgt[]i - 1]

上述分析向我们揭示了本题的最优子结构：最大价值 dp[i。由此可推导出状态转移方程：dp[i, c] = max(dp[i - 1, c], dp[i - 1, c - wgt[i - 1]] + val[i - 1])。需要注意的是，若当前物品重量 wgt[i - 1] 超出剩余背包容量 c，则只能选择不放入背包

  • 第三步：确定边界条件和状态转移顺序

当无物品或无剩余背包容量时最大价值为 0，即首列 dp[i, 0] 和首行 dp[0, c] 都等于 0。

当前状态 [i, c] 从上方的状态 [i - 1, c] 和左上方的状态 [i - 1, c - wgt[i - 1]] 转移而来，因此通过两层循环正序遍历整个 dp 表即可。根据以上分析，我们接下来按顺序实现暴力搜索、记忆化搜索、动态规划解法

方法一：暴力搜索

搜索代码包含以下要素：

  • 递归参数：状态 [i, c]
  • 返回值：子问题的解 dp[i, c]
  • 终止条件：当物品编号越界 i = 0 或背包剩余容量为 0 时，终止递归并返回价值 0
  • 剪枝：若当前物品重量超出背包剩余容量，则只能选择不放入背包
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 0-1 背包：暴力搜索
int knapsackDFS(int[] wgt, int[] val, int i, int c) {
    // 若已选完所有物品或背包无剩余容量，则返回价值 0
    if (i == 0 || c == 0) {
        return 0;
    }
    // 若超过背包容量，则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFS(wgt, val, i - 1, c);
    }
    // 计算不放入和放入物品 i 的最大价值
    int no = knapsackDFS(wgt, val, i - 1, c);
    int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 返回两种方案中价值更大的那一个
    return Math.max(no, yes);
}

由于每个物品都会产生不选和选两条搜索分支，因此时间复杂度为 $O(2^n)$。观察容易发现其中存在重叠子问题。当物品较多、背包容量较大，尤其是相同重量的物品较多时，重叠子问题的数量将会大幅增多

方法二：记忆化搜索

为了保证重叠子问题只被计算一次，我们借助记忆列表 mem 来记录子问题的解，其中 mem[i][c] 对应 dp[i, c]。引入记忆化之后，时间复杂度取决于子问题数量，也就是 $O(ncap)$。实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 0-1 背包：记忆化搜索
int knapsackDFSMem(int[] wgt, int[] val, int[][] mem, int i, int c) {
    // 若已选完所有物品或背包无剩余容量，则返回价值 0
    if (i == 0 || c == 0) {
        return 0;
    }
    // 若已有记录，则直接返回
    if (mem[i][c] != -1) {
        return mem[i][c];
    }
    // 若超过背包容量，则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFSMem(wgt, val, mem, i - 1, c);
    }
    // 计算不放入和放入物品 i 的最大价值
    int no = knapsackDFSMem(wgt, val, mem, i - 1, c);
    int yes = knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 记录并返回两种方案中价值更大的那一个
    mem[i][c] = Math.max(no, yes);
    return mem[i][c];
}

方法三：动态规划

动态规划实质上就是在状态转移中填充 dp 表的过程，代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 0-1 背包：动态规划
int knapsackDP(int[] wgt, int[] val, int cap) {
    int n = wgt.length;
    // 初始化 dp 表
    int[][] dp = new int[n + 1][cap + 1];
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[i][c] = Math.max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[n][cap];
}

时间复杂度和空间复杂度都由数组 dp 大小决定，即 $O(ncap)$

空间优化

由于每个状态都只与其上一行的状态有关，因此我们可以使用两个数组滚动前进，将空间复杂度从 $O(n^2)$ 降至 $O(n)$。进一步思考，我们能否仅用一个数组实现空间优化呢？观察可知，每个状态都是由正上方或左上方的格子转移过来的。假设只有一个数组，当开始遍历第 i 行时，该数组存储的仍然是第 i - 1 行的状态

  • 如果采取正序遍历，那么遍历到 dp[i, j] 时，左上方 dp[i - 1, 1] ~ dp[i - 1, j - 1] 值可能已经被覆盖，此时就无法得到正确的状态转移结果
  • 如果采取倒序遍历，则不会发生覆盖问题，状态转移可以正确进行

在代码实现中，我们仅需将数组 dp 的第一维 i 直接删除，并且把内循环更改为倒序遍历即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 0-1 背包：空间优化后的动态规划
int knapsackDPComp(int[] wgt, int[] val, int cap) {
    int n = wgt.length;
    // 初始化 dp 表
    int[] dp = new int[cap + 1];
    // 状态转移
    for (int i = 1; i <= n; i++) {
        // 倒序遍历
        for (int c = cap; c >= 1; c--) {
            if (wgt[i - 1] <= c) {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}

完全背包问题

给定 n 个物品，第 i 个物品的重量为 wgt[i - 1]、价值为 val[i - 1]，和一个容量为 cap 的背包。每个物品可以重复选取，问在限定背包容量下能放入物品的最大价值？

动态规划思路

完全背包问题和 0-1 背包问题非常相似，区别仅在于不限制物品的选择次数：

  • 在 0-1 背包问题中，每种物品只有一个，因此将物品 i 放入背包后，只能从前 i - 1 个物品中选择
  • 在完全背包问题中，每种物品的数量是无限的，因此将物品 i 放入背包后，仍可以从前 i 个物品中选择

在完全背包问题的规定下，状态 [i, c] 的变化分为两种情况：

  • 不放入物品 i：与 0-1 背包问题相同，转移至 [i - 1, c]
  • 放入物品 i：与 0-1 背包问题不同，转移至 [i, c - wgt[i - 1]]

从而状态转移方程变为：dp[i, c] = max(dp[i - 1, c], dp[i, c - wgt[i - 1]] + val[i - 1])

代码实现

对比两道题目的代码，状态转移中有一处从 i - 1 变为 i，其余完全一致：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 完全背包：动态规划
int unboundedKnapsackDP(int[] wgt, int[] val, int cap) {
    int n = wgt.length;
    // 初始化 dp 表
    int[][] dp = new int[n + 1][cap + 1];
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[i][c] = Math.max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[n][cap];
}

空间优化

由于当前状态是从左边和上边的状态转移而来的，因此空间优化后应该对 dp 表中的每一行进行正序遍历。这个遍历顺序与 0-1 背包正好相反。代码实现比较简单，仅需将数组 dp 的第一维删除：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 完全背包：空间优化后的动态规划
int unboundedKnapsackDPComp(int[] wgt, int[] val, int cap) {
    int n = wgt.length;
    // 初始化 dp 表
    int[] dp = new int[cap + 1];
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[c] = dp[c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}

分治

「分治 divide and conquer」，全称分而治之，是一种非常重要且常见的算法策略。分治通常基于递归实现，包括"分"和"治"两个步骤：

  1. 分（划分阶段）：递归地将原问题分解为两个或多个子问题，直至到达最小子问题时终止
  2. 治（合并阶段）：从已知解的最小子问题开始，从底至顶地将子问题的解进行合并，从而构建出原问题的解

归并排序是分治策略的典型应用之一

  1. 分：递归地将原数组（原问题）划分为两个子数组（子问题），直到子数组只剩一个元素（最小子问题）
  2. 治：从底至顶地将有序的子数组（子问题的解）进行合并，从而得到有序的原数组（原问题的解）

如何判断分治问题

一个问题是否适合使用分治解决，通常可以参考以下几个判断依据：

  1. 问题可以分解：原问题可以分解成规模更小、类似的子问题，以及能够以相同方式递归地进行划分
  2. 子问题是独立的：子问题之间没有重叠，互不依赖，可以独立解决
  3. 子问题的解可以合并：原问题的解通过合并子问题的解得来

显然，归并排序满足以上三条判断依据：

  1. 问题可以分解：递归地将数组（原问题）划分为两个子数组（子问题）
  2. 子问题是独立的：每个子数组都可以独立地进行排序（子问题可以独立进行求解）
  3. 子问题的解可以合并：两个有序子数组（子问题的解）可以合并为一个有序数组（原问题的解）

通过分治提升效率

分治不仅可以有效地解决算法问题，往往还可以提升算法效率。在排序算法中，快速排序、归并排序、堆排序相较于选择、冒泡、插入排序更快，就是因为它们应用了分治策略。

为什么分治可以提升算法效率，其底层逻辑是什么？

操作数量优化

以"冒泡排序"为例，其处理一个长度为 n 的数组需要 $O(n^2)$ 时间。假设我们将数组从中点处分为两个子数组，则划分需要 $O(n)$ 时间，排序每个子数组需要 $O((n/2)^2)$ 时间，合并两个子数组需要 $O(n)$ 时间，总体时间复杂度为：

接下来，我们计算以下不等式，其左边和右边分别为划分前和划分后的操作总数：

这意味着当 n > 4 时，划分后的操作数量更少，排序效率应该更高。请注意，划分后的时间复杂度仍然是平方阶 $O(n^2)$，只是复杂度中的常数项变小了

进一步想，如果我们把子数组不断地再从中点处划分为两个子数组，直至子数组只剩一个元素时停止划分呢？这种思路实际上就是"归并排序"，时间复杂度为 $O(nlogn)$

再思考，如果我们多设置几个划分点，将原数组平均划分为 k 个子数组呢？这种情况与"桶排序"非常类似，它非常适合排序海量数据，理论上时间复杂度可以达到 $O(n + k)$

并行计算优化

我们知道，分治生成的子问题是相互独立的，因此通常可以并行解决。也就是说，分治不仅可以降低算法的时间复杂度，还有利于操作系统的并行优化。并行优化在多核或多处理器的环境中尤其有效，因为系统可以同时处理多个子问题，更加充分地利用计算资源，从而显著减少总体的运行时间。

分治常见应用

一方面，分治可以用来解决许多经典算法问题：

  • 寻找最近点对：该算法首先将点集分成两部分，然后分别找出两部分中的最近点对，最后找出跨越两部分的最近点对
  • 大整数乘法：例如 Karatsuba 算法，它将大整数乘法分解为几个较小的整数的乘法和加法
  • 矩阵乘法：例如 Strassen 算法，它将大矩阵乘法分解为多个小矩阵的乘法和加法
  • 汉诺塔问题：汉诺塔问题可以通过递归解决，这是典型的分治策略应用
  • 求解逆序对：在一个序列中，如果前面的数字大于后面的数字，那么这两个数字构成一个逆序对。求解逆序对问题可以利用分治的思想，借助归并排序进行求解

另一方面，分治在算法和数据结构的设计中应用非常广泛：

  • 二分查找：二分查找是将有序数组从中点索引处分为两部分，然后根据目标值与中间元素值比较结果，决定排除哪一半区间，并在剩余区间执行相同的二分操作
  • 归并排序：本节开头已介绍，不再赘述
  • 快速排序：快速排序是选取一个基准值，然后把数组分为两个子数组，一个子数组的元素比基准值小，另一子数组的元素比基准值大，再对这两部分进行相同的划分操作，直至子数组只剩下一个元素
  • 桶排序：桶排序的基本思想是将数据分散到多个桶，然后对每个桶内的元素进行排序，最后将各个桶的元素依次取出，从而得到一个有序数组
  • 树：例如二叉搜索树、AVL 树、红黑树、B 树、B+ 树等，它们的查找、插入和删除等操作都可以视为分治策略的应用
  • 堆：堆是一种特殊的完全二叉树，其各种操作，如插入、删除和堆化，实际上都隐含了分治的思想
  • 哈希表：虽然哈希表来并不直接应用分治，但某些哈希冲突解决方案间接应用了分治策略，例如，链式地址中的长链表会被转化为红黑树，以提升查询效率

可以看出，分治是一种润物细无声的算法思想，隐含在各种算法与数据结构之中

回溯

「回溯算法 backtracking algorithm」是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止。回溯算法通常采用深度优先搜索来遍历解空间。在二叉树章节中，我们提到前序、中序和后序遍历都属于深度优先搜索

给定一棵二叉树，搜索并记录所有值为 7 的节点，请返回节点列表

对于此题，我们前序遍历这棵树，并判断当前节点的值是否为 7，若是，则将该节点的值加入结果列表 res 之中

1
2
3
4
5
6
7
8
9
10
11
12
// 前序遍历：例题一
void preOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    if (root.val == 7) {
        // 记录解
        res.add(root);
    }
    preOrder(root.left);
    preOrder(root.right);
}

尝试与回退

之所以称之为回溯算法，是因为该算法在搜索解空间时会采用尝试与尝试回退的策略。当算法在搜索过程中遇到某个状态无法继续前进或无法得到满足条件的解时，它会撤销上一步的选择，退回到之前的状态，并尝试其他可能的选择。对于例题一，访问每个节点都代表一次尝试，而越过叶节点或返回父节点的 return 则表示回退。值得说明的是，回退并不仅仅包括函数返回。为解释这一点，我们对例题一稍作拓展

在二叉树中搜索所有值为 7 的节点，请返回根节点到这些节点的路径

在例题一代码的基础上，我们需要借助一个列表 path 记录访问过的节点路径。当访问到值为 7 的节点时，则复制 path 并添加进结果列表 res 。遍历完成后，res 中保存的就是所有的解。代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 前序遍历：例题二
void preOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    // 尝试
    path.add(root);
    if (root.val == 7) {
        // 记录解
        res.add(new ArrayList<>(path));
    }
    preOrder(root.left);
    preOrder(root.right);
    // 回退
    path.remove(path.size() - 1);
}

在每次尝试中，我们通过将当前节点添加进 path 来记录路径；而在回退前，我们需要将该节点从 path 中弹出，以恢复本次尝试之前的状态。我们可以将尝试和回退理解为前进与撤销，两个操作互为逆向

剪枝

复杂的回溯问题通常包含一个或多个约束条件，约束条件通常可用于剪枝

在二叉树中搜索所有值为 7 的节点，请返回根节点到这些节点的路径，并要求路径中不包含值为 3 的节点

为了满足以上约束条件，我们需要添加剪枝操作：在搜索过程中，若遇到值为 3 的节点，则提前返回，不再继续搜索。代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 前序遍历：例题三
void preOrder(TreeNode root) {
    // 剪枝
    if (root == null || root.val == 3) {
        return;
    }
    // 尝试
    path.add(root);
    if (root.val == 7) {
        // 记录解
        res.add(new ArrayList<>(path));
    }
    preOrder(root.left);
    preOrder(root.right);
    // 回退
    path.remove(path.size() - 1);
}

"剪枝"是一个非常形象的名词。在搜索过程中，我们剪掉了不满足约束条件的搜索分支，避免许多无意义的尝试，从而提高了搜索效率

框架代码

接下来，我们尝试将回溯的尝试、回退、剪枝的主体框架提炼出来，提升代码的通用性。在以下框架代码中，state 表示问题的当前状态，choices 表示当前状态下可以做出的选择：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 回溯算法框架
void backtrack(State state, List<Choice> choices, List<State> res) {
    // 判断是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
        // 不再继续搜索
        return;
    }
    // 遍历所有选择
    for (Choice choice : choices) {
        // 剪枝：判断选择是否合法
        if (isValid(state, choice)) {
            // 尝试：做出选择，更新状态
            makeChoice(state, choice);
            backtrack(state, choices, res);
            // 回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}

接下来，我们基于框架代码来解决例题三。状态 state 为节点遍历路径，选择 choices 为当前节点的左子节点和右子节点，结果 res 是路径列表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 判断当前状态是否为解
boolean isSolution(List<TreeNode> state) {
    return !state.isEmpty() && state.get(state.size() - 1).val == 7;
}

// 记录解
void recordSolution(List<TreeNode> state, List<List<TreeNode>> res) {
    res.add(new ArrayList<>(state));
}

// 判断在当前状态下，该选择是否合法
boolean isValid(List<TreeNode> state, TreeNode choice) {
    return choice != null && choice.val != 3;
}

// 更新状态
void makeChoice(List<TreeNode> state, TreeNode choice) {
    state.add(choice);
}

// 恢复状态
void undoChoice(List<TreeNode> state, TreeNode choice) {
    state.remove(state.size() - 1);
}

// 回溯算法：例题三
void backtrack(List<TreeNode> state, List<TreeNode> choices, List<List<TreeNode>> res) {
    // 检查是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
    }
    // 遍历所有选择
    for (TreeNode choice : choices) {
        // 剪枝：检查选择是否合法
        if (isValid(state, choice)) {
            // 尝试：做出选择，更新状态
            makeChoice(state, choice);
            // 进行下一轮选择
            backtrack(state, Arrays.asList(choice.left, choice.right), res);
            // 回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}

相比基于前序遍历的代码实现，基于回溯算法框架的代码实现虽然显得啰唆，但通用性更好。实际上，许多回溯问题可以在该框架下解决。我们只需根据具体问题来定义 state 和 choices ，并实现框架中的各个方法即可

常用术语

名词 定义 例题三
解（solution） 解是满足问题特定条件的答案，可能有一个或多个 根节点到节点 7 的满足约束条件的所有路径
约束条件（constraint） 约束条件是问题中限制解的可行性的条件，通常用于剪枝 路径中不包含节点 3
状态（state） 状态表示问题在某一时刻的情况，包括已经做出的选择 当前已访问的节点路径，即 path 节点列表
尝试（attempt） 尝试是根据可用选择来探索解空间的过程，包括做出选择，更新状态，检查是否为解 递归访问左（右）子节点，将节点添加进 path ，判断节点的值是否为 7
回退（backtracking） 回退指遇到不满足约束条件的状态时，撤销前面做出的选择，回到上一个状态 当越过叶节点、结束节点访问、遇到值为 3 的节点时终止搜索，函数返回
剪枝（pruning） 剪枝是根据问题特性和约束条件避免无意义的搜索路径的方法，可提高搜索效率 当遇到值为 3 的节点时，则不再继续搜索

问题、解、状态等概念是通用的，在分治、回溯、动态规划、贪心等算法中都有涉及

优点与局限性

回溯算法本质上是一种深度优先搜索算法，它尝试所有可能的解决方案直到找到满足条件的解。这种方法的优点在于能够找到所有可能的解决方案，而且在合理的剪枝操作下，具有很高的效率。然而，在处理大规模或者复杂问题时，回溯算法的运行效率可能难以接受：

  • 时间：回溯算法通常需要遍历状态空间的所有可能，时间复杂度可以达到指数阶或阶乘阶
  • 空间：在递归调用中需要保存当前的状态（例如路径、用于剪枝的辅助变量等），当深度很大时，空间需求可能会变得很大

即便如此，回溯算法仍然是某些搜索问题和约束满足问题的最佳解决方案。对于这些问题，由于无法预测哪些选择可生成有效的解，因此我们必须对所有可能的选择进行遍历。在这种情况下，关键是如何优化效率，常见的效率优化方法有两种：

  • 剪枝：避免搜索那些肯定不会产生解的路径，从而节省时间和空间
  • 启发式搜索：在搜索过程中引入一些策略或者估计值，从而优先搜索最有可能产生有效解的路径

回溯典型例题

回溯算法可用于解决许多搜索问题、约束满足问题和组合优化问题

搜索问题：这类问题的目标是找到满足特定条件的解决方案

  • 全排列问题：给定一个集合，求出其所有可能的排列组合
  • 子集和问题：给定一个集合和一个目标和，找到集合中所有和为目标和的子集
  • 汉诺塔问题：给定三根柱子和一系列大小不同的圆盘，要求将所有圆盘从一根柱子移动到另一根柱子，每次只能移动一个圆盘，且不能将大圆盘放在小圆盘上

约束满足问题：这类问题的目标是找到满足所有约束条件的解

  • n 皇后：在 n × n 的棋盘上放置 n 个皇后，使得它们互不攻击
  • 数独：在 9 × 9 的网格中填入数字 1 ~ 9，使得每行、每列和每个 3 × 3 子网格中的数字不重复
  • 图着色问题：给定一个无向图，用最少的颜色给图的每个顶点着色，使得相邻顶点颜色不同

组合优化问题：这类问题的目标是在一个组合空间中找到满足某些条件的最优解

  • 0-1 背包问题：给定一组物品和一个背包，每个物品有一定的价值和重量，要求在背包容量限制内，选择物品使得总价值最大
  • 旅行商问题：在一个图中，从一个点出发，访问所有其他点恰好一次后返回起点，求最短路径
  • 最大团问题：给定一个无向图，找到最大的完全子图，即子图中的任意两个顶点之间都有边相连

请注意，对于许多组合优化问题，回溯不是最优解决方案。

  • 0-1 背包问题通常使用动态规划解决，以达到更高的时间效率
  • 旅行商是一个著名的 NP-Hard 问题，常用解法有遗传算法和蚁群算法等
  • 最大团问题是图论中的一个经典问题，可用贪心算法等启发式算法来解决

全排列问题

全排列问题是回溯算法的一个典型应用。它的定义是在给定一个集合（如一个数组或字符串）的情况下，找出其中元素的所有可能的排列

无相等元素的情况

输入一个整数数组，其中不包含重复元素，返回所有可能的排列

从回溯算法的角度看，我们可以把生成排列的过程想象成一系列选择的结果。假设输入数组为 [1, 2, 3]，如果我们先选择 1，再选择 3，最后选择 2，则获得排列 [1, 3, 2]。回退表示撤销一个选择，之后继续尝试其他选择。从回溯代码的角度看，候选集合 choices 是输入数组中的所有元素，状态 state 是直至目前已被选择的元素。请注意，每个元素只允许被选择一次，因此 state 中的所有元素都应该是唯一的

为了实现每个元素只被选择一次，我们考虑引入一个布尔型数组 selected ，其中 selected[i] 表示 choices[i] 是否已被选择，并基于它实现以下剪枝操作：

  • 在做出选择 choice[i] 后，我们就将 selected[i] 赋值为 true，代表它已被选择
  • 遍历选择列表 choices 时，跳过所有已被选择的节点，即剪枝

剪枝操作将搜索空间大小从 $O(n^n)$ 减小至 $O(n!)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 回溯算法：全排列 I
void backtrack(List<Integer> state, int[] choices, boolean[] selected, List<List<Integer>> res) {
    // 当状态长度等于元素数量时，记录解
    if (state.size() == choices.length) {
        res.add(new ArrayList<Integer>(state));
        return;
    }
    // 遍历所有选择
    for (int i = 0; i < choices.length; i++) {
        int choice = choices[i];
        // 剪枝：不允许重复选择元素
        if (!selected[i]) {
            // 尝试：做出选择，更新状态
            selected[i] = true;
            state.add(choice);
            // 进行下一轮选择
            backtrack(state, choices, selected, res);
            // 回退：撤销选择，恢复到之前的状态
            selected[i] = false;
            state.remove(state.size() - 1);
        }
    }
}

// 全排列 I
List<List<Integer>> permutationsI(int[] nums) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    backtrack(new ArrayList<Integer>(), nums, new boolean[nums.length], res);
    return res;
}

考虑相等元素的情况

输入一个整数数组，数组中可能包含重复元素，返回所有不重复的排列

在上一题的代码的基础上，我们考虑在每一轮选择中开启一个哈希表 duplicated ，用于记录该轮中已经尝试过的元素，并将重复元素剪枝：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 回溯算法：全排列 II
void backtrack(List<Integer> state, int[] choices, boolean[] selected, List<List<Integer>> res) {
    // 当状态长度等于元素数量时，记录解
    if (state.size() == choices.length) {
        res.add(new ArrayList<Integer>(state));
        return;
    }
    // 遍历所有选择
    Set<Integer> duplicated = new HashSet<Integer>();
    for (int i = 0; i < choices.length; i++) {
        int choice = choices[i];
        // 剪枝：不允许重复选择元素 且 不允许重复选择相等元素
        if (!selected[i] && !duplicated.contains(choice)) {
            // 尝试：做出选择，更新状态
            duplicated.add(choice); // 记录选择过的元素值
            selected[i] = true;
            state.add(choice);
            // 进行下一轮选择
            backtrack(state, choices, selected, res);
            // 回退：撤销选择，恢复到之前的状态
            selected[i] = false;
            state.remove(state.size() - 1);
        }
    }
}

// 全排列 II
List<List<Integer>> permutationsII(int[] nums) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    backtrack(new ArrayList<Integer>(), nums, new boolean[nums.length], res);
    return res;
}

假设元素两两之间互不相同，则 n 个元素共有 n! 种排列（阶乘）；在记录结果时，需要复制长度为 n 的列表，使用 $O(n)$ 时间。因此时间复杂度为 $O(n!n)$。最大递归深度为 n ，使用 $O(n)$ 栈帧空间。selected 使用 $O(n)$ 空间。同一时刻最多共有 n 个 duplicated ，使用 $O(n^2)$ 空间。因此空间复杂度为 $O(n^2)$

两种剪枝对比

请注意，虽然 selected 和 duplicated 都用于剪枝，但两者的目标不同

  1. 重复选择剪枝：整个搜索过程中只有一个 selected 。它记录的是当前状态中包含哪些元素，其作用是防止 choices 中的任一元素在 state 中重复出现。
  2. 相等元素剪枝：每轮选择（每个调用的 backtrack 函数）都包含一个 duplicated 。它记录的是在本轮遍历（for 循环）中哪些元素已被选择过，其作用是保证相等的元素只被选择一次。

N 皇后问题

根据国际象棋的规则，皇后可以攻击与同处一行、一列或一条斜线上的棋子。给定 n 个皇后和一个 n x n 大小的棋盘，寻找使得所有皇后之间无法相互攻击的摆放方案

逐行放置策略

皇后的数量和棋盘的行数都为 n，因此我们容易得到一个推论：棋盘每行都允许且只允许放置一个皇后。也就是说，我们可以采取逐行放置策略：从第一行开始，在每行放置一个皇后，直至最后一行结束。从本质上看，逐行放置策略起到了剪枝的作用，它避免了同一行出现多个皇后的所有搜索分支

列与对角线剪枝

为了满足列约束，我们可以利用一个长度为 n 的布尔型数组 cols 记录每一列是否有皇后。在每次决定放置前，我们通过 cols 将已有皇后的列进行剪枝，并在回溯中动态更新 cols 的状态

那么，如何处理对角线约束呢？设棋盘中某个格子的行列索引为(row, col)，选定矩阵中的某条主对角线，我们发现该对角线上所有格子的行索引减列索引都相等，即对角线上所有格子的 row - col 为恒定值

也就是说，如果两个格子满足 row1 - col1 = row2 - col2，则它们一定处在同一条主对角线上。利用该规律，我们可以借助数组 diags1 记录每条主对角线上是否有皇后。

同理，次对角线上的所有格子的 row + col 是恒定值。我们同样也可以借助数组 diags2 来处理次对角线约束。

代码实现

请注意，n 维方阵中 row - col 的范围是 [-n + 1, n - 1]，row + col 的范围是 [0, 2n - 2]，所以主对角线和次对角线的数量都为 2n - 1，即数组 diags1 和 diags2 的长度都为 2n - 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 回溯算法：N 皇后
void backtrack(int row, int n, List<List<String>> state, List<List<List<String>>> res,
        boolean[] cols, boolean[] diags1, boolean[] diags2) {
    // 当放置完所有行时，记录解
    if (row == n) {
        List<List<String>> copyState = new ArrayList<>();
        for (List<String> sRow : state) {
            copyState.add(new ArrayList<>(sRow));
        }
        res.add(copyState);
        return;
    }
    // 遍历所有列
    for (int col = 0; col < n; col++) {
        // 计算该格子对应的主对角线和副对角线
        int diag1 = row - col + n - 1;
        int diag2 = row + col;
        // 剪枝：不允许该格子所在列、主对角线、副对角线上存在皇后
        if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
            // 尝试：将皇后放置在该格子
            state.get(row).set(col, "Q");
            cols[col] = diags1[diag1] = diags2[diag2] = true;
            // 放置下一行
            backtrack(row + 1, n, state, res, cols, diags1, diags2);
            // 回退：将该格子恢复为空位
            state.get(row).set(col, "#");
            cols[col] = diags1[diag1] = diags2[diag2] = false;
        }
    }
}

// 求解 N 皇后
List<List<List<String>>> nQueens(int n) {
    // 初始化 n*n 大小的棋盘，其中 'Q' 代表皇后，'#' 代表空位
    List<List<String>> state = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        List<String> row = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            row.add("#");
        }
        state.add(row);
    }
    boolean[] cols = new boolean[n]; // 记录列是否有皇后
    boolean[] diags1 = new boolean[2 * n - 1]; // 记录主对角线上是否有皇后
    boolean[] diags2 = new boolean[2 * n - 1]; // 记录副对角线上是否有皇后
    List<List<List<String>>> res = new ArrayList<>();

    backtrack(0, n, state, res, cols, diags1, diags2);

    return res;
}

逐行放置 n 次，考虑列约束，则从第一行到最后一行分别有 n、n - 1、… 、2、1 个选择，因此时间复杂度为 $O(n!)$。实际上，根据对角线约束的剪枝也能够大幅缩小搜索空间，因而搜索效率往往优于以上时间复杂度。

数组 state 使用 $O(n^2)$ 空间，数组 cols、diags1 和 diags2 皆使用 $O(n)$ 空间。最大递归深度为 n，使用 $O(n)$ 栈帧空间。因此空间复杂度为 $O(n^2)$

Q & A

怎么理解回溯和递归的关系？

总的来看，回溯是一种"算法策略"，而递归更像是一个"工具"

  1. 回溯算法通常基于递归实现。然而，回溯是递归的应用场景之一，是递归在搜索问题中的应用
  2. 递归的结构体现了"子问题分解"的解题范式，常用于解决分治、回溯、动态规划（记忆化递归）等问题