Algo

由于实际测试具有较大的局限性，因此我们考虑仅通过一些计算来评估算法的效率。这种估算方法被称为渐近复杂度分析（asymptotic complexity analysis），简称复杂度分析。

• “时间和空间资源”分别对应时间复杂度（time complexity）和空间复杂度（space complexity）。
• “随着输入数据大小的增加”意味着复杂度反映了算法运行效率与输入数据体量之间的关系。
• “时间和空间的增长趋势”表示复杂度分析关注的不是运行时间或占用空间的具体值，而是时间或空间增长的“快慢”。

迭代（iteration）

递归（recursion）,通过函数调用自身来解决问题:（“将问题分解为更小子问题”）

1. 递：程序不断深入地调用自身，通常传入更小或更简化的参数，直到达到“终止条件”。
2. 归：触发“终止条件”后，程序从最深层的递归函数开始逐层返回，汇聚每一层的结果。

而从实现的角度看，递归代码主要包含三个要素。

1. 终止条件：用于决定什么时候由“递”转“归”。
2. 递归调用：对应“递”，函数调用自身，通常输入更小或更简化的参数。
3. 返回结果：对应“归”，将当前递归层级的结果返回至上一层。

虽然从计算角度看，迭代与递归可以得到相同的结果，但它们代表了两种完全不同的思考和解决问题的范式。

• 迭代：“自下而上”地解决问题。从最基础的步骤开始，然后不断重复或累加这些步骤，直到任务完成。
• 递归：“自上而下”地解决问题。将原问题分解为更小的子问题，这些子问题和原问题具有相同的形式。接下来将子问题继续分解为更小的子问题，直到基本情况时停止（基本情况的解是已知的）。

过深的递归可能导致栈溢出错误

尾递归

有趣的是，如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或解释器优化，使其在空间效率上与迭代相当。这种情况被称为尾递归（tail recursion）。

• 普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下文。

• 尾递归：递归调用是函数返回前的最后一个操作，这意味着函数返回到上一层级后，无须继续执行其他操作，因此系统无须保存上一层函数的上下文。

  例如：

  /* 尾递归 */
  int tailRecur(int n, int res) {
  // 终止条件
  if (n == 0)
  return res;
  // 尾递归调用
  return tailRecur(n - 1, res + n);
  }

普通递归：

txt

python
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

在普通递归中，递归调用 factorial(n - 1) 发生在函数的末尾，并且返回值被乘以 n 后再返回。

尾递归：

txt

python
def factorial_tail(n, accumulator=1):
    if n == 0:
        return accumulator
    else:
        return factorial_tail(n - 1, accumulator * n)

以上述递归函数为例，求和操作在递归的“归”阶段进行。这意味着最初被调用的函数实际上是最后完成其求和操作的，这种工作机制与栈的“先入后出”原则异曲同工。

事实上，“调用栈”和“栈帧空间”这类递归术语已经暗示了递归与栈之间的密切关系。

1. 递：当函数被调用时，系统会在“调用栈”上为该函数分配新的栈帧，用于存储函数的局部变量、参数、返回地址等数据。
2. 归：当函数完成执行并返回时，对应的栈帧会被从“调用栈”上移除，恢复之前函数的执行环境。

时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大时的增长趋势。

在计算机科学中，”渐近上界” 是一种用于分析算法性能的概念，特别是与时间复杂度和空间复杂度相关。在时间复杂度分析中，渐近上界的目的在于确定算法在数据规模趋于无穷大时的最坏性能表现。为了更好地理解这一概念，可以从几个角度来探讨：

1. 什么是渐近上界？

渐近上界指的是某个函数在趋于某个极限（例如，无限大）时，其增长速率的上限。它通常用于描述算法的最坏情况性能，表示随着输入规模增加，算法的运行时间或使用的资源上限。

2. 大-O 表示法

在算法分析中，渐近上界最常用的表示法是大-O 表示法。用 O(f(n)) 表示某个算法的时间复杂度，意味着这个算法的运行时间在最坏情况下不会超过某个函数 f(n) 的增长速率。

例如，若算法的时间复杂度是 O(n^2)，表示无论最坏情况下发生了什么，这个算法的运行时间最多是某个常数与 n^2 的乘积。这里 n 是输入数据的规模。

3. 用途

