数据结构与算法

数据结构是一种具有一定逻辑关系，在计算机中应用某种存储结构，并且封装了相应操作的数据元素集合。它包含三方面的内容，逻辑结构、存储结构和数据的运算。

绪论

1. 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令包括一个或多个操作。
2. 数据的逻辑结构和存储结构是密不可分的，算法的设计取决于所选定的逻辑结构，而算法的实现依赖于采用的存储结构。
3. 算法的五个特性：有穷性、确定性、可行性、输入、输出。
4. 通常设计一个好的算法应考虑：正确性、可读性、健壮性、效率与低存储量需求。
5. 所谓时间复杂度，是指最坏情况下估算算法执行时间的一个上界。

常见的数据结构

• **堆（Heap）：**堆是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。

• **栈（Stack）：**栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。

• **队列（Queue）：**队列和栈类似，也是一种特殊的线性表。和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。

• **数组（Array）：**数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。

• **链表（Linked List）：**链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。

• **树（Tree）：**树是典型的非线性结构，它是包括，2 个结点的有穷集合 K。

• **图（Graph）：**图是另一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。

• **散列表（Hash table）：**散列表源自于散列函数(Hash function)，其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较操作而直接取得所查记录。

栈

• 栈主要用于存储局部变量、函数参数和返回地址，也就是说变量的赋值是被储存在栈中的。
• 它遵循后进先出（LIFO, Last In First Out）的原则，即最后放入的元素最先被移除。

堆

• 堆用于存储动态分配的内存如对象和数组，即程序在运行时根据需要分配和释放的内存（如 js 中引用类型的数据）。
• 它没有后进先出的限制，可以在任意位置分配和释放内存。

提示

以下是一个同时使用了堆和栈的 js 代码

const obj = { test: 123 };

这里发生的事情可以分解如下：

1. obj 是一个变量，它存储在栈中。
2. { test: 123 } 是一个对象，它存储在堆中。
3. 变量 obj 实际上存储的是对该对象在堆中的引用（或内存地址）

队列

队列是受限访问集合中的另一种数据类型，就像前面讨论的堆栈一样。主要区别在于队列是按照**FIFO（先进先出）**模型组织的：队列中第一个插入的元素是第一个被移除的元素。

提示

比如事件循环中的异步任务，弹窗队列等。

数组

数组是最简单也是最常见的数据结构。它们的特点是可以通过索引（位置）轻松访问元素。

提示

想象一下有一排剧院椅。每把椅子都分配了一个位置（从左到右），因此每个观众都会从他将要坐的椅子上分配一个号码。这是一个数组。将问题扩展到整个剧院（椅子的行和列），您将拥有一个二维数组（矩阵）

链表

在这个图解中，Head Pointer 是指向链表头节点的指针。每个节点都包含一个数据域和一个指向下一个节点的指针域。链表的最后一个节点的指针域为 null，表示链表的结束。

• 链表是线性数据结构，就像数组一样,区别是用的不是连续的内存空间（只有需要存储数据时，才去划分新的空间，节省资源），允许在任意位置插入和删除结点，更方便频繁的操作。
• 包括单项链表，双项链表，循环链表。

提示

例如分页管理和路由管理的上一页和下一页就有些链表的思想在里面。（即一系列节点通过指针（或引用）相互连接——可以应用于分页数据的存储和访问）

树

我们在任何需要描绘层次结构的时候都使用树，可以很方便的代表你上下层级关系。

二叉树和二叉搜索树

二叉树是一种特殊类型的树：每个顶点最多可以有两个子节点。

二叉搜索树是一棵二叉树，其中节点的值属于一个完全有序的集合——任何任意选择的节点的值都大于左子树中的所有值，而小于右子树中的所有值。

图

图有两种主要类型：有向图和无向图。

在无向图中，边(x, y)在两个方向上都可用：(x, y)和(y, x)。在有向图中，边(x, y)称为箭头，方向由其名称中顶点的顺序给出：箭头(x, y)与箭头(y, x) 不同。

