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 String Table - 数据持久化

最长公共子串 的 LeetCode 解题笔记。

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

最长公共子序列 的 LeetCode 解题笔记。

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

最长无重复子串 的 LeetCode 解题笔记。

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. 由最小规模问题的解得

编辑距离 的 LeetCode 解题笔记。

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. 参考 - 排序算法稳定性\ 百度百科 - 堆排序 \- 维基百科，自由的百科全书

下一个排列 的 LeetCode 解题笔记。

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

全排列 的 LeetCode 解题笔记。

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

子集 的 LeetCode 解题笔记。

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

不同路径 的 LeetCode 解题笔记。

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

岛屿数量 的 LeetCode 解题笔记。

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

CAS 的基本语义、用途、ABA 问题和 CPU 原子指令实现。

最大正方形 的 LeetCode 解题笔记。

基于 CAS 的无锁队列历史实现记录，以及安全内存回收边界。

课程表问题：DFS 与 BFS 拓扑排序。

分割等和子集 的 LeetCode 解题笔记。

单词拆分：DFS 与 DFS + 记忆化。

完全平方数 的 LeetCode 解题笔记。

二维网格中的单词搜索，使用 DFS。

目标和 的 LeetCode 解题笔记。

最长公共子串题目记录。

组合总和 的 LeetCode 解题笔记。

设计 LRU 缓存结构：map + 双向链表，以及 Go / Java 实现。

零钱兑换 的 LeetCode 解题笔记。

最长公共子序列：递归、DFS + 记忆化和动态规划。

戳气球 的 LeetCode 解题笔记。

电话号码的字母组合：使用 DFS 枚举组合。

打家劫舍 的 LeetCode 解题笔记。

编辑距离：递归与递归 + 缓存。

最佳买卖股票时机含冷冻期 的 LeetCode 解题笔记。

字母异位词分组：暴力法与 hash。

最小路径和 的 LeetCode 解题笔记。

找到字符串中所有字母异位词：暴力与滑动窗口 + 统计。

最长递增子序列 的 LeetCode 解题笔记。

最长公共前缀：暴力与前缀树思路。

跳跃游戏 的 LeetCode 解题笔记。

乘积最大子数组 的 LeetCode 解题笔记。

判断字符串是否回文：翻转与双指针。

最大子序和 的 LeetCode 解题笔记。

反转字符串的 Go 实现。

缺失的第一个正数 的 LeetCode 解题笔记。

计算回文子串数量：暴力与中心扩展。

三数之和 的 LeetCode 解题笔记。

寻找重复数 的 LeetCode 解题笔记。

最长回文子串：暴力法与中心扩散法。

两数之和 的 LeetCode 解题笔记。

找到所有数组中消失的数字 的 LeetCode 解题笔记。

字符串形式的大数加法，从右往左相加并记录进位。

和为K的子数组 的 LeetCode 解题笔记。

最长连续序列 的 LeetCode 解题笔记。

使用栈解码 k[encoded_string] 形式的字符串。

使用栈标记匹配括号，再统计最长连续有效区间。

通过全排列枚举保留或删除字符，筛选最长的合法括号结果。

括号生成：全排列 + 栈，以及对左右括号进行剪枝。

判断括号序列是否合法：栈与字符串替换。

支持 . 和 * 的正则表达式匹配。

二分查找上界 的 LeetCode 解题笔记。

使用暴力 set 与滑动窗口求最长无重复子串。

在排序数组中查找元素的第一个和最后一个位置 的 LeetCode 解题笔记。

使用带权并查集计算变量之间的除法关系。

统计 0 到 num 的每个整数二进制表示中 1 的个数。

使用按位异或计算两个整数之间的汉明距离。

二分查找上界 的 LeetCode 解题笔记。

反转 32 位有符号整数的十进制数字并处理溢出。

在排序数组中查找元素的第一个和最后一个位置 的 LeetCode 解题笔记。

使用斐波那契递推计算爬楼梯的方法数。

在转动过的有序数组中寻找目标值 的 LeetCode 解题笔记。

在转动过的有序数组中寻找目标值 的 LeetCode 解题笔记。

将两个有序整数数组合并为一个有序数组。

寻找峰值 的 LeetCode 解题笔记。

使用排序或快速排序 partition 寻找数组中的第 K 大元素。

在升序整数数组中使用二分查找目标值。

寻找旋转排序数组中的最小值 的 LeetCode 解题笔记。