渐近上界有助于比较不同算法的性能，并帮助工程师选择适当的算法。在设计和优化算法时，了解渐近上界也有助于避免性能陷阱。

4. 如何理解渐近上界？

渐近上界在数学上是严格定义的。函数 T(n) 的渐近上界是 f(n)，如果存在常数 c 和 n_0 使得对于所有 n ≥ n_0，都有 T(n) ≤ c * f(n)。这意味着当 n 足够大时，T(n) 不会超过 c * f(n)，即使在最坏情况下。

5. 示例

考虑一个算法的时间复杂度是 3n^2 + 2n + 7。这个算法的渐近上界是 O(n^2)，因为当 n 足够大时，3n^2 是增长最快的项，其他项的影响可以忽略。

txt

/* 指数阶（递归实现） */
int expRecur(int n) {
    if (n == 1)
        return 1;
    return expRecur(n - 1) + expRecur(n - 1) + 1;
}

txt

/*对数阶*/
int linearLogRecur(int n) {
    if (n <= 1)
        return 1;
    int count = linearLogRecur(n / 2) + linearLogRecur(n / 2);

    return count;
}

txt

/* 线性对数阶 */
int linearLogRecur(int n) {
    if (n <= 1)
        return 1;
    int count = linearLogRecur(n / 2) + linearLogRecur(n / 2);
    for (int i = 0; i < n; i++) {
        count++;
    }
    return count;
}

算法在运行过程中使用的内存空间主要包括以下几种。

• 输入空间：用于存储算法的输入数据。
• 暂存空间：用于存储算法在运行过程中的变量、对象、函数上下文等数据。
• 输出空间：用于存储算法的输出数据。

一般情况下，空间复杂度的统计范围是“暂存空间”加上“输出空间”。

txt

struct Node {
    int val;
    Node *next;
    Node(int x) : val(x), next(nullptr) {}
};

Node(int x) : val(x), next(nullptr) 是一个构造函数的定义

txt

int func() {
    // 执行某些操作
    return 0;
}
/* 循环的空间复杂度为 O(1) */
void loop(int n) {
    for (int i = 0; i < n; i++) {
        func();
    }
}
/* 递归的空间复杂度为 O(n) */
void recur(int n) {
    if (n == 1) return;
    return recur(n - 1);
}

函数 loop() 和 recur() 的时间复杂度都为

，但空间复杂度不同。

• 函数 loop() 在循环中调用了

次 function() ，每轮中的 function() 都返回并释放了栈帧空间，因此空间复杂度仍为

。

递归函数 recur() 在运行过程中会同时存在

个未返回的 recur() ，从而占用 的栈帧空间。

txt

/* 线性阶 */
void linear(int n) {
    // 长度为 n 的数组占用 O(n) 空间
    vector<int> nums(n);
    // 长度为 n 的列表占用 O(n) 空间
    vector<ListNode> nodes;
    for (int i = 0; i < n; i++) {
        nodes.push_back(ListNode(i));
    }
    // 长度为 n 的哈希表占用 O(n) 空间
    unordered_map<int, string> map;
    for (int i = 0; i < n; i++) {
        map[i] = to_string(i);
    }
}

/* 线性阶（递归实现） */
void linearRecur(int n) {
    cout << "递归 n = " << n << endl;
    if (n == 1)
        return;
    linearRecur(n - 1);
}

Q：函数和方法这两个术语的区别是什么？

函数（function）可以被独立执行，所有参数都以显式传递。方法（method）与一个对象关联，被隐式传递给调用它的对象，能够对类的实例中包含的数据进行操作。

下面以几种常见的编程语言为例来说明。

• C 语言是过程式编程语言，没有面向对象的概念，所以只有函数。但我们可以通过创建结构体（struct）来模拟面向对象编程，与结构体相关联的函数就相当于其他编程语言中的方法。
• Java 和 C# 是面向对象的编程语言，代码块（方法）通常作为某个类的一部分。静态方法的行为类似于函数，因为它被绑定在类上，不能访问特定的实例变量。
• C++ 和 Python 既支持过程式编程（函数），也支持面向对象编程（方法）。

常见的数据结构包括数组、链表、栈、队列、哈希表、树、堆、图，它们可以从“逻辑结构”和“物理结构”两个维度进行分类。

逻辑结构：线性与非线性

