30 个最基本的数据结构和算法的完整介绍

数据结构和算法 (DSA) 通常被认为是一个令人望而生畏的话题——这是一种常见的误解。它们构成了科技领域最具创新性概念的基础，对于求职/实习申请者和经验丰富的程序员来说都至关重要。掌握 DSA 意味着你能够运用计算和算法思维来解决前所未有的问题，并为任何科技公司（包括你自己的公司）的价值做出贡献！通过理解它们，你可以提高代码的可维护性、可扩展性和效率。

话虽如此，我决定将我在#100DaysOfCode挑战期间在Twitter上发布的所有 DSA 线程集中起来。本文旨在让 DSA 看起来不像人们想象的那么令人生畏。它包括 15 种最有用的数据结构和 15 种最重要的算法，可以帮助您在面试中脱颖而出，提高您的竞争性编程技能。每章都包含带有附加信息和练习问题的有用链接。DS 主题附有图形表示和关键信息。每个算法都实现到不断更新的Github repo中。在撰写本文时，它包含每个提及的算法（不仅如此）的伪代码、C ++、Python 和 Java（仍在进行中）实现。由于其他才华横溢且充满热情的开发人员通过添加新算法和新编程语言实现为其做出贡献，这个存储库正在不断扩展。

内容

一、数据结构

1. 数组
2. 链表
3. 堆栈
4. 队列
5. 地图和哈希表
6. 图表
7. 树木
8. 二叉树和二叉搜索树
9. 自平衡树（AVL 树、红黑树、伸展树）
10. 堆
11. 特里斯
12. 线段树
13. 芬威克树
14. 不相交集合并集
15. 最小生成树

二、算法

1. 分而治之
2. 排序算法（冒泡排序、计数排序、快速排序、归并排序、基数排序）
3. 搜索算法（线性搜索、二分搜索）
4. 埃拉托斯特尼筛法
5. Knuth-Morris-Pratt算法
6. 贪婪 I（轴上不重叠区间的最大数量）
7. 贪婪 II（分数背包问题）
8. 动态规划 I (0-1背包问题)
9. 动态规划 II（最长公共子序列）
10. 动态规划 III（最长递增子序列）
11. 凸包
12. 图遍历（广度优先搜索、深度优先搜索）
13. Floyd-Warshall/Roy-Floyd算法
14. Dijkstra算法和Bellman-Ford算法
15. 拓扑排序

一、数据结构

1. 数组

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

它们有什么用途？

想象一下剧院里有一排椅子。每把椅子都被分配了一个位置（从左到右），因此每个观众都会分配一个从他/她将坐的椅子开始的编号。这是一个数组。将问题扩展到整个剧院（椅子的行和列），你将得到一个二维数组（矩阵）！

特性

• 元素的值按顺序放置并通过其索引从 0 到数组长度 -1 进行访问；
• 数组是一块连续的内存块；
• 它们通常由相同类型的元素组成（这取决于编程语言）；
• 元素的访问和添加速度很快；搜索和删除不需要 O(1) 完成。

有用的链接

• GeeksforGeeks：数组简介
• LeetCode 问题集
• 面试中 50 个最常遇到的数组编码问题

2. 链表

链表是一种线性数据结构，类似于数组。链表和数组的主要区别在于，链表的元素并非存储在连续的内存位置。它由节点（存储当前元素值和指向下一个元素的地址引用的实体）组成。这样，元素之间通过指针链接。

它们有什么用途？

 链表的一个相关应用是实现浏览器的上一页和下一页。双向链表是存储用户搜索显示的页面的理想数据结构。

特性

• 它们有三种类型：单层、双层和圆形；
• 元素不存储在连续的内存块中；
• 非常适合出色的内存管理（使用指针意味着动态内存使用）；
• 插入和删除很快；访问和搜索元素在线性时间内完成。

有用的链接

• 可视化链表
• SDE 面试中关于链表数据结构的 50 个最常见问题

3. 堆栈

栈是一种抽象数据类型，它形式化了限制访问集合的概念。这种限制遵循 LIFO（后进先出）规则。因此，最后一个添加到栈中的元素也是第一个从栈中移除的元素。
栈可以用数组或链表来实现。

它们有什么用途？

生活中最常见的例子是食堂里叠放的盘子。最上面的盘子最先被拿走，最下面的盘子则留在盘子堆里时间最长。
栈最有用的一种情况是，当你需要获取给定元素的逆序时。只需将它们全部压入栈中，然后弹出即可。
另一个有趣的应用是有效括号问题。给定一串括号，你可以使用栈来检查它们是否匹配。

特性

• 一次只能访问最后一个元素（顶部的元素）；
• 一个缺点是，一旦你从顶部弹出元素以访问其他元素，它们的值将从堆栈的内存中丢失；
• 其他元素的访问在线性时间内完成；任何其他操作都在 O(1) 内完成。

