HongdouHub/LeetCode

This repository is to record some leetcode's study experience.

LeetCode 刷题总结

This repository is to record some leetcode's study experience.

一、 总结

序号	题型	链接
1	509. 斐波那契数 322. 零钱兑换 - 最少的硬币个数 518. 零钱兑换 II - 硬币组合数	动态规划套路详解
2	17. 电话号码的字母组合 20. 有效的括号 22. 括号生成 37. 解数独 51. N皇后 52. N皇后 II 39. 组合总和 40. 组合总和 II 46. 全排列 47. 全排列 II 78. 子集 90. 子集 II	回溯算法解题套路框架 回溯算法框架实战：括号生成
3	17. 电话号码的字母组合 752. 打开转盘锁 773. 滑动谜题	BFS 算法框架套路详解
4	1011. 在D天内送达包裹的能力 222. 完全二叉树的节点个数 300. 最长上升子序列 875. 爱吃香蕉的珂珂	我写了首诗，让你闭着眼睛也能写对二分搜索
5	76. 最小覆盖子串 567. 字符串的排列 438. 找到字符串中所有字母异位词 3. 无重复字符的最长子串	我写了首诗，把所有滑动窗口问题变成了默写题
6	121. 买卖股票的最佳时机 122. 买卖股票的最佳时机 II 123. 买卖股票的最佳时机 III 188. 买卖股票的最佳时机 IV 309. 最佳买卖股票时机含冷冻期 714. 买卖股票的最佳时机含手续费	一个方法团灭 LeetCode 股票买卖问题
7	198. 打家劫舍 213. 打家劫舍II 337. 打家劫舍III	⼀个⽅法团灭 LeetCode 打家劫舍问题
8	1. 两数之和 167. 两数之和 II - 输⼊有序数组 170. 两数之和 III - 数据结构设计 15. 三数之和 18. 四数之和	一个方法从 2Sum 秒杀到 100Sum
9	887. 鸡蛋掉落	经典动态规划：高楼扔鸡蛋 动态规划（只解释官方题解方法一）（Java）
10	416. 分割等和子集	经典动态规划：子集 / 0-1背包问题 0 - 1背包问题：当前考虑的物品拿或者不拿
11	322. 零钱兑换 - 最少的硬币个数 518. 零钱兑换 II - 硬币组合数	经典动态规划：完全背包问题 动态规划（完全背包问题，有公式推导） 完全背包问题： 背包里的物品可以无限次选取
12	224. 基本计算器 227. 基本计算器II 772. 基本计算器III	拆解复杂问题：实现一个完整计算器
1	5. 最长回文子串 300. 最长上升子序列 516. 最长回文子序列 1143. 最长公共子序列 14. 最长公共前缀 53. 最大字序和	子序列问题通用思路| 最长回文子序列 动态规划之最长公共子序列（LCS）
2	130. 被围绕的区域 200. 岛屿数量 547. 朋友圈 990. 等式方程的可满足性	union-find （并查集）算法详解加应用
3	28. 实现 strStr()	KMP 算法详解
4	239. 滑动窗口最大值 503. 下一个更大元素II - 循环数组	单调队列解题详解
5	435. 无重叠区间	贪心算法之区间调度问题
6	877. 石子游戏	解决博弈问题的动态规划通用思路
7	416. 分割等和子集	0-1 背包问题变体之子集分割
8	42. 接雨水	图解接雨水：动态规划和双指针思路
9	204. 计数质数	如何高效判定、筛选素数
10	72. 编辑距离	编辑距离面试题详解
11	25. K 个一组翻转链表	递归思维：如何跳出细节？
12	354. 俄罗斯套娃信封问题	最长递增子序列扩展到二维而已
13	384. 打乱数组	洗牌算法深度详解
14	146. LRU缓存机制	LRU 策略详解和实现
15	43. 字符串相乘	高频面试系列：字符串乘法（优化竖式）

二、刷题记录