逻辑结构揭示了数据元素之间的逻辑关系。在数组和链表中，数据按照一定顺序排列，体现了数据之间的线性关系；而在树中，数据从顶部向下按层次排列，表现出“祖先”与“后代”之间的派生关系；图则由节点和边构成，反映了复杂的网络关系。

如图 3-1 所示，逻辑结构可分为“线性”和“非线性”两大类。线性结构比较直观，指数据在逻辑关系上呈线性排列；非线性结构则相反，呈非线性排列。

• 线性数据结构：数组、链表、栈、队列、哈希表，元素之间是一对一的顺序关系。
• 非线性数据结构：树、堆、图、哈希表。

非线性数据结构可以进一步划分为树形结构和网状结构。

• 树形结构：树、堆、哈希表，元素之间是一对多的关系。
• 网状结构：图，元素之间是多对多的关系。

内存是所有程序的共享资源，当某块内存被某个程序占用时，则无法被其他程序同时使用了。因此在数据结构与算法的设计中，内存资源是一个重要的考虑因素。比如，算法所占用的内存峰值不应超过系统剩余空闲内存；如果缺少连续大块的内存空间，那么所选用的数据结构必须能够存储在分散的内存空间内。

如图 3-3 所示，物理结构反映了数据在计算机内存中的存储方式，可分为连续空间存储（数组）和分散空间存储（链表）。物理结构从底层决定了数据的访问、更新、增删等操作方法，两种物理结构在时间效率和空间效率方面呈现出互补的特点。

值得说明的是，所有数据结构都是基于数组、链表或二者的组合实现的。例如，栈和队列既可以使用数组实现，也可以使用链表实现；而哈希表的实现可能同时包含数组和链表。

链表在初始化后，仍可以在程序运行过程中对其长度进行调整，因此也称“动态数据结构”。数组在初始化后长度不可变，因此也称“静态数据结构”。值得注意的是，数组可通过重新分配内存实现长度变化，从而具备一定的“动态性”。

基本数据类型是 CPU 可以直接进行运算的类型，在算法中直接被使用，主要包括以下几种。

• 整数类型 byte、short、int、long 。
• 浮点数类型 float、double ，用于表示小数。
• 字符类型 char ，用于表示各种语言的字母、标点符号甚至表情符号等。
• 布尔类型 bool ，用于表示“是”与“否”判断。

基本数据类型以二进制的形式存储在计算机中。一个二进制位即为 1比特。在绝大多数现代操作系统中，1字节（byte）由 8比特（bit）组成。

txt

/* 初始化数组 */
// 存储在栈上
int arr[5];
int nums[5] = { 1, 3, 2, 5, 4 };
// 存储在堆上（需要手动释放空间）
int* arr1 = new int[5];
int* nums1 = new int[5] { 1, 3, 2, 5, 4 };

在C++中，将数据存储在栈上和堆上有以下区别：

1. 存储位置：
   • 栈上：栈上的数据存储在程序的栈内存中，它们的分配和释放由编译器自动管理。栈上的数据通常具有较短的生命周期，当函数执行结束时，其内部的局部变量就会被自动释放。
   • 堆上：堆上的数据存储在程序的堆内存中，它们的分配和释放通常由程序员手动管理。堆上的数据可以具有较长的生命周期，直到显式释放内存或程序终止时才会被释放。
2. 动态性：
   • 栈上：栈上的内存分配是静态的，大小在编译时确定，并且通常比较有限。由于栈上的内存分配由编译器管理，所以分配和释放速度较快。
   • 堆上：堆上的内存分配是动态的，大小可以在运行时确定，并且可以根据需要动态增长。由于堆上的内存分配由程序员管理，因此可能会产生内存泄漏或内存碎片等问题。
3. 访问方式：
   • 栈上：栈上的数据访问速度通常比较快，因为它们存储在内存中的连续位置上，并且可以直接通过指针或引用进行访问。
   • 堆上：堆上的数据访问速度可能比较慢，因为它们存储在内存中的不同位置上，并且需要通过指针间接访问。

在实际编程中，选择栈上或堆上的存储方式取决于数据的生命周期、大小和访问方式等因素。

Q:把数组存储在堆，栈上，那堆栈是什么

A：在计算机科学中，”堆栈”通常指的是”栈”和”堆”这两种不同的内存分配区域，它们用于存储程序运行时所需的数据和内存。这两者虽然名字相似，但是在内存管理和使用方面有着不同的作用和特点：