有用的链接

• CS学院：Stack介绍
• CS 学院：Stack 应用程序 - Soldiers Row
• LeetCode 问题集

4.队列

队列是另一种来自受限访问集合的数据类型，类似于之前讨论过的堆栈。主要区别在于队列采用 FIFO（先进先出）模型组织：队列中第一个插入的元素也是第一个被移除的元素。队列可以使用固定长度数组、循环数组或链表来实现。

它们有什么用途？

 这种抽象数据类型 (ADT) 的最佳用途当然是模拟现实生活中的队列。例如，在呼叫中心应用程序中，队列用于保存等待顾问帮助的客户——这些客户应该按照他们拨打的电话的顺序获得帮助。
 优先级队列是一种特殊且非常重要的队列类型。元素根据与其关联的“优先级”被引入队列：优先级最高的元素最先被引入队列。这种 ADT 在许多图算法（Dijkstra 算法、广度优先搜索 (BFS)、Prim 算法、霍夫曼编码——下文将详细介绍）中都至关重要。它使用堆来实现。
 另一种特殊的队列类型是双端队列（双关语，发音为“deck”）。元素可以在队列的两端插入/移除。

特性

• 我们可以直接访问引入的“最旧”元素；
• 搜索元素将从队列的内存中删除所有访问的元素；
• 弹出/推送元素或获取队列前端都是在常数时间内完成的。搜索是线性的。

有用的链接

• 可视化队列
• LeetCode 问题集

5. 地图和哈希表

映射（字典）是抽象数据类型，包含键的集合和值的集合。每个键都关联一个值。
 哈希表是一种特殊类型的映射。它使用哈希函数生成哈希码，放入桶或槽的数组中：对键进行哈希处理，生成的哈希值指示值的存储位置。
 最常见的哈希函数（在众多函数中）是模常数函数。例如，如果常数为 6，则键 x 的值是x%6。
理想情况下，哈希函数会将每个键分配给唯一的桶，但大多数哈希函数的设计都采用了不完善的函数，这可能会导致具有相同生成值的键之间发生冲突。这种冲突总是以某种方式得到解决。

它们有什么用途？

 映射最为人熟知的应用是语言词典。每种语言中的每个单词都分配有其对应的定义。它使用有序映射（其键按字母顺序排列）实现。
 联系人也是一个映射。每个姓名都分配有一个电话号码。
 另一个有用的应用是值的规范化。假设我们想为一天中的每一分钟（24 小时 = 1440 分钟）分配一个从 0 到 1439 的索引。哈希函数为h(x) = x.hour*60+x.minute。

特性

• 键是唯一的（没有重复）；
• 抗碰撞性：很难找到具有相同密钥的两个不同输入；
• 原像抵抗：给定一个值 H，应该很难找到一个密钥 x，使得h(x)=H；
• 第二原像抗性：给定一个键及其值，很难找到具有相同值的另一个键；
• 术语：
• *“地图”：Java，C++；
• * “字典”：Python、JavaScript、.NET；
• * “关联数组”：PHP。
• 因为映射是使用自平衡红黑树（如下所述）实现的，所以所有操作都在 O(log n) 中完成；所有哈希表操作都是常量。

有用的链接

• Codeforces 问题集

6.图表

图是一种非线性数据结构，表示两个集合对：G={V, E}，其中 V 是顶点（节点）集合，E 是边（箭头）集合。节点是通过边互连的值 - 边描述了两个节点之间的依赖关系（有时与成本/距离相关）。
 图主要有两种类型：有向图和无向图。在无向图中，边(x, y)在两个方向上均可用：(x, y)和(y, x)。在有向图中，边(x, y)称为箭头，方向由其名称中顶点的顺序给出：箭头(x, y)与箭头(y, x)不同。

它们有什么用途？

 图是各种网络的基础：社交网络（例如 Facebook、LinkedIn），甚至是城市街道网络。社交媒体平台的每个用户都是一个包含其所有个人数据的结构——它代表网络的一个节点。Facebook 上的好友关系是无向图中的边（因为它是互易的），而在 Instagram 或 Twitter 上，帐户与其关注者/关注者帐户之间的关系是有向图中的箭头（不是互易的）。

特性

 图论是一个广泛的领域，但我们将重点介绍一些最为人熟知的概念：

• 无向图中节点的度是其关联边的数量；
• 有向图中节点的内部/外部度是指向/来自该节点的箭头数；
• 从节点 x 到节点 y 的链是相邻边的连续，其中 x 为其左端，y 为其右端；
• 循环是 x=y 的链；图可以是循环的/非循环的；如果 V 中的任意两个节点之间存在链，则图是连通的；
• 可以使用广度优先搜索（BFS）或深度优先搜索（DFS）来遍历和处理图，两者均在 O(|V|+|E|) 中完成，其中 |S| 是集合 S 的基数；查看下面的链接以获取图论中的其他重要信息。

