Algorithm

仓库介绍

leetcode 题解，记录自己的 leetcode 解题之路。

本仓库目前分为四个部分：

• 第一个部分是 算法刷题技巧和一些算法模板，掌握一些接替模板，可以快速帮助我们理解一个问题的接替方法。
• 第二部分是对于数据结构与算法的总结
• 第三部分是对刷过的提机型汇总。
• 第四部分是计划， 这里会记录将来要加入到以上三个部分内容

算法基础

1. 时间复杂度
2. 空间复杂度

基础数据结构

线性表

• 线性表
• 列表（必学）
• 链表（必学）
• 跳跃表（知道原理理，应⽤用，最后⾃自⼰己实现⼀一遍）
• 并查集（建议结合刷题学习）

不⽤用说，链表、列列表必须，不不过重点是链表。

栈与队列

• 栈（必学）
• 队列（必学）
• 优先队列、堆（必学）
• 多级反馈队列（原理理与应⽤用）

特别是优先队列，再刷题的时候，还是经常⽤用到的，队列列与栈，是最基本的数据结构，必学。可以通过博客来学习

哈希表（必学）

• 碰撞解决⽅方法：开放定址法、链地址法、再次哈希法、建⽴立公共溢出区（必学）
• 布隆隆过滤器器（原理理与应用）

树

• 二叉树：各种遍历（递归与⾮递归）（必学）
• 哈夫曼树与编码（原理理与应用）
• AVL树（必学）
• B 树与 B+ 树（原理理与应用）
• 前缀树（原理理与应用）
• 红⿊黑树（原理理与应用）
• 线段树（原理理与应用）
• 堆：最大堆 ／ 最小堆
• 树与图：最近公共祖先、并查集
• 字符串：前缀树（字典树） ／ 后缀树

树相关是知识还是挺多的，建议看书，可以看《算法第四版》。

数组

• 矩阵（必学）

算法概述

十大排序算法

• 简单排序：插入排序、选择排序、冒泡排序（必学）
• 分治排序：快速排序、归并排序（必学，快速排序还要关注中轴的选取⽅方式）
• 分配排序：桶排序、基数排序
• 树状排序：堆排序（必学）
• 其他：计数排序（必学）、希尔排序

图论算法

• 图的表示：邻接矩阵和邻接表
• 遍历算法：深度搜索和⼴广度搜索(必学)
• 最短路路径算法：Floyd，Dijkstra（必学）
• 最小⽣生成树算法：Prim，Kruskal（必学）
• 实际常⽤用算法：关键路路径、拓扑排序（原理与应用）
• ⼆分图匹配：配对、匈⽛牙利利算法（原理与应用）
• 拓展：中心性算法、社区发现算法（原理与应用）

搜索算法

• 回溯算法
• 递归算法
• 深度优先遍历(DFS)
• 广度优先遍历(BFS)
• 二叉搜索树

动态规划

• 树形DP：01背包问题
• 线性DP：最长公共子序列列、最长公共⼦子串
• 区间DP：矩阵最大值（和以及积）
• 数位DP：数字游戏
• 状态压缩DP：旅行商

字符匹配算法

• 正则表达式
• 模式匹配：KMP、Boyer-Moore

其他算法技巧

• 双指针
• 二分查找
• 滑动窗口
• 分治算法
• 贪心算法
• 前缀匹配树

---

在这一部分，我将会更新一些常用的算法技巧，掌握一些算法技巧不是偷懒，而是为了更好的刷题，更高效的去解答每一道题目，可以帮助我们迅速的去定位一些问题的解法，常用的一些技巧，比如：双指针，二分查找，滑动窗口，递归等等，并且还会借鉴网上的一些模板，形成自己的一套接替思路，希望可以帮到大家。

注：本人在学习算法阶段，笔记是参考博主labuladong,还是非常感谢这位大神的方法和技巧，让我受益匪浅，下面的笔记是参考这位博主的，加了一些自己的观点和代码补充。