1. 栈（Stack）：
   • 栈是一种内存分配区域，用于存储函数调用时的局部变量、函数参数、函数返回地址等信息。
   • 栈上的内存分配由编译器自动管理，通常采用后进先出（LIFO）的方式进行操作。函数调用时，会将局部变量等信息压入栈中，函数返回时则将其弹出。
   • 栈上的内存分配速度快，但是空间有限，通常用于存储函数调用时所需的临时数据。
2. 堆（Heap）：
   • 堆是另一种内存分配区域，用于存储程序运行时动态分配的内存，例如使用new和delete操作符创建和释放的对象。
   • 堆上的内存分配由程序员手动管理，它的大小和生命周期可以动态确定。堆上的内存通常用于存储程序运行时动态产生的数据结构、对象等。
   • 堆上的内存分配速度相对较慢，因为需要进行动态分配和释放，并且可能产生内存碎片等问题。

总的来说，栈和堆是程序运行时两种不同的内存分配区域，它们有着不同的管理方式、分配速度和用途，程序员可以根据需要选择合适的内存分配方式来管理程序的数据和内存。

Q ：存储在堆上，是要求定义为指针吗

A : 在C++中，使用new操作符分配内存时，返回的是指向分配内存的指针。因此，存储在堆上的数据需要定义为指针类型，以便程序员能够通过指针来访问和操作这些数据，并在适当的时候手动释放内存空间，以避免内存泄漏。

以下是一个简单的示例，演示如何声明和使用函数指针：

txt

cpp
#include <iostream>

// 声明一个接受两个整数参数并返回它们之和的函数
int add(int a, int b) {
    return a + b;
}

// 声明一个接受两个整数参数并返回它们之差的函数
int subtract(int a, int b) {
    return a - b;
}

int main() {
    // 声明一个指向函数的指针，该函数接受两个整数参数并返回一个整数
    int (*operation)(int, int);

    // 将函数 add 的地址赋值给指针变量 operation
    operation = add;

    // 使用指针调用函数 add
    int result1 = operation(10, 5);
    std::cout << "Result of add: " << result1 << std::endl;

    // 将函数 subtract 的地址赋值给指针变量 operation
    operation = subtract;

    // 使用指针调用函数 subtract
    int result2 = operation(10, 5);
    std::cout << "Result of subtract: " << result2 << std::endl;

    return 0;
}

在这个示例中，int (*operation)(int, int); 声明了一个名为 operation 的函数指针，它指向一个接受两个整数参数并返回一个整数的函数。然后，通过将函数的地址赋值给指针变量 operation，可以使用该指针来调用不同的函数。

txt

/* 扩展数组长度 */
int *extend(int *nums, int size, int enlarge) {
    // 初始化一个扩展长度后的数组
    int *res = new int[size + enlarge];
    // 将原数组中的所有元素复制到新数组
    for (int i = 0; i < size; i++) {
        res[i] = nums[i];
    }
    // 释放内存
    delete[] nums;
    // 返回扩展后的新数组
    return res;
}

返回类型为 int *，意味着该函数返回的是一个指向整数类型的指针，即指向数组的指针。

数组的优点与局限性

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

• 空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。

• 支持随机访问：数组允许在

• 时间内访问任何元素。

• 缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。

连续空间存储是一把双刃剑，其存在以下局限性。

• 插入与删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素。

• 长度不可变：数组在初始化后长度就固定了，扩容数组需要将所有数据复制到新数组，开销很大。

• 空间浪费：如果数组分配的大小超过实际所需，那么多余的空间就被浪费了。

• delete 用于释放通过 new 分配的单个对象的内存。

• delete[] 用于释放通过 new[] 分配的数组的内存。

数组典型应用

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

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

存储数组的内存空间必须是连续的

链表的组成单位是节点（node）对象。每个节点都包含两项数据：节点的“值”和指向下一节点的“引用”。

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

txt

/* 链表节点结构体 */
struct ListNode {
    int val;         // 节点值
    ListNode *next;  // 指向下一节点的指针
    ListNode(int x) : val(x), next(nullptr) {}  // 构造函数
};

为什么结构体也有构造函数:

在C++中，结构体（struct）和类（class）都可以拥有构造函数。构造函数用于初始化对象的数据成员，在创建对象时自动调用。

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

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

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

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

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

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