有用的链接

• 图表编辑器
• 维基百科：图表 - 离散数学
• CS 学院：图形表示
• LeetCode 问题集

7.树木

树是一种无向图，其连通性极小（如果我们消除一条边，图就不再连通），而无环性极高（如果我们添加一条边，图就不再无环）。因此，任何无环连通的无向图都是树，但为了简单起见，我们将有根树称为树。
 根是一个固定节点，它确定了树中边的方向，因此一切“开始”都从这里开始。叶子是树的终端节点——一切“结束”都从这里结束。
 顶点的子节点是其下方的关联顶点。一个顶点可以有多个子节点。顶点的父节点是其上方的关联顶点——它是唯一的。

它们有什么用途？

 每当我们需要描绘层级结构时，我们都会用树形结构。我们自己的家谱就是一个很好的例子。你最古老的祖先是树的根。最年轻的一代代表叶子的集合。 
 树形结构还可以表示你所在公司中的上下级关系。这样你就可以找出谁是你的经理，以及你应该管理谁。

特性

• 根没有父节点；
• 叶子没有子项；
• 根与节点 x 之间的链的长度表示 x 所在的级别；
• 树的高度是它的最大级别（在我们的例子中为 3）；
• 遍历树的最常用方法是 O(|V|+|E|) 中的 DFS，但我们也可以使用 BFS；使用 DFS 在任何图中遍历的节点的顺序形成 DFS 树，它向我们指示了节点被访问的时间。

有用的链接

• TutorialsPoint：树
• Codeforces 问题集

8.二叉树和二叉搜索树

二叉树是一种特殊的树：每个顶点最多可以有两个子节点。在严格二叉树中，除叶子节点外，每个节点都恰好有两个子节点。具有 n 层的完全二叉树包含所有2ⁿ-1 个可能的节点。
 二叉搜索树是一种节点值属于全序集的二叉树——任意选定节点的值都大于其左子树的所有值，并且小于其右子树的所有值。

它们有什么用途？

 逆波兰表示法 (BT) 的一个重要应用是逻辑表达式的表示和求值。每个表达式可以分解为变量/常量和运算符。这种表达式的书写方法称为逆波兰表示法 (RPN)。这样，它们可以形成一棵二叉树，其中内部节点是运算符，叶子节点是变量/常量——这被称为抽象语法树 (AST)。 
 二叉树 (BST) 因其快速的键值搜索特性而被广泛使用。AVL 树、红黑树、有序集和映射都是使用 BST 实现的。

特性

• BT 的 DFS 遍历有三种类型：
• * 预订（根、左、右）；
• * 中序（左，根，右）；
• * 后序（左、右、根）；全部在 O（n）时间内完成；
• 中序遍历按升序给出树中的所有节点；
• 最左边的节点是 BST 中的最小值，最右边的节点是最大值；
• 注意 RPN 是 AST 的中序遍历；
• BST 具有排序数组的优点，但具有对数插入的缺点——其所有操作都在 O(log n) 时间内完成。

有用的链接

• GeeksforGeeks：二叉树
• GeeksforGeeks：表达式树的评估
• Medium：最佳 BST 实践问题和面试问题

9. 自平衡树

所有这些类型的树都是自平衡二叉搜索树。区别在于它们以对数时间平衡高度的方式。AVL
树在每次插入/删除操作后都能达到自平衡，因为一个节点的左子树和右子树的高度模差最大为 1。AVL 树以其发明者 Adelson-Velsky 和 ​​Landis 的名字命名。
在红黑树中，每个节点存储一个表示颜色的额外位，用于确保每次插入/删除操作后的平衡。
在伸展树中，最近访问的节点可以快速再次访问，因此任何操作的摊销时间复杂度仍然为 O(log n)。

它们有什么用途？

AVL 似乎是数据库理论中最好的数据结构。RBT
用于组织可比较的数据片段，例如文本片段或数字。在 Java 8 中，HashMap 就是使用 RBT 实现的。计算几何和函数式编程中的数据结构也使用 RBT 构建。
在 Windows NT 中（虚拟内存、网络和文件系统代码中），Splay 树用于缓存、内存分配器、垃圾收集器、数据压缩、Rops（用于长文本字符串的字符串替换）。

特性

• 任何自平衡 BST 中任何操作的摊销时间复杂度都是 O(log n)；
• 在最坏情况下，AVL 的最大高度是 1.44 * log2n（为什么？*提示：想象一下所有级别都已满的 AVL 的情况，除了最后一个只有一个元素的级别）；
• 在实践中，AVL 是搜索元素最快的，但为了实现自平衡而旋转子树的成本很高；
• 同时，由于没有旋转，RBT 提供更快的插入和删除速度；
• 伸展树不需要存储任何簿记数据。

