数据结构与算法之美（一）

基础知识

20个最常用的、最基础数据结构与算法

10个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树。

10个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

几种常见时间复杂度实例分析

常见的复杂度量级

常量阶O(1)、对数阶O(log n)、 线性阶O(n)、线性对数阶O(nlog n)、指数阶O(2^n)、阶乘阶O(n!)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)。

常见的多项式时间复杂度

  1. O(1)

    只要代码的执行时间不随n的增大而增大，这样代码的时间复杂度我们都记作O(1)。或者说，一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是O(1)。

  2. O(log n)、O(nlog n)

    代码例子

    1
    2
    3
    4
    5
    int i = 1;
    while (i <= n)
    {
        i = i*2;
    }

    通过2x=n求解x这个问题我们想高中应该就学过了，我就不多说了。x=log2 n，所以，这段代码的时间复杂度就是O(log2 n)。

    不管是以2为底、以3为底，还是以10为底，我们可以把所有对数阶的时间复杂度都记为O(log n)。

    如果一段代码的时间复杂度是O(log n)，我们循环执行n遍，时间复杂度就是O(nlog n)了。而且，O(nlog n)也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是O(nlog n)。

  3. O(m+n)、O(m*n)

    代码例子

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    int cal(int m, int n)
    {
        int sum_1 = 0;
        int i = 1;
        for(; i < m; ++i)
        {
            sum_1 = sum_1 + i;
        }

        int sum_2 = 0;
        int j = 1;
        for(; j < n; ++j)
        {
            sum_2 = sum_2 + j;
        }
        return sum_1+sum_2;
    }

    从代码中可以看出，m和n是表示两个数据规模。我们无法事先评估m和n谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是O(m+n)。

    针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为：T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法则继续有效：T1(m) * T2(n) = O(f(m) * f(n))。

空间复杂度分析

常用的空间复杂度就是O(1)、O(n)、O(n^2)。

最好、最坏情况时间复杂度

为了表示代码在不同情况下的不同时间复杂度，我们需要引入三个概念：最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度。

  • 最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度。
  • 最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度。

数组

数组是一种线性表结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

定义的关键词

  • 线性表。线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。
  • 连续的内存空间和相同类型的数据。正是因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问”。但有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

数组支持随机访问，根据下标随机访问的时间复杂度为O(1)，平均情况时间复杂度为O(n)。

链表

三种最常见的链表结构

单链表：

  • 链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址（后继指针next）。
  • 有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址NULL，表示这是链表上最后一个结点。
  • 针对链表的插入和删除操作，我们只需要考虑相邻结点的指针改变，所以对应的时间复杂度是O(1)。
  • 链表随机访问的性能没有数组好，需要O(n)的时间复杂度。

循环链表：

  • 是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。

  • 优点是从链尾到链头比较方便，当要处理的数据具有环型结构特点时，就特别适合采用循环链表

双向链表：

  • 支持两个方向，每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点。

  • 双向链表可以支持O(1)时间复杂度的情况下找到前驱结点。

  • 对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。因为，我们可以记录上次查找的位置p，每次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化；而消耗过多内存的程序，可以通过消耗更多的时间（时间换空间）来降低内存的消耗。

链表Vs数组

时间复杂度数组链表
插入删除O(n)O(1)
随机访问O(1)O(n)

数组简单易用，在实现上使用的是连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法有效预读。
数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区别。

写链表代码的技巧

  1. 理解指针或引用的含义

    将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

  2. 警惕指针丢失和内存泄漏

    我们插入结点时，一定要注意操作的顺序，要先将结点x的next指针指向结点b，再把结点a的next指针指向结点x，这样才不会丢失指针，导致内存泄漏。

  3. 利用哨兵简化实现难度

    利用哨兵，可以统一为相同的代码实现逻辑了。

  4. 重点留意边界条件处理

    用来检查链表代码是否正确的边界条件

    • 如果链表为空时，代码是否能正常工作？
    • 如果链表只包含一个结点时，代码是否能正常工作？
    • 如果链表只包含两个结点时，代码是否能正常工作？
    • 代码逻辑在处理头结点和尾结点的时候。是否能正常工作？

  5. 举例画图，辅助思考

    你可以找一个具体的例子，把它画在纸上，释放一些脑容量，留更多的给逻辑思考，这样就会感觉到思路清晰很多。

    当我们写完代码之后，也可以举几个例子，画在纸上，照着代码走一遍，很容易就能发现代码中的Bug。

  6. 多写多练，没有捷径

    常见的链表操作

    • 单链表反转
    • 链表中环的检测
    • 两个有序的链表合并
    • 删除链表倒数第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