比如好友关系是无向图，关注者/关注帐户之间的关系是有向图。

散列表

又称哈希表或哈希映射。

Maps （dictionaries）是包含键集合和值集合的抽象数据类型。每个键都有一个与之关联的值。

常用算法

• **检索：**检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。
• **插入：**往数据结构中增加新的节点。
• **删除：**把指定的结点从数据结构中去掉。
• **更新：**改变指定节点的一个或多个字段的值。
• **排序：**把节点按某种指定的顺序重新排列。例如递增或递减。

1.分治算法（Divide and Conquer）

分而治之（DAC）本身并不是一个特定的算法，而是在深入研究其他主题之前需要了解的重要算法类别。它用于解决可以划分为与原始问题相似但规模较小的子问题的问题。然后 DAC 递归地求解它们，最后合并结果以找到问题的解决方案。

它分为三个阶段：

• 划分——将问题分解为子问题；
• 用递归解决子问题；
• 合并——子问题的结果到最终解决方案中。

它是干什么用的？

分治算法（DAC） 的一种实际应用是使用多个处理器进行并行编程，因此子问题在不同的机器上执行。

DAC 是许多算法的基础，例如快速排序、合并排序、二分搜索或快速乘法算法。

特性

• 每个 DAC 问题都可以写成一个递推关系；因此，必须找到停止递归的基本情况；
• 它的复杂度是T(n)=D(n)+C(n)+M(n)，这意味着每个阶段都有不同的复杂度，具体取决于问题。

2. 排序算法（Sorting Algorithms）

排序算法用于根据元素上的比较运算符重新排列给定元素（来自数组或列表）。当我们提到一个排序数组时，我们通常会想到升序（比较运算符是“<”）。排序有多种类型，具有不同的时间和空间复杂度。其中一些是基于比较的，有些则不是。以下是最流行/最有效的排序方法：

冒泡排序（Bubble Sort）

冒泡排序是最简单的排序算法之一。它基于相邻元素之间的重复交换（如果它们的顺序错误）。它是稳定的，它的时间复杂度是 O(n²) 并且它需要 O(1) 辅助空间。

计数排序（Counting Sort）

计数排序不是基于比较的排序。它基本上是使用每个元素的频率（一种散列），确定最小值和最大值，然后在它们之间迭代以根据其频率放置每个元素。它在 O(n) 中完成，空间与数据范围成正比。如果输入范围不明显大于元素数量，则它是有效的。

快速排序（Quick Sort）

快速排序是分而治之的一个应用。它基于选择一个元素作为枢轴（第一个、最后一个或中间值），然后交换元素以将枢轴放置在所有小于它的元素和所有大于它的元素之间。它没有额外的空间和 O(n*log n) 时间复杂度——基于比较的方法的最佳复杂度。

归并排序（Merge Sort）

归并排序也是一个分而治之的应用程序。它将数组分成两半，对每一半进行排序，然后合并它们。它的时间复杂度也是 O(n*log n)，所以它也像 Quick Sort 一样超快，但不幸的是它需要 O(n) 额外空间来同时存储两个子数组，最后合并它们。

基数排序（Radix Sort）

基数排序使用计数排序作为子程序，因此它不是基于比较的算法。我们怎么知道CS是不够的？假设我们必须对[1, n²] 中的元素进行排序。使用 CS，我们需要 O(n²)。我们需要一个线性算法——O(n+k)，其中元素在[1, k]范围内。它从最不重要的一个（单位）开始，到最重要的（十、百等）对元素进行逐位排序。额外空间（来自 CS）：O(n)。

3. 搜索算法（Searching Algorithms）

搜索算法旨在检查数据结构中元素的存在，甚至返回它。有几种搜索方法，但这里是最受欢迎的两种：

线性搜索（Linear Search）

该算法的方法非常简单：您从数据结构的第一个索引开始搜索您的值。您将它们一一比较，直到您的值和当前元素相等。如果该特定值不在 DS 中，则返回 -1。

时间复杂度：O(n)

二分查找（Binary Search）