有用的链接

• GeeksforGeeks：AVL 树
• GeeksforGeeks：红黑树
• GeeksforGeeks：伸展树

10.堆

最小堆是一棵二叉树，其中每个节点都具有一个属性，即其值大于或等于其父节点的值：val[par[x]] <= val[x]，其中 x 是堆中的一个节点，val[x]是其值，par[x]是其父节点。
还有一种最大堆，它实现了相反的关系。
二叉堆是一棵完全二叉树（所有层级都已填满，除了最后一层）。

它们有什么用途？

正如我们几天前讨论过的，优先级队列可以用二叉堆高效实现，因为它支持在 O(log n) 时间内执行 insert()、delete()、extractMax() 和 decreaseKey() 操作。因此，堆在图算法中也至关重要（因为优先级队列的存在）。
任何时候，当你需要快速访问最大/最小元素时，堆都是最佳选择。
堆也是堆排序算法的基础。

特性

• 它始终是平衡的：任何时候我们在结构中删除/插入一个元素，我们只需要“筛选”/“渗透”它，直到它处于正确的位置;
• 节点k > 1的父节点是[k/2]（其中 [x] 是 x 的整数部分），其子节点是2*k和2*k+1；
• 优先级队列的替代方案是设置 ordered_map（在 C++ 中）或任何其他可以轻松访问最小/最大元素的有序结构；
• 根具有优先级，因此访问根的时间复杂度为 O(1)，插入/删除时间为 O(log n)；创建堆时间为 O(n)；堆排序时间为 O(n*log n)。

有用的链接

• GeeksforGeeks: 堆

11.尝试

Trie 是一种高效的信息检索数据结构。它也称为前缀树，是一种允许插入和搜索的搜索树，时间复杂度为 O(L)，其中 L 是键的长度。
如果我们将键存储在一个均衡的二叉搜索树 (BST) 中，则所需的时间与 L * log n 成正比，其中 n 是树中键的数量。因此，Trie 是一种比 BST 更快的数据结构（时间复杂度为 O(L)），但代价是 Trie 的存储需求更高。

它们有什么用途？

字典树主要用于存储字符串及其值。它最酷的应用之一是 Google 搜索栏中的输入自动完成和自动建议。字典树是最佳选择，因为它是最快的：更快的搜索速度比不使用字典树节省的存储空间更有价值。
输入单词的正字法自动校正也是使用字典树完成的，方法是在词典中查找该单词，或者在同一文本中查找该单词的其他实例。

特性

• 它具有键值关联；键通常是一个单词或其前缀，但可以是任何有序列表；
• 根以空字符串作为键；
• 节点的值与其子节点的值之间的长度差为 1；这样，根节点的子节点将存储长度​​为 1 的值；作为结论，我们可以说来自第 k 层的节点 x 具有长度为 k 的值；
• 正如我们所说，插入/搜索操作的时间复杂度为 O(L)，其中 L 是键的长度，这比 BST 的 O(log n) 快得多，但与哈希表相当；
• 空间复杂度实际上是一个缺点：O(ALPHABET_SIZE*L*n)。

有用的链接

• 中等：尝试理解尝试
• GeeksforGeeks：尝试

12. 线段树

线段树是一种完整的二叉树，它能够高效地响应查询，同时仍能轻松地修改其元素。
给定数组中索引为 i 的每个元素代表一个以[i, i]区间为标签的叶子节点。如果一个节点的子节点分别标记为[x, y]和[y, z]，则该节点的标签为[x, z]区间。因此，给定 n 个元素（索引为 0），线段树的根节点将被标记为[0, n-1]。

它们有什么用途？

它们在那些可以使用分治法（我们将要讨论的第一个算法概念）解决的任务中非常有用，并且可能需要更新其元素。这样，在更新元素时​​，包含该元素的任何区间也会被修改，因此复杂度是对数的。例如，求 n 个给定元素的和/最大值/最小值是线段树最常见的应用。如果发生元素更新，二分查找也可以使用线段树。

特性

• 作为二叉树，节点 x 将有2*x和2*x+1作为子节点，并有[x/2]作为父节点，其中[x]是 x 的整数部分；
• 在线段树中更新整个范围的一种有效方法称为“惰性传播”，它也是在 O(log n) 中完成的（有关操作的实现，请参阅下面的链接）；
• 它们可以是 k 维的：例如，有 q 个查询要求找到一个矩阵的给定子矩阵的总和，我们可以使用二维线段树；
• 更新元素/范围需要 O(log n) 时间；回答查询是恒定的（O(1)）；
• 空间复杂度是线性的，这是一个很大的优势：O（4*n）。

有用的链接

• CP 算法：线段树。惰性传播
• GeeksforGeeks：线段树
• Codeforces 问题集

13. 芬威克树

