Data Structures and Algorithms

在计算机科学中，数据结构（Data Structure）是计算机中存储、组织数据的方式。算法（Algorithms）用来设计一种使用计算机来解决问题的方法。

算法效率的度量

时间复杂度

如何计算：

1. 找到一个基本操作（最深层循环）
2. 分析该基本操作的执行次数 $x$ 与问题规模 $n$ 的关系 $x = f(n)$
3. $x$ 的数量级 $O(x)$ 就是算法时间复杂度 $T(n)$

常用技巧：

• 加法规则：$O(f(n)) + O(g(n)) = O(\max \lbrace f(n), g(n)) \rbrace$
• 乘法规则：$O(f(n)) \times O(g(n)) = O(f(n) \times g(n))$
• $O(1) < O(\log_2 n) < O(n) < O(n\log_2 n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$

三种复杂度：

• 最坏时间复杂度：考虑输入数据最坏的情况
• 平均时间复杂度：考虑所有输入数据都等概率出现的情况
• 最好时间复杂度：考虑输入数据"最好"的情况

空间复杂度

如何计算：

1. 找到所占空间大小与问题规模相关的变量
2. 分析所占空间 $x$ 与问题规模 $n$ 的关系 $x = f(n)$
3. $x$ 的数量级 $O(x)$ 就是算法空间复杂度 $S(n)$

特别注意含有递归的程序：找到递归调用深度 $x$ 与问题规模 $n$ 的关系 $x = f(n)$

链表(Linked List)

单链表的插入

头插一个节点

• head初始指向NULL

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

struct Node{
    int data;
    struct Node *next;
};
// global variable, can be accessed anywhere
struct Node* head;

void Insert(int x)
{
    // malloc返回指向起始地址的指针
    struct Node* temp = (Node*)malloc(sizeof(struct Node));
    temp->data = x;
    temp->next = head;
    head = temp; 
}

任意位置插入节点

分配给我们的程序或应用程序的内存通常分为：

• Heap
• Stack
• Static/Global
• Code(Text)

应用程序内存的一部分用于存储所有需要被执行的指令，另一部分用来存储全局变量，贯穿整个程序或者说应用程序的生命周期。

存储器的一部分称为栈，用于存储所有有关函数调用执行的信息，存储所有局部变量。并且这三个部分的大小是固定的，它们的大小在编译的时候就决定了。最后一部分我们称为堆或空闲存储，是不固定的，我们可以请求内存运行时从堆中读取数据，这就是使用malloc或new运算符所做的事情。

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

struct Node{
    int data;
    struct Node *next;
};
// global variable, can be accessed anywhere
struct Node* head;

void Insert(int data, int n)
{
    // Node* temp1 = new Node();
    struct Node* temp1 = (struct Node*)malloc(sizeof(struct Node*));
    temp1->data = data;
    temp1->next = NULL;

    // 当想插入头部时
    if (n == 1)
    {
        temp1->next = head;
        head = temp1;
        return;
    }

    Node* temp2 = head;
    // 其他情况：首先从头开始，需要转到第n-1个节点
    for (int i = 0; i < n - 2; ++i)
    {
        temp2 = temp2->next;
    }
    temp1->next = temp2->next;
    temp2->next = temp1;
}

总结

• 按位序插入（带头节点）：平均时间复杂度 $O(n)$

单链表的删除

删除链表中的某个节点一定需要知道这个点的前继节点，所以需要一直有指针指向前继节点

还有一种删除是伪删除，是指复制一个和要删除节点值一样的节点，然后删除，这样就不必知道其真正的前继节点了

反转链表-单向链表

[206] Reverse Linked List

依次遍历链表节点，每遍历一个节点即逆置一个节点：

• 原始链表：head -> 1 -> 2 -> 3 -> 4 -> 5
• 新链表：new_head -> NULL

循环5次后：

• 原始链表：head -> NULL
• 新链表：new_head -> 5 -> 4 -> 3 -> 2 -> 1

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def reverseList(self, head):
        new_head = None
        while head:
            # 第一步首先需要备份，备份后才可以修改head指针
            temp = head.next
            head.next = new_head
            new_head = head
            head = temp
            
        return new_head

[92] Reverse Linked List II

将链表从位置m到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
31
32
33
34
35
36
37
38
39

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        # 计算需要逆置的节点个数
        change_len = n - m + 1
        # 初始化开始逆置的节点的前驱
        pre_head = None
        # 最终转换后的链表头节点，非特殊情况即为head
        result = head

        # 1. head向前移动m-1个位置，记录该节点前驱和该节点
        while head and m - 1:
            # 记录head前驱
            pre_head = head
            head = head.next
            m = m - 1
        
        # 将modify_list_tail指向当前的head，即逆置后的链表尾
        modify_list_tail = head
        new_head = None

        # 2. 从head开始，逆置change_len = n-m+1个节点
        while head and change_len:
            temp = head.next
            head.next = new_head
            new_head = head
            head = temp
            change_len = change_len - 1

        # 3. 将pre_head与new_head连接，modify_list_tail与head链接
        # 连接逆置后的链表尾与逆置段的后一个节点
        modify_list_tail.next = head

        if pre_head:
            pre_head.next = new_head
        else:
            # 如果pre_head为空，说明m=1从第一个节点开始逆置，结果即为逆置后的头节点
            result = new_head

        return result

栈(Stack)

栈是一种LIFO(Last In First Out)的数据结构，常用方法有添加元素，取栈顶元素，弹出栈顶元素，判断栈是否为空

1
2
3
4
5
6

stack = []
len(stack) # size of stack

# more efficient stack
import collections
stack = collections.deque()

• len(stack) != 0 - 判断stack是否为空
• stack[-1] - 取栈顶元素，不移除
• pop() - 移除栈顶元素并返回该元素
• append(item) - 向栈顶添加元素

队列(Queue)

队列是一个FIFO(先进先出)的数据结构，并发中使用较多，可以安全地将对象从一个任务传给另一个任务

• 通过pop()在list的尾部弹出元素实现Stack的LIFO
• 如果是pop(0)则弹出头部的元素实现Queue的FIFO

1
2
3
4
5
6
7
8
9
10

>>> l = []
>>> l.append(2)
>>> l.append(4)
>>> l.append(6)
>>> l
[2, 4, 6]
>>> l.pop() # 后进先出 -> 栈
6
>>> l.pop(0) # 先进先出 -> 队列
2

排序(Sort)

插入排序(Insertion Sort)

1. 从第一个元素开始，该元素可认为已排序
2. 取下一个元素，对已排序数组从后往前扫描
3. 若从排序数组中取出的元素大于新元素，则移至下一位置
4. 重复步骤3，直至找到已排序元素小于或等于新元素的位置
5. 插入新元素至该位置
6. 重复2~5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 插入排序
void insertSort(int arr[], int n)
{
    int key, j;
    for (int i = 1; i < n; i++)
    {
        // 1.选择未排序的第一个元素key
        key = arr[i];
        // 从 key 的前一个位置开始比较
        j = i - 1;

        // 2.从key前一个元素开始比较，找到比key大的元素就继续向前找
        while (j >= 0 && arr[j] > key)
        {
            // 用前一个元素覆盖当前元素
            arr[j + 1] = arr[j];
            j -= 1;
        }
        // 3.循环结束后，将 key 插入到相应位置
        arr[j + 1] = key;
    }
}

• 稳定性：由于只需要找到不大于当前数的位置而并不需要交换，因此，直接插入排序是稳定的排序方法
• 适用场景：插入排序由于 $O(n^2)$ 的复杂度，在数组较大的时候不适用。但是，在数据比较少的时候，是一个不错的选择，一般做为快速排序的扩充

希尔排序(shell sort)

希尔排序是插入排序的改良版，又叫缩小增量排序，在希尔排序出现之前，计算机界普遍存在"排序算法不可能突破 $O(n^2)$ "的观点。希尔排序是第一个突破 $O(n^2)$ 的排序算法，它是简单插入排序的改进版，与插入排序不同的是，会优先比较距离较远的元素。希尔排序的提出，主要基于以下两点：

1. 插入排序算法在数组基本有序的情况下，可以近似达到 $O(n)$ 复杂度，效率极高
2. 但插入排序每次只能将数据移动一位，在数组较大且基本无序的情况下性能会迅速恶化

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

1. 选择一个增量序列 $t_1, t_2, \cdots, t_k$，其中 $t_i > t_j, t_k = 1$
2. 按增量序列个数 $k$，对序列进行 $k$ 趟排序
3. 每趟排序，根据对应的增量 $t_i$，将待排序列分割成若干长度为 $m$ 的子序列，分别对各子表进行直接插入排序
   1. 仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度

简单地来说其包含四层循环：最外面一层是增量，每循环一次增量减一，直到最后进行增量为1的排序。次外层是对每组数据进行排序。还有两层就是插入排序的操作

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

void shellSort(int arr[], int n)
{
    // Donald Shell增量
    for (int gap = n/2; gap >= 1; gap/=2)
    {
        for (int i = gap; i < n; i++)
        {
            for (int j = i; j >= gap && arr[j - gap] > arr[j]; j-=gap)
            {
                int temp = arr[j - gap];
                arr[j - gap] = arr[j];
                arr[j] = temp;
            }
        }
    }
} 

• 稳定性：Shell排序是一个多次插入的过程。在一次插入中我们能确保不移动相同元素的顺序，但在多次的插入中，相同元素完全有可能在不同的插入轮次被移动，最后稳定性被破坏
• 适用场景：Shell排序虽然快，但是毕竟是插入排序，其数量级并没有后起之秀–快速排序 $O(n \log n)$ 快。在大量数据面前，Shell排序不是一个好的算法。但是，中小型规模的数据完全可以使用它

选择排序(Selection Sort)

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

// 选择排序
void selectionSort(int arr[], int n)
{
    // 最后一轮不需要遍历，已经是有顺序了
    for (int i = 0; i < n - 1; i++)
    {
        int min_index = i;
        // 循环查找最小值
        for (int j = i + 1; j < n; j++)
        {
            if (arr[min_index] > arr[j])
                min_index = j;
        }
        // 交换
        swap(&arr[min_index], &arr[i]);
    }
}

• 稳定性：用数组实现的选择排序是不稳定的，用链表实现的选择排序是稳定的。不过，一般提到排序算法时，大家往往会默认是数组实现，所以选择排序是不稳定的
• 适用场景：选择排序实现也比较简单，并且由于在各种情况下复杂度波动小，因此一般是优于冒泡排序的。在所有的完全交换排序中，选择排序也是比较不错的一种算法。但是，由于固有的O(n2)复杂度，选择排序在海量数据面前显得力不从心。因此，它适用于简单数据排序

冒泡排序(Bubble Sort)

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

// 冒泡排序
void bubbleSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        // 以后每次循环的次数为arr.length-1-i
        for (int j = 0; j < n - 1 - i; j++)
        {
            // 相邻两个元素作比较，如果前面元素大于后面，进行交换
            if (arr[j] > arr[j + 1])
                swap(&arr[j], &arr[j + 1]);
        }
    }
}