可以使用动态数组（dynamic array）来实现列表。它继承了数组的各项优点，并且可以在程序运行过程中进行动态扩容。

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

数据结构的缓存效率

缓存虽然在空间容量上远小于内存，但它比内存快得多，在程序执行速度上起着至关重要的作用。由于缓存的容量有限，只能存储一小部分频繁访问的数据，因此当 CPU 尝试访问的数据不在缓存中时，就会发生缓存未命中（cache miss），此时 CPU 不得不从速度较慢的内存中加载所需数据。

为了尽可能达到更高的效率，缓存会采取以下数据加载机制。

• 缓存行：缓存不是单个字节地存储与加载数据，而是以缓存行为单位。相比于单个字节的传输，缓存行的传输形式更加高效。
• 预取机制：处理器会尝试预测数据访问模式（例如顺序访问、固定步长跳跃访问等），并根据特定模式将数据加载至缓存之中，从而提升命中率。
• 空间局部性：如果一个数据被访问，那么它附近的数据可能近期也会被访问。因此，缓存在加载某一数据时，也会加载其附近的数据，以提高命中率。
• 时间局部性：如果一个数据被访问，那么它在不久的将来很可能再次被访问。缓存利用这一原理，通过保留最近访问过的数据来提高命中率。

栈（stack）是一种遵循先入后出逻辑的线性数据结构。

如图 5-1 所示，我们把堆叠元素的顶部称为“栈顶”，底部称为“栈底”。将把元素添加到栈顶的操作叫作“入栈”，删除栈顶元素的操作叫作“出栈”。因此我们只能在栈顶添加或删除元素,然而，数组和链表都可以在任意位置添加和删除元素，因此栈可以视为一种受限制的数组或链表。

txt

基于数组实现的栈
vector<int> stack;
/* 获取栈的长度 */
stack.size()
入栈
stack.push_back(num);
出栈
stack.pop_back();
访问栈顶元素
stack.back();

back就是栈顶的位置

txt

有专用的栈方法
stack<int> stack;

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

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

/* 元素出栈 */
stack.pop(); // 无返回值

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

/* 判断是否为空 */
bool empty = stack.empty();

队列（queue）是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开。

txt

/* 初始化队列 */
queue<int> queue;

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

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

/* 元素出队 */
queue.pop();

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

/* 判断队列是否为空 */
bool empty = queue.empty();

添加队尾，删除队首—–先来后到

双向队列：

txt

/* 初始化双向队列 */
deque<int> deque;

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

/* 访问元素 */
int front = deque.front(); // 队首元素
int back = deque.back();   // 队尾元素

/* 元素出队 */
deque.pop_front();  // 队首元素出队
deque.pop_back();   // 队尾元素出队

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

/* 判断双向队列是否为空 */
bool empty = deque.empty();

DoublyListNode *pre, *cur = front; 确实是一个比较容易产生误解的地方，但实际上这行代码并不是同时给 pre 和 cur 赋值为 front。这行代码实际上相当于两行分开的声明和初始化：

txt

cpp
DoublyListNode *pre; // 声明一个指向 DoublyListNode 类型的指针 pre
DoublyListNode *cur = front; // 声明一个指向 DoublyListNode 类型的指针 cur，并将其初始化为 front

这里的 pre 只是声明了一个指针，但并没有初始化，所以它的值是未定义的，你需要在后续代码中对其进行初始化。而 cur 在声明时已经被初始化为 front。

哈希表（hash table），又称散列表，它通过建立键 key 与值 value 之间的映射，实现高效的元素查询。具体而言，我们向哈希表中输入一个键 key ，则可以在 O(1)时间内获取对应的值 value 。

unordered_map 是 C++ 标准库中的一种关联容器（Associative Container），它提供了快速的键值对存储和检索功能。它是通过哈希表实现的，因此提供了高效的插入、删除和查找操作。

txt

/* 初始化哈希表 */
unordered_map<int, string> map;

/* 添加操作 */
// 在哈希表中添加键值对 (key, value)
map[12836] = "小哈";
map[15937] = "小啰";
map[16750] = "小算";
map[13276] = "小法";
map[10583] = "小鸭";

/* 查询操作 */
// 向哈希表中输入键 key ，得到值 value
string name = map[15937];

/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
map.erase(10583);