芬威克树（Fenwick Tree），又称二叉索引树（BIT），是一种用于高效更新和查询的数据结构。与线段树相比，BIT 占用空间更小，也更易于实现。

它们有什么用途？

BIT 用于计算前缀和——第 i 个位置元素的前缀和是从第一个位置到第 i 个位置元素的和。它们用数组表示，其中每个索引都以二进制表示。例如，索引 10 相当于十进制中的索引 2。

特性

• 树的构建是最有趣的部分：首先，数组应该以 1 为索引；要找到节点 x 的父节点，您应该将其索引 x 转换为二进制系统并翻转最右边的有效位；例如，节点 6 的父节点是 4；6 = 1*2²+1*2¹+0*2⁰ => 1"1"0（翻转）=> 100 = 1*2²+0*2¹+0*2⁰ = 4；
• 最后，对元素进行与运算，每个节点应包含一个可以添加到前缀和的区间（有关构造和实现的更多信息，请参阅下面的链接）；
• 更新的时间复杂度仍然是 O(log n)，查询的时间复杂度仍然是 O(1)，但空间复杂度有更大的优势：O(n)，而线段树的则是 O(4*n)。

有用的链接

• Tushar Roy：BIT
• GeeksforGeeks：BIT
• CP算法：BIT

14. 不相交集合并集

给定 n 个元素，每个元素代表一个独立的集合。不相交集合并 (DSU) 允许我们执行以下两项操作：

1. UNION — 组合任意两个集合（如果两个不同元素的集合不是来自同一集合，则将它们统一起来）；
2. FIND — 查找元素所属的集合。

它们有什么用途？

DSU 在图论中非常重要。你可以检查两个顶点是否来自同一个连通分量，甚至可以合并两个连通分量。
我们以城镇为例。由于人口和经济增长的邻近城市正在扩张，它们很容易形成一个大都市。因此，两个城市合并，它们的居民居住在同一个大都市。我们还可以通过调用 FIND 函数来检查一个人居住在哪个城市。

特性

• 它们用树来表示；一旦两个集合合并在一起，两个根中的一个就成为主根，而另一个根的父级就是另一棵树的叶子之一；
• 一种实用的优化是通过树的高度进行压缩；这样，通过最大的树进行并集，可以轻松更新它们的数据（参见下面的实现）；
• 所有操作均在 O(1) 时间内完成。

有用的链接

• GeeksforGeeks：DSU
• CP算法：DSU
• Codeforces 问题集

15.最小生成树

给定一个连通无向图，该图的生成树是一棵子图，该子图是一棵树，将所有节点连接在一起。一个图可以包含许多不同的生成树。加权连通无向图的最小生成树 (MST) 是指权重（成本）小于或等于其他所有生成树权重的生成树。生成树的权重是赋予生成树每条边的权重之和。

它们有什么用途？

最小生成树 (MST) 问题是一个优化问题，即最小成本问题。假设有一个路线网络，我们可以认为，影响 n 个城市之间建立国道的因素之一是两个相邻城市之间的最小距离。
这样，国道就用道路网络图的最小生成树 (MST) 来表示。

特性

• 作为一棵树，具有 n 个顶点的图的 MST 具有n-1 条边；可以使用以下方法解决：
• * Prim 算法——密集图的最佳选择（具有 n 个节点且边数接近n(n-1)/2 的图）；
• * Kruskal 算法——最常用；它是一种基于不相交集并集的贪婪算法（我们也将讨论它）；
• 构建它的时间复杂度为 O(n log n) 或 O(n log m)（对于 Kruskal）（取决于图），对于 Prim 为 O(n²)。

有用的链接

• CP算法：MST
• MST 教程

二、算法

1.分而治之

分治法 (DAC) 本身并非一种特定的算法，而是一类重要的算法，在深入研究其他主题之前需要先理解。它用于解决那些可以分解成与原问题类似但规模较小的子问题的问题。DAC 随后以递归方式求解这些子问题，并最终合并结果以找到问题的解。
它包含三个阶段：

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

它有什么用途？

DAC 的一个实际应用是使用多处理器进行并行编程，因此子问题可以在不同的机器上执行。DAC
是许多算法的基础，例如快速排序、归并排序、二分查找或快速乘法算法。

特性

• 每个 DAC 问题都可以写成递归关系；因此，找到停止递归的基本情况至关重要；
• 其复杂度为T(n)=D(n)+C(n)+M(n)，即每个阶段根据问题的不同具有不同的复杂度。

有用的链接

• 分而治之的实施
• GeeksforGeeks：DAC
• 精彩：DAC

2.排序算法

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

冒泡排序

冒泡排序是最简单的排序算法之一。它基于相邻元素顺序错误时反复交换元素。它比较稳定，时间复杂度为 O(n²)，需要 O(1) 的辅助空间。

• 冒泡排序可视化

计数排序