序号	题目序号	题目解法	复杂度
1	1. 两数之和	哈希表	时/空 - O(n) / O(n)
2	10. 正则表达式匹配 '.' 和 '*'	动态规划	时/空 - O(mn) / O(mn)
3	100. 相同的树	深度优先 广度优先	时/空 - O(n) / O(min(m,n)) 时/空 - O(n) / O(min(m,n))
4	1011. 在D天内送达包裹的能力	左右指针二分查找	时/空 - O(NlogN) / O(1)
5	111. 二叉树的最小深度	递归深度/广度优先	时/空 - O(n) / O(log(n))
6	1118. 一月有多少天	闰年判断：能400整除，能4但不能100整除	无
7	1143. 最长公共子序列	动态规划	时/空 - O(mn)
8	130. 被围绕的区域	递归深度 并查集	时/空 - O(n) / O(1) 时/空 - O(n) / O(n)
9	141. 环形链表	哈希表 快慢指针	时/空 - O(n) 时/空 - O(n) / O(1)
10	142. 环形链表II	哈希表 快慢指针	时/空 - O(n) 时/空 - O(n) / O(1)
11	146. LRU缓存机制	双向哈希链表（get / put）	操作 - O(1)
12	167. 两数之和 II - 输入有序数组	左右指针两边夹 二分查找	时/空 - O(N) / O(1) 时/空 - O(NlogN) / O(1)
13	170. 两数之和 III - 数据结构设计	哈希表法 左右指针两边夹	时间 add【O(1)】 find【O(n)】 空间 - O(n)
	170. 两数之和 III - 数据结构设计	左右指针二分查找	时间 add【O(1)】 find【O(n log(n))】 空间 - O(n)