• 稳定性：在相邻元素相等时，它们并不会交换位置，所以，冒泡排序是稳定排序
• 适用场景：冒泡排序思路简单，代码也简单，特别适合小数据的排序。但是，由于算法复杂度较高，在数据量大的时候不适合使用
• 代码优化：由于在数据基本有序的情况下，性能最好。要使算法在最佳情况下有 $O(n)$ 复杂度，需要做一些改进，增加一个swap的标志，当前一轮没有进行交换时，说明数组已经有序，没有必要再进行下一轮的循环了，直接退出

堆排序(Heap Sort)

下面这个链接我觉得是非常通俗易懂的

• 图解排序算法(三)之堆排序

堆定义和存储

二叉堆是一种完全二叉树，对于完全二叉树来说，只有树 的最后一层的节点不是满的，其他层都是满的，完全二叉树采用顺序存储，利用数组进行实现

• Node: $i$
• Parent = $\lfloor \frac{i}{2} \rfloor$
• Left child = $2i$
• Right child = $2i + 1$

建堆

在堆中定义以下几种操作：其中步骤1是给步骤2和3用的

1. 最大堆调整（Max-Heapify）：将堆的末端子节点 $\lfloor \frac{n}{2} \rfloor \sim 1$ 作调整（从最后一颗子树开始，往前进行筛选），使得子节点永远小于父节点
2. 创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆；建堆时可以自顶向下，也可以采取自底向上
3. 堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