计数排序不是基于比较的排序。它本质上是利用每个元素的频率（一种哈希算法），确定最小值和最大值，然后在它们之间迭代，根据频率对每个元素进行排序。它的复杂度为 O(n)，占用空间与数据范围成正比。如果输入范围不显著大于元素数量，则计数排序效率较高。

• 计数排序可视化

快速排序

快速排序是“分而治之”的一种应用。它基于选择一个元素作为基准（第一个、最后一个或中位数），然后交换元素，使基准位于所有小于它的元素和所有大于它的元素之间。它不占用额外空间，时间复杂度为 O(n*log n)——这是基于比较的方法中最佳的复杂度。
以下是选择最后一个元素作为基准的演示：

• 快速排序可视化

合并排序

归并排序也是一种分治应用。它将数组分成两半，对每半进行排序，然后合并它们。它的时间复杂度也是 O(n*log n)，因此它也像快速排序一样超级快，但遗憾的是，它需要 O(n) 的额外空间来同时存储两个子数组，并最终将它们合并。

• 合并排序可视化

基数排序

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

• 基数排序可视化

有用的链接

• 冒泡排序实现
• 计数排序实现
• 快速排序实现
• 归并排序实现
• 基数排序实现

3. 搜索算法

搜索算法旨在检查数据结构中某个元素是否存在，并返回该元素。搜索方法有很多种，但以下是最常用的两种：

线性搜索

该算法的方法非常简单：从数据结构的第一个索引开始搜索值。逐个比较它们，直到值与当前元素相等。如果该特定值不在 DS 中，则返回 -1。
时间复杂度：O(n)

二分查找

BS 是一种基于分治法的高效搜索算法。遗憾的是，它仅适用于已排序的数据结构。作为 DAC 方法，你需要不断将 DS 分成两半，并将搜索中的值与中间元素的值进行比较。如果它们相等，则搜索结束。无论哪种情况，如果你的值大于/小于中间元素，则搜索应继续在右半/左半部分进行。
时间复杂度：O(log n)。

有用的链接

• 线性搜索实现
• 二分查找实现

4. 埃拉托斯特尼筛法

给定一个整数 n，打印所有小于或等于 n 的素数。
埃拉托斯特尼筛选法是解决这个问题最有效的算法之一，它完美地适用于小于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² 开始。最后，这些倍数中有一半是偶数，而且我们迭代的是奇素数，因此在倍数检查循环中，我们可以轻松地从 2*x 迭代到 2*x。 空间复杂度：O(n)。 时间复杂度：经典算法为 O(n*log(log n))，优化算法为 O(n)。 为什么是 O(n*log(log n))？答案是：

有用的链接

• 埃拉托斯特尼筛法的实现

5. Knuth-Morris-Pratt 算法

给定一段长度为 n 的文本和一个长度为 m 的模式，找出文本中所有出现该模式的位置。Knuth
-Morris-Pratt 算法 (KMP) 是解决模式匹配问题的一种有效方法。
其简单解决方案基于使用“滑动窗口”，每次设置新的起始索引时，我们都会逐个字符地进行比较，从文本的索引 0 开始到索引 nm。这样，时间复杂度为 O(m*(n-m+1))~O(n*m)。KMP
是对简单解决方案的一种优化：其复杂度为 O(n)，并且当模式包含许多重复的子模式时效果最佳。因此，它也使用滑动窗口，但不是将所有字符与子字符串进行比较，而是不断寻找当前子模式的最长后缀，也就是它的前缀。换句话说，每当我们在进行一些匹配后检测到不匹配时，我们就已经知道下一个窗口文本中的一些字符。因此，再次匹配它们是没有意义的，所以我们用文本中该前缀后面的字符重新匹配相同的字符。我们如何知道应该跳过多少个字符呢？我们应该构建一个预处理数组，告诉我们应该跳过多少个字符。

有用的链接

• Tushar Roy：KMP教程
• KMP实施

6.贪婪

贪婪算法主要用于需要优化的问题，局部最优解可以引出全局最优解。
也就是说，使用贪婪算法时，每一步的最优解都会引出全局最优解。然而，在大多数情况下，我们在某一步做出的决策会影响下一步的决策列表。在这种情况下，算法必须经过数学证明。贪婪算法在某些数学问题上也能产生很好的解决方案，但并非在所有问题上都能产生很好的解决方案（可能无法保证获得最优解）！

贪婪算法通常包含五个组成部分：

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

分数背包问题

给定 n 件物品的重量和价值，我们需要将这些物品放入容量为 W 的背包中，以使背包的总价值最大化（允许取用单件物品：每件物品的价值与其重量成正比）。
贪婪算法的基本思想是按照物品的价值/重量比对所有物品进行排序。然后，我们将尽可能多的整件物品放入背包中。一旦我们发现一件物品的重量 (w2) 大于背包中剩余的重量 (w1)，我们就将其拆分：只取用其中的w2-w1部分，以最大化我们的利润。此贪婪算法保证正确。

