1. 回溯算法概述回溯算法（backtracking algorithm）是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，直到找到解或者尝试了所有可能的选择都无法找到解为止。这种走不通就退回再走的技术称为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
回溯算法通常采用深度优先搜索来遍历解空间，前序、中序和后序遍历都属于深度优先搜索。回溯算法的核心思想有两点：
深度优先搜索：回溯算法基于深度优先搜索的思想，它会沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点所在的路径无法得到有效的解时，算法会回溯到上一个节点，尝试其他的路径继续搜索。
穷举与剪枝：本质上是对所有可能的解进行穷举搜索，但与纯粹的暴力枚举不同，回溯算法会在搜索过程中根据问题的约束条件进行剪枝操作，避免对一些明显不可能产生解的分支进行搜索，从而提高搜索效率。
1. 分治算法概述分治算法（Divide and Conquer）是一种重要的算法设计策略，其基本思想是将一个规模较大的问题分解为若干个规模较小、相互独立且与原问题形式相同的子问题，然后递归地解决这些子问题，最后将子问题的解合并起来得到原问题的解。
分治算法通常包含三个步骤：
分解（Divide）：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
解决（Conquer）：若子问题规模较小而容易被解决则直接求解，否则递归地解各个子问题。
合并（Combine）：将各个子问题的解合并为原问题的解。
2. 分支算法经典案例2.1 归并排序归并排序是分治算法的一个经典应用，它的基本思想是将一个数组分成两个子数组，分别对这两个子数组进行排序，然后将排好序的子数组合并成一个有序的数组。
归并排序算法
2.2 快速排序快速排序采用分治策略，通过递归地将数组分割成子数组来实现排序。其平均时间复杂度为 **O(n log n)**，在大多数情况下表现良好，因此在实际应用中广泛使用。
快速排序算法
2.3 合并K个有序单链表
给定一个链表数组，每个链表都已经按升序排列，要求使 ...
1. 贪心算法概述贪心算法（Greedy Algorithm）是一种基于局部最优选择的算法设计思想，其核心在于每一步都做出当前看起来最优的选择，并希望通过这些局部最优选择的累积，最终得到全局最优解。它不回溯，也不考虑未来的可能影响，而是“贪心”地选择当前最有利的选项。
在处理某些问题的时候使用贪心算法通常遵循以下步骤：
分解问题：将原问题分解为一系列子问题。
贪心选择：在每一个子问题中，都做出当前看起来最优的选择。
求解子问题：对每一个子问题求解，得到子问题的局部最优解。
合并解：将所有子问题的局部最优解合并起来，得到原问题的解。
贪心算法典型的应用场景:
问题类型
示例
贪心策略
区间调度问题
活动选择、无重叠区间
按结束时间排序，选最早结束的区间
最小生成树
Prim、Kruskal 算法
每次选权重最小的边
最短路径问题
Dijkstra 算法
每次选当前距离起点最近的节点
哈夫曼编码
数据压缩
合并频率最小的字符节点
部分背包问题
物品可分割的背包问题
按单位价值排序，优先选高价值物品
贪心算法与动态规划作为两种重要的算法设计策略，掌握贪心算 ...
1. 哈希表哈希表（Hash Table）是一种高效的数据结构，用于存储键值对（Key-Value Pair）。它通过哈希函数将键映射到数组中的特定位置，从而实现快速的插入、删除和查找操作。在 C++ 的标准模板库（STL）中，有多个容器基于哈希表实现，它们为开发者提供了高效的数据存储和查找方式：
std::unordered_map和std::unordered_set
std::unordered_multimap 和 std::unordered_multiset
作为一名专业的 C++ 程序员，我们不应仅仅满足于表面的认知，而要深入探寻事物背后的原理。就如同我们即将研究哈希表的底层实现一样，在开启这段深入探究之旅前，我们很有必要先了解一些关于哈希表的基础概念。这样一来，我们就能搭建起一个扎实的知识框架，为后续更深入地剖析哈希表的底层奥秘做好充分准备。
1.1 哈希函数哈希函数是哈希表的核心所在，它具备强大的功能，能够把任意大小的数据（即键）精准地映射为固定大小的数据，而这种固定大小的数据通常表现为整数。在理想的情形下，哈希函数理应满足以下几个至关重要的条件：
均匀分布特性 ...
数据结构
未读1. 最小生成树概述最小生成树（Minimum Spanning Tree，简称为 MST）作为图论领域的关键概念，在加权连通图里有着广泛且重要的应用。在深入探究最小生成树的具体内涵之前，让我们先一同回顾图论中的一些基础知识点：
加权图
加权图（Weighted Graph）是一种每条边都被赋予一个权值（Weight）的图。这些权值可以代表距离、成本、时间等实际意义的度量。比如在一个表示城市间道路的图中，边的权值可以表示两个城市之间的距离。
连通图
连通图（Connected Graph）指的是在无向图中，任意两个顶点之间都存在路径相连。也就是说，从图中的任意一个顶点出发，都能够到达其他任何顶点。
联通网
带权连通图就是连通网。
生成树
生成树是一种特殊的连通子图，涵盖了连通图里的所有N个顶点，并且恰好包含N−1条边。
最小生成树这一概念，最初主要是为加权连通无向图量身打造的。不过，在有向图领域，也衍生出了与之类似的拓展性概念。而本课程所涉及的内容，主要围绕加权连通无向图来逐步展开，以此来探讨最小生成树相关知识。
对于一个加权连通无向图 G=(V,E)，其中V是图的顶点集合 ...
1. 并查集概述并查集（Union-Find），又称不相交集合（Disjoint Set Union, DSU），是一种用于处理不相交集合的合并与查询问题的数据结构。它支持两种主要操作：
查找（Find）：确定一个元素属于哪个集合。
合并（Union）：将两个不同的集合合并成一个集合。
并查集常见的存储方式是使用数组来模拟树结构，利用数组存储每个元素的父节点信息。数组的下标对应元素编号，数组中存储的值代表该元素的父节点编号。通过不断查找元素的父节点，最终找到根节点，以此确定元素所属的集合。
在上图里呈现的是两棵树的结构，而在并查集这种数据结构体系中，这两棵树分别对应着两个集合。从存储实现的角度来看，这两个集合通常会以两个数组的形式来进行表示。
（图1）数组下标
0
1
2
3
4
5
节点值
D
E
F
G
H
J
存储的父节点编号
0
0
0
0
1
3
（图2）数组下标
0
1
2
3
4
5
6
节点值
A
B
C
D
E
F
G
存储的父节点编号
0
0
0
1
3
4
5
在并查集所构建的树状结构里，根节点处于一种特殊地位，它不 ...
1. 最短路径概述在计算机科学和图论领域中，图的最短路径问题是一个非常重要且经典的问题。图是由顶点（节点）和连接这些顶点的边组成的数据结构，在许多实际场景中都有广泛应用，如地图导航、网络路由、社交网络分析等。最短路径问题的目标是在一个图中找到从一个特定的起始顶点到另一个目标顶点的路径，使得这条路径上所有边的权值之和最小。
依据图中边是否具有方向对最短路径进行分类，可将其明确划分为有向图最短路径和无向图最短路径这两类。
1.1 有向图的最短路径在有向图中，边是有方向的，从顶点u到顶点v的路径必须沿着边的方向进行。因此，有向图中顶点之间的可达性和最短路径是有方向性的，即从u到v的最短路径和从v到u的最短路径可能不同，甚至一个方向可达而另一个方向不可达。
有向图的的最短路径的应用场景举例：
交通网络：例如城市中的单行道网络，车辆只能按照规定的方向行驶，就可以用有向图来表示，计算从一个地点到另一个地点的最短路径。
任务调度：在项目管理中，任务之间存在先后依赖关系，用有向边表示任务的先后顺序，可通过计算有向图的最短路径来确定项目的最短完成时间。
然后，我们再来了解一下有向图最短路径的求解方式 ...
1. 图的基本概念图（Graph）是一种极为重要且基础的结构。由顶点（Vertex，也称为节点 Node）集合V和边（Edge）集合 E组成的一种数据结构，通常表示为 G=(V,E)其中 V代表顶点的有穷非空集合，而 E 则代表边的集合。
接下来，我们再了解一些图相关的术语：
顶点（Vertex）集合：具有有穷性且非空，意味着其中包含有限数量的顶点元素，并且至少存在一个顶点
边（Edge）集合：边用于表示顶点与顶点之间的关联关系，它们可以是无向的，用以体现顶点间的双向联系，也可以是有向的，来明确顶点间的单向关联
度（Degree）：在无向图中，一个顶点的度是指与该顶点相连的边的数量；
入度（In - Degree）：在有向图中，入度是指向该顶点的边的数量
出度（Out - Degree）：在有向图中，出度是从该顶点出发的边的数量。
相邻顶点（Adjacent Vertices）：如果两个顶点之间有边相连，则称这两个顶点相邻。
生成树（Spanning Tree）：连通无向图的一个子图，它是包含图中所有顶点的树（无环的连通图）。
森林（Forest）：由若干棵树组成的图，即每个连通 ...
1. Trie 树的基本概念Trie树，又称字典树、前缀树，是一种树形数据结构，常用于高效地存储和检索字符串集合。它的主要特点是利用字符串的公共前缀来减少存储空间和提高查询效率，特别适用于字符串的前缀匹配、自动补全、拼写检查等场景。
对于一棵字典树而言具有以下基本性质：
它是一棵多叉树，每个节点代表一个字符。根节点不包含字符，除根节点外的每个节点都包含一个字符。
从根节点到某一节点的路径上经过的字符连接起来，即为该节点对应的字符串。
每个节点可能有多个子节点，每个子节点对应一个不同的字符。
通常在表示字符串集合的Trie树中，会有一些特殊标记来表示某个节点是否是一个字符串的结尾。
下图是一颗字典树，在树中存储了这些单词：
app、apple、acc、acce、access、
back、backup、backed、be、bea、bear
ca、can、cancel、cancer、car、carbon、cause
基于字典树的特性，我们可以得知它是天然支持前缀匹配的，因为字典树可以适用于以下的场景：
字符串检索
可以高效地查找某个字符串是否存在于一个字符串集合中，时间复杂度为 ...
1. 跳跃表基本概念跳跃表（Skip List）是一种概率性数据结构，它就像是升级版的有序链表，专门用来实现有序集合的功能。它通过引入多层索引来提高查找、插入和删除操作的效率，使得这些操作的时间复杂度可以达到 O(logn)，其效率可以与平衡二叉搜索树相媲美。跳跃表的核心思想是通过随机化来维护多层索引，从而避免像平衡树那样复杂的平衡操作。
随机性决定节点层数：在跳跃表中，每个节点的层数是随机确定的。
当插入一个新节点时，算法会根据一个随机过程来决定该节点应该拥有多少层。通常，这个随机过程基于抛硬币的思想，比如抛一次硬币，正面则该节点的层数加 1，继续抛硬币，直到出现反面为止。这种随机性使得跳跃表在构建时不需要预先知道数据集的大小和分布，它会在动态插入和删除元素的过程中自动调整结构。
平均性能而非最坏性能保证：跳跃表通过随机化的方式来平衡其结构，从而在平均情况下达到较好的性能。
虽然在最坏情况下，跳跃表的性能可能会退化为普通链表的性能（例如所有节点的层数都为 1），但这种情况发生的概率非常低。它的平均时间复杂度为 O(logn)，这里的平均是基于随机算法的期望性能，而不是对所有 ...