/* 遍历哈希表 */
// 遍历键值对 key->value
for (auto kv: map) {
    cout << kv.first << " -> " << kv.second << endl;
}
// 使用迭代器遍历 key->value
for (auto iter = map.begin(); iter != map.end(); iter++) {
    cout << iter->first << "->" << iter->second << endl;
}

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

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

输入一个 key ，哈希函数的计算过程分为以下两步。

1. 通过某种哈希算法 hash() 计算得到哈希值。
2. 将哈希值对桶数量（数组长度）capacity 取模，从而获取该 key 对应的数组索引 index 。

txt

index = hash(key) % capacity

<Pair *> 表示这个 vector 存储的是指向 Pair 类型对象的指针。

vector<Pair *> 创建了一个存储指向 Pair 结构的指针的动态数组，即每个元素都是指向 Pair 结构的指针。

我们将多个输入对应同一输出的情况称为哈希冲突（hash collision）。

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

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

但此方法简单粗暴且有效，但效率太低，因为哈希表扩容需要进行大量的数据搬运与哈希值计算。为了提升效率，我们可以采用以下策略。

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

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

链式地址

在原始哈希表中，每个桶仅能存储一个键值对。链式地址（separate chaining）将单个元素转换为链表，将键值对作为链表节点，将所有发生冲突的键值对都存储在同一链表中。图 6-5 展示了一个链式地址哈希表的例子。

图 6-5 链式地址哈希表

基于链式地址实现的哈希表的操作方法发生了以下变化。

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

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

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

开放寻址

开放寻址（open addressing）不引入额外的数据结构，而是通过“多次探测”来处理哈希冲突，探测方式主要包括线性探测、平方探测和多次哈希等。

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

• 插入元素：通过哈希函数计算桶索引，若发现桶内已有元素，则从冲突位置向后线性遍历（步长通常为

• ），直至找到空桶，将元素插入其中。

• 查找元素：若发现哈希冲突，则使用相同步长向后进行线性遍历，直到找到对应元素，返回 value 即可；如果遇到空桶，说明目标元素不在哈希表中，返回 None 。

图 6-6 展示了开放寻址（线性探测）哈希表的键值对分布。根据此哈希函数，最后两位相同的 key 都会被映射到相同的桶。而通过线性探测，它们被依次存储在该桶以及之下的桶中。

值得注意的是，我们不能在开放寻址哈希表中直接删除元素。这是因为删除元素会在数组内产生一个空桶 None ，而当查询元素时，线性探测到该空桶就会返回，因此在该空桶之下的元素都无法再被访问到，程序可能误判这些元素不存在

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

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

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

平方探测

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

步。

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

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

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

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

二叉树的常用术语如图所示。

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

常见二叉树类型

完美二叉树

所有层的节点都被完全填满。

完全二叉树

只有最底层的节点未被填满，且最底层节点尽量靠左填充。

完满二叉树

除了叶节点之外，其余所有节点都有两个子节点。

平衡二叉树

任意节点的左子树和右子树的高度之差的绝对值不超过 1 。