有用的链接

• 最大非重叠间隔数实现
• 分数背包问题的实现

7.动态规划

动态规划 (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]描述的是放入物品的情况。也就是说，dp[i-1][cw-w[i]]表示取出 i-1 个元素的最大收益，即它们的权重是当前元素的权重，不包括物品的权重。最后，我们将物品的值添加到其中， 结果存储在dp[n][W]中。通过简单的观察可以进行优化：在递归中，当前行仅受前一行的影响。因此，将 DP 结构存储到矩阵中是不必要的，而应该选择数组以获得更好的空间复杂度：O(n)。时间复杂度：O(n*W)。

有用的链接

• 0-1背包问题的实现

8.最长公共子序列

给定两个序列，求出它们中最长子序列的长度。子序列是指以相同的相对顺序出现，但不一定连续的序列。例如，“bcd”、“abdg”、“c”是“abcdefg”的子序列。
这是动态规划的另一个应用。LCS 算法使用动态规划 (DP) 来解决上述问题。
实际的子问题是找到序列 A 中分别从索引 i 开始，序列 B 中分别从索引 j 开始的最长公共子序列。
接下来，我们将构建动态规划结构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)

有用的链接

• LCS 实现

9.最长递增子序列

给定一个包含 n 个元素的序列 A，找到最长子序列的长度，使得其所有元素都按递增顺序排列。子序列是以相同的相对顺序出现但不一定连续的序列。例如，“bcd”，“abdg”，“c”是“abcdefg”的子序列。LIS
是另一个可以使用动态规划解决的经典问题。使用数组l[ ]作为 DP 结构
来查找递增子序列的最大长度，其中l[i]是包含A[i]的递增子序列的最大长度，其元素来自[A[i], ..., A[n]] 子序列。如果A[i]之后的所有元素都小于l[i]，则为 1。否则，它是 A[i] 之后所有大于它的元素之间的 1 + 最大值。显然，l[n]=1，其中 n 是 A 的长度。该实现采用自下而上的方式（从末尾开始）。 在当前元素之后的所有元素中查找最大值时，存在一个优化问题。我们能做的最好的就是对最大值元素进行二分查找。 为了找到已知最大长度的子序列，我们只需使用一个额外的数组ind[ ]，用于存储每个最大值的索引。 时间复杂度：O(n*log n)， 额外空间：O(n)

有用的链接

• LIS 实施

10.凸包

给定同一平面上的 n 个点集，找到包含所有给定点（位于多边形内部或其侧面）的最小面积凸多边形。这样的多边形称为凸包。凸包问题是一种经典的几何问题，在实际生活中有很多应用。例如，防撞：如果汽车的凸包避免了碰撞，那么汽车也能避免碰撞。路径计算是使用汽车的凸表示来完成的。形状分析也是借助凸包完成的。这样，通过凸缺陷树匹配模型就可以轻松地进行图像处理。
有一些算法用于查找凸包，例如 Jarvis 算法、Graham 扫描等。今天我们将讨论 Graham 扫描和一些有用的优化。Graham
扫描按极角（由某个点和其他选定点确定的直线的斜率）对点进行排序。然后，使用堆栈存储当前时刻的凸包。当将点 x 压入堆栈时，其他点将从堆栈中弹出，直到 x 和由最后两个点确定的线形成的角小于 180°。最后，引入堆栈的最后一个点闭合多边形。由于排序，此方法的时间复杂度为 O(n*log n)。但是，此方法在计算斜率时会产生精度误差。
一种具有相同时间复杂度但误差较小的改进解决方案是按坐标（x，然后 y）对点进行排序。然后我们考虑由最左边和最右边的点形成的线，并将问题分为两个子问题。最后，我们找到线两侧的凸包。所有给定点的凸包是两个凸包的重合。

有用的链接

• 凸包实现

11. 图遍历

遍历图的问题是指按照特定顺序访问所有节点，通常在此过程中计算其他有用的信息。

广度优先搜索

广度优先搜索 (BFS) 算法是确定图是否连通的最常用方法之一 — — 或者换句话说，找到 BFS 源节点的连通分量。BFS
还用于计算源节点和所有其他节点之间的最短距离。BFS 的另一个版本是 Lee 算法，用于计算网格中两个单元格之间的最短路径。
该算法首先访问源节点，然后访问其将被推送到队列中的邻居节点。从队列中弹出第一个元素。我们将访问它的所有邻居，并将以前未访问过的邻居推送到队列中。重复该过程，直到队列为空。当队列变空时，这意味着所有可到达的顶点都已被访问，算法结束。

深度优先搜索

