Algorithm

1. 数据结构 1.1. 数组 - array.md 1.2. 链表 - linkedlist.md 1.3. 栈 - stack.md 1.4. 队列 - queue.md 1.5. 堆 - heap.md 1.6. 树 - tree.md 1.7. 图 - graph.md 1.8. 哈希表 -

1. 是什么 - 可动态扩容的数组 2. 动态数组 2.1. 数据结构 - 存放数据的数组 - 已使用的长度 - 总长度 2.2. API 2.3. 实现 2.3.1. 测试 3. 刷题套路 3.1. 双指针 3.1.1. 同向 - - [0, i) 是处理好的数据， [i, j) 是处理过但不需要

1. 是什么 - K-V对 2. 二叉搜索树实现 2.1. 数据结构 - 二叉搜索树 2.2. API 2.3. 实现 2.3.1. 测试 3. 哈希表实现 3.1. hash函数的设计 - 原则 - 一致性：如果a==b，则hash（a）==hash（b） - 高效性：计算高效简便 - 均匀性：哈

1. 是什么 2. 数组 vs 链表 数组按照索引查找快，链表插入删除快 3. 单向链表 3.1. 数据结构 - 头节点 - 长度 3.2. API 3.3. 实现 3.3.1. 测试 4. 双向链表 4.1. 数据结构 - 头节点 - 尾节点 - 长度 4.2. API - 同单向链表 4.3.

1. 是什么 - 先进先出 2. 普通队列 2.1. 数据结构 - 动态数组或链表 2.2. API 2.3. 实现 2.3.1. 测试 3. 循环队列 3.1. 数据结构 - 存放数据的数组 - 已使用的长度 - 总长度 - 头节点下标位置 - 尾节点下标位置 3.2. API - 同队列 3.3

1. 是什么 - 无序、不重复的集合 1.1. 数据结构 - hashmap 1.2. API 1.3. 实现 1.3.1. 测试

1. 是什么 - 后进先出 1.1. 数据结构 - 动态数组或链表 1.2. API 2. 实现 2.1. 测试

1. 二叉树是什么 每个节点最多有两个子节点 2. 二叉树操作 2.1. 遍历 2.1.1. 先序遍历 先访问根节点，然后访问左子树，最后访问右子树 2.1.2. 中序遍历 先访问左子树，然后访问根节点，最后访问右子树 2.1.3. 后序遍历 先访问左子树，然后访问右子树，最后访问根节点 2.1.4

1. 红黑树是什么 - 一种平衡二叉查找树 - 满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值 - 满足5条特性即可保证平衡 - 节点 要么是Red，要么是Black - 根节点 是Black - 叶子节点 （外部节点以及空节点）都是Black - Red

1. 跳表是什么 - 跳表相当于普通的链表有两个区别 - 有上、下、左、右四个指针 - 多了层的概念 1.1. 举例 - 普通链表 - - 有效层数为2的跳表 - - 有效层数为4的跳表 - 1.2. 特点 - 随机的数据结构 - 最底层包含了整个跳表的所有元素 - 典型的空间换时间，增删查改效率为

1. 堆是什么 逻辑上看成一棵树，实际上是个数组。 - 位置关系 在数组起始位置为0的情形中： - 父节点i的左子节点在位置 2 i + 1 - 父节点i的右子节点在位置 2 i + 2 - 子节点i的父节点在位置 (i - 1) / 2 - 排序属性 - 最大堆：父节点的值 左右节点 - 最小堆：

1. BitMap是什么 - 又叫位图 - 把数据存放在一个以bit为单位的数据结构里，每位都只有0和1两个值。为0的时候，证明值不存在；为1的时候说明存在。 1.1. 举例 这个时候假如我们要存放2 4 6 8 9 10 17 19 21这些数字到我们的BitMap里，我们只需把对应的位设置为1就

1. 为什么需要BloomFilter 1.1. BloomFiler vs HashSet 一个网站有 20 亿 url 存在一个黑名单中，这个黑名单要怎么存？ 若此时随便输入一个 url，你如何快速判断该 url 是否在这个黑名单中？并且需在给定内存空间（比如：500M）内快速判断出 - 如果使