排序

可以发现，如果使用最小堆进行排序的话，数组中的元素最后会是逆序的，还要格外的reverse，所以要从小到大排序还是要用最大堆

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

// heapify 堆调整为大堆顶，即将最大值放在根结点
void heapify(int arr[], int n, int i)
{
    // n 堆的大小
    // i 子树根的索引
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    // 找出两个子节点中的最大值
    // 当左节点存在且比根节点大
    if (left < n && arr[largest] < arr[left])
        largest = left;

    // 当右节点存在且比根节点大
    if (right < n && arr[largest] < arr[right])
        largest = right;

    // 当找出的最大值不是当前父节点对应的值, 那么将父节点和最大值所对应的下标交换
    // If largest is not root
    if (largest != i)
    {
        swap(&arr[largest], &arr[i]);
        heapify(arr, n, largest);
    }
}

// 堆排序
void heapSort(int arr[], int n)
{
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        heapify(arr, n, i);
    }

    // 一对一的将元素从堆中删除
    for (int i = n - 1; i >= 0; i--)
    {
        // 交换现在的根节点到最后
        swap(&arr[0], &arr[i]);
        // 重新创建最大堆，确保array[0]是[0, i]中的最大值
        // 注意这里一定要将顶堆限制在[0, i]的范围内，否则刚抽取出的最大值又被放到最大堆的起始了！
        heapify(arr, i, 0);
    }
}