14	198. 打家劫舍	动态规划 滚动窗口	时/空 - O(n) / O(n) 时/空 - O(n) / O(1)
15	20. 有效的括号	暴力循环	时/空 - O(n)
16	204. 计数质数	暴力求解 高效算法 - Sieve of Eratosthenes	时/空 - O(n^2) / O(1) 时/空 - O(N*logN)/ O(1)
17	213. 打家劫舍II	动态规划	时/空 - O(n)
18	22. 括号生成	递归深度/广度优先 回溯算法 动态规划	时/空 - O(n^2)
19	222. 完全二叉树的节点个数	暴力递归 递归算出深度，二分查找看节点是否存在	时/空 - O(n) / O(logn) 时/空 - O(log2n) / O(1)
20	224. 基本计算器	栈和反转字符串 通用解法	时/空 - O(n) 时/空 - O(n)
21	225. 用队列实现栈	单队列 Queue、Deque【LinkedList】 双队列 Queue【ArrayDeque】	时/空 -
22	227. 基本计算器II	通用解法	时/空 - O(n) 时/空 - O(n)
23	232. 用栈实现队列	双栈模拟
24	234. 回文链表	将值复制到数组中后用双指针法 反转后半部分链表	时/空 - O(n) / O(n) 时/空 - O(n) / O(1)
25	236. 二叉树的最近公共祖先	递归深度优先	时/空 - O(n) / O(log n)
26	239. 滑动窗口最大值	双端队列 + 单调队列 + 滑动窗口	时/空 - O(n) / O(n)
27	25. K个一组翻转链表	翻转部分链表	时/空 - O(n)
28	26. 删除排序数组中的重复项	暴力修改
29	28. 实现 strStr()	暴力求解	时/空 - O(mn)
30	292. Nim游戏	不能被4整除
31	3. 无重复字符的最长子串	哈希表	时/空 - O(n)
32	300. 最长上升子序列	动态规划 二分查找	时/空 - O(n^2) / O(n) 时/空 - O(N·logN) / O(n)
33	312. 戳气球	记忆化搜索 动态规划	时/空 - O(n^3) / O(n^2) 时/空 - O(n^3) / O(n^2)
34	319. 灯泡开关	1. 亮与否，跟操作次数有关 2. 操作次数就是该数的因数个数 3. 因数为奇数则亮灯 4. 奇数表明该位置是完全平方数 5. 计算有多少个完全平方数
35	322. 零钱兑换 - 最少的硬币个数	动态规划	时/空 - O(mn) / O(n)
36	337. 打家劫舍III	递归深度优先	时/空 - O(n) / O(logn)
37	34. 在排序数组中查找元素的第一个和最后一个位置	暴力左右指针两边夹 二分搜索 - 寻找左侧边界 二分搜索 - 寻找右侧边界	时/空 - O(n)
38	354. 俄罗斯套娃信封问题	1. 对宽度 w 进行升序排序 2. 对相同w的 高度 h 降序排序 3. 最长上升子序列求解	时/空 - O(n^2) / O(n)
39	355. 设计推特	1. 哈希表来存储用户的信息 2. 链表存储发送的推文 3. 优先队列（大顶堆）排序
40	37. 解数独	回溯算法
41	372. 超级次方	1. a[1,2,3,4] = (a[1,2,3]) ^ 10 · a ^ 4 2. (a * b) % p = (a % p * b % p) % p
42	382. 链表随机节点	1. Random.nextInt - 【0, n) 2. 以 1/i 的概率选择第i个元素
43	384. 打乱数组	1. 以 1/i 的概率选择第i个元素 2. Fisher-Yates 洗牌算法
44	392. 判断子序列	双指针	时/空 - O(n+m) / O(1)
45	398. 随机数索引	以 1/i 的概率选择第i个元素
46	416. 分割等和子集	1. 0-1背包问题 + 动态规划 2. 0-1背包问题 + 动态规划 + 滚动数组	时/空 - O(nc) / O(nc) 时/空 - O(nc) / O(c)
47	42. 接雨水	按列求解	时/空 - O(n) / O(n)
48	43. 字符串相乘	优化竖式，用一维数组存储结果集每一位	时/空 - O(mn) / O(m+n)
49	435. 无重叠区间	1. 先以end做升序排序 2. 贪心解法	时/空 - O(n) / O(1)
50	438. 找到字符串中所有字母异位词	滑动窗口	时/空 - O(mn) / O(1)
51	448. 找到所有数组中消失的数字	1. 哈希表 2. 原地修改【数值取负数】	时/空 - O(n) / O(n) 时/空 - O(n) / O(1)
52	45. 跳跃游戏 II	贪心算法	时/空 - O(n) / O(1)
53	450. 删除二叉搜索树中的节点	1. 二叉排序树 - 中序 - 升序结果 2. 前驱节点 3. 后继节点 4. 递归深度优先
54	452. 用最少数量的箭引爆气球	1. 先以end做升序排序 2. 贪心解法	时/空 - O(NlogN) / O(1)
55	46. 全排列	回溯算法 + 深度优先
56	496. 下一个更大元素I - 非循环数组	1. 双指针 2. 单调栈	时/空 - O(N^2 + M) / O(N) 时/空 - O(N + M) / O(N)
57	5. 最长回文子串	1. 暴力解法+双指针两边夹 2. 动态规划	时/空 - O(n^3) / O(1) 时/空 - O(n^2) / O(n^2)
58	503. 下一个更大元素II - 循环数组	1. 双倍数组，逆序遍历，push前赋值 2. 单调栈	时/空 - O(n) / O(n)
59	509. 斐波那契数	动态规划	时/空 - O(n) / O(n)
60	51. N皇后	回溯算法	时/空 - O(n!) / O(n)
	52. N皇后 II	回溯算法	时/空 - O(n!) / O(n)