1. 图是什么 - 由边和顶点组成 2. 图分类 有方向 无方向 ------ --------- --------- 有权重 有向有权图 无向有权图 无权重 有向无权图 无向无权图 3. 图的表示 3.1. 邻接矩阵 - 用二维数组存储顶点之间的关系：两顶点相邻则为1，不相邻则为 0 - 3.2.

1. 是什么 - 一种树结构，区别在于是孩子指向父亲 2. 有什么用 - 解决连接问题（比路径问题更加简单） 3. 实现 3.1. API 3.2. Quick Find 3.2.1. 测试 3.3. Quick Union - 3.3.1. 测试 3.4. 基于size的优化 3.4.1. 测试

1. 是什么 - log-structured merge-tree - 一种数据结构，用于write-heavy的场景 2. 为什么LSM适合写多读少 - 利用了磁盘顺序写的速度快于磁盘随机写 3. 数据结构 3.1. SSTables - Sorted Strings Table - 数据持久化

1. 什么是ziplist - Redis底层的一种数据结构，用于实现list、zset > 2026 注：这是旧版 Redis 的实现背景；现代 Redis 已不再以 ziplist 作为这些结构的主要编码。 - 一段连续的内存空间 2. 为什么需要ziplist - 动态数组：由长度+元素列表组成。每个元素占用的空间大小相同，类型也是相同的 - - ziplist：也由长度+元素列表组成。不同之处在于 - 每个元素

1. B Tree是什么 - self-balance search tree中的一种 - 是个多叉查找树 - 2. 为什么需要B Tree 2.1. 背景 - 数据库查询的需求： - 根据某个值查找数据，比如 select from user where id=1234； - 根据区间值来查找某些

1. 什么是稀疏索引 - 首先他是个索引 - 索引.md - 其次他是稀疏的 - 稀疏索引和密集索引的区别在于是否为每个key都建立索引 2. 为什么需要稀疏索引 稀疏索引占用空间小 2.1. 稀疏索引 vs 密集索引 稀疏索引 密集索引 ------------------ -----------

1. 索引是什么 - 索引是一种把查找关键字和对应的数据记录关联起来（可以看作key-value对）的数据结构 - 索引查找是通过索引来查找数据 2. 为什么需要索引 - 用来加速数据的查找 3. 稀疏索引 vs 稠密索引 - 稀疏索引.md 4. 正排索引 vs 倒排索引 - 倒排索引.md 5.

1. 正排索引 文档Id- 文档 ，比如MySQL 1.1. 如何查找包含关键词的文档 1. 需要遍历所有文档 【O(N)】 2. 逐字逐字匹配 【O(m+n)】 2. 倒排索引 关键词- 文档Id + 文档Id- 文档 ，比如ES 先把文档分词，然后记录分词以及对应文档Id的映射，同时记录文档ID

1. 是什么 缓存能提高查找效率，但是缓存空间是有限的，需要把用不到的数据淘汰出缓存 2. 分类 2.1. FIFO 2.1.1. 是什么 First In First Out：优先淘汰最早进入被缓存的数据 2.1.2. 实现 队列即可 2.2. LRU 2.2.1. 是什么 Least Recen

1. 动态规划步骤 1. 递归+记忆化- 递推 2. 状态的定义： opt[n],dp[n],fib[n] 3. 状态转移方程： opt[n]=best of(opt[n-1], opt[n-2], ...) 4. 最优子结构 2. 例子 2.1. 路径数目计算 - 递归 - - 递推 - -

1. 是什么 - 每一步都采取当前状态下的最优选择（局部最优解），从而希望推导出全局最优解 2. 举例 2.1. 最优装载 2.1.1. 思路 - 每次都选择重量最小的装上船 2.1.2. 实现 2.1.2.1. 测试 2.2. 零钱兑换 - 假设有 25 分、10 分、5 分、1 分的硬币，现要找

1. 是什么 - 将原问题分解成若干个规模较小的子问题（子问题和原问题的结构一样，只是规模不一样） - 子问题又不断分解成规模更小的子问题，直到不能再分解（直到可以轻易计算出子问题的解） - 利用子问题的解推导出原问题的解 1.1. 递归 - 分治适合用递归实现，复杂度分析使用主定理 - - 递归.