---

排序算法

排序算法介绍 常用算法技巧

基于交换的排序

1. 冒泡排序
2. 快速排序

基于堆排序和快速选择排序的top算法比较

1. 两种算法比较
2. Top K问题解决方法

基于插入的排序

1. 插入排序
2. 希尔排序

基于选择的排序

1. 简单选择排序
2. 堆排序
3. 堆排序代码

归并排序

基数排序

剑指Offer

数据结构

涉及数组，字符串，链表，树，栈和队列等数据结构，这一部分主要是熟悉java语言中的各种集合的实现和方法，理解每一种数据结构的优点和缺点，使用情景等。

数组

数组：使用连续的内存，可以根据下表在o(1)时间内读取和写入任何元素，效率很高，但是在插入一个元素的时候，效率就很低。数组可以用来实现哈希表，把数组的下表作为哈希表的键值key，而元素就代表哈希表的值。

3. 剑指 Offer 03. 数组中重复的数字
4. 剑指 Offer 04. 二维数组中的查找
5. 剑指 Offer 05. 替换空格
6. 剑指 Offer 06. 从尾到头打印链表
7. 剑指 Offer 07. 重建二叉树
8. 剑指offer面试题8：二叉树的下一个节点
9. 剑指 Offer 09. 用两个栈实现队列

算法

递归和循环

如果我们在程序中需要重复的多次计算相同的问题，那么通常可以使用递归或者循环，但是往往递归算法的效率不如循环。

7. 剑指 Offer 10- I. 斐波那契数列
8. 322. 零钱兑换
9. 剑指 Offer 10- II. 青蛙跳台阶问题

查找和排序

• 顺序查找：元素无序时查找
• 二分查找：相对有序的数组中查找
• 哈希查找：o(1)时间内查找元素
• 二叉排序树：一种特殊的树结构

9. 剑指 Offer 11. 旋转数组的最小数字

回溯

10. 剑指 Offer 12. 矩阵中的路径
11. 一维数组和二维数组回溯问题

动态规划

11. 剑指 Offer 14- I. 剪绳子

位运算

12. 剑指 Offer 15. 二进制中1的个数
13. 位运算

代码的完整性

13. 高质量代码
14. 剑指 Offer 16. 数值的整数次方
15. 剑指 Offer 17. 打印从1到最大的n位数
16. 剑指 Offer 18. 删除链表的节点
17. 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

代码的鲁棒性(健壮性)

健壮性就是需要我们考虑不合法的输入，针对不合法的输入需要给出反馈，比如空指针，空字符串，索引越界怎么办。