BS 是一种基于分而治之的高效搜索算法。不幸的是，它只适用于排序的数据结构。作为一种 DAC 方法，您连续将 DS 分成两半，并将搜索中的值与中间元素的值进行比较。如果它们相等，则搜索结束。无论哪种方式，如果您的值大于/小于它，搜索应该继续在右/左半部分。

时间复杂度：O(log n)

4. 埃氏筛法（Sieve of Eratosthenes）

给定一个整数 n，打印所有小于或等于 n 的素数。 Eratosthenes 筛法是解决这个问题的最有效的算法之一，它完美地适用于小于10.000.000 的n 。

该方法使用频率列表/映射来标记[0, n]范围内每个数字的素数：如果 x 是素数，则ok[x]=0，否则ok[x]=1。

我们开始从列表中选择每个素数，并用 1 标记列表中的倍数——这样，我们选择未标记的 (0) 数。最后，我们可以在 O(1) 中轻松回答任意数量的查询。

经典算法在许多应用中都是必不可少的，但我们可以进行一些优化。首先，我们很容易注意到 2 是唯一的偶素数，因此我们可以单独检查它的倍数，然后在范围内迭代以找到从 2 到 2 的素数。其次，很明显，对于数字 x，我们之前在迭代 2、3 等时已经检查了 2x、3x、4x 等。这样，我们的乘数检查 for 循环每次都可以从 x² 开始。最后，即使这些倍数中有一半是偶数，而且我们也在迭代奇素数，因此我们可以在倍数检查循环中轻松地从 2x 迭代到 2x。

空间复杂度：O(n) 时间复杂度：O(n*log(log n)) 用于经典算法，O(n) 用于优化算法。

5. 字符串匹配算法（Knuth-Morris-Pratt）

给定长度为 n 的文本和长度为 m 的模式，找出文本中所有出现的模式。

Knuth-Morris-Pratt 算法 (KMP) 是解决模式匹配问题的有效方法。 天真的解决方案基于使用“滑动窗口”，每次设置新的起始索引时，我们都会比较字符与字符，从文本的索引 0 开始到索引 nm。这样，时间复杂度是 O(m*(n-m+1))~O(n*m)。

KMP 是对朴素解决方案的优化：它在 O(n) 中完成，并且当模式具有许多重复的子模式时效果最佳。因此，它也使用滑动窗口，但不是将所有字符与子字符串进行比较，而是不断寻找当前子模式的最长后缀，这也是它的前缀。换句话说，每当我们在某些匹配后检测到不匹配时，我们就已经知道下一个窗口文本中的某些字符。因此，再次匹配它们是没有用的，因此我们重新开始匹配文本中具有该前缀后的字符的相同字符。我们怎么知道我们应该跳过多少个字符？好吧，我们应该构建一个预处理数组，告诉我们应该跳过多少个字符。

6.贪婪算法（Greedy）

Greedy 方法多用于需要优化且局部最优解导致全局最优解的问题。

也就是说，当使用 Greedy 时，每一步的最优解都会导致整体最优解。然而，在大多数情况下，我们在一个步骤中做出的决定会影响下一步的决定列表。在这种情况下，必须用数学方法证明算法。Greedy 也会在一些数学问题上产生很好的解决方案，但不是全部（可能无法保证最佳解决方案）！

贪心算法通常有五个组成部分：

• 候选集——从中创建解决方案；
• 选择函数——选择最佳候选人；
• 可行性函数——可以确定候选人是否能够为解决方案做出贡献；
• 一个目标函数——将候选人分配给（部分）解决方案；
• 一个解决方案函数——从部分解决方案构建解决方案。

分数背包问题

给定n个物品的重量和价值，我们需要将这些物品放入容量为W的背包中，以获得背包中的最大总价值（允许取件物品：一件物品的价值与其重量成正比）。

贪心方法的基本思想是根据它们的价值/重量比对所有项目进行排序。然后，我们可以添加尽可能多的整个项目。当我们发现一件比背包中剩余重量 (w1) 重 (w2) 的物品时，我们将对其进行分割：仅取出w2-w1以最大化我们的利润。保证这个贪心的解决方案是正确的。