• 稳定性：堆排序存在大量的筛选和移动过程，属于不稳定的排序算法
• 适用场景：堆排序在建立堆和调整堆的过程中会产生比较大的开销，在元素少的时候并不适用。但是，在元素比较多的情况下，还是不错的一个选择。尤其是在解决诸如"前 $n$ 大的数"一类问题时，几乎是首选算法

快速排序(Quick 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

int partition(int arr[], int low, int high)
{
    int i = low;
    int j = high - 1;
    // 枢纽元素，这里初始选为最后一个
    int pivot = arr[high];

    // j指向比枢纽小的元素，i指向比枢纽大的元素
    while (1)
    {
        // j遇到比枢纽元素小的元素就停下来，i遇到比枢纽元素大的元素停下来
        while (arr[i] < pivot)
            i += 1;
        while (arr[j] > pivot)
            j -= 1;

        if (i < j)
            swap(&arr[i], &arr[j]);
        else
            break;
    }
    // 把枢纽元素放到正确的位置
    swap(&arr[i], &arr[high]);
    // 返回枢纽的位置
    return i;
}

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int mid = partition(arr, low, high);
        quickSort(arr, low, mid - 1);
        quickSort(arr, mid + 1, high);
    }
}

时间复杂度(平均)：$O(n \log_2 n)$

1. 每一层划分时间复杂度为 $O(N)$
2. 平均划分层数为 $O(\log_2 n)$

