Leetcode刷题记录

记录一下自己的刷题思路，题目来源很杂，不只leetcode，还有别的地方(Codeforces/UVA)的，但是大部分是leetcode。

Tips

• 序号用下划线加粗的题目是用来复习某个特定算法的极佳例子。（如53:回朔算法/109:LRU算法/149:排序算法）
• 题目思路在代码注释里，方便阅读理解。

Contact

咨询问题可以联系邮箱或者知乎私信，每天都会看。

• 邮箱：astzls213@163.com/astzls213@gmail.com

• 知乎ID：甄洛生

目录

	题目	类型	代码	难度	备注
1	4. 寻找两个正序数组的中位数	二分查找	C	**	百度一面
2	546. 移除盒子	动态规划	C	***
3	面试题 02.01 移除重复节点	益智	C++	*
4	ACM 洪水	益智	C	***	很好玩的一题，抽象思维
5	26. 删除排序数组中的重复项	数组	Python	*
6	29. 两数相除	益智	C;Go	**	记住logN解法
7	31. 下一个排列	数组	Python / C++	***	用右边交换左边的数，使得增量足够小
8	33. 搜索旋转排序数组	二分查找	C	*
9	2. 两数相加	链表	C	*
10	36. 有效的数独	哈希表	Python	*
11	101. 对称二叉树	树	C	*
12	50. Pow(x, n)	二分查找	C	*
13	62. 不同路径	动态规划	C	*
14	74. 搜索二维矩阵	双指针	Python	*
15	1. 两数之和	数组	Go / C++	*
16	3. 无重复字符的最长子串	字符串	Go	**	很好玩的一题
17	5. 最长回文子串	动态规划	Go / C++	**	这题的O(n)解法有点难
18	6. Z 字形变换	益智	Go	*	找规律题
19	7. 整数反转	数学	Go	*
20	9. 回文数	数学	Go	*
21	10. 正则表达式匹配	动态规划	Go	***	状态方程有点难想到
22	11. 盛最多水的容器	双指针	Go	*	双指针经典题
23	12. 整数转罗马数字	数学	Go	*	很无聊的题..
24	14. 最长公共前缀	字符串	Go	*	暴力就完事了
25	15. 三数之和	双指针	Go	**	如何避免重复答案很重要
26	16. 最接近的三数之和	双指针	Go	*	比三数之和简单
27	17. 电话号码的字母组合	DFS	Go	*	好久没写DFS，有点生疏
28	18. 四数之和	双指针	Go	*	三数之和变形题
29	19. 删除链表的倒数第 N 个结点	链表	Go	*
30	20. 有效的括号	栈	Go	*
31	21. 合并两个有序链表	链表	Go	*	O(1)空间复杂度要学会
32	22. 括号生成	回朔	Go	**	回朔算法很适合这题
33	23. 合并K个升序链表	堆	Go/Java	*	构造数组+排序+构造链表
34	24. 两两交换链表中的节点	递归	Go	*	往递归想就简单了
35	25. K 个一组翻转链表	链表	Go	***	此题难在设计
36	27. 移除元素	数组	Go	*	假移除真交换
37	28. 实现 strStr()	字符串	Go	*	哈希法判断字符串相等有点意思
38	30. 串联所有单词的子串	字符串	Go	**	词频+滑动窗口
39	32. 最长有效括号	动态规划/栈	Go	***	看了题解才会，草
40	34. 在排序数组中查找元素的第一个和最后一个位置	二分查找	Go	*
41	35. 搜索插入位置	二分查找	Go	*	二分查找变形题
42	37. 解数独	回朔算法	Go / C++	**	代码写的不够快还是
43	38. 外观数列	递归	Go	*	无聊
44	39. 组合总和	回朔算法	Go	*
45	40. 组合总和 II	回朔算法	Go	*	044的变形题
46	41. 缺失的第一个正数	原地哈希	Go	***	O(n)算法有点难想 操
47	Shopee 笔试题1.有效的括号字符串	回朔算法	Go	**
48	42. 接雨水	双指针	Go	***	又是看题解的一天
49	43. 字符串相乘	数学	Go	***	NMSL
50	415. 字符串相加	字符串	Go	*
51	44. 通配符匹配	动态规划	Go	**	NMSL
52	45. 跳跃游戏 II	贪心算法	Go	*	So easy
53	46. 全排列	回朔算法	Go / C++	**	减少空间复杂度值得思考
54	47. 全排列 II	回朔算法	Go / C++	*	避免重复答案
55	48. 旋转图像	益智	Go	***	没想到O(1)空间复杂度解法
56	49. 字母异位词分组	字符串	Go	**	词频+哈希表
57	51. N 皇后	回朔算法	Go	*
58	52. N皇后 II	回朔算法	Go	*
59	53. 最大子序和	动态规划/分治	Go /Java	*	注意分治法！
60	54. 螺旋矩阵	代码设计	Go	**	妙在标记已读数字解决边界问题
61	55. 跳跃游戏	贪心算法	Go	*
62	56. 合并区间	益智	Go	*
63	78. 子集	回朔算法	Go	*
64	57. 插入区间	益智	Go	*
65	58. 最后一个单词的长度	字符串	Go	*	XSWL
66	59. 螺旋矩阵 II	代码设计	Go	*	格局小了
67	60. 排列序列	数学	Go	**	找出规律即可
68	61. 旋转链表	链表	Go	*
69	63. 不同路径 II	动态规划	Go	*	注意滚动数组思想
70	64. 最小路径和	动态规划	Go / C++	*	滚动数组/拓展: 输出最优路径
71	65. 有效数字	有穷自动机	Go	***	编译原理的有穷自动机模型
72	66. 加一	数组	Go	*
73	67. 二进制求和	字符串	Go	*
74	69. x 的平方根	二分查找	Go	*
75	70. 爬楼梯	动态规划	Go	*
76	71. 简化路径	字符串	Go	**	分割+状态机
77	72. 编辑距离	动态规划	Go	***	又是看题解的一天
78	73. 矩阵置零	益智	Go	*	注意O(1)空间复杂度的解法
79	75. 颜色分类	数组	Go	*
80	76. 最小覆盖子串	双指针	Go	***	词频+滑动窗口
81	77. 组合	回朔算法	Go	*
82	79. 单词搜索	回朔算法	Go /Java	**
83	80. 删除排序数组中的重复项 II	双指针	Go	***	O(n) O(1)难想到
84	81. 搜索旋转排序数组 II	DFS	Go	*	这个有重复元素
85	82. 删除排序链表中的重复元素 II	双指针	Go	*
86	83. 删除排序链表中的重复元素	双指针	Go	*
87	84. 柱状图中最大的矩形	单调栈	Go	***	学到了学到了
88	85. 最大矩形	单调栈	Go	***	上一题的变形题
89	86. 分隔链表	双指针	Go	*
90	88. 合并两个有序数组	双指针	Go	*
91	89. 格雷编码	数学	Go	*	找规律题
92	90. 子集 II	回朔算法	Go	*	三数之和避免重复解
93	91. 解码方法	动态规划	Go	*
94	92. 反转链表 II	链表	Go	*	难在设计
95	94. 二叉树的中序遍历	二叉树	Go	*
96	95. 不同的二叉搜索树 II	递归	Go	***	又是看题解的一天
97	96. 不同的二叉搜索树	动态规划	Go	*	卡特兰数列有点东西
98	98. 验证二叉搜索树	二叉树	Go	*	BST中序遍历的性质
99	97. 交错字符串	动态规划	Go	*
100	99. 恢复二叉搜索树	二叉树	Go	*	利用BST中序遍历的性质
101	100. 相同的树	二叉树	Go	*	还是中序遍历或递归
102	102. 二叉树的层序遍历	BFS	Go	*
103	103. 二叉树的锯齿形层序遍历	BFS	Go	*
104	104. 二叉树的最大深度	递归	Go	*
105	105. 从前序与中序遍历序列构造二叉树	递归	Go	*	先序遍历中序遍历性质
106	106. 从中序与后序遍历序列构造二叉树	递归	Go	*
107	107. 二叉树的层序遍历 II	BFS	Go	*
108	108. 将有序数组转换为二叉搜索树	递归	Go	*	中序遍历性质
109	146. LRU 缓存机制	设计	Go / C++	**	哈希表+双向链表
110	134. 加油站	贪心算法	Go	*
111	109. 有序链表转换二叉搜索树	链表	Go	*	list->array->tree
112	110. 平衡二叉树	递归	Go / Java	*
113	111. 二叉树的最小深度	递归	Go	*
114	112. 路径总和	回朔算法	Go	*
115	113. 路径总和 II	回朔算法	Go	**
116	152. 乘积最大子数组	动态规划	Go / C++	***	又是看题解的一天
117	189. 旋转数组	数组	Go	*	翻转法有意思
118	114. 二叉树展开为链表	二叉树	Go	**	思路有却写不出代码草
119	121. 买卖股票的最佳时机	益智	Go / C++	*
120	124. 二叉树中的最大路径和	递归	Go / C++	****	这谁想到得到啊草
121	128. 最长连续序列	哈希表	Go	***	又是哈希表记录数字出现情况
122	136. 只出现一次的数字	数学	Go	*	异或运算的妙用
123	141. 环形链表	链表	Go / C++	*	快慢指针很秀
124	139. 单词拆分	动态规划	Go /Java	***	哈希表+转移方程有点难想
125	142. 环形链表 II	双指针/数学	Go / C++	***	O(1)空间复杂度解法难想
126	148. 排序链表	排序	Go	****	迭代版归并排序代码难写
127	155. 最小栈	栈/设计	Go	*	双栈即可
128	198. 打家劫舍	动态规划	Go	*
129	200. 岛屿数量	DFS/BFS	Go	***	没想到cnm
130	239. 滑动窗口最大值	堆/双端队列	Go / C++	***	队列是我没想到的
131	221. 最大正方形	动态规划	Go	***	有时dp保存的不是答案
132	739. 每日温度	单调栈	Go	*	单调栈用于找左边/右边第一个小于/大于当前位置数的位置
133	279. 完全平方数	动态规划	Go	*
134	122. 买卖股票的最佳时机 II	贪心算法	Go / C++	*
135	668. 乘法表中第k小的数	二分查找	Go	****	二分查找还能这样用@_@
136	378. 有序矩阵中第 K 小的元素	二分查找	Go	**	135变形题
137	125. 验证回文串	双指针	Go	*
138	343. 整数拆分	动态规划	Go / C++	***	O(n)的动态规划难证明
139	322. 零钱兑换	动态规划	Go / C++	**	贪心可用仅当零钱面值为常数c的幂
140	199. 二叉树的右视图	BFS	Go / C++	*
141	字节笔试C题. 从0至N的最小代价	动态规划	Go	***	NMSL
142	百度笔试A题. 牛牛最小的进食次数	贪心算法	Go	**	发现了Go的一个坑/题目简介in注释
143	153. 寻找旋转排序数组中的最小值	二分搜索	Go	*
144	470. 用 Rand7() 实现 Rand10()	随机算法	Go	**	又是看题解的一天
145	剑指 Offer 43. 1～n 整数中 1 出现的次数	数学	Go / C++	***	NMSL
146	300. 最长递增子序列	动态规划	Go	***	dp[i]指以i为子序列最后元素的最长长度
147	206. 反转链表	链表	Go	*	三指针反转，头节点很重要
148	598. 范围求和 II	益智	Go	*
149	912. 排序数组	排序	Go	*	要求做到面试手撕代码
150	264. 丑数 II	动态规划	Go	***	提前批字节商业化三面原题
151	华为机试A题. 球队积分排行	排序	Go	*
152	华为机试B题. 最小员工数目	益智	Python	**	输入是真的蛋疼
153	华为机试C题. 最小移动步数	动态规划	Go	***	通过95%cases，最后超时了
154	154. 寻找旋转排序数组中的最小值 II	二分查找	Go	**	注意不能用low和mid比较
155	腾讯笔试B题. 消除数字	栈	Go	*	考场PTSD了 以为是动态规划
156	腾讯笔试C题. 过钢索	动态规划	Go	***	转移方程有点难想
157	215. 数组中的第K个最大元素	排序	C	*	代码写的不够熟练
158	Shortest Path with Obstacle	数学	Go	*	回归刷题day1
159	Alphabetical Strings	益智	Go	*	思路简单，关注怎么实现
160	680. 验证回文字符串 Ⅱ	双指针/递归	Go	*
161	Kefa and First Steps	益智	C	*	Go会TLE，草
162	美团2021第一场B	浮点数	Go	*
163	美团2021第一场C	贪心	Go	*
164	美团2021第一场A	益智	Go	**	找到规律就很简单
165	美团2022第一场C	二分插入/堆	Java / C++	**	TreeSet yyds
166	169. 多数元素	投票算法	Java	**	好巧妙的算法
167	1555C - Coin Rows	动态规划	C++	1300
168	492B - Vanya and Lanterns	益智	C++	1200
169	1553D - Backspace	贪心	Java	1500
170	1368B - Codeforces Subsequences	数学	C++	1500	直接打表 秀死你
171	阿里2022-08-13 A	动态规划	Java	*	特点在于大数
172	米哈哟2022-08-15 A	栈	Java	*
173	米哈哟2022-08-15 B	贪心	Java	**
174	235. 二叉搜索树的最近公共祖先	递归	C++	*
175	236. 二叉树的最近公共祖先	递归	C++	**
176	1555D - Say No to Palindromes	动态规划	C++	1600	很巧妙的题
177	377A - Maze	DFS	C++	1600	逆向思维 找连通空闲点
178	1344A - Hilbert's Hotel	数论	C++	1600	多模拟找规律
179	371C - Hamburgers	二分查找	C++	1600	以后大数题还是用Java好
180	129. 求根节点到叶节点数字之和	二叉树	C++	*
181	706C - Hard problem	动态规划	C++	1600	dp[i][0/1]表示第i个字符串不反转/反转的最小排序代价，同时还要注意溢出问题。
182	1526B - I Hate 1111	数学	C++	1400	问题等价于x == 11a + 111b?(a, b为整数)
183	网易2021笔试-C++开发工程师（提前批）A	递归	C++	***	暴力可AC
184	网易2021笔试-C++开发工程师（提前批）D	图论	C++	**	tarjan算法入门题
185	505B - Mr. Kitayuta's Colorful Graph	DFS/并查集	C++	1400	暴力DFS或并查集
186	01字符串中01出现次数相同最长子串	暴力/哨兵	C++	***	O(n)时间复杂度巧妙
187	2022届网易秋季校园招聘-通用技术A卷 A	暴力	C++	*
188	2022届网易秋季校园招聘-通用技术A卷 B	模拟	C++	*
189	2022届网易秋季校园招聘-通用技术A卷 C	益智	C++	**	分配糖果变形题
190	2022届网易秋季校园招聘-通用技术A卷 D	DFS	Java	*	注意起始位置为障碍物也可以这种情形
191	123. 买卖股票的最佳时机 III	动态规划	C++	***	dp边界值怎么界定很重要
192	188. 买卖股票的最佳时机 IV	动态规划	C++	***
193	2022腾讯后台&综合第一场 A	链表	C++	*
194	2022腾讯后台&综合第一场 C	贪心	C++	***	双栈贪心上船
195	2022腾讯后台&综合第一场 D	贪心	C++	***	推导出贪心结论就很容易
196	2022Shopee笔试第一场 A	二分查找	C++	*	leetcode34
197	2022Shopee笔试第一场 B	DFS	C++	*	leetcode200
198	2022Shopee笔试第一场 C	链表	C++	*	leetcode25 水b虾皮
199	1143. 最长公共子序列	动态规划	C++	**
200	160. 相交链表	链表	C++	*
201	162. 寻找峰值	二分查找	C++	*
202	C - Little Girl and Maximum Sum	贪心/差分	C++	1500	O(n)统计区间重叠次数很巧妙，注意int会overflow
203	A - Simply Strange Sort	实现	C++	800
204	C - Deep Down Below	贪心/堆	C++	1300
205	450. 删除二叉搜索树中的节点	递归	C++	**	抖音社交三面原题
206	2022网易互娱A	实现	C++	**
207	2022拼多多A	贪心+排序	C++	*
208	2022拼多多C	数学+二分查找	C++	***	二分查找木棍能够围的最大正方形边长
209	402. 移掉 K 位数字	单调栈	C++	**	注意边界情形
210	617. 合并二叉树	递归	C++	*
211	416. 分割等和子集	动态规划	C++	**
212	1293. 网格中的最短路径	BFS	C++	**	BFS经典题目，注意和DFS的区别
213	2022微软A	贪心	C++	*	微软是题库随机抽，而且是自己设计测试用例
214	2022微软B	暴力	C++	*
215	2022微软C	贪心	C++	***	典型的性价比问题
216	116. 填充每个节点的下一个右侧节点指针	二叉树/递归	C++	**	利用已连接的next链，递归解法也很巧妙
217	117. 填充每个节点的下一个右侧节点指针 II	二叉树	C++	***	引入头节点简化代码设计很巧
218	118. 杨辉三角	数学	C++	*
219	A - Linear Keyboard	实现	C++	*
220	D - Blue-Red Permutation	贪婪	C++	**