求平方根 的 LeetCode 解题笔记。

按顺时针螺旋顺序遍历矩阵。

在循环有序字符列表中寻找大于目标字母的最小字母。

接雨水 的 LeetCode 解题笔记。

盛最多水的容器 的 LeetCode 解题笔记。

先排序再按位置插入，重建由身高和前置人数描述的队列。

重新排列非负整数，使其拼接成最大的整数。

使用递归回溯生成字符串的所有排列，去重后按字典序排序。

使用频率统计与排序或最小堆寻找前 K 个高频元素。

使用计数 map 或候选抵消方法寻找数组中的多数元素。

使用计数或异或寻找数组中只出现一次的元素。

将数组中的零移动到末尾并保持非零元素的相对顺序。

通过左右乘积数组计算除自身以外数组元素的乘积。

使用快速排序、桶排序或移动零思路对 0、1、2 原地分类。

从右上角开始搜索行列均有序的二维矩阵。

使用斐波那契数列的迭代关系计算青蛙跳台阶的跳法数量。

通过递推公式和规律推导每次可跳任意级台阶时的跳法数量。

记录斐波那契数列的递归、缓存和动态规划三种实现。

通过逐位移位统计 32 位二进制表示中 1 的个数。

通过循环乘法计算浮点数的整数次方，并处理负指数。

逐个枚举整数并取模统计从 1 到 n 的十进制表示中数字 1 出现的次数。

乘积最大子数组 的 LeetCode 解题笔记。

使用 map 统计字符次数并保留输入顺序，查找字符流中第一个只出现一次的字符。

和为K的子数组 的 LeetCode 解题笔记。

记录字符串循环左移的切片拼接和三次翻转实现。

最大正方形 的 LeetCode 解题笔记。

排序后将大小王视为 0，利用非零牌之间的间隔判断五张牌能否组成顺子。

每日温度 的 LeetCode 解题笔记。

记录逐字符拼接和预分配空间两种将空格替换为 %20 的实现。

每日温度 的 LeetCode 解题笔记。

记录通过递归或栈按从尾到头顺序输出链表的方法。

滑动窗口最大值 的 LeetCode 解题笔记。

记录使用栈和三指针反转单链表的实现。

合并区间 的 LeetCode 解题笔记。

最小栈 的 LeetCode 解题笔记。

记录迭代和递归合并两个有序链表的实现。

排序 的 LeetCode 解题笔记。

记录数组、长度换算和快慢指针查找倒数第 k 个结点的方法。

寻找两个正序数组的中位数 的 LeetCode 解题笔记。

跳跃游戏 的 LeetCode 解题笔记。

记录通过原链表节点间插入副本节点来复制复杂链表的方法。

最短无序连续子数组 的 LeetCode 解题笔记。

记录 set 和快慢指针查找链表环入口结点的方法。

买卖股票的最佳时机 的 LeetCode 解题笔记。

记录通过链表长度差和双指针查找两个链表第一个公共结点的方法。

旋转图像 的 LeetCode 解题笔记。

记录通过计数或集合删除排序链表中所有重复结点的方法。

实现 Trie 前缀树的 LeetCode 解题笔记。

记录递归判断一个序列是否为二叉搜索树后序遍历结果的方法。

不同的二叉搜索树 的 LeetCode 解题笔记。

记录通过完整中序遍历或父指针关系查找二叉树中序后继结点的方法。

二叉树中序遍历的 LeetCode 解题笔记。

记录通过中序遍历或递归把二叉搜索树转换为排序双向链表的方法。

从前序与中序遍历序列构造二叉树的 LeetCode 解题笔记。

记录通过中序遍历查找二叉搜索树第 k 小结点，以及反向中序查找第 k 大结点的方法。

实现二叉树先序、中序和后序遍历的笔记。

记录通过递归取左右子树最大深度计算二叉树深度的方法。

把二叉搜索树转换为累加树的 LeetCode 解题笔记。

记录使用队列进行二叉树层序遍历并从上到下输出节点的方法。

验证二叉搜索树的 LeetCode 解题笔记。

记录通过递归比较左右子树镜像位置判断二叉树是否对称的方法。

二叉树展开为链表的 LeetCode 解题笔记。

记录通过比较左右子树高度差并递归检查子树判断平衡二叉树的方法。

二叉树最近公共祖先的 LeetCode 解题笔记。