61	516. 最长回文子序列	动态规划	时/空 - O(n^2) / O(n^2)
62	518. 零钱兑换 II - 硬币组合数	动态规划 + 完全背包问题 + 分类计数原理	时/空 - O(m · n^2) / O(m · n) 时/空 - O(n^2) / O(n)
63	53. 最大子序和	双层循环	时/空 - O(n!) / O(1)
64	55. 跳跃游戏	贪心算法 回溯算法	时/空 - O(n) / O(1) 时/空 - O(n!) / O(1)
65	56. 合并区间	排序 + 大小值指针	时/空 - O(nlogn) / O(n)
66	560. 和为K的子数组	枚举法 前缀和 + 哈希表优化	时/空 - O(n^2) / O(1) 时/空 - O(n) / O(n)
67	567. 字符串的排列	哈希表法 + 滑动窗口 数组法 + 滑动窗口	时/空 - O(mn) / O(1)
68	645. 错误的集合	排序法 哈希表法 额外数组法 额外空间法	时/空 - O(n · log n) / O(1) 时/空 - O(n) / O(n) 时/空 - O(n) / O(n) 时/空 - O(n) / O(1)
69	651. 四键键盘
70	700. 二叉搜索树中的搜索	深度优先遍历	时/空 - O(n) / O(1)
71	701. 二叉搜索树中的插入操作	深度优先遍历	时/空 - O(n) / O(1)
72	704. 二分查找	二分查找	时/空 - O(n) / O(1)
73	72. 编辑距离	动态规划	时/空 - O(mn) / O(mn)
74	733. 图像渲染	深度优先遍历	时/空 - O(n) / O(1)
75	752. 打开转盘锁	广度优先遍历	时/空 - O(N^2 · A^N + D) / O(A^N + D) A 表示数字的个数， N 表示状态的位数， D 表示死亡数字数组的大小
76	76. 最小覆盖子串	滑动窗口	时/空 - O(m + n) / O(m + n)
77	77. 组合	回溯算法	时/空 - O(n * k) / O(n)
78	772. 基本计算器III	通用解法	时/空 - O(n) 时/空 - O(n)
79	773. 滑动谜题	广度优先遍历	时/空 - O(N^2 · A^N + D) / O(A^N + D) A 表示数字的个数， N 表示状态的位数
80	78. 子集	回溯算法	时/空 - O(n!) / O(n)
81	83. 删除排序链表中的重复元素	哈希表法	时/空 - O(n) / O(n)
82	855. 考场就座	使用 TreeSet	时/空 - O(P) / O(n) seat() : 遍历整个有序集合 - O(P) leave() : 遍历树高 - O(logP)
83	875. 爱吃香蕉的珂珂	二分查找	时/空 - O(NlogN) / O(1)
84	877. 石子游戏	数学方式 动态规划 记忆化递归 + 相对分数	时/空 - O(1) / O(1) 时/空 - O(n ^ 2) / O(n ^ 2) 时/空 - O(NlogN) / O(1)
85	887. 鸡蛋掉落	递归 + 备忘录 + 二分法 动态规划 - 二分法求解	时/空 - O(n * k · log n) / O(n * k) 时/空 - O(n * k · log n) / O(n * k)
86	92. 反转链表 II	翻转链表	时/空 - O(n) / O(1)
87	969. 煎饼排序	查找最大的下标，放到数组末尾，递归从后向前	时/空 - O(n^2) / O(1)
88	98. 验证二叉搜索树	深度优先递归遍历 中序遍历	时/空 - O(nlog n) / O(1)
89	986. 区间列表的交集	大小值指针遍历	时/空 - O(m + n) / O(1)
90	990. 等式方程的可满足性	并查集	时/空 - O(n) / O(n)
91	121. 买卖股票的最佳时机
92	122. 买卖股票的最佳时机 II
93	123. 买卖股票的最佳时机 III
94	188. 买卖股票的最佳时机 IV
95	309. 最佳买卖股票时机含冷冻期
96	714. 买卖股票的最佳时机含手续费