深度优先搜索 (DFS) 算法是另一种常见的遍历方法。在检查图的连通性时，它实际上是最佳选择。
首先，我们访问根节点并将其推送到堆栈中。当堆栈不为空时，我们检查顶部的节点。如果该节点有未访问的邻居，则选择其中一个并将其推送到堆栈中。否则，如果所有邻居都已被访问，则弹出该节点。当堆栈为空时，算法结束。
经过这样的遍历，就形成了 DFS 树。DFS 树有许多应用；最常见的应用之一是存储每个节点的“起始”和“结束”时间——它进入堆栈的时刻，分别是它从堆栈中弹出的时刻。

有用的链接

• BFS 实现
• DFS实现
• BFS 可视化
• 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²)

有用的链接

• FW 实现

13. Dijkstra算法和Bellman-Ford算法

Dijkstra算法

给定一个图和图中的源顶点，找到从源到给定图中所有顶点的最短路径。Dijkstra
算法用于在加权图中查找此类路径，其中所有权重均为正。Dijkstra
是一种贪婪算法，它使用以源节点为根的最短路径树 (SPT)。SPT 是一种自平衡二叉树，但该算法可以使用堆（或优先级队列）实现。我们将讨论堆解决方案，因为它的时间复杂度为 O(|E|*log |V|)。其思想是使用图的邻接表表示。这样，将使用 BFS 在 O(|V|+|E|) 时间内遍历节点。
所有顶点都使用 BFS 遍历，尚未确定最短距离的顶点将存储到最小堆（优先级队列）中。
创建最小堆 (Min-Heap) 后，每个节点及其距离值都会被推入其中。然后，源节点成为堆的根节点，距离为 0。其他节点的距离将被赋值为无穷大。当堆不为空时，我们提取距离值最小的节点 x。对于每个与 ​​x 相邻的顶点 y，我们检查 y 是否在最小堆中。在这种情况下，如果距离值大于 (x, y) 的权重加上 x 的距离值，则更新 y 的距离值。

Bellman-Ford算法

正如我们之前所说，Dijkstra 仅适用于正加权图。Bellman 解决了这个问题。给定一个加权图，我们可以检查它是否包含负循环。如果不包含，那么我们也可以找到从我们的源到其他点的最小距离（可能为负权重）。Bellman
-Ford 非常适合分布式系统，尽管它的时间复杂度为 O(|V| |E|)。
我们像在 Dijkstra 中一样初始化 dist[ ]。对于 *|V|-1次，对于每个(x, y)边，如果dist[y] > dist[x] + (x, y) 的权重，那么我们用它来更新dist[y]
。 我们重复最后一步以找到可能的负循环。这个想法是，如果没有负循环，最后一步保证最小距离。如果有任何节点在当前步骤中的距离比上一步更短，那么就检测到了负循环。

有用的链接

• Dijkstra 实现
• BF实施

14. Kruskal算法

我们之前讨论过什么是最小生成树。
有两种算法可以找到图的 MST：Prim（适用于密集图）和 Kruskal（适用于大多数图）。现在我们将讨论 Kruskal 算法。Kruskal
开发了一种贪婪算法来查找 MST。它在罕见图上很有效，因为它的时间复杂度为 O(|E|*log |V|)。
该算法的方法如下：我们按权重升序对所有边进行排序。然后，选择最小的边。如果它不与当前 MST 形成循环，我们将它包括在内。否则，丢弃它。重复最后一步，直到 MST 中有 |V|-1 条边。
使用 Disjoint-Set-Union 将边包含到 MST 中，这在前面也讨论过。

有用的链接

• Kruskal实现

15.拓扑排序

有向无环图 (DAG) 就是一个不含环的有向图。DAG
中的拓扑排序是对顶点进行线性排序，即对于每个拱(x, y)，节点 x 位于节点 y 之前。
显然，拓扑排序中的第一个顶点是入度为 0 的顶点（没有指向它的拱）。
另一个特殊性质是 DAG 没有唯一的拓扑排序。BFS
实现遵循以下流程：找到入度为 0 的节点，并将第一个顶点推入排序。然后从图中删除该顶点。由于新图也是 DAG，我们可以重复该过程。

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

• 我们已访问完的节点（从堆栈中弹出）；
• 当前位于堆栈中的节点；
• 尚未被发现的节点。

如果在 DAG 中的 DFS 过程中，节点 x 有一条指向节点 y 的出边，那么 y 要么属于第一类别，要么属于第三类别。如果 y 在堆栈中，那么(x, y)将结束一个循环，这与 DAG 的定义相矛盾。
这个性质实际上告诉我们，一个顶点在其所有出边邻居都弹出后才会从堆栈中弹出。因此，要对图进行拓扑排序，我们需要跟踪弹出顶点的逆序列表。

有用的链接

• 拓扑排序实现

哇，你已经读完这篇文章了。谢谢你的关注！:) 祝你编程愉快！