18. 剑指 Offer 22. 链表中倒数第k个节点
19. 剑指 Offer 22. 合并两个有序链表
20. 剑指 Offer 22. 合并k个有序链表
21. 剑指 Offer 22. 判断量表中是否包含环
22. 剑指 Offer 22. 判断两个链表是否相交
23. 剑指 Offer 23. 链表中环的入口节点
24. 剑指 Offer 24. 反转链表
25. 剑指 Offer 25. 合并两个排序的链表
26. 剑指 Offer 26. 树的子结构
27. 剑指 Offer 27. 二叉树的镜像
28. 剑指 Offer 28. 对称的二叉树
29. 剑指 Offer 30. 包含min函数的栈
30. 剑指 Offer 31. 栈的压入、弹出序列
31. 剑指 Offer 32 - I. 从上到下打印二叉树
32. 剑指 Offer 32 - II. 从上到下打印二叉树 II
33. 剑指 Offer 32 - III. 从上到下打印二叉树 III
34. 剑指 Offer 33. 二叉搜索树的后序遍历序列
35. 剑指 Offer 34. 二叉树中和为某一值的路径
36. 剑指 Offer 35. 复杂链表的复制
37. 剑指 Offer 36. 二叉搜索树与双向链表
38. 剑指 Offer 37. 序列化二叉树
39. 剑指 Offer 38. 字符串的排列
40. 剑指 Offer 39. 数组中出现次数超过一半的数字
41. 剑指 Offer 40. 最小的k个数
42. 剑指 Offer 40. 最小的k个数1
43. Top问题解决方案
44. 剑指 Offer 42. 连续子数组的最大和
45. 剑指 Offer 45. 把数组排成最小的数
46. 剑指 Offer 46. 把数字翻译成字符串
47. 剑指 Offer 47. 礼物的最大价值
48. 剑指 Offer 48. 最长不含重复字符的子字符串
49. 剑指 Offer 49. 丑数
50. 剑指 Offer 50. 第一个只出现一次的字符
51. 剑指 Offer 51. 数组中的逆序对
52. 剑指 Offer 52. 两个链表的第一个公共节点
53. 剑指 Offer 56 - I. 数组中数字出现的次数
54. 剑指 Offer 56 - I. 数组中数字出现的次数
55. 剑指 Offer 53 - I. 在排序数组中查找数字 I
56. 剑指 Offer 53 - II. 0～n-1中缺失的数字
57. 剑指 Offer 54. 二叉搜索树的第k大节点
58. 剑指 Offer 55 - I. 二叉树的深度
59. 剑指 Offer 55 - II. 平衡二叉树
60. 剑指 Offer 56 - I. 数组中数字出现的次数
61. 剑指 Offer 57. 和为s的两个数字
62. 剑指 Offer 57 - II. 和为s的连续正数序列
63. 剑指 Offer 58 - I. 翻转单词顺序
64. 剑指 Offer 58 - II. 左旋转字符串
65. 剑指 Offer 59 - I. 滑动窗口的最大值
66. 剑指 Offer 59 - II. 队列的最大值
67. 剑指 Offer 61. 扑克牌中的顺子
68. 剑指 Offer 62. 圆圈中最后剩下的数字

---

Leetcode hot 100

1. 判断链表是否包含环
2. 两数相加
3. 1. 两数之和
4. 无重复字符的最长子串
5. 6.最长回文子串
6. 7. 整数反转
7. 8. 字符串转换整数 (atoi)
8. 9. 回文数
9. 11.盛最多水的容器
10. 12. 整数转罗马数字
11. 13. 罗马数字转整数
12. 14. 最长公共前缀
13. 15. 三数之和
14. 16. 最接近的三数之和
15. 7. 电话号码的字母组合
16. 19. 删除链表的倒数第 N 个结点
17. 20. 有效的括号
18. 22. 括号生成
19. 23. 合并K个升序链表
20. 24. 两两交换链表中的节点
21. 25. K 个一组翻转链表.md
22. 26. 删除有序数组中的重复项
23. 27. 移除元素
24. 31. 下一个排列
25. 33. 搜索旋转排序数组
26. 34. 在排序数组中查找元素的第一个和最后一个位置
27. 39. 组合总和
28. 40. 组合总和 II
29. 41. 缺失的第一个正数
30. 42. 接雨水
31. 45. 跳跃游戏 II
32. 46. 全排列
33. 47. 全排列 II
34. 48. 旋转图像
35. 50. Pow(x, n)
36. 55. 跳跃游戏
37. 56. 合并区间
38. 57. 插入区间
39. 60. 排列序列
40. 61. 旋转链表
41. 63. 不同路径 II
42. 64. 最小路径和
43. 69. x 的平方根
44. 72. 编辑距离
45. 75. 颜色分类
46. 76. 最小覆盖子串
47. 77. 组合
48. 79. 单词搜索
49. 80. 删除有序数组中的重复项 II
50. 81. 搜索旋转排序数组 II
51. 82. 删除排序链表中的重复元素 II
52. 83. 删除排序链表中的重复元素
53. 单调栈
54. 90. 子集 II
55. 92. 反转链表 II
56. 93. 复原 IP 地址
57. 96. 不同的二叉搜索树
58. 101. 对称二叉树
59. 105. 从前序与中序遍历序列构造二叉树
60. 114. 二叉树展开为链表
61. 121. 买卖股票的最佳时机
62. 124. 二叉树中的最大路径和
63. 128. 最长连续序列
64. 136. 只出现一次的数字
65. 141. 环形链表
66. 142. 环形链表 II
67. 146. LRU 缓存
68. 148. 排序链表
69. 152. 乘积最大子数组
70. 160. 相交链表
71. 169. 多数元素
72. 198. 打家劫舍
73. 200. 岛屿数量
74. 206. 反转链表
75. 215. 数组中的第K个最大元素
76. 221. 最大正方形
77. 226. 翻转二叉树
78. 234. 回文链表
79. 236. 二叉树的最近公共祖先
80. 238. 除自身以外数组的乘积
81. 239. 滑动窗口最大值
82. 240. 搜索二维矩阵 II
83. 279. 完全平方数
84. 283. 移动零
85. 287. 寻找重复数
86. 300. 最长递增子序列
87. 309. 最佳买卖股票时机含冷冻期
88. 714. 买卖股票的最佳时机含手续费
89. 338. 比特位计数
90. 347. 前 K 个高频元素
91. 416. 分割等和子集
92. 438. 找到字符串中所有字母异位词
93. 448. 找到所有数组中消失的数字
94. 461. 汉明距离
95. 494. 目标和
96. 538. 把二叉搜索树转换为累加树
97. 543. 二叉树的直径
98. 560. 和为 K 的子数组
99. 581. 最短无序连续子数组
100. 617. 合并二叉树
101. 647. 回文子串
102. 739. 每日温度