记录通过递归、栈和队列交换左右子树生成二叉树镜像的方法。

二叉树直径的 LeetCode 解题笔记。

记录使用队列和行尾指针把二叉树按层打印为多行的方法。

在二叉树中寻找两个节点最近公共祖先的笔记。

记录在逐层打印二叉树的基础上交替反转行顺序实现之字形遍历的方法。

合并二叉树的 LeetCode 解题笔记。

记录通过先序递归匹配判断一棵二叉树是否为另一棵树子结构的方法。

对称二叉树的 LeetCode 解题笔记。

记录根据前序遍历和中序遍历递归重建二叉树的方法。

打家劫舍 III 的 LeetCode 解题笔记。

记录通过深度优先遍历、先序遍历和回溯查找二叉树中路径和的方法。

求根节点到叶节点数字之和的 LeetCode 解题笔记。

记录使用先序遍历，以及先序遍历与中序遍历组合序列化和反序列化二叉树的方法。

翻转二叉树的 LeetCode 解题笔记。

记录字符串转整数的字符解析和 atoi 实现。

路径总和3的 LeetCode 解题笔记。

记录通过字符串切分和两次翻转实现单词顺序反转的方法。

二叉树的最大深度的 LeetCode 解题笔记。

记录使用辅助最小值栈实现 O(1) 获取栈最小值的方法。

二叉树的最大路径和的 LeetCode 解题笔记。

记录通过辅助栈判断给定序列是否为合法弹出序列的方法。

二叉树的右视图的 LeetCode 解题笔记。

记录使用两个栈实现队列 Push、Pop、Peek 和 Empty 操作的方法。

二叉树的层序遍历的 LeetCode 解题笔记。

记录《剑指 Offer》“二维数组中的查找”的原始解题笔记。

二叉树的序列化与反序列化的 LeetCode 解题笔记。

记录《剑指 Offer》“和为S的两个数字”的原始解题笔记。

二叉树的锯齿形层序遍历的 LeetCode 解题笔记。

记录《剑指 Offer》“和为S的连续正数序列”的原始解题笔记。

两两交换链表中的节点的 LeetCode 解题笔记。

记录《剑指 Offer》“圆圈中最后剩下的数”的原始解题笔记。

反转链表 II的 LeetCode 解题笔记。

记录《剑指 Offer》“把数组排成最小的数”的原始解题笔记。

反转链表的 LeetCode 解题笔记。

记录《剑指 Offer》“数字在排序数组中出现的次数”的原始解题笔记。

链表中的节点每k个一组翻转的 LeetCode 解题笔记。

记录《剑指 Offer》“数组中出现次数超过一半的数字”的原始解题笔记。

两数相加的 LeetCode 解题笔记。

记录《剑指 Offer》“数组中只出现一次的数字”的原始解题笔记。

删除排序链表中的重复元素 II的 LeetCode 解题笔记。

记录《剑指 Offer》“数组中的逆序对”的原始解题笔记。

删除排序链表中的重复元素的 LeetCode 解题笔记。

记录《剑指 Offer》“数组中重复的数字”的原始解题笔记。

删除链表的倒数第n个节点的 LeetCode 解题笔记。

记录《剑指 Offer》“旋转数组的最小数字”的原始解题笔记。

回文链表的 LeetCode 解题笔记。

记录《剑指 Offer》“最小的K个数”的原始解题笔记。

回文链表的 LeetCode 解题笔记。

记录《剑指 Offer》“机器人的运动范围”的原始解题笔记。

环形链表的 LeetCode 解题笔记。

记录《剑指 Offer》“滑动窗口的最大值”的原始解题笔记。

环形链表2的 LeetCode 解题笔记。

记录《剑指 Offer》“调整数组顺序使奇数位于偶数前面”的原始解题笔记。

旋转链表的 LeetCode 解题笔记。

记录《剑指 Offer》“连续子数组的最大和”的原始解题笔记。

环形链表的 LeetCode 解题笔记。

环形链表2的 LeetCode 解题笔记。

相交链表的 LeetCode 解题笔记。

重排链表的 LeetCode 解题笔记。

分隔链表的 LeetCode 解题笔记。

合并k个已排序的链表的 LeetCode 解题笔记。

合并两个有序链表的 LeetCode 解题笔记。

奇偶链表的 LeetCode 解题笔记。

排序链表的 LeetCode 解题笔记。

相交链表的 LeetCode 解题笔记。