7. 动态规划（Dynamic Programming）

动态规划 (DP) 是一种类似于分而治之的方法。它还将问题分解为类似的子问题，但它们实际上是重叠和相互依赖的——它们不是独立解决的。

每个子问题的结果都可以在以后随时使用，它是使用记忆（预先计算）构建的。DP 主要用于（时间和空间）优化，它基于寻找循环。

DP 应用包括斐波那契数列、河内塔、Roy-Floyd-Warshall、Dijkstra 等。 下面我们将讨论 0-1 背包问题的 DP 解决方案。

0–1 背包问题

给定n个物品的重量和价值，我们需要将这些物品放入容量为W的背包中，以获得背包中的最大总值（不允许像贪婪解决方案中的那样分割物品）。 0-1 属性是由我们应该选择整个项目或根本不选择它的事实给出的。 我们构建了一个 DP 结构作为矩阵dp[i][cw]存储我们通过选择总权重为 cw 的 i 个对象可以获得的最大利润。很容易注意到我们应该首先用v[i]初始化dp[1][w[i] ]，其中w[i]是第 i 个对象的权重，v[i] 是它的值。 复现如下：

dp[i][cw] = max(dp[i-1][cw], dp[i-1][cw-w[i]]+v[i])

我们稍微分析一下。

dp[i-1][cw]描述了我们没有在背包中添加当前物品的情况。dp[i-1][cw-w[i]]+v[i]就是我们添加item的情况。话虽如此，dp[i-1][cw-w[i]]是采用 i-1 个元素的最大利润：所以它们的重量是当前重量，没有我们的物品重量。最后，我们将项目的值添加到它。

答案存入dp[n][W]. 通过一个简单的观察进行优化：在循环中，当前行仅受前一行的影响。因此，将DP结构存储到矩阵中是不必要的，因此我们应该选择一个空间复杂度更好的数组：O(n)。时间复杂度：O(n*W)。

8. 最长公共子序列（Longest Common Subsequence）

给定两个序列，找出它们中存在的最长子序列的长度。子序列是以相同的相对顺序出现的序列，但不一定是连续的。例如，“bcd”、“abdg”、“c”都是“abcdefg”的子序列。

这是动态规划的另一个应用。LCS 算法使用 DP 来解决上述问题。

实际的子问题是要分别从序列 A 中的索引 i 开始，分别从序列 B 中的索引 j 中找到最长公共子序列。

接下来，我们将构建 DP 结构lcs[ ][ ]（矩阵），其中lcs[i][j]是从 A 中的索引 i 开始，分别是 B 中的索引 j 的公共子序列的最大长度。我们将以自顶向下的方式构建它。显然，解决方案存储在lcs[n][m] 中，其中 n 是 A 的长度，m 是 B 的长度。

递推关系非常简单直观。为简单起见，我们将考虑两个序列都是 1 索引的。首先，我们将初始化lcs[i][0] , 1<=i<=n和lcs[0][j] , 1<=j<=m , 0, 作为基本情况（没有从 0 开始的子序列）。然后，我们将考虑两种主要情况：如果A[i]等于B[j]，则lcs[i][j] = lcs[i-1][j-1]+1（比之前的 LCS 多一个相同的字符）。否则，它将是lcs[i-1][j]（如果不考虑A[i]）和lcs[i][j-1]（如果不考虑B[j]）之间的最大值）。

时间复杂度：O(n*m) 附加空间：O(n*m)

9. 最长递增子序列（Longest Increasing Subsequence）

给定一个包含 n 个元素的序列 A，找到最长子序列的长度，使其所有元素按递增顺序排序。子序列是以相同的相对顺序出现的序列，但不一定是连续的。例如，“bcd”、“abdg”、“c”是“abcdefg”的子序列。

LIS 是另一个可以使用动态规划解决的经典问题。