序号	题目序号	题目解法	复杂度
97	2. 两数相加	暴力求解	时/空 - O(m+n) / O(1)
98	4. 寻找两个正序数组的中位数	归并排序 二分法查找 - 递归	时/空 - O(m+n) / O(m+n) 时/空 - O(log(m+n)) / O(1)
99	6. Z 字形变换	暴力Flag求解	时/空 - O(n) / O(n)
100	7. 整数反转	按位反转，注意数据溢出	时/空 - O(n) / O(1)
101	8. 字符串转换整数 (atoi)	暴力解法，注意数据溢出	时/空 - O(n) / O(1)
102	9. 回文数	暴力解法，左右指针两边夹，注意抹掉高位和地位的方式	时/空 - O(n) / O(1)
103	11. 盛最多水的容器	暴力解法，左右指针两边夹	时/空 - O(n) / O(1)
104	14. 最长公共前缀	暴力解法	时/空 - O(n) / O(1)
105	15. 三数之和	哈希表 排序后，双指针两边夹	时/空 - O(n^2) / O(n) 时/空 - O(n^2) / O(1)
106	16. 最接近的三数之和	排序后，双指针两边夹	时/空 - O(n^2) / O(1)
107	17. 电话号码的字母组合	广度优先遍历 回溯算法
108	18. 四数之和	排序后，左右指针两边夹	时/空 - O(n^3) / O(1)
109	19. 删除链表的倒数第N个节点	快慢指针	时/空 - O(n) / O(1)
110	21. 合并两个有序链表	归并排序 递归求解	时/空 - O(m+n) / O(m+n) 时/空 - O(m+n) / O(1)
111	23. 合并K个升序链表	分治-链表两两合并 优先级队列	时/空 - O(m+n) / O(m+n) 时/空 - O(nlogk) / O(1)
112	24. 两两交换链表中的节点	非递归解法 递归解法	时/空 - O(n) / O(1) 时/空 - O(n) / O(1)
113	27. 移除元素	拷贝覆盖	时/空 - O(n) / O(1)
114	29. 两数相除	负数累加计数，排除正数溢出问题
115	30. 串联所有单词的子串	哈希表	时/空 - O(mn) / O(mn)
116	39. 组合总和	回溯算法
117	40. 组合总和 II	回溯算法
118	47. 全排列 II	回溯算法，Deque（LinkedList）优化存取
119	62. 不同路径	动态规划	时/空 - O(n^2) / O(n^2)
120	63. 不同路径 II	动态规划，翻转二维数组，尾部开始遍历	时/空 - O(n^2) / O(n^2)
121	69. x 的平方根	二分搜索法 牛顿迭代法	时/空 - O(log n) / O(1)
122	70. 爬楼梯	递归斐波那契数列方法（带缓存） 动态规划	时/空 - O(n) / O(n) 时/空 - O(n) / O(n)
123	90. 子集 II	回溯算法
124	102. 二叉树的层序遍历	深度优先 广度优先	时/空 - O(n) / O(logn) 时/空 - O(n) / O(logn)
125	120. 三角形最小路径和	深度优先 动态规划	时/空 - O(2^(m*n)) / O(log n) 时/空 - O(mn) / O(n)
126	152. 乘积最大子数组	用零分割多段数组，每段数组通过负数个数求相乘最大值 动态规划	时/空 - O(n) / O(n) 时/空 - O(n) / O(1)
127	169. 多数元素	暴力求解 哈希表 先排序，后遍历，大于 n/2即可 分治求解	时/空 - O(n^2) / O(n) 时/空 - O(n) / O(n) 时/空 - O(nlog) / O(1) 时/空 - O(n) / O(n)
128	200. 岛屿数量	染色法（广度优先） 染色法（深度优先） 并查集	时/空 - O(n^2) / O(n) 时/空 - O(n^2) / O(1) 时/空 - O(n^2) / O(n)
129	206. 反转链表 - (单链表 / 双向链表)	一次遍历，存储"前一个、下一个（+临时）节点"	时/空 - O(n) / O(1)
130	208. 实现 Trie (前缀树 / 字典树)	字典树，用n叉树实现 注意：从A开始到z一共58个字符（26 * 2 + 6）	时/空 - O(n) / O(1)
131	212. 单词搜索 II	字典树 + 回溯算法	时/空 - O(n^n + m) / O(mn)
132	242. 有效的字母异位词	遍历一维数组	时/空 - O(n) / O(1)
133	338. 比特位计数	i & (i - 1) 可以去除二进制数中最小的1	时/空 - O(n) / O(1)
134	547. 朋友圈	并查集	时/空 - O(n^2) / O(n)
135	703. 数据流中的第 K 大元素	堆排序	时/空 - O(log n) / O(1)
136	144. 二叉树的前序遍历	深度优先遍历	时/空 - O(log n) / O(1)