最坏时间复杂度：$O(n^2)$，即这个时候原来数组本来就是从小到大顺序，我们选基准元素是最后一个的情况

1. 每一层划分时间复杂度为 $O(N)$
2. 平均划分层数为 $O(n)$

• 稳定性：快速排序并不是稳定的。这是因为我们无法保证相等的数据按顺序被扫描到和按顺序存放
• 适用场景：快速排序在大多数情况下都是适用的，尤其在数据量大的时候性能优越性更加明显。但是在必要的时候，需要考虑下优化以提高其在最坏情况下的性能

归并排序(Merge Sort)

归并排序有2种：迭代版和递归版

迭代版本：

1. 把长度为 $n$ 的输入序列分成两个长度为 $n/2$ 的子序列
2. 对这两个子序列分别采用归并排序
3. 将两个排序好的子序列合并成一个最终的排序序列

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

// 合并
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    // 申请两个辅助数组L，R
    int L[n1], R[n2];

    // 复制数据至辅助数组L，R中
    for (i = 0; i < n1; i++)
    {
        L[i] = arr[l + i];
    }
    for (j = 0; j < n2; j++)
    {
        R[j] = arr[m + 1 + j];
    }

    i = 0;
    j = 0;
    k = l;

    // 合并
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i += 1;
        }
        else
        {
            arr[k] = R[j];
            j += 1;
        }
        k += 1;
    }

    // 若辅助数组L中有剩余
    while (i < n1)
    {
        arr[k] = L[i];
        i += 1;
        k += 1;
    }

    // 若辅助数组R中有剩余
    while (j < n2)
    {
        arr[k] = R[j];
        j += 1;
        k += 1;
    }
}

// 归并排序
void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        // (l+r)/2与一样，这里是为了防止溢出
        int mid = l + (r - l) / 2;

        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }
}

• 稳定性：因为我们在遇到相等的数据的时候必然是按顺序"抄写"到辅助数组上的，所以，归并排序同样是稳定算法
• 适用场景：归并排序在数据量比较大的时候也有较为出色的表现（效率上），但是，其空间复杂度 $O(n)$ 使得在数据量特别大的时候（例如，1千万数据）几乎不可接受。而且，考虑到有的机器内存本身就比较小，因此，采用归并排序一定要注意

计数排序(Counting Sort)

算法描述：

1. 定新数组大小：找出待排序的数组中最大和最小的元素
2. 统计次数：统计数组中每个值为 $i$ 的元素出现的次数，存入新数组 $C$ 的第 $i$ 项
3. 对统计次数逐个累加：对所有的计数累加（从 $C$ 中的第一个元素开始，每一项和前一项相加）
4. 反向填充目标数组：将每个元素 $i$ 放在新数组的第 $C(i)$ 项，每放一个元素就将 $C(i)$ 减去1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def countingSort(array):
    # 获取最大，最小值
    largest = max(array)
    smallest = min(array)
    # 用于统计个数的空数组，初始化为0
    counter = [0 for i in range(largest - smallest + 1)]
    # 桶内索引值
    index = 0

    # 统计每个元素出现的次数
    for i in range(len(array)):
        counter[array[i] - smallest] += 1
    for j in range(len(counter)):
        while counter[j] > 0:
            # 取出元素
            array[index] = j + smallest
            index += 1
            counter[j] -= 1
    return array

整个过程需要遍历两次数组，一次是遍历长度为 $n$ 的数组，另一次是从计数器（假设有 $k$ 个计数器）中遍历，因此时间复杂度为 $O(n + k)$ 。而在计数排序的过程中用到了长度为 $k$ 的额外数组，故空间复杂度为 $O(k)$。

• 稳定性：相同的两个元素，经过排序后位置顺序没有变化，稳定
• 适用场景：排序目标要能够映射到整数域，其最大值最小值应当容易辨别。例如高中生考试的总分数，显然用0-750就可以了。计数排序需要占用大量空间，它比较适用于数据比较集中的情况