1. 递归是什么 - 函数自己调用自己 2. 递归的调用过程 - 以求和函数为例 - 测试 - 过程分析 3. 递归基本思想 1. 拆解问题 1. 把规模大的问题拆成规模较小的问题 2. 规模较小的问题拆成规模更小的问题 3. 规模小到一定程度可以直接得出答案 2. 求解 1. 由最小规模问题的解得

1. 回溯是什么 - 每一步都选择一条路出发，能进则进，不能进则退回上一步（回溯），换一条路再试 2. 八皇后问题 - 2.1. 思路 - 暴力法 - 从 64 个格子中选出任意 8 个格子摆放皇后，检查每一种摆法的可行性 - 一共有 种摆法 - 每一行只能放一个皇后，那么只有 种摆法 - 回溯+剪

1. DFS是什么 - 深度优先搜索，适用于字符串、数组、树，经常配合回溯.md使用 2. 字符串 2.1. 全排列 - 输入一个字符串，输出它的全排列 - 分析：使用树 - 2.1.1. 经典做法 2.1.2. 升级版 2.2. 组合 - 子集.md 3. 数组 3.1. 组合总和 - 组合总和.

1. 二分查找 在已排序的数组中，取中间值【middle】跟查找值【target】比较 - target = middle，那么就返回middle的位置 - target < middle的话，那么在数组左半部分继续查找 - target middle的话，那么在数组右半部分继续查找 2. 实现 2

1. 冒泡排序 有序的数组是不存在逆序对的，非有序的则存在逆序对，只需要把逆序对交换一下即可 - 多趟扫描 - 每趟相邻项比较，如果是逆序对那么交换位置 2. 特点 - 稳定性：稳定 - 时间复杂度：O（n²） - 空间复杂度：O（1） 3. 实现 3.1. 测试 4. 优化 - 如果某一趟中没有一

1. 线性查找 2. 实现 2.1. 测试

1. 堆排序 heap.md 建堆+删除 2. 特点 - 稳定性：不稳定 - 时间：O（nlogn） - 空间：O（1） 3. 实现 3.1. 测试 4. 参考 - 排序算法稳定性\ 百度百科 - 堆排序 \- 维基百科，自由的百科全书

1. 归并排序 采用了分而治之的思想，就是说把一个大的问题分成小的问题，然后递归求解 不停地把数组拆成两半，直到有序（只有一个节点），最后进行合并 如果说快速排序的关键在于分，那么归并排序的关键在于合 2. 特点 - 稳定性：稳定 - 原地排序：不是 - 复杂度 - 时间：O（nlogn） - -

1. 插入排序 把数组分成有序和无序的部分，从无序部分取出每一个元素插入到已排好序的数组中 在数组相对有序的情况下效率比选择排序高，时间复杂度O（N） 2. 特点 - 稳定性：稳定 - 原地排序 - 空间复杂度：O（1） - 时间复杂度：O（n²） 3. 过程 4. 实现 4.1. 测试 5. 参考

1. 快速排序 采用了分而治之的思想，就是说把一个大的问题分成小的问题，然后递归求解 快速排序想选取一个pivot，比他小的移动到左边，比他大的移动到右边， 对左边的小数组和右边的小数组做同样的处理 如果说归并排序的关键在于合并，那么快速排序的关键在于拆分 2. 效率 - 稳定性：不稳定 - 原地排

1. 选择排序 遍历的时候寻找最大的值，完成遍历后把他放在合适的位置。 相对于冒泡排序来说减少了交换的次数 2. 特点 - 稳定性：不稳定 - 原地排序 - 时间复杂度：O（n²） - 空间复杂度：O（1） 3. 过程 4. 实现 4.1. 测试 5. 参考 - 排序算法稳定性\ 百度百科

1. 常见排序算法 1.1. 冒泡排序 - 冒泡排序.md 1.2. 选择排序 - 选择排序.md 1.3. 插入排序 - 插入排序.md 1.4. 归并排序 - 归并排序.md 1.5. 快速排序 - 快速排序.md 1.6. 堆排序 - 堆排序.md 2. 排序对比 时间复杂度 空间复杂度 是否