1 - 数据结构---数组(Array)
描述
数组是将 相同类型 元素存储于 连续内存空间 的数据结构, 其长度 不可变
// c++
int array[3]
array[0] = 1
array[1] = 2
array[2] = 3
2 - 数据结构---链表(List)
描述
链表以 节点 为单位，每个元素都是一个独立对象，在内存空间的存储是 非连续的。
struct ListNode {
int val; // 节点值
ListNode *next; // 后继节点引用
ListNode(int x) : val(x), next(NULL) {}
};
3 - 数据结构---栈
描述
栈是一种具有 先入后出 特点的抽象数据结构，可使用 数组 或 链表 实现。
5 - 数据结构---队列
描述
队列是一种具有 先入先出 特点的抽象数据结构，可使用 链表 实现。
6 - 数据结构---树(Tree)
树结构的常用表示方法
第一个儿子/下一兄弟的表示方法
struct TreeNode
{
Object element;
Treenode *firstchild
Treenode *nextSibling
}
树结构的基本操作
树结构的遍历
前序遍历
对节点的处理工作在其子节点被处理前执行
后续遍历
对节点的处理工作在其子节点被处理后执行
中序遍历
对节点的处理工作在其左节点之后, 右节点之前
应用
输出目录中所有文件的名字， 要求深度为 d 的文件名将被 d 次跳格（tab）缩进后打印其名
计算目录大小
6.1 - AVL树(Tree)
描述
AVL(Adelson-Velskii and Landis) 是带有 平衡条件(balance condition) 的 二叉查找树(BST),通过自动调整树的结构，AVL树可以确保查找、插入和删除操作的时间复杂度为 \(O(\log{n})\)。
用来衡量其"平衡程度"的标准是树中某个节点的左右子树的高度差
树的 高度 是指树中 层数 的总数。
平衡条件
AVL树中的每个节点的左右子树高度差（称为平衡因子）最多为1，(这样的约束确保了树的高度在\(O(\log{n})\)范围内)。即左右子树的高度差为 -1、0 或 1。否则，树需要通过旋转操作进行重新平衡。
树的旋转（为了保证平衡性）
- 左左(外-单)
- 左右(内-双)
- 右左(内-双)
- 右右(外-单)
单旋转
双旋转
6.2 - 查找树ADT---二叉查找树(Binary Search Tree)
描述
二叉查找树， 是二叉树在查找中的应用。 使二叉树变为二叉查找树的方法， 是增加一个性质： 对于树中的每个结点Node， 它的左子树中的所有项的值， 都小于X中的项， 而它的右子树中所有的项目的值大于 X 中的项。 其中(小于&大于)仅表达某种的排列规则在结点之间递归传递
二叉查找树的框架
template<typename Comparable>
class BinarySearchTree
{
public:
BinarySearchTree();
BinarySearchTree(const BinarySearchTree &node);
~BinarySearchTree();
const Comparable &findMin() const;
const Comparable &findMax() const;
bool contains(const Comparable &node) const;
bool isEmpty() const;
void printTree() const;
void makeEmpty();
void insert(const Comparable &node);
void remove(const Comparable &node);
const BinarySearchTree & operator=(const BinarySearchTree &rhs);
private:
struct BinaryNode
{
Comparable element;
BinaryNode *left;
BinaryNode *right;
BinaryNode(const Comparable &theelement, BinaryNode *lt, BinaryNode *rt): element(theelement), left(lt), right(rt)
}
BinaryNode *root;
// =========== recuris sub progress
void insert(const Comparable &node, BinaryNode *&t) const;
void remove(const Comparable &node, BinaryNode *&t) const;
BinaryNode *findMin(BinaryNode *t) const;
BinaryNode *findMax(BinaryNode *t) const;
bool contains(const Comparable &x, BinaryNode *&t) const;
void makeEmpty(BinaryNode *&t);
void printTree(BinaryNode *t) const;
BinaryNode *clone(BinaryNode *t) const;
}
随机生成二叉查找树
6.3 - 二叉树(Binary Tree)
描述
一颗每个结点的子节点不多于两个
实现
struct BNode
{
Object element; // The data in the node
BNode *left; // Left child
BNode *right; // Right child
}
应用
表达式树
表达树中的树叶是 操作数(operand)
其他的节点是 操作符(operator)
中缀表达式(infix expresion) / 中缀遍历(inorder traversal)
写一种算法将后缀表达式 转变为 表达式树
将 中缀表达式 转变为 后缀表达式 的算法
从两种常用类型的输入生成表达式树
6.4 - 平衡二叉查找树(Balanced Binary Search Tree)
描述
平衡二叉树（Balanced Binary Tree）是一种二叉树结构，其中任意节点的左右子树的高度差（通常称为平衡因子）不超过1。这种特性确保了树的高度接近于最小，使得在最坏情况下的查找、插入和删除操作的时间复杂度为O(log n)，其中n是树中节点的数量。
常见的平衡二叉树类型
AVL 树
- 在AVL树中，任意节点的左右子树高度差不超过1。
- 在插入或删除节点后，AVL树会通过旋转操作来重新平衡树结构。
- AVL树以其高度平衡的性质著称，查找效率非常高。
红黑树
- 红黑树是一种相对松散的平衡二叉树，它放宽了AVL树的平衡要求。
- 在红黑树中，树的每个节点都有一个颜色属性（红色或黑色），并且通过一系列的规则确保树大致平衡。
- 红黑树的查找、插入和删除操作时间复杂度同样为O(log n)，但是它在频繁插入和删除的情况下表现得比AVL树更好。
6.5 - 伸展树
描述
一种保证从空树开始任意连续M次对树的操作最多花费\(O(M\log{N})\)时间的树
不存在不好的输入序列
基本想法： 当一个 Node 被访问后， 就要经过一系列 AVL 树的旋转被推到根上
伸展(Splayling)
伸展的方法类似于旋转, 在旋转如何实施上增加一些选择的余地
之子形
一子形
伸展树的操作
7 - 数据结构---图
描述
图是由[节点(Node)]通过[边(Edge)]相连组成的集合，用以表示实体之间的关系。图可以用
来建模社交网络、计算机网络、交通网络等。图包
含[顶点（节点）]和[边（节点之间的连接）]。图可以是[有向的]也可以是[无向的]，并且
可以[包含环]或者是[无环的]。图的遍历算法包括[广度优先搜索]和[深度优先搜索]。
图的术语
- 顶点: 顶点
- 边：顶点之间的连接线称为边。
- 路径：从一个顶点到另一个顶点之间经过的所有顶点的描述
- 路径长度：路劲上对单元路线的计量。
- 环：起点和终点为同一个顶点的路径。
- 负权环：在「加权图」中，如果一个环的所有边的权重加起来为负数，我们就称之为
「负权环」。
- 连通性：两个不同顶点之间存在至少一条路径，则称这两个顶点是连通的。
- 顶点的度：「度」适用于无向图，指的是和该顶点相连接的所有边数称为顶点的度。
- 顶点的入度：「入度」适用于有向图，一个顶点的入度为 𝑑 d，则表示有 𝑑 d 条与
顶点相连的边指向该顶点。
- 顶点的出度：「出度」适用于有向图，它与「入度」相反。一个顶点的出度为 𝑑 d，
则表示有 𝑑 d 条与顶点相连的边以该顶点为起点。
图的分类
- 无向图: 边的两个节点是没有顺序关系的, A-B 和 B-A 是一条边
- 有向图: 边的两个节点是有顺序关系的, A->B 和 B->A 是不同的
- 加权图: 图中的每条边带有一个权重的参数
图的相关算法
- 并查集（ Union Find ）数据结构
- 「图」的深度优先搜索算法
- 「图」的广度优先搜索算法
- 最小生成树相关定理和算法
- 单源最短路径相关算法
- Dijkstra 算法
- Bellman-Ford 算法
- 拓扑排序之 Kahn 算法
7.1 - 图的表示方法
描述
邻接矩阵
用一个二维矩阵来存储两个节点之间的状态
缺点: 面对稀疏图时，有很多空间没有储存有效信息
- 确定邻接至或邻接于一个给定节点的集合需要用时 \(\Theta{(n)}\), 增加或删除一条
边仅需要 \(\Theta{(1)}\)
邻接链表
只考虑那些有连边的点对
对一个有 n 个点的图, 可以用 n 个链表, 第 i 个链表中存着从 i 直接连接的点
链式前向星表示的图
链式前向星（也称为邻接表的一种变种）是一种用于存储图的数据结构，它结合了数组和链表的优点，既节省空间又方便使用。在链式前向星中，每个节点的边不是直接存储在一个链表中，而是通过一个数组来存储所有边的信息，同时使用两个辅助数组来记录每条边的起点以及下一条边的位置。
7.2 - 图的深度优先搜索算法
描述
深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。
DFS 的基本思想是从一个初始节点开始，尽可能[深入地探索]其子节点，直到无法继续深入
为止，然后回溯到上一个节点，继续探索其他未访问过的分支。这种策略类似
于[树的先序遍历] 。
DFS 的基本步骤
- 选择一个其实节点: 选择图中的任意一个节点作为起始节点
- 标记节点为已访问: 将当前节点标记为已访问，避免重复访问
- 递归访问相邻节点: 对于当前节点的每一个未访问过的相邻节点，递归地执行 DFS
- 回溯: 当当前节点的所有相邻节点都被访问过之后，回溯到上一个节点，继续访问
其他未访问过的分支
7.3 - 图的广度优先搜索算法
描述
广度优先搜索（Breadth-First Search，简称 BFS）是一种用于遍历或搜索树或图的算法。
这种算法从根节点开始，然后遍历所有[相邻的]节点，之后对于每一个相邻的节点，再遍历
它们未访问过的相邻节点，依次类推，直到所有的节点都被访问过为止。BFS 是一种逐层扩
展节点的搜索策略，即先搜索离起始节点最近的所有节点，然后再搜索下一层的节点。
BFS 的基本步骤
- 初始化：选择一个起始节点，将其标记为已访问，并放入队列中。
- 处理队列中的节点：
- 从队列中移除第一个节点。
- 对于这个节点，访问它所有的邻接点。如果某个邻接点没有被访问过，则标记这个邻
接点为已访问，并将其添加到队列的末尾。
- loop[2]，直到队列为空。
在实际操作中，为了防止重复访问同一个节点，通常需要使用一个数据结构来记录已经访
问过的节点。此外，队列是实现 BFS 的关键数据结构，因为它是先进先出（FIFO）的数
据结构，能够确保节点按照其被发现的顺序被处理。
7.4 - 最小生成树
描述
生成树（Spanning Tree）是[图论]中的一个重要概念，尤其在处理连通图时非常有用。生
成树是指一个[无向图]的一个子图，它是一个包含图中所有顶点的树。也就是说，生成树是
一棵包含了原图中所有节点的[无环连通子图]
最小生成树
最小生成树（Minimum Spanning Tree, MST）是图论中的一个基本概念，特别是在处理加权
无向图时非常重要。给定一个加权无向图，最小生成树是指该图的一个生成树，其中所有边
的权重之和是最小的。这意味着，在保证所有节点连通的情况下，最小生成树选取的边的总
成本最低
8 - 数据结构---散列表(Hash Set)
概览
哈希表 是一种使用 哈希函数 组织数据, 以支持 快速插入和搜索 的数据结构
有两种不同类型的哈希表: 哈希集合 和 哈希映射
- 哈希集合 是 集合 的实现方式之一, 用于存储 非重复值
- 哈希映射 是 映射 的实现方式之一, 用于存储
(key, value) 键值对
哈希表的原理
哈希表(散列表): 借助 哈希函数, 将键映射到存储桶地址:
- 首先, 开辟一定长度的, 具有连续物理地址的
桶数组 - 在插入一个新键时,
哈希函数将决定该键应该分配到哪个桶中, 并将该键存储在相应的桶中 - 在搜索一个键时,
哈希表 将使用哈希函数来找到对应的桶, 并在该桶中进行搜索
什么是哈希函数
哈希函数会起到压缩键的地址空间的作用, 设键的地址空间为S, 桶的地址空间则为 T, 那么 S 远大于 T
- 哈希函数的结果(键)与桶的对应关系具有确定性
- 哈希函数不应该太过复杂
- 哈希函数的结果分布应具有均匀性
理想情况下, 完美的哈希函数是键与桶的一一对应, 但是完美的哈希函数并不常见, 一般来讲, 结果分布越随机, 越均匀的哈希函数, 它的性能越好, 一方面, 如果分布过于集中再某些桶中, 会加剧这些桶发生冲突的概率, 另一方面, 剩余的桶由于没有得到有效利用导致空间利用率较低
负载因子(装填因子)
是哈希表的一个重要参数，它反映了哈希表的装满程度; 假设一个公司的电话共有10个, 每个电话号码是 00000000 到 99999999 内的任意八位数字, 这里有一个方案: 将每个可能的电话号码作为一个桶, 使得电话好嘛与桶一一对应, 则一共需要 100000000 个桶; 其中 实际利用桶的个数 / 桶的总数 则为负载因子. 在这个例子中, 负载因子太小以至于接近于0, 这样的方案是不现实的. 一般情况下, 比较合理的负载因子是 0.7.
哪些因素会影响 哈希函数
哈希函数是导致冲突的原因之一，更进一步，如果我们增加桶的数量，再采用合适的哈希函数，可使发生冲突的可能性大大减小
哈希集合 和 哈希映射 之间的区别
如何正确使用 标准模板库 中的哈希集合及哈希映射
在哈希表中，插入 和 查找 操作的复杂度是多少？
如何使用 哈希集合 解决与重复元素相关的问题
如何使用 哈希映射 解决与滑动窗口相关的问题
如何在使用 哈希表 时设计正确的键
8.1 - 解决哈希冲突的一般方法
什么是哈希冲突
简单来说, 假设一个哈希函数是: \(y=x \ mod \ 5\), 那么又两个键 1987 和 2 得到的结果都是 2, 则称为 哈希冲突, 其与 哈希函数 有关
冲突的解决
线性试探法
线性试探法属于 开放定址法 的一种, 除此之外, 开放定址法还包括 二元探测法, 双重嘻哈希发等. 当插入键 key 时候, 如果发现桶单元 bucket[hash(key)] 已经被占用, 则向下线性寻找, 直到找到可以使用的空桶.
故而经过第 i 次试探后, 桶单元为:
$$
bucket[(hash(key)+i) \ mod \ M], \ i = 1, 2, 3, \cdots
$$
当 查找到某个 key 时, 首先通过哈希函数计算出桶的位置, 然后比较该桶中保存的值是否为该 key, 如果不是, 则继续向下寻找, 如果查到末尾, 则会从头开始查找
而删除某个 key 时, 为了避免查找过程中出现信息丢失, 则会将删除位置标记为 deleted, 这样, 当进行线性查找时, 遇到 deleted 会继续向下查找而不会中断
链地址法
解决冲突的另一种办法是将桶内产生冲突的 key 串成一个链表
再哈希法
再哈希法比较典型的应用是双重哈希法, 即发生冲突时, 通过使用另一个哈希函数来避免冲突, 在构造另一个哈希函数的时候, 需要具备一些约束条件才能避免再次冲突
双重哈希法中存在的问题有
- 与线性试探法比, 双重哈希法会消耗较多的时间
- 在双重哈希法中, 删除会使问题变得复杂, 如果逻辑删除数量太多, 则应重新构建哈希表
公共溢出区法
公共溢出区法就是建立另一个哈希表 dict_overflow 作为公共溢出区, 当发生冲突时, 则将该 key 保存在该 哈希表中
9.1 - 双指针
当只有一个输入, 从该输入的两端遍历
int fn(vector<int>& arr)
{
int left = 0; // left pointer index
int right = int(array.size()) - 1; // right pointer index
int ans = 0;
while(left < right)
{
if(true /* condition */)
{
// ...
left++;
}
else
{
// ...
right--;
}
}
return ans;
}
有两个输入, 两个都需要遍历
public int fn(int[] arr1, int[] arr2)
{
int i = 0; // pointer at arr1
int j = 0; // pointer at arr2
int ans = 0;
while(i < arr1.length && j < arr2.length)
{
if(true /* condition */){
// ...
i++;
}
else {
// ...
j++;
}
}
return ans;
}
滑动窗口
用指针决定运算的范围
int fn(vector<int> &arr)
{
int left = 0, right = 0, cur = 0;
while(left < right)
{
}
}