public class ArrayStack
{
    // 数组
    private string[] items;
    // 栈中元素个数
    private int count;
    // 栈的大小
    private int n;
    
    // 初始化器数组，申请一个大小为n的数组空间
    public ArrayStack(int n)
    {
        this.items = new string[n];
        this.count = 0;
        this.n = n;
    }
    
    // 入栈操作
    public bool push(string item)
    {
        // 数组空间不够了，直接返回false，入栈失败。
        if(count == n) return false;
        // 将item放到下标为count的位置，并且count加1
        items[count] = item;
        ++count;
        return true;
    }
    
    // 出栈操作
    public string pop()
    {
        // 栈为空，则直接返回null
        if(count == 0) return null;
        // 返回下标为count-1的数组元素，并且栈中元素个数count减1
        string tmp = items[count-1];
        --count;
        return tmp;
    }
}

不管是顺序栈还是链式栈，我们存储数据只需要一个大小为n的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是O(1)。注意，这里存储数据需要一个大小为n的数组，并不是说空间复杂度就是O(n)。因为这n个空间是必须的，无法省掉的。所有我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。

不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是O(1)。

栈在表达式求值中的应用

编译器是通过两个栈来实现的。其中一个保存操作数的栈，另一个保存运算符的栈，我们从左到右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取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
// 用数组实现的队列
public class ArrayQueue
{
    // 数组：items，数组大小：n
    private string[] items;
    private int n = 0;
    // head表示队头下标，tail表示队尾下标
    private int head = 0;
    private int tail = 0;

    // 申请一个大小为capacity的数组
    public ArrayQueue(int capacity)
    {
        items = new string[capacity];
        n = capacity;
    }

    // 入队
    public bool enqueue(string item)
    {
        // 如果tail==n 表示队列已经满了
        if (tail == n)
        {
            // tail == n && head == 0,表示整个队列都占满了
            if (head == 0) return false;
            // 数据搬移
            for (int i = head; i < taill; ++i)
            {
                items[i - head] = items[i];
            }
            // 搬移玩之后重新更新head和tail
            tail -= head;
            head = 0;
        }
        items[tail] = item;
        ++tail;
        return true;
    }

    // 出队
    public string dequeue()
    {
        // 如果head == tail表示队列为空
        if (head == tail) return null;
        string ret = items[head];
        ++head;
        return ret;
    }
}

循环队列

循环队列，顾名思义，它长得像一个环。原本数组是有头有尾的，是一条直线。现在我们把首尾相连，扳成了一个环。

循环队列为空的判断条件仍然是head = tail，队列满的判断条件(tail+1)%n = head。当队列满时，tail指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。

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
public class CircularQueue
{
    // 数组：items，数组大小：n
    private string[] items;
    private int n = 0;
    // head表示队头下标，tail表示队尾下标
    private int head = 0;
    private int tail = 0;

    // 申请一个大小为capacity的数组
    public CircularQueue(int capacity)
    {
        items = new string[capacity];
        n = capacity;
    }

    // 入队
    public bool enqueue(string item)
    {
        // 队列满了
        if ((tail + 1) % n == head) return false;
        items[tail] = item;
        tail = (tail + 1) % n;
        return true;
    }

    // 出队
    public string dequeue()
    {
        // 如果head == tail 表示队列为空
        if (head == tail) return null;
        string ret = items[head];
        head = (head + 1) % n;
        return ret;
    }
}

阻塞队列和并发队列

阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在enqueue()、dequeue()方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用CAS原子操作，可以实现非常高效的并发队列。

读书笔记
#读书笔记 #技术
数据结构与算法之美（一）
http://blog.chcaty.cn/2021/07/20/shu-ju-jie-gou-yu-suan-fa-zhi-mei-yi/
作者
caty
发布于
2021年7月20日
许可协议