数据结构

---

栈与队列

1. 20. 有效的括号
2. 1047. 删除字符串中的所有相邻重复项
3. 剑指 Offer 59 - I. 滑动窗口的最大值
4. 347. 前 K 个高频元素

---

二叉树

1. 二叉树(一)
2. 二叉树(二)
3. 二叉树(三)
4. 二叉树的层次遍历
5. 二叉树的层平均值
6. N叉树的层次遍历
7. 二叉树非递归遍历
8. 404、二叉树左叶子之和
9. 513、找树左下角的值
10. 112、路径总和
11. 617、合并二叉树
12. 700、二叉搜索树中的搜索
13. 297、二叉树的序列化
14. 二叉搜索树(一)
15. 二叉搜索树(二)
16. 二叉搜索树(三)

基础算法

BFS

1. BFS(一)
2. BFS(二)
3. BFS和DFS
4. 判断有向图中是否有环
5. 199、二叉树的右视图
6. 116、填充每个节点的下一个右侧节点指针
7. 找每一层中的最大值
8. N叉树的层次遍历

DFS

1. 剑指 Offer 28. 对称的二叉树
2. 104. 二叉树的最大深度
3. 257. 二叉树的所有路径
4. 236. 二叉树的最近公共祖先
5. 226. 翻转二叉树
6. 222、完全二叉树节点个数
7. 判断是否是平衡二叉树
8. 最大键值和
9. 530、二叉搜索树的最小绝对差.md
10. 701、二叉搜索树中的插入
11. 450、二叉搜索树中的删除
12. 108.将有序数组转换为二叉搜索树

---

链表

1. 判断链表是否包含环
2. 递归反转整个链表
3. 148. 排序链表
4. 链表相交
5. 反转链表
6. 迭代反转链表
7. 回文链表
8. 奇偶链表
9. 链表题目

字符串

1. 字符串算法模板

2. 131. 分割回文串

3. 验证回文串

4. 有效的字母异位词

5. 字符串中的第一个唯一字符

---

数组

1. 只出现一次的数字
2. 多数元素
3. 搜索二维矩阵 II
4. 152. 乘积最大子数组
5. 189. 轮转数组
6. 存在重复元素
7. 移动零
8. 两个数组的交集 II