[

理想结构与退化结构

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

完美二叉树是理想情况，可以充分发挥二叉树“分治”的优势。

链表则是另一个极端，各项操作都变为线性操作，时间复杂度退化至 O(n)

二叉树遍历

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

二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等。

层序遍历

从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。

层序遍历本质上属于广度优先遍历（breadth-first traversal），也称广度优先搜索（breadth-first search, BFS），它体现了一种“一圈一圈向外扩展”的逐层遍历方式。

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

txt

/* 层序遍历 */
vector<int> levelOrder(TreeNode *root) {
    // 初始化队列，加入根节点
    queue<TreeNode *> queue;
    queue.push(root);
    // 初始化一个列表，用于保存遍历序列
    vector<int> vec;
    while (!queue.empty()) {
        TreeNode *node = queue.front();
        queue.pop();              // 队列出队
        vec.push_back(node->val); // 保存节点值
        if (node->left != nullptr)
            queue.push(node->left); // 左子节点入队
        if (node->right != nullptr)
            queue.push(node->right); // 右子节点入队
    }
    return vec;
}

前序、中序和后序遍历都属于深度优先遍历（depth-first traversal），也称深度优先搜索（depth-first search, DFS），它体现了一种“先走到尽头，再回溯继续”的遍历方式。

前序、中序和后序遍历是针对二叉树的三种不同的遍历方式，它们的区别在于遍历节点的顺序：

1. 前序遍历（Preorder Traversal）：
   • 遍历顺序：根节点 -> 左子树 -> 右子树
   • 具体操作：先访问根节点，然后递归地对左子树进行前序遍历，最后递归地对右子树进行前序遍历。
2. 中序遍历（Inorder Traversal）：
   • 遍历顺序：左子树 -> 根节点 -> 右子树
   • 具体操作：先递归地对左子树进行中序遍历，然后访问根节点，最后递归地对右子树进行中序遍历。
3. 后序遍历（Postorder Traversal）：
   • 遍历顺序：左子树 -> 右子树 -> 根节点
   • 具体操作：先递归地对左子树进行后序遍历，然后递归地对右子树进行后序遍历，最后访问根节点。

总的来说，这三种遍历方式主要区别在于根节点的访问顺序与左右子树的递归顺序。

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

txt

/* 前序遍历 */
void preOrder(TreeNode *root) {
    if (root == nullptr)
        return;
    // 访问优先级：根节点 -> 左子树 -> 右子树
    vec.push_back(root->val);
    preOrder(root->left);
    preOrder(root->right);
}

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

/* 后序遍历 */
void postOrder(TreeNode *root) {
    if (root == nullptr)
        return;
    // 访问优先级：左子树 -> 右子树 -> 根节点
    postOrder(root->left);
    postOrder(root->right);
    vec.push_back(root->val);
}

1. “递”表示开启新方法，程序在此过程中访问下一个节点。
2. “归”表示函数返回，代表当前节点已经访问完毕。

二叉树数组表示

用数组来表示二叉树

表示完美二叉树

给定一棵完美二叉树，我们将所有节点按照层序遍历的顺序存储在一个数组中，则每个节点都对应唯一的数组索引。

根据层序遍历的特性，我们可以推导出父节点索引与子节点索引之间的“映射公式”：若某节点的索引为i ，则该节点的左子节点索引为2i+1 ，右子节点索引为2i+2

映射公式的角色相当于链表中的节点引用（指针）。给定数组中的任意一个节点，我们都可以通过映射公式来访问它的左（右)子节点。

表示任意二叉树

完美二叉树是一个特例，在二叉树的中间层通常存在许多 None 。由于层序遍历序列并不包含这些 None ，因此我们无法仅凭该序列来推测 None 的数量和分布位置。这意味着存在多种二叉树结构都符合该层序遍历序列。

为了解决此问题，我们可以考虑在层序遍历序列中显式地写出所有 None 。如图 7-14 所示，这样处理后，层序遍历序列就可以唯一表示二叉树了

txt

/* 二叉树的数组表示 */
// 使用 int 最大值 INT_MAX 标记空位
vector<int> tree = {1, 2, 3, 4, INT_MAX, 6, 7, 8, 9, INT_MAX, INT_MAX, 12, INT_MAX, INT_MAX, 15};

完全二叉树:只有最底层的节点未被填满，且最底层节点尽量靠左填充。

完全二叉树非常适合使用数组来表示。回顾完全二叉树的定义，None 只出现在最底层且靠右的位置，因此所有 None 一定出现在层序遍历序列的末尾。这意味着使用数组表示完全二叉树时，可以省略存储所有 None ，非常方便.

优点与局限性

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

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

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

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

二叉搜索树

二叉搜索树（binary search tree）满足以下条件:

1.对于根节点，左子树中所有节点的值<根节点的值<右子树中所有节点的值。

2,任意节点的左、右子树也是二叉搜索树，即同样满足条件 1. 。

插入节点

给定一个待插入元素 num ，为了保持二叉搜索树“左子树 < 根节点 < 右子树”的性质,

1. 查找插入位置：与查找操作相似，从根节点出发，根据当前节点值和 num 的大小关系循环向下搜索，直到越过叶节点（遍历至 None ）时跳出循环。
2. 在该位置插入节点：初始化节点 num ，将该节点置于 None 的位置。

只能插在NONE节点处,即*pre = nullptr

• 二叉搜索树不允许存在重复节点，否则将违反其定义。因此，若待插入节点在树中已存在，则不执行插入，直接返回。
• 为了实现插入节点，我们需要借助节点 pre 保存上一轮循环的节点。这样在遍历至 None 时，我们可以获取到其父节点，从而完成节点插入操作。

删除节点