桶排序(Bucket Sort)

• 稳定性：可以看出，在分桶和从桶依次输出的过程是稳定的。但是，由于我们在对每个桶进行排序时使用了其他算法，所以，桶排序的稳定性依赖于这一步。如果我们使用了快排，显然，算法是不稳定的
• 适用场景：桶排序可用于最大最小值相差较大的数据情况，但桶排序要求数据的分布必须均匀，否则可能导致数据都集中到一个桶中。比如[104,150,123,132,20000], 这种数据会导致前4个数都集中到同一个桶中。导致桶排序失效

基数排序(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
49
50
51
52

// A utility function to get maximum value in arr[]
int getMax(int arr[], int n)
{
    int mx = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > mx)
            mx = arr[i];
    return mx;
}

// A function to do counting sort of arr[] according to
// the digit represented by exp.
void countSort(int arr[], int n, int exp)
{
    int output[n]; // output array
    int count[10] = {0};

    // Store count of occurrences in count[]
    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    // Change count[i] so that count[i] now contains actual
    // position of this digit in output[]
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    // Build the output array
    for (int i = n - 1; i >= 0; i--)
    {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // Copy the output array to arr[], so that arr[] now
    // contains sorted numbers according to current digit
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

// The main function to that sorts arr[] of size n using
// Radix Sort
void radixSort(int arr[], int n)
{
    // Find the maximum number to know number of digits
    int m = getMax(arr, n);

    // Do counting sort for every digit. Note that instead
    // of passing digit number, exp is passed. exp is 10^i
    // where i is current digit number
    for (int exp = 1; m / exp > 0; exp *= 10)
        countSort(arr, n, exp);
}

• 稳定性：通过上面的排序过程，我们可以看到，每一轮映射和收集操作，都保持从左到右的顺序进行，如果出现相同的元素，则保持他们在原始数组中的顺序。可见，基数排序是一种稳定的排序
• 适用场景：基数排序要求较高，元素必须是整数，整数时长度10W以上，最大值100W以下效率较好，但是基数排序比其他排序好在可以适用字符串，或者其他需要根据多个条件进行排序的场景，例如日期，先排序日，再排序月，最后排序年 ，其它排序算法可是做不了的

树(Tree)

树的基本概念

树是一种非线性表结构，树的重要性质：

• 如果树有 $n$ 个顶点，那么其就有 $n - 1$ 条边，这说明了树的顶点数和边数是同阶的。
• 任何一个节点到根节点存在唯一路径，路径的长度为节点所处的深度

二叉树(Binary Tree)

二叉树的第 $i$ 层至多有 $2^{i-1}$ 个节点；深度为 $k$ 的二叉树至多有 $2^k - 1$ 个节点

二叉树的遍历

• 前序遍历(Pre-order)：根-左-右
• 中序遍历(In-order)：左-根-右
• 后序遍历(Post-order)：左-右-根

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

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

class Traversal(object):
    def __init__(self):
        # stack
        self.traverse_path = list()

    def preorder(self, root):
        if root:
            # 访问根节点-第一次路过时访问(前序遍历)
            self.traverse_path.append(root.val)
            # 递归遍历左子树
            self.preorder(root.left)
            # 递归遍历右子树
            self.preorder(root.right)

    def inorder(self,root):
        if root:
            self.inorder(root.left)
            # 访问根节点-第二次路过时访问(中序遍历)
            self.traverse_path.append(root.val)
            self.inorder(root.right)

    def postorder(self,root):
        if root:
            self.postorder(root.left)
            self.postorder(root.right)
            # 访问根节点-第三次路过时访问(后序遍历)
            self.traverse_path.append(root.val)

除此之外，二叉树还有层序遍历：

• [102] Binary Tree Level Order Traversal

二叉查找树(Binary Search Tree)

二叉排序树相关操作的代码实现：查找，插入，删除

这里二叉排序树的删除：

1. 如果要删除的节点是叶节点，即 No Child，则直接删除，不会破坏二叉排序树的性质
2. 如果要删除的节点只有一个子节点，即 One child，则让删除的节点的子树直接替代它的位置即可
3. 如果要删除的节点有2个子节点，即 2 children，则第一种方案：可以从当前删除节点的右子树中，寻找最小值的节点来替代（也就是右子树按照中序遍历第一个被访问的元素）；第二种方案：可以从当前删除节点的左子树中，寻找最大值的节点来替代

关于查找效率分析：

最好情况：$n$ 个节点的二叉树最小高度为 $\lfloor \log_2 n \rfloor + 1$。平均查找长度 $= O(\log_2 n)$

最坏情况：每个节点只有一个分支，树高$h =$ 节点数 $n$。平均查找长度 $= O(n)$

平衡二叉树(AVL)

[110] Balanced Binary Tree

• 代码实现

调整不平衡

• LL：在A的左孩子的左子树插入导致A不平衡，将A的左孩子右上旋
• RR：在A的右孩子的右子树插入导致A不平衡，将A的右孩子左上旋
• LR：在A的左孩子的右子树插入导致A不平衡，将A的左孩子的右孩子先左上旋再右上旋
• RL：在A的右孩子的左子树插入导致A不平衡，将A的右孩子的左孩子先右上旋再左上旋

图(Graph)

图的表示通常使用邻接矩阵和邻接表，前者易实现但是对于稀疏矩阵会浪费较多空间，后者使用链表的方式存储信息但是对于图搜索时间复杂度较高

邻接矩阵

设顶点个数为 $V$, 那么邻接矩阵可以使用 $V \times V$ 的二维数组来表示。 $g[i][j]$ 表示顶点 $i$ 和顶点 $j$ 的关系，对于无向图可以使用0/1表示是否有连接，对于带权图则需要使用INF来区分。有重边时保存边数或者权值最大/小的边即可

1
2
3
4
5
6

#define MaxVertexNum 100
typedef struct {
    char Vex[MaxVertexNum];                 // 顶点表
    bool Edge[MaxVertexNum][MaxVertexNum];  // 邻接矩阵，边表
    int vexnum, arcnum;                     // 图的当前顶点数和边数/弧数
} MGraph;

1
2
3
4
5
6
7
8
9

#define MaxVertexNum 100
#define INFINITY                                // 定义常量无穷
typedef char VertexType;                        // 顶点的数据类型
typedef int EdgeType;                           // 带权图中边上权值的数据类型
typedef struct {
    VertexType Vex[MaxVertexNum];               // 顶点
    EdgeType Edge[MaxVertexNum][MaxVertexNum];  // 边的权
    int vexnum, arcnum;                         // 图的当前顶点数和边数/弧数
} MGraph;

邻接表法

图的基本操作

图的广度优先遍历

图的深度优先遍历

最小生成树

最短路径问题

Leetcode 刷题

链表

栈，队列，堆

贪心

递归，回溯，分治

二叉树与图

二分查找与二叉排序树

哈希表与字符串

搜索

动态规划

复杂数据结构

统计素数的个数

统计 N 以内的素数个数（素数：只能被1和自身整除的自然数，0和1除外）

暴力算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

func isPrime(x int) bool {
	for i := 2; i*i <= x; i++ {
		if x%i == 0 {
			return false
		}
	}

	return true
}

func countPrime(n int) int {
	count := 0
	for i := 2; i < n; i++ {
		if isPrime(i) {
			count += 1
		} else {
			count += 0
		}
	}

	return count
}

埃筛法：

参考

• 2020 王道考研 数据结构
• [算法总结] 十大排序算法
• 算法与数据结构等 - 知识荟萃