使用数组l[ ]作为 DP 结构来寻找递增子序列的最大长度，其中l[i]是包含A[i]的递增子序列的最大长度，其元素来自[A[i] ], ..., A[n]] 子序列。l[i]为 1，如果A[i]之后的所有元素比它小。否则，在 A[i] 之后大于它的所有元素之间的最大值为 1+。显然，l[n]=1，其中 n 是 A 的长度。 实现是自底向上的（从末尾开始）。

在搜索当前元素之后的所有元素之间的最大值时出现了一个优化问题。我们能做的最好的事情是二分搜索最大元素。

为了找到现在已知的最大长度的子序列，我们只需要使用一个额外的数组ind[]，它存储每个最大值的索引。

时间复杂度：O(n*log n) 附加空间：O(n)

10.凸包算法（Convex Hull）

给定同一平面中的一组 n 个点，找到包含所有给定点（位于多边形内部或其边上）的最小面积凸多边形。这种多边形称为凸包。凸包问题是一个经典的几何，在现实生活中有很多应用。例如，碰撞避免：如果汽车的凸包避免碰撞，那么汽车也能避免碰撞。路径的计算是使用汽车的凸表示完成的。形状分析也是在凸包的帮助下完成的。这样，图像处理很容易通过匹配模型的凸缺陷树来完成。

有一些算法用于寻找凸包，如 Jarvis 算法、Graham 扫描等。今天我们将讨论 Graham 扫描和一些有用的优化。

格雷厄姆扫描按极角对点进行排序——由某个点和其他选定点确定的线的斜率。然后用一个栈来存储当前时刻的凸包。当一个点 x 被压入堆栈时，其他点会被弹出堆栈，直到 x 与最后两个点所确定的线形成小于 180° 的角度。最后，引入堆栈的最后一个点关闭多边形。由于排序，这种方法的时间复杂度为 O(n*log n)。但是，这种方法在计算斜率时会产生精度误差。

一种改进的解决方案具有相同的时间复杂度，但误差较小，按坐标（x，然后是 y）对点进行排序。然后我们考虑由最左边和最右边的点形成的线，并将问题分为两个子问题。最后，我们在这条线的每一边找到了凸包。所有给定点的凸包是两个包的重聚。

11. 图遍历（Graph Traversals）

遍历图的问题是指以特定顺序访问所有节点，通常沿途计算其他有用信息。

广度优先搜索（Breadth-First Search）

广度优先搜索 (BFS) 算法是确定图是否连通的最常用方法之一——或者换句话说，查找 BFS 源节点的连通分量。

BFS 还用于计算源节点和所有其他节点之间的最短距离。BFS 的另一个版本是 Lee 算法，用于计算网格中两个单元格之间的最短路径。

该算法首先访问源节点，然后访问将被推入队列的邻居。队列中的第一个元素被弹出。我们将访问它的所有邻居，并将之前未访问的邻居推入队列。重复该过程直到队列为空。当队列为空时，表示所有可达顶点都已访问完毕，算法结束。

深度优先搜索（Depth-First Search）

深度优先搜索 (DFS) 算法是另一种常见的遍历方法。在检查图形的连通性时，它实际上是最好的选择。

首先，我们访问根节点并将其压入堆栈。虽然堆栈不为空，但我们检查顶部的节点。如果该节点有未访问的邻居，则选择其中一个并将其压入堆栈。否则，如果它的所有邻居都被访问过，我们就会弹出这个节点。当堆栈变空时，算法结束。

经过这样的遍历，就形成了一个DFS树。DFS 树有很多应用；最常见的一种是存储每个节点的“开始”和“结束”时间——它进入堆栈的时刻，分别是它从堆栈中弹出的时刻。

12. 弗洛依德算法（Floyd-Warshall）

Floyd-Warshall / Roy-Floyd 算法解决了所有对最短路径问题：找到给定边加权有向图中每对顶点之间的最短距离。