当待删除节点的度为2时，我们无法直接删除它，而需要使用一个节点替换该节点。由于要保持二叉搜索树“左子树 <根节点 <右子树”的性质，因此这个节点可以是右子树的最小节点或左子树的最大节点。

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

二叉树的中序遍历遵循“左 根 右”的遍历顺序，而二叉搜索树满足“左子节点 根节点 右子节点”的大小关系。

这意味着在二叉搜索树中进行中序遍历时，总是会优先遍历下一个最小节点，从而得出一个重要性质：二叉搜索树的中序遍历序列是升序的。

利用中序遍历升序的性质，我们在二叉搜索树中获取有序数据仅需O(n)时间，无须进行额外的排序操作，非常高效。

int val{}; 是C++中的变量声明语句，其中 int 表示变量的类型为整数类型，val 是变量名，{} 表示进行了值初始化。

在C++11及其之后的标准中，使用 {} 进行初始化被称为列表初始化或者统一初始化。对于内置类型（如 int、float、double 等），使用 {} 进行初始化时，如果未提供初始值，则会将变量初始化为零值，即 0。这种初始化方式也可以保证初始化的一致性，并且在某些情况下可以避免隐式类型转换带来的问题。

AVL 树

在多次插入和删除操作后，二叉搜索树可能退化为链表。在这种情况下，所有操作的时间复杂度将从

O(log n)劣化成O(n)

AVL 树既是二叉搜索树，也是平衡二叉树，同时满足这两类二叉树的所有性质，因此是一种平衡二叉搜索树（balanced binary search tree）。

节点的平衡因子（balance factor）定义为节点左子树的高度减去右子树的高度，同时规定空节点的平衡因子为0 。

AVL 树旋转

AVL 树的特点在于“旋转”操作，它能够在不影响二叉树的中序遍历序列的前提下，使失衡节点重新恢复平衡。换句话说，旋转操作既能保持“二叉搜索树”的性质，也能使树重新变为“平衡二叉树”。

我们将平衡因子绝对值>1的节点称为“失衡节点”。根据节点失衡情况的不同，旋转操作分为四种：右旋、左旋、先右旋后左旋、先左旋后右旋。

1. 右旋

当节点 child 有右子节点（记为 grand_child ）时，需要在右旋中添加一步：将 grand_child 作为 node 的左子节点。

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

先左旋后右旋

先右旋后左旋

DFS（深度优先搜索）遍历二叉树是一种遍历或搜索算法，用来访问二叉树中的所有节点，其目的是尽可能深地访问树的分支。DFS在二叉树中常用的有三种遍历方式：前序遍历（Pre-order）、中序遍历（In-order）和后序遍历（Post-order）。下面详细解释这三种遍历方式：

1. 前序遍历（Pre-order Traversal）：
   • 访问顺序：先访问根节点，然后递归地进行前序遍历左子树，接着递归地进行前序遍历右子树。
   • 应用：前序遍历常用于打印树的结构，复制树结构。
2. 中序遍历（In-order Traversal）：
   • 访问顺序：先递归地进行中序遍历左子树，然后访问根节点，最后递归地进行中序遍历右子树。
   • 应用：对于二叉搜索树（BST），中序遍历可以得到一个有序的数据序列。
3. 后序遍历（Post-order Traversal）：
   • 访问顺序：先递归地进行后序遍历左子树，然后递归地进行后序遍历右子树，最后访问根节点。
   • 应用：后序遍历常用于访问节点后再执行操作的场景，如计算一个文件夹的总大小时。

DFS 遍历的核心在于使用递归（或显式使用栈）来实现持续深入每个分支直到达到叶子节点或满足某些条件后回溯到上一节点。这种方式非常适合处理具有层级关系的数据，如文件系统的目录结构、组织结构等。在二叉树的上下文中，DFS遍历可以帮助理解和操作树的结构。

txt

visited.count(adjVet)

count 是 unordered_set 提供的的一个成员函数，它返回集合中指定元素的数量。如果 adjVet 是指向图中的一个顶点的指针，并且这个顶点已经被添加到 visited 集合中，那么 visited.count(adjVet) 将返回 1，表示该顶点已经被访问过。如果 adjVet 不在 visited 集合中，那么返回 0，表示该顶点还没有被访问过。

txt

visited.emplace(adjVet);

emplace 是一个函数，它用于在容器中直接构造并插入元素，而不需要创建元素的副本