数据结构和算法知识汇总

数据结构和算法
数据结构和算法
发布日期:   2020-12-03
文章字数:   12.3k
阅读时长:   45 分
阅读次数:  

目录

  1. 时间复杂度
  2. 数组
  3. 树
  4. 散列
  5. 优先级队列（堆）
  6. 排序
  7. 图
  8. 算法

参考资料

  • 《数据结构与算法分析》
  • 代码随想录

复杂度分析

一些基本的时间复杂度

  • O(N)

    for(int i = 1; i < n; i++){
    System.out.print(i);
}

  • O(N^2)

    for(int i = 1; i < n; i++){
    for(int j = 1; j < n; j++){
        System.out.print(i + "..." + "j");
    }
}

  • O(log(n))

    for(int i = 1; i < n; i = i * 2){
    System.out.print(i);
}

    当出现对数时间复杂度时，可以优先考虑折半查找，如二分法、归并排序等。

  • O(k^n)

    int fib(int n){
    if(n <= 2){
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

递归

  • 主定理计算时间复杂度

    image-20220310103515959

  • 尾递归

    如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

    原理：当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。

    参考：递归与尾递归总结 - huan欢 - 博客园

    针对尾递归优化的语言可以通过尾递归防止栈溢出。尾递归事实上和循环是等价的，没有循环语句的编程语言只能通过尾递归实现循环。

Java常见数据结构的复杂度

image-20220310103613699

  • 特别注意一下跳跃表

    思想：升维和空间换时间，改善链表随机访问过慢的情况

    image-20220310103846892

    在调表中查询任意数据的时间复杂度都是O(log(n))。

数组

  • 一维数组是存放在连续内存空间上的相同类型数据的结合

    image-20220310134027486

    需要两点注意的是

    • 数组下标都是从0开始的。
    • 数组内存空间的地址是连续的

    正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

  • 二维数组在内存的空间地址是连续的么？

    不同编程语言的内存管理是不一样的，以C++为例，在C++中二维数组是连续分布的。

链表

概念

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

链接的入口节点称为链表的头结点也就是head。

如图所示：

链表1

链表的类型

  • 单链表

    刚刚说的就是单链表。

  • 双链表

    单链表中的节点只能指向节点的下一个节点。

    双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

    双链表 既可以向前查询也可以向后查询。

    如图所示：

    链表2

  • 循环链表

    循环链表，顾名思义，就是链表首尾相连。

    循环链表可以用来解决约瑟夫环问题。

    链表4

链表的存储方式

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

如图所示：

链表3

这个链表起始节点为2， 终止节点为7， 各个节点分布在内存个不同地址空间上，通过指针串联在一起。

链表的定义

// 单链表
class ListNode {
    public int val;  // 节点上存储的元素
    public ListNode next;  // 指向下一个节点的指针
    public ListNode(){} //默认构造函数
    public ListNode(int x){ // 节点的构造函数
        this.val = x;
    } 
}

性能分析

再把链表的特性和数组的特性进行一个对比，如图所示：

链表-链表与数据性能对比

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。

树

相关概念

（1）树的定义，一种最自然的方式是递归的方式。

（2）深度：从根到一个节点的唯一路径的长

（3）叶节点（树叶）：没有儿子的节点。在Java中，叶节点的左右节点为null。

（4）高：一个节点到叶节点的最长路径的长

（5）常见的遍历方式

  • DFS：前序、中序、后序

  • BFS：层序

二叉树

（1）定义：每个节点都不能有多于两个的儿子

（2）实现

public class TreeNode {  
  Object element;  
  TreeNode left;  
  TreeNode right;
}

（3）其他概念

· 完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。

· 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。

二叉查找树

（1）定义：对于树中的每个节点X，它的左子树中所有项的值小于X中的项，而它的右子树中所有项的值大于X中的项。注意：二叉树中元素不能相等。

（2）查找元素contains

​ 根据目标元素和左右子树元素的大小关系，递归查找。

public boolean contains( int x, TreeNode t){
  if(t == null){
    return false;
  }
  int res = x.compareTo(t.val);
  if(res < 0){
    return contains(x, t.left);
  }else if(res > 0){
    return contains(x, t.right);
  }else {
    return true;
  }
}

（3）findMin和findMax

​ 往树的最左节点和最右节点找。

img

（4）insert

根据大小关系，遍历并比较，遍历到叶节点时插入

img

（5）remove

​ 用其右子树的最小的数据代替该节点的数据，并递归的删除那个节点。

img

AVL树

概念

（1）背景：对于二叉搜索树，当向一棵树输入预先排好序的数据，将会退化成一个链表。

（2）特性：带有平衡条件的二叉查找树，它必须保证树的深度须是O(log N)。

（3）定义：一颗AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树（空树的高度为-1）

旋转

当进行插入操作时，可能破坏AVL树的特性。通过旋转操作来恢复平衡特性。

分类

img img img img

代码

（1）插入

img

（2）右旋

img

（3）左旋

img

伸展树

概念

（1）伸展树（Splay Tree）主要特点是不会保证树一直是平衡的，但各种操作的平摊时间复杂度是O(log n)

（2）伸展树的出发点

考虑到局部性原理（刚被访问的内容下次可能仍会被访问，查找次数多的内容可能下一次会被访问），为了使整个查找时间更小，被查频率高的那些节点应当经常处于靠近树根的位置。这样，很容易得想到以下这个方案：每次查找节点之后对树进行重构，把被查找的节点搬移到树根，这种自调整形式的二叉查找树就是伸展树。每次对伸展树进行操作后，它均会通过旋转的方法把被访问节点旋转到树根的位置。

为了将当前被访问节点旋转到树根，我们通常将节点自底向上旋转，直至该节点成为树根为止。“旋转”的巧妙之处就是在不打乱数列中数据大小关系（指中序遍历结果是全序的）情况下，所有基本操作的平摊复杂度仍为O（log n）。

旋转方式

伸展树主要有三种旋转操作，分别为单旋转，一字形旋转和之字形旋转。为了便于解释，我们假设当前被访问节点为X，X的父亲节点为Y（如果X的父亲节点存在），X的祖父节点为Z（如果X的祖父节点存在）。

（1）单旋转

节点X的父节点Y是根节点。这时，如果X是Y的左孩子，我们进行一次右旋操作；如果X 是Y 的右孩子，则我们进行一次左旋操作。经过旋转，X成为二叉查找树T的根节点，调整结束。

img

（2）一字型旋转

节点X 的父节点Y不是根节点，Y 的父节点为Z，且X与Y同时是各自父节点的左孩子或者同时是各自父节点的右孩子。这时，我们进行一次左左旋转操作或者右右旋转操作。

img

（3）之字形旋转

节点X的父节点Y不是根节点，Y的父节点为Z，X与Y中一个是其父节点的左孩子而另一个是其父节点的右孩子。这时，我们进行一次左右旋转操作或者右左旋转操作。

img

（4）伸展树区间操作

在实际应用中，伸展树的中序遍历即为我们维护的数列，这就引出一个问题，怎么在伸展树中表示某个区间？比如我们要提取区间[a,b]，那么我们将a前面一个数对应的结点转到树根，将b 后面一个结点对应的结点转到树根的右边，那么根右边的左子树就对应了区间[a,b]。原因很简单，将a 前面一个数对应的结点转到树根后， a 及a 后面的数就在根的右子树上，然后又将b后面一个结点对应的结点转到树根的右边，那么[a,b]这个区间就是下图中B所示的子树。

img

利用区间操作我们可以实现线段树的一些功能，比如回答对区间的询问（最大值，最小值等）。具体可以这样实现，在每个结点记录关于以这个结点为根的子树的信息，然后询问时先提取区间，再直接读取子树的相关信息。还可以对区间进行整体修改，这也要用到与线段树类似的延迟标记技术，即对于每个结点，额外记录一个或多个标记，表示以这个结点为根的子树是否被进行了某种操作，并且这种操作影响其子结点的信息值，当进行旋转和其他一些操作时相应地将标记向下传递。

B树(B-树）、B+树、B*树

参考连接：B树（B-树）、B+树、B*树 - 简书、B树与B+树简明扼要的区别_Hannah-CSDN博客_b树和b+树区别

红黑树

参考：美团：红黑树深入剖析及Java实现

定义

是AVL树的另一种变种，带有下列附加条件的自平衡二叉查找树：

（1）节点是红色或黑色。

（2）根节点是黑色。

（3）每个叶子节点都是黑色的空节点（NIL节点）。

（4）每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

（5）从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

img

关键性质

从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

调整

插入一个叶子节点后，由于插入破坏的红黑树性质，要进行一定的调整。有变色和旋转两种方式。

变色

为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。

旋转

img

插入

新插入的节点是红色的（之所以将新插入的结点的颜色赋为红色，是因为：如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑结点，这个是很难调整的。但是设为红色结点后，可能会导致出现两个连续红色结点的冲突，那么可以通过颜色调换和树旋转来调整，这样简单多了），插入修复操作如果遇到父节点的颜色为黑则修复操作结束。也就是说，只有在父节点为红色节点的时候是需要插入修复操作的。

插入修复操作分为以下的三种情况，而且新插入的节点和父节点都是红色的：

· 叔叔节点也为红色。

· 叔叔节点为空，且祖父节点、父节点和新节点处于一条斜线上。

· 叔叔节点为空，且祖父节点、父节点和新节点不处于一条斜线上。

（1）插入操作-case 1

case 1的操作是将父节点和叔叔节点与祖父节点的颜色互换，这样就符合了RBTRee的定义。即维持了高度的平衡，修复后颜色也符合RBTree定义的第三条和第四条。下图中，操作完成后A节点变成了新的节点。如果A节点的父节点不是黑色的话，则继续做修复操作。

img

（2）插入操作-case 2

case 2的操作是将B节点进行右旋操作，并且和父节点A互换颜色。通过该修复操作RBTRee的高度和颜色都符合红黑树的定义。如果B和C节点都是右节点的话，只要将操作变成左旋就可以了。

img

（3）插入操作-case 3

case 3的操作是将C节点进行左旋，这样就从case 3转换成case 2了，然后针对case 2进行操作处理就行了。case 2操作做了一个右旋操作和颜色互换来达到目的。如果树的结构是下图的镜像结构，则只需要将对应的左旋变成右旋，右旋变成左旋即可。

img

插入操作的总结：插入后的修复操作是一个向root节点回溯的操作，一旦牵涉的节点都符合了红黑树的定义，修复操作结束。

对比AVL树

img

  • 从查找或者读取性质来说的话，AVL更好，因为AVL是更平衡的

  • 红黑树提供了更快的插入和删除操作，因为AVL的旋转次数会更多，红黑树只是一个近似平衡的

  • AVL树需要存储平衡因子或是高度信息，但红黑树只需要1个bit存储红或者黑即可。

  • 总结上述：

    当读操作很多，写操作很少的时候，用AVL树

    当读写操作相当时，优先使用红黑树，比较简洁也比较好实现。红黑树尝尝用在高级语言库里面，比如TreeMap或者TreeSet。

另外参考：关于AVL树和红黑树的一点看法 - 知乎

散列

概念

散列是一种用于以常数平均时间执行插入、删除和查找的技术。

散列函数

（1）每个关键字被映射到从0到TableSize-1这个范围中的某个数，并被放到适当的单元中，这个映射即为散列函数。

（2）有写关键字不是整型，需要通过hashcode（）先转换为int类型，再进行hash & (TableSize - 1)

哈希冲突

概念

当两个关键字散列到同一个值的时候，即为冲突

解决方式

分离链接法

（1）概念

将散列到同一个值的所有元素保留到一个链表中

（2）新的元素插入在链表的表头，不仅仅因为方便，还因为新近插入的元素最有可能不久又被访问。

开放定址法

（1）f(i)为冲突解决方法，h为散列表对应位置

h_{i} (x) = ( hash(x) + f(i))  mod (TableSize - 1)

· f的常见设计方法：
· 线性探测法f(i) = i
· 平方探测法f(i) = i^2
· 双散列f(i) = i * hash’(x)

（2）对于不适用分离链接的散列表来说，填装因子（已有元素个数 / TableSize）应该不低于0.5.这样的表叫做探测散列表。

再散列

在哈希表填装到一定程度时（由负载因子决定），将表先扩大到原来的两倍，再将元素重新散列到新表上。

优先级队列（堆）

模型

  • 堆至少需要下列两种操作的数据结构：

    （1）Insert

    （2）deleteMin（删除最小者，也可以是最大者）

  • 时间负载度

    • 插入/删除操作：O(log(n))（这里也看到说是O(n)的，待验证）
    • 去除操作：O(1)

二叉堆

性质

恰似AVL树，对堆的一次操作可能破坏这两个性质中的一个。

结构性

（1）堆是一棵被完全填满的二叉树，有可能例外是在底层，底层元素从左到右填入，即完全二叉树。

（2）如是数组实现二叉堆，则对于当前位置i，左儿子在2i，右儿子在2i + 1，父节点在i / 2位置。

堆序性

对于小根堆，每一个节点X，X的父亲中的关键字小于或等于X中的关键字。所以可以常数时间，获得极值。

基本堆操作

两个操作时间复杂度都为O(log N）

（1）insert插入（上滤）

​ · 将新元素插入到下一个可用位置（保证结构性，即完全二叉树）

​ · 比较新元素和其父节点元素的大小，若比父元素小，就交换两个位置，继续向上比较

img img

（2）deleteMin删除堆顶（下滤）

· 将堆最后一个元素放入堆顶，即删除堆顶元素

· 将该元素与两个儿子比较，与其中的较小者交换，并继续向下比较。

img img

d-堆

d-堆是二叉堆的简单推广，就像一个二叉堆，只是所有的节点需要有d个儿子。

img

其他堆

  • 左式堆

  • 斜堆

  • 二项队列

排序

参考：developer1024 - 知乎

img

image-20220310113755176

在面试中最重要的就是O(nlogn)的三个排序算法：堆排、快排、归并排序

基于比较的排序

插入排序

（1）算法：由N-1趟排序组成，对于p = 1到N-1趟，插入排序保证从位置0到位置p上的元素为已排序状态。

（2）时间复杂度 O(N^2)

（3）说明图

（4）代码

public static void insertSort(int[] arr) {
   if (arr == null || arr.length < 2) {
     return;
   }
   for (int i = 1; i < arr.length; i++) {
     for (int j = i - 1; j > -1; j--) {
       if (arr[j] > arr[j + 1]) {
         swap(arr, j, j + 1);
       }
     }
   }
 }

冒泡排序

选择排序

希尔排序

（1）算法

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比冒泡和插入有较大提高。

步骤：

① 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。

② 所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序。

③ 取第二个增量d2小于d1重复上述的分组和排序，直至所取的增量dt=1(dt小于dt-l小于…小于d2小于d1)，即所有记录放在同一组中进行直接插入排序为止。

（2）时间复杂度

· 平均时间复杂度：O(Nlog2N)

· 最佳时间复杂度：

· 最差时间复杂度：O(N^2)

· 空间复杂度：O(1)

· 稳定性：不稳定

· 复杂性：较复杂

（3）说明图

img

（4）代码

img

堆排序

（1）算法：

① 将待排序的序列构造成一个最大堆，此时序列的最大值为根节点

② 依次将根节点与待排序序列的最后一个元素交换

③ 再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列

（2）复杂度分析

· 平均时间复杂度：O(nlogn)

· 最佳时间复杂度：O(nlogn)

· 最差时间复杂度：O(nlogn)

· 稳定性：不稳定

归并排序

（1）算法

归并排序是用分治思想，分治模式在每一层递归上有三个步骤：

· 分解（Divide）：将n个元素分成个含n/2个元素的子序列。

· 解决（Conquer）：用合并排序法对两个子序列递归的排序。

· 合并（Combine）：合并两个已排序的子序列已得到排序结果。

（2）复杂度分析

· 平均时间复杂度：O(nlogn)

· 最佳时间复杂度：O(n)

· 最差时间复杂度：O(nlogn)

· 空间复杂度：O(n)

· 排序方式：In-place

· 稳定性：稳定

（3）说明图

img

快速排序

（1）算法：

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

① 从数列中挑出一个元素，称为 “基准”（pivot），

② 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

③ 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

（2）复杂度分析

· 平均时间复杂度：O(NlogN)

· 最佳时间复杂度：O(NlogN)

· 最差时间复杂度：O(N^2)

· 空间复杂度：根据实现方式的不同而不同

基于计数的排序

计数排序

（1）算法

使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），然后进行分配、收集处理：

① 分配。扫描一遍原始数组，以当前值-minValue作为下标，将该下标的计数器增1。

② 收集。扫描一遍计数器数组，按顺序把值收集起来。

具体步骤：

① 找出待排序的数组中最大和最小的元素

② 统计数组中每个值为i的元素出现的次数，存入数组C的第i项

③ 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）

④ 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

（2）复杂度分析

· 平均时间复杂度：O(n + k)

· 最佳时间复杂度：O(n + k)

· 最差时间复杂度：O(n + k)

· 空间复杂度：O(n + k)

（3）代码

public class CountingSort{
  public static void main(String[]argv){
    int[] A = CountingSort.countingSort(new int[]{16,4,10,14,7,9,3,2,8,1});
    Utils.print(A);
  }
  public static int[] countingSort(int[]A){
    int[] B = new int[A.length];// 假设A中的数据a'有，0<=a' && a' < k并且k=100
    int k=100;
    countingSort(A,B,k);
    returnB;
  }
  private static void countingSort(int[]A,int[]B,intk){
    int[]C =new int[k];// 计数
    for(int j=0; j<A.length; j++){
      int a = A[j];
      C[a]+=1;
    }
    Utils.print(C);// 求计数和
    for( int i=1;i<k; i++){
      C[i]=C[i]+C[i-1];
    }
    Utils.print(C);// 整理
    for(int j= A.length-1;j>=0;j--){
      int a=A[j];
      B[C[a]-1] = a;
      C[a] -=1;
    }
  }
}

桶排序

（1）算法

桶排序的思想近乎彻底的分治思想。桶排序假设待排序的一组数均匀独立的分布在一个范围中，并将这一范围划分成几个子范围（桶）。然后基于某种映射函数f ，将待排序列的关键字 k 映射到第i个桶中 (即桶数组B 的下标i) ，那么该关键字k 就作为 B[i]中的元素 (每个桶B[i]都是一组大小为N/M 的序列 )。接着将各个桶中的数据有序的合并起来 : 对每个桶B[i] 中的所有元素进行比较排序 (可以使用快排)。然后依次枚举输出 B[0]….B[M] 中的全部内容即是一个有序序列。

（2）复杂度分析

· 平均时间复杂度：O(n + k)

· 最佳时间复杂度：O(n + k)

· 最差时间复杂度：O(n ^ 2)

· 空间复杂度：O(n * k)

· 稳定性：稳定

（3）说明图

img

基数排序

（1）算法

原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

· MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序

· LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

具体步骤：

① 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。

② 从最低位开始，依次进行一次排序。

③ 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

（2）复杂度分析

· 时间复杂度：O(k*N)

· 空间复杂度：O(k + N)

· 稳定性：稳定

（3）说明图

img

外部排序

概念

外部排序算法由两个阶段构成：

（1）按照内存大小，将大文件分成若干长度为 l 的子文件（l 应小于内存的可使用容量），然后将各个子文件依次读入内存，使用适当的内部排序算法对其进行排序（排好序的子文件统称为“归并段”或者“顺段”），将排好序的归并段重新写入外存，为下一个子文件排序腾出内存空间；

（2）对得到的顺段进行合并，直至得到整个有序的文件为止。

示例

例如，有一个含有 10000 个记录的文件，但是内存的可使用容量仅为 1000 个记录，毫无疑问需要使用外部排序算法，具体分为两步：

· 将整个文件其等分为 10 个临时文件（每个文件中含有 1000 个记录），然后将这 10 个文件依次进入内存，采取适当的内存排序算法对其中的记录进行排序，将得到的有序文件（初始归并段）移至外存。

· 对得到的 10 个初始归并段进行如图的两两归并，直至得到一个完整的有序文件。

img

这里只用了2路进行归并，还有更多路平衡归并。

img

图

一些概念

  1. 图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为**G =(V,E)**；

    图的顶点个数不能为0，但边数可以为0，一般没有空图的说法，图论里的零图是表示只由孤立节点组成的图。

  2. 权：边有值

  3. 路径：一个顶点序列；路径的长：路径上的边数

  4. 环：含有一条从一个顶点到它自身的边

  5. 简单路径：该路径上的所有顶点都是互异的，但第一个顶点和最后一个顶点可能相同

  6. 圈：有向图中，满足w1=wn且长至少为1的一条路径

  7. 连通：无向图中，每个顶点到其他顶点都有一条路径。具有这样性质的有向图称为强连通的。若有向图去掉方向后的基础图是连通的，则称该有向图为弱连通的。

  8. 完全图：每一对顶点间都存在一条边的图。

    含有n个顶点的无向完全图有n*(n-1)/2条边，有向完全图有n*(n-1)条边。

  9. 入度：有向图中，顶点v的入度是边（u, v）的条数

  10. 入度等于出度等于边数，图的度之和等于边数的二倍。

  11. 简单图，即没有环也没有重边的图。

  12. 边数少的图就是稀疏图，边数多的图就是稠密图。

  13. 顶点的度是依附于该顶点的边数

  14. 简单通路就是顶点没有重复的路径。

  15. 简单回路：除了第一个点和最后一个点外，没有重复访问的点。

  16. 无权图的路径长度为路径边的条数。

  17. 连通分量：非联通图的极大连通子图称为连通分量，（连同依附于所有点的边）

  18. 生成树：n个节点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。含有n-1条边，多一条边构成回路，少一条边不连通。生成森林就是分别得到一棵生成树。

图的表示

（1）邻接矩阵（稠密图适用）

对于每条边（u, v）置A[u][v]等于true，否则数组的元素就是false。如果边有一个权，那么可以置A[u][v]等于该权，使用一个很大或者很小的全标记不存在的边。

image-20220310095830503

（2）邻接表（稀疏图适用）

对每个顶点，使用一个表存放所有邻接的顶点。由数组+链表组成。

image-20220310095856840

img
  • 邻接矩阵需要为每个顶点都分配n个边的空间，其实很多边是不存在的，会造成一定空间的浪费
  • 邻接表的实现只关心存在的边，因此没有空间浪费

图的代码

class Node{
    public String name; // A B C ...
    public int code; // 0, 1, 2 ... 邻接矩阵的下标
    public Node(){};
    public NOde(String name, int code){
        this.name = name;
        this.code = code;
    }
}

public class Graph {
    private List<Node> nodeList; // 存储节点信息
    private int[][] edges; //邻接矩阵表示法：存储变信息，是否有边或者权重值
    private int numOfEdges; //边的数量
    private Set<Node> isVisited; //访问过的节点
    
    // 构造函数
    public Graph(int n){
        this.edges = new int[n][n];
        this.nodeList = new ArrayList<Node>(n);
        this.numOfEdeges = 0;
        this.isVisited = new HashSet();
    }
    
    // 插入一个节点
    public void insertNode(Node node){
        this.nodeList.add(node);
    }
    
    // 插入一条边
	public void insertEdge(Node n1, Node n2, int weight){
       	this.edges[n1.code][n2.code] = weight;
        this.edges[n2.code][n1.code] = weight;
        this.numOfEdges++;
    }
    
    // 获取图中的节点数量
    public int getNumOfNode(){
        return this.nodeList.size();
    }
    
    // 获取边的数量
    public int getNumOfEdges(){
        return this.numOfEdges;
    }
    
    // 获取一条边的权重
    public int getWeight(Node n1, Node n2){
        return this.edges[n1.code][n2.code];
    }
    
    // 显示图
    public void showGraph(){
        for(int[] link : edges){
            System.out.println(Arrays.toString(link));
        }
    }
    
    
    /*
    下面是常见的两种遍历操作：DFS和BFS
    */
    // 获取邻接节点列表的方法
    public List<Node> getNeighborList(Node node){
        List<Node> res = new ArrayList();
        for(Node n : this.nodeList){
            if(edges[node.code][n.code] > 0){
                res.add(n);
            }
        }
        return res;
    }
    
    // DFS, 参数：为遍历的起始顶点
    public void dfs(Node node){
        if(node == null || this.isVisited.contains(node)){
            return;
        }
        System.out.print(node.name + "->");
        this.isVisited.add(node);
        for(Node neighbor : getNeighborList(node)){
            if(!isVisited.contains(neighbor)){
                dfs(neighbor);
            }
        }
    }
    
    // BFS，参数：为遍历的起始顶点
    public void bfs(Node node){
        Queue<Node> q = new LinkedList();
        q.offer(node);
        System.out.println(node.name + " ");
        this.isVisited.add(node);
        while(!q.isEmpty()){
            int size = q.size();
            while(size > 0){
                Node top = q.poll();
                for(Node n : getNeighborList(top)){
                    if(!this.isVisited.contains(n)){
                        q.offer(n);
                        System.out(print(n.name + " "));
                        this.isVisted.add(n);
                    }
                }
                size--;
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args){
        int n = 5;
        Node A = new Node("A", 0);
        Node B = new Node("B", 1);
        Node C = new Node("C", 2);
        Node D = new Node("D", 3);
        Node E = new Node("E", 4);
        Graph g = new Graph(n);
        // 插入节点
        g.insertNode(A);
        g.insertNode(B);
        g.insertNode(C);
        g.insertNode(D);
        g.insertNode(E);
        // 插入边
        g.insertEdge(A, B, 1);
        g.insertEdge(A, C, 1);
        g.insertEdge(B, C, 1);
        g.insertEdge(B, D, 1);
        g.insertEdge(B, E, 1);
        g.showGraph();
        // bfs
        g.bfs(A);
        // dfs
        g.dfs(A);
    }
}

拓扑排序

对有向无圈图的顶点的一种排序，使得如果存在一条从u到v的路径，那么在排序中v就在u的后面。

拓扑排序不是唯一的。

图的遍历

  • 深度优先搜索（DFS）是从某个顶点出发，然后递归地遍历所有与其邻接的顶点。
  • 广度有限搜素（BFS）是从某个顶点触发，一层一层的遍历顶点。

为了避免圈的出现，当访问一个顶点v的时候，由于我们当时已经到该点处，因此可以标记该点是访问过的，并且对于尚未被标记的所有邻接顶点递归调用搜索。

无向图

img

利用上述步骤，可以在无向图中构成深度优先生成树。

双连通性

（1）双连通性

​ 一个连通的无向图如果不存在被删除之后使得剩下的图不在连通的顶点，那么这样的无向连通图就称为是双连通的。

（2）如果一个图不是双连通的，那么，将其删除使图不再连通的那些顶点叫作割点。

（3）利用深度优先搜索，可以找出连通图中的所有割点的线性时间算法。

欧拉回路

在图中找出一条圈路径，使得该路径访问图的每条边恰好一次，该问题即为欧拉回路问题。

可以得出，欧拉回路只有当图是连通的且每个顶点的度（即，边的条数）是偶数时才有可能存在。

最短路径算法

单源最短路径问题：给定一个赋权图G=（V，E）和一个特定顶点s作为输入，找出从s到G中每一个其他顶点的最短赋权路径。

无权最短路径

先搜索距离s为1的点，再搜索距离为2的点，依次往下，这种方法称为广度优先搜索（BFS）。这类似树中的层序遍历。同样适用队列进行算法运算。

img img img

Dijkstra算法

（1）概念

​ 是解决单源最短路径问题（赋权图中）的一般解法。

​ 是贪婪（心）算法最好的例子，每个阶段把它当作最好的去处理。

​ 只要边的值没有负值，该算法总能顺利工作。

（2）算法

参考：（七）通俗易懂理解——dijkstra算法求最短路径 - 知乎

img

img

img

img

img

img

img

img

img

具有负边值的图

img

无圈图

以拓扑顺序选择顶点。当一个顶点v被选取后，按照拓扑顺序的法则它没有从unknown顶点发出的进入边，因此它的距离d可不再被降低。

最小生成树

概念

（1）最小生成树

​ 由图的那些连接图的所有顶点的边构成的树，且其总价值最低。

（2）最小生成树存在当且仅当图是连通的。

（3）最小生成树的边数为顶点总数V - 1

（4）贪婪算法是成立的，即在建立生成树时所添加的边在所有避免成圈的边中其值最小。

Prim算法

算法在每一阶段都可以通过选择边（u, v）使得（u，v）的值是所有u在树上但v不在树上的边的值中的最小者而找出一个新的顶点并把它添加到这棵树中。

img img

img

img

img

img

img

img

Kruskal算法

算法连续地按照最小的权选择边，并且当所选的边不产生圈时就把它作为所选定的边。

Kruskal算法也是贪婪算法。

算法在实施的任意时刻，两个顶点属于同一个集合当且仅当他们在当前的生成森林中连通。因此，每个顶点最初是在它自己的集合中，如果u和v在同一个集合中，那么连接他们的边就要放弃，由于他们已经连通了，因此再添加边（u, v）就会形成一个圈；如果这两个顶点不在同一个集合中，则将该边加入。

img img img

算法

​ 这里列出常见的一些解决问题的方法，和其基本的理论知识

​ 需要对照时间的例子，来更深层的理解，可以参考**Leetcode分类刷题**来进行训练。

单调栈和单调队列

分治

概念

分治算法主要分为两部分组成：

  • 分：递归解决较小的问题（基本情况除外）

  • 治：从子问题的解构建原问题的解

    一般坚持子问题不相交的原则。

主定理判断时间复杂度

img

分治代码模板

def divide_conquer(problem, param1, param2, ...):
    # recursion terminator 递归终止条件
    if problem is Node:
        print_result
        return
    # prepare data 预处理数据
    data = prepare_data(problem)
    subproblems = split_problem(problem, data)
    # conquer subproblems 解决子问题
    subresult1 = self.divide_conquer(subproblems[0], p1, p2 ...)
    subresult2 = self.divide_conquer(subproblems[1], p1, p2 ...)
    ...
    # process and generate the final result 通过子问题结果得出最终结果
    result = process_result(subresult1, subresult2, ...)
    # revert the current level states 返回现在的状态
    return result

回溯

  • 概念

    回溯法采用试错的思想，它尝试分步的去解决一个问题，在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至上几步的计算，再通过其他的可能的分步解答再次尝试寻找问题的答案

  • 回溯法通常使用递归方法来实现

    在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。

  • 为了加快回溯，降低时间复杂度，可以进行剪枝操作

    在一步内删除一大组可能性的做法叫做裁剪（剪枝）

  • 常见运用场景：

    • 组合问题

      N个数里面按一定规则找出k个数的集合

    • 排列问题

      N个数按一定规则全排列，有几种排列方式

    • 切割问题

      一个字符按一定规则有几种切割方式

    • 子集问题

      一个N个数的集合里有多少符合条件的子集

    • 棋盘问题

      N皇后，解数独等等

DFS与BFS

概念

​ 深度优先搜索和广度优先搜索，常在递归、回溯、图的遍历、树的遍历等情况下使用。

DFS

  • 递归模板

    visited = set()
def dfs(node, visited):
    visited.add(node)
    # process current node
    ...
    # 遍历下一个节点
    for next_node int node.children():
        if not next_node int visited:
            dfs(next_node, visited)

  • 二叉树的DFS

    visited = set()
def dfs(node):
    if node in visited:
		return
    visited.add(node)
    # process current node
    ...
    # 遍历下一个节点
    dfs(node.left)
    dfs(node.right)

BFS

def bfs(graph, start, end):
    queue = []
    queue.append([start])
    visited.add(start)
    while queue:
        node = queue.pop()
        visited.add(node)
        process(node)
        nodes = generate_related_nodes(node)
        queue.push(nods);
    # other processing work
    ...

BFS和DFS该在什么时候使用

参考：什么时候用深搜（dfs）什么时候用广搜（bfs)

  • BFS是用来搜索最短径路的解是比较合适的，比如求最少步数的解，最少交换次数的解，因为BFS搜索过程中遇到的解一定是离根最近的，所以遇到一个解，一定就是最优解，此时搜索算法可以终止。这个时候不适宜使用DFS，因为DFS搜索到的解不一定是离根最近的，只有全局搜索完毕，才能从所有解中找出离根的最近的解。（当然这个DFS的不足，可以使用迭代加深搜索ID-DFS去弥补）
  • 空间优劣上，DFS是有优势的，DFS不需要保存搜索过程中的状态，而BFS在搜索过程中需要保存搜索过的状态，而且一般情况需要一个队列来记录。
  • DFS适合搜索全部的解，因为要搜索全部的解，那么BFS搜索过程中，遇到离根最近的解，并没有什么用，也必须遍历完整棵搜索树，DFS搜索也会搜索全部，但是相比DFS不用记录过多信息，所以搜素全部解的问题，DFS显然更加合适。

贪心

算法

​ 贪婪算法分阶段的工作，在每一个阶段，可以认为所做决定是好的，而不考虑将来的后果。当算法终止时，希望局部最优等于全局最优。

  • 对比贪心和动态规划

    贪心与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。

    动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能

    即：

    • 贪心：当下做局部最优判断
    • 回溯：能够回退
    • 动态规划：最优判断 + 回退

哈夫曼编码

（1）数据结构

· 每个字符通过从根节点开始用0指示左分支用1指示右分支而以记录路径的方法表示出来

· 所有的字符都放在树叶上，每个字符编码后，前缀不同，这种编码方式称为前缀码。

（2）哈夫曼算法

​ 算法对由树组成的一个森林进行。一棵树的权等于它的树叶的频率的和。任意选取最小权的两棵树T1和T2，并任意形成以T1和T2为子树的新树，直到形成一个森林算法结束。

（3）特点：两个频率最小的字符必然是两个最深的节点。

二分查找

  • 前提

    • 目标函数单调性（单调递增或递减）
    • 存在上下界
    • 能够通过索引访问

  • 模板

    left,right = 0, len(array) - 1
while left <= right:
    mid = left + (right - left) / 2
    if array[mid] == target:
        break or return result
    elif array[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

双指针法

  • 通过左右两个指针逼近结果，加快搜索速度

  • 二分查找就是一个例子

  • 常见场景

    • 数组
    • 字符串
    • 链表
    • N数之和

  • 除了链表一些题目一定要使用双指针，其他题目都是使用双指针来提高效率，一般是将O(n^2)的时间复杂度，降为O(n)。

动态规划

基本概念

  • 概念

    编译器尝尝不能正确对待递归算法，结果导致低效的程序。

    将递归算法重新写成非递归算法，把子问题的答案系统地记录在一个表内，即为动态规划。

    第一次看会有些理解不了，可以参考这个故事：通过金矿模型介绍动态规划

  • 关键点

    • 最优子结构

      opt[n] = best_of(opt[n - 1], opt[n - 2], …)

    • 存储中间状态

      opt[i]

    • 递推公式（状态转移方程 or DP方程）

      Fib: opt[i] = opt[n - 1] + opt[n - 2]

      二维路径：opt[i, j] = opt[i + 1][j] + opt[i][j + 1]

  • 一般步骤

    1. 确定dp数组以及下标的含义
    2. 确定递推公式
    3. dp数组如何初始化
    4. 确定遍历顺序
    5. 举例推导dp数组

背包问题

背包分类

image-20220310130024575

如下图可以分为：

  • 01背包

    • 二维dp方式

      注意点：初始化使用倒叙

      image-20220310133127775、

    • 一维dp方式

      注意点：

      • 初始化为0

      • 只能先遍历物品，再遍历背包

      • 遍历背包时，只能倒叙遍历（这样能保证，后面的状态不依赖前面的状态，保证一个物品只取一遍）

      image-20220310133201688

  • 完全背包

  • 多重背包

  • 分组背包

背包问题思路

  1. 分析是否为背包问题

    背包问题特征：

    给定一个target，target可以是数字也可以是字符串，再给定一个数组nums，nums中装的可能是数字，也可能是字符串，问：能否使用nums中的元素做各种排列组合得到target

  2. 是否是哪种背包问题

    根据题目给的数组中的元素是否可以重复使用，判断01背包还是完全背包

    • 01背包（二维dp方式），nums放在外循环，target放在内循环，且内循环倒序

      for num in nums:
    for i in range(target, nums - 1, -1):

    • 完全背包，nums放在外循环，target放在内循环，且内循环正序

      for num in nums:
    for i in range(nums, target + 1):

  3. 是否考虑元素之间的顺序

    组合问题还是排序问题

    如果考虑顺序问题，在组合问题的基础上，需将target放在外循环，将nums放在内循环

    for i in range(1, target + 1):
    for num in nums:

常见题型

  1. 组合问题公式

    dp[i] += dp[i - num]

  2. True、False问题公式

    dp[i] = dp[i] or dp[i - num]

  3. 最大最小问题公式

    dp[i] = min(dp[i], dp[i - num] + 1) 
或者
dp[i] = max(dp[i], dp[i - num] + 1)

常见场景

image-20220310131816790

字典树

​ 字典树，即Trie树，又称单词查找树或键树，是一种树形结构。

​ 典型应用是用于统计和排序大量的字符串（但不限于字符串），所以经常被搜索引擎用于文本词频统计。

​ 优点：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

image-20220310112704367

代码实现参考leetcode208，典型例题leetcode212 单词搜索II

image-20220310112855557

并查集

详细可以参考：并查集

并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

  • 合并（Union）：把两个不相交的集合合并为一个集合。
  • 查询（Find）：查询两个元素是否在同一个集合中。

位运算

  • XOR 异或

    image-20220310113619817

  • 指定位置的位运算

    image-20220310113634465

  • 一些常见运用和场景

    image-20220310113700353

随机化算法

（1）算法

​ 在算法期间，随机数至少有一次用于决策。该算法的运行时间不只依赖于特定的输入，而且依赖于所出现的随机数。

（2）示例

​ 将快排改进，枢纽元在整个数组中随机选取。

高级字符串算法

Rabin-Karp算法

  • 概念

    ​ 在一般的算法中，问你需要挨个比较所有字符，才知道模板字符串找那个是否包含子串

    ​ 为了避免挨个判断，可以尝试一次性判断两者是否想的，因此需要一个好的哈希函数。

  • 基本思想

    1. 假设子串的长度为M(pat)，目标字符串的长度为N(txt)
    2. 计算子串的hash值hash_pat
    3. 计算目标字符串txt中每个长度为M的子串的hash值（共需要计算N - M + 1次）
    4. 比较hash值：如果hash值相同，字符串必然不匹配；如果hash值相同，还需要使用一般的算法再次判断

KMP算法

文章作者: 小小千千
文章链接: https://jason-qianhao.github.io/2020/12/03/shu-ju-jie-gou-he-suan-fa/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 小小千千 !
数据结构和算法
赏
评论
  目录