FW 是一个动态规划应用程序。DP 结构（矩阵）dist[ ][ ]用输入图矩阵初始化。然后我们将每个顶点视为其他两个节点之间的中间体。最短路径在每两对节点之间更新，任何节点 k 作为中间顶点。如果 k 是 i 和 j 之间排序路径中的中间值，则dist[i][j]成为dist[i][k]+dist[k][j]和dist[i][j]之间的最大值。

时间复杂度：O(n³) 空间复杂度：O(n²)

13. Dijkstra 算法和 Bellman-Ford 算法

迪杰斯特拉（Dijkstra） 算法

给定一个图和图中的一个源顶点，找出从源到给定图中所有顶点的最短路径。

Dijkstra 算法用于在加权图中找到这样的路径，其中所有的权重都是正的。

Dijkstra 是一种贪心算法，它使用以源节点为根的最短路径树（SPT）。SPT 是一种自平衡二叉树，但该算法可以使用堆（或优先级队列）来实现。我们将讨论堆解决方案，因为它的时间复杂度是 O(|E|*log |V|)。这个想法是使用图形的邻接列表表示。这样，节点将使用 BFS （广度优先搜索）在 O(|V|+|E|) 时间内遍历。

所有顶点都用 BFS 遍历，那些最短距离尚未最终确定的顶点被存储到最小堆（优先队列）中。

创建最小堆并将每个节点连同它们的距离值一起推入其中。然后，源成为距离为 0 的堆的根。其他节点将无限分配为距离。当堆不为空时，我们提取最小距离值节点 x。对于与 x 相邻的每个顶点 y，我们检查 y 是否在最小堆中。在这种情况下，如果距离值大于 (x, y) 的权重加上 x 的距离值，那么我们更新 y 的距离值。

贝尔曼-福特（Bellman-Ford）算法

正如我们之前所说，Dijkstra 仅适用于正加权图。贝尔曼解决了这个问题。给定一个加权图，我们可以检查它是否包含负循环。如果没有，那么我们还可以找到从我们的源到其他源的最小距离（可能为负权重）。

Bellman-Ford 非常适合分布式系统，尽管它的时间复杂度是 O(|V| |E|)。

我们初始化一个 dist[] 就像在 Dijkstra 中一样。对于 *|V|-1次，对于每个(x, y)边，如果dist[y] > dist[x] + (x, y) 的权重，那么我们用它更新dist[y]。

我们重复最后一步以可能找到负循环。这个想法是，如果没有负循环，最后一步保证最小距离。如果有任何节点在当前步骤中的距离比上一步中的距离短，则检测到负循环。

14.克鲁斯卡尔算法（Kruskal’s Algorithm）

我们之前已经讨论过什么是最小生成树。

有两种算法可以找到图的 MST：Prim（适用于密集图）和 Kruskal（适用于大多数图）。现在我们将讨论 Kruskal 算法。

Kruskal 开发了一种贪心算法来寻找 MST。它在稀有图上很有效，因为它的时间复杂度是 O(|E|*log |V|)。

该算法的方法如下：我们按权重的递增顺序对所有边进行排序。然后，选取最小的边。如果它不与当前 MST 形成循环，我们将其包括在内。否则，丢弃它。重复最后一步，直到 MST 中有 |V|-1 条边。

将边包含到 MST 中是使用 Disjoint-Set-Union 完成的，这也在前面讨论过。

15. 拓扑排序（Topological Sorting）

有向无环图 (DAG) 只是一个不包含循环的有向图。

DAG 中的拓扑排序是顶点的线性排序，使得对于每个拱形(x, y)，节点 x 出现在节点 y 之前。

显然，拓扑排序中的第一个顶点是一个入度为 0 的顶点（没有拱形指向它）。

另一个特殊属性是 DAG 没有唯一的拓扑排序。

BFS （广度优先搜索）实现遵循此例程：找到一个入度为 0 的节点并将第一个推入排序。该顶点已从图中删除。由于新图也是一个 DAG，我们可以重复这个过程。

在 DFS 期间的任何时候，节点都可以属于以下三个类别之一：

• 我们完成访问的节点（从堆栈中弹出）；
• 当前在堆栈上的节点；
• 尚未发现的节点。