---

算法

---

滑动窗口

1. 滑动窗口框架
2. 3. 无重复字符的最长子串

---

动态规划

动态规划问题步骤

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

动态规划一定要记住的三个条件：重叠子问题，最优子结构，状态转移方程。

明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case。

1. 动态规划问题框架
2. 详解动态规划
3. 动态规划的两个问题
4. 剑指 Offer II 088. 爬楼梯的最少成本.md
5. 动态规划空间优化，机器人路径1
6. 63. 不同路径 II
7. 343. 整数拆分
8. 96. 不同的二叉搜索树
9. 0-1背包框架一
10. 0-1背包问题二
11. 416. 分割等和子集
12. 1049. 最后一块石头的重量 II
13. 494. 目标和
14. 完全背包
15. 518. 零钱兑换 II
16. 377. 组合总和 Ⅳ
17. 爬楼梯
18. 322. 零钱兑换
19. 279. 完全平方数
20. 背包问题
21. 198. 打家劫舍
22. 213. 打家劫舍 II
23. 121. 买卖股票的最佳时机
24. 122. 买卖股票的最佳时机 II
25. 300. 最长递增子序列
26. 674. 最长连续递增序列
27. 718. 最长重复子数组
28. 1143. 最长公共子序列
29. 1035. 不相交的线
30. 53. 最大子数组和
31. 392. 判断子序列
32. 115. 不同的子序列
33. 583. 两个字符串的删除操作
34. 72. 编辑距离
35. 647. 回文子串
36. 516. 最长回文子序列
37. DP26跳跃游戏(一)
38. 45. 跳跃游戏 II

注：动态规划篇很多参考labuladong的算法，只是为了记录笔记学习，没有其他任何商业用途。

---

子序列类问题

---

回溯法

1. 回溯法算法框架
2. 回溯法详解
3. 回溯法二
4. 回溯法三

子集和组合

1. 78.子集
2. 90.子集 II
3. 77. 组合
4. 39.组合总和
5. 40.组合总和 II
6. 216. 组合总和 III
7. 93. 复原 IP 地址

全排列

1. 46. 全排列
2. 47. 全排列 II
3. 剑指 Offer 38. 字符串的排列
4. 22. 括号生成
5. 17、电话号码的字母组合
6. 路径和问题

回溯搜索

1. 剑指 Offer 12. 矩阵中的路径
2. 回溯法整理
3. 代码整理

---

贪心算法

贪心算法一般分为如下四步：

1. 将问题分解为若干个子问题

2. 找出适合的贪心策略

3. 求解每一个子问题的最优解

4. 将局部最优解堆叠成全局最优解

5. 贪心算法一

6. [贪心算法二](https://github.com/justdoitMr/Algorithm/blob/main/Note/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95(%E4%BA%8C%EF%BC%89.md)

7. 视频拼接

8. 455. 分发饼干

9. 376. 摆动序列

10. 53. 最大子数组和

11. 122. 买卖股票的最佳时机 II

12. 55. 跳跃游戏

13. 45. 跳跃游戏 II

14. 1005. K 次取反后最大化的数组和

15. 135. 分发糖果

16. 860. 柠檬水找零

17. 452. 用最少数量的箭引爆气球

18. 435. 无重叠区间

19. 763. 划分字母区间

20. 56. 合并区间

21. 738. 单调递增的数字

---

二分法

1. 二分查找框架
2. 二分搜索二
3. [二分搜索三](https://github.com/justdoitMr/Algorithm/blob/main/Note/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE(%E4%B8%89%EF%BC%89.md)
4. 二分搜索四
5. 33. 搜索旋转排序数组

---

双指针

---

数据结构设计

1. LFU算法
2. LRU算法
3. 最大频率栈
4. 单调栈
5. 单调队列
6. 栈实现队列
7. 拓扑排序

---

笔记整理

1. 数据结构

2. 算法

---