友情支持

如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜

支付宝

微信

有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

2025年03月 刷题日志

序号 题目 题解 备注

1

206. 反转链表

题解

⭕️ 递归解法非常妙!传一个参数,nextnext 比较麻烦,传两个参数比较简单。

2

34. 在排序数组中查找元素的第一个和最后一个位置

题解

✅ 思考清楚确定边界时,中间指针的移动方向即可迎刃而解。

3

33. 搜索旋转排序数组

题解

⭕️ 重点去处理有序部分,在有序部分内查找不到,则去另外一部分去查找。

4

56. 合并区间

题解

✅ 对区间进行排序,然后快慢指针在当前数组上对其进行合并。

5

81. 搜索旋转排序数组 II

题解

✅ 关注有序区间,确定目标值在有序区间内,则在有序区间查找;反之,则在另外一部分内查找。另外,通过移动一个指针即可避开重复元素。

6

1. 两数之和

题解

✅ 注意审题!返回的是数组下标。

7

15. 三数之和

题解

✅ 双指针

8

141. 环形链表

题解

✅ 快慢指针

9

202. 快乐数

题解

✅ 快慢指针

10

76. 最小覆盖子串

题解

⭕️ 滑动窗口,一定注意细节的处理。

11

316. 去除重复字母

题解

❌ 完全想不到单调栈!

12

347. 前 K 个高频元素

题解

✅ Top K 问题,优先队列;桶排序

13

215. 数组中的第K个最大元素

题解

⭕️ 快速选择,想清楚边界情况!

14

41. 缺失的第一个正数

题解

⭕️ 循环排序,看了答案,自己写出来了。

15

295. 数据流的中位数

题解

⭕️ 双堆,思路理解,写代码却有很多问题。

16

23. 合并 K 个升序链表

题解

✅ 多路归并

17

102. 二叉树的层序遍历

题解

✅ 广度优先搜索

18

124. 二叉树中的最大路径和

题解

⭕️ 深度优先搜索,注意处理负数情况

19

3. 无重复字符的最长子串

题解

✅ 滑动窗口

20

146. LRU 缓存

题解

✅ 链表前后指针操作

21

206. 反转链表

题解

✅ 两种解法:递归+迭代

22

215. 数组中的第K个最大元素

题解

✅ 快速选择

23

25. K 个一组翻转链表

题解

✅ 分段递归反转,再拼接

24

208. 实现 Trie (前缀树)

题解

✅ 前缀树,竟然一次通过

25

547. 省份数量

题解

✅ 并查集,竟然一次通过

26

15. 三数之和

题解

✅ 利用递归“降维”

27

207. 课程表

题解

✅ 拓扑排序

28

53. 最大子数组和

题解

⭕️ 动态规划。稀里糊涂就对了,还要对推演。另有更精妙的分治解法,抽空再尝试。

29

21. 合并两个有序链表

题解

30

5. 最长回文子串

题解

✅ 有更高效的马拉车算法,抽空可以尝试一下。

31

33. 搜索旋转排序数组

题解

⭕️ 重点关注有序部分,优先在有序部分查找,不在有序部分再去无序部分查找。注意判定有序部分的方法: nums[0]nums[mid] 相比较,而不是 nums[left](它的值会来回变)。

32

200. 岛屿数量

题解

✅ 想尝试并查集,结果失败。还是沉岛大法好啊!

33

46. 全排列

题解

✅ 回溯

34

231. 2 的幂

题解

✅ 更巧妙的解法是位运算,如果 n2 的幂,则二进制只有第一位是 1,减一则二进制都是 1,相与 n & (n - 1) 则为 0

35

88. 合并两个有序数组

题解

num1 后面空着,则从后向前合并。

36

50. Pow(x, n)

题解

✅ 递归很简单,抽空再思考一下非递归形式。

37

148. 排序链表

题解

✅ 分治

38

474. 一和零

题解

❌ 动态规划,多维度“物品”就无从下手,还要多练。

39

322. 零钱兑换

题解

⭕️ 动态规划,完全背包问题

40

90. 子集 II

题解

⭕️ 子集,需要注意重复元素的处理。现在用 Set 记录已添加子集的方案还可以再优化。添加优化解法。

41

46. 全排列

题解

✅ 子集。注意对比子集模式在处理子集和排列时的不同:①子集直接在结果中添加新子集;②排列则是将结果中的元素出队,添加新元素后,再入队。

42

121. 买卖股票的最佳时机

题解

✅ 遍历找最大差值

43

236. 二叉树的最近公共祖先

题解

✅ 递归遍历查找目标节点,找到则返回,找不到则返回 null,当左右都不是 null 时,则当前节点即是最近公共祖先。

44

92. 反转链表 II

题解

✅ 链表反转

45

28. 找出字符串中第一个匹配项的下标

题解

✅ 暴力破解。更有的解法是 KMP 算法、Boyer-Moore 算法、Sunday 算法等算法。

46

54. Spiral Matrix

题解

✅ 使用递归来推进层级。注意处理细节。另外,在“上”和“右”能覆盖“全部”(比如一行多列或者多行一列)时,才能在“下”之前根据长度返回。尝试了每段“读取”只剩一个的方案,不行,有很多意外情况要处理。

47

415. 字符串相加

题解

✅ 双指针

48

143. Reorder List

题解

✅ 双指针+链表反正+链表合并

49

142. 环形链表 II

题解

✅ 双指针+数学

50

19. 删除链表的倒数第 N 个结点

题解

✅ 双指针+虚拟头节点。使用虚拟头结点会省事好多。

51

93. 复原 IP 地址

题解

✅ 回溯

52

1137. 第 N 个泰波那契数

题解

✅ 动态规划

53

746. 使用最小花费爬楼梯

题解

✅ 动态规划

54

198. 打家劫舍

题解

✅ 动态规划

55

213. 打家劫舍 II

题解

✅ 动态规划

56

337. 打家劫舍 III

题解

✅ 动态规划+树 = 树形动态规划

57

2560. 打家劫舍 IV

题解

❌ 看答案也一脸懵逼!

58

740. 删除并获得点数

题解

❌ 把题目理解错了。处理后就是最简单的打家劫舍问题。

59

62. 不同路径

题解

✅ 动态规划

60

63. 不同路径 II

题解

✅ 动态规划

61

980. 不同路径 III

题解

❌ 明知是回溯,但在处理当前节点时,总把当前和下一步混在一起。有思路,没写出代码。

62

64. 最小路径和

题解

✅ 动态规划。直接在原有矩阵上操作即可。

63

120. 三角形最小路径和

题解

✅ 动态规划。从底向上比从上向底效率更高。

64

931. 下降路径最小和

题解

✅ 动态规划

65

1289. 下降路径最小和 II

题解

⭕️ 动态规划。题目理解错误。

66

221. 最大正方形

题解

✅ 动态规划。直接将结果存储在参数矩阵上。如果正方形想扩大,则左边,左上和上面三个都是正方形时才可以,可以直接去这三者中的最小值。

67

139. 单词拆分

题解

⭕️ 回溯+备忘录。首先想到的是回溯,但是超时(通过34/47的测试用例)。参考别人题解后,得到启发,加上备忘录通过。参考答案写出了动态规划的解法。思考如何从基于回溯+备忘录转变为动态规划?

68

140. 单词拆分 II

题解

✅ 回溯。没想到从 LinkedList 切换到 ArrayList,内存占用就大幅下降 43.77% → 91.82%。没有使用备忘录耗时已经击败了 98.49%。

69

516. 最长回文子序列

题解

❌ 动态规划。相当于在“结尾”中寻找回文子串。从一维字符串字符坐标去看转移方程,会更加清楚明了。

70

11. 盛最多水的容器

题解

✅ 双指针

71

27. 移除元素

题解

✅ 快慢指针。慢指针记录满足条件的长度,快指针指向需要处理的元素。

72

42. 接雨水

题解

❌ 使用单调栈没写出来。使用单调栈,需 h × w,不能只看头顶的容量。使用左右双指针夹逼代码更简单,只需要计算头顶的容量即可。

73

72. 编辑距离

题解

✅ 动态规划。思考如何进一步优化成一维数组?

74

662. 二叉树最大宽度

题解

⭕️ 添加虚拟节点的做法超时。看答案给节点加编号通过。

75

31. 下一个排列

题解

❌ 明白大概意思,思路不够条理,写不出代码。

76

189. 轮转数组

题解

❌ 题目理解错误,是轮转数组,不是旋转数组。

77

203. 移除链表元素

题解

✅ 快慢指针。看答案,一个指针也可以!而且代码更简单!

78

718. 最长重复子数组

题解

❌ 动态规划。这里求的是公共子数组,只能在两个字符相等时,在上一个字符的基础上加 1,否则就应该设置为 0。不能取 min{dp[i-1][j], dp[i][j-1]}

79

1143. 最长公共子序列

题解

✅ 动态规划。注意区分“子序列”和“子数组”的区别。

80

209. 长度最小的子数组

题解

✅ 滑动窗口。没想到队列也能当滑动窗口。

81

131. Palindrome Partitioning

题解

✅ 回溯

82

721. 账户合并

题解

❌ 并查集。通过邮箱编号建立连接,而不是通过账户索引建立连接。

83

128. 最长连续序列

题解

⭕️ 最初思路是排序。看答案,可以构建集合,然后“起点”(没有前一个数字)数字开始统计。

84

707. 设计链表

题解

85

1081. 不同字符的最小子序列

题解

❌ 单调栈,与 316. Remove Duplicate Letters 相同。知道用单调栈,但还是没写出来。

86

1997. 访问完所有房间的第一天

题解

❌ 动态规划。看答案也一脸懵逼!

87

530. 二叉搜索树的最小绝对差

题解

✅ 二叉树中根遍历。

88

2850. 将石头分散到网格图的最少移动次数

题解

⭕️ 回溯。找出所有的高峰和山谷,然后对高峰做排列,计算各种排列与山谷的距离,取最小值即可。有模糊思路,看答案才写出代码。

89

30. 串联所有单词的子串

题解

❌ 滑动窗口。要分情况处理窗口移动问题。

90

32. 最长有效括号

题解

⭕️ 栈。使用栈记录左右括号的下标,匹配后标注“占位符”。最后,统计占位符中的数量,找出最大长度。

91

74. 搜索二维矩阵

题解

✅ 二分查找。把矩阵按行“拼接”,然后二分查找,解法非常妙。

92

84. 柱状图中最大的矩形

题解

❌ 单调栈。一脸懵逼。哨兵技巧非常巧妙。

93

1047. 删除字符串中的所有相邻重复项

题解

⭕️ 栈。把 StringBuilder 当做栈来使用。将最后一个字符与当前字符比较,相等则删除最后一个字符,否则就添加。

94

1049. 最后一块石头的重量 II

题解

❌ 动态规划,0/1 背包问题。一脸懵逼。

95

37. 解数独

题解

⭕️ 回溯。学习使用位操作来标注已用字符,计算未用字符。位操作真是太玄妙了!

96

39. 组合总和

题解

✅ 回溯

97

40. 组合总和 II

题解

✅ 回溯。注意同层剪枝的技巧。

98

48. 旋转图像

题解

✅ 使用递归来推进循环。

99

49. 字母异位词分组

题解

✅ 使用 Map 存字符和数量即可。

100

560. 和为 K 的子数组

题解

✅ 前缀和。需要记录每一个和的出现次数。

101

69. x 的平方根

题解

✅ 二分查找。使用一个单独变量来保存最后一个小于等于的中间值,那么即可直接获取答案。

102

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

题解

✅ 有差价就买卖,见好就收。

103

125. 验证回文串

题解

✅ 双指针

104

136. 只出现一次的数字

题解

✅ 位运算。出现两次,则异或后为 0,所有数字异或,最后只剩下出现一次的数字。

105

649. Dota2 参议院

题解

✅ 贪心算法。优先禁止最近的对方议员投票。不停循环,直到只留下一方议员。

106

670. 最大交换

题解

✅ 贪心算法。最高位尽可能跟后面的最大数字进行交换。

107

167. 两数之和 II - 输入有序数组

题解

✅ 双指针

108

697. 数组的度

题解

109

211. 添加与搜索单词 - 数据结构设计

题解

✅ 前缀树。需要处理通配符的情况,尤其要注意结尾字符的处理。

110

216. 组合总和 III

题解

✅ 回溯

111

224. 基本计算器

题解

❌ 使用双栈来分别存放数字和操作符。

112

239. 滑动窗口最大值

题解

✅ 单调栈。有很多细节需要考虑。

113

260. 只出现一次的数字 III

题解

⭕️ 在 136. 只出现一次的数字 基础上,做了进一步延伸。需要先根据所有数异或值的最后一位 1,将数字分为两部分,再分别做异或。

114

137. 只出现一次的数字 II

题解

❌ 位运算。按位统计 1 出现的次数,取余留下来的则是 只出现一次的数字所拥有的 1,然后再做运算恢复成原始数字即可。

115

115. 不同的子序列

题解

❌ 动态规划。

116

1530. 好叶子节点对的数量

题解

⭕️ 还有瑕疵,还需要继续优化。

117

1171. 从链表中删去总和值为零的连续节点

题解

❌ 前缀和。想到了前缀和,但是没想到可以利用中间和为 0,直接跳过这部分节点。

118

123. 买卖股票的最佳时机 III

题解

❌ 动态规划。思路还需要多揣摩和思考。

119

199. 二叉树的右视图

题解

✅ 深度优先遍历。按照 <level, node> 的格式,把每个节点都放到 Map 里,因为是先左后右,所以,每层最后只剩下了最右边的元素。

120

2684. 矩阵中移动的最大次数

题解

✅ 动态规划。也可以使用深度优先搜索的解法,使用深度优先搜索时,需要把处理过的节点值设置为 0,防止重新判断,加快处理速度。

121

787. K 站中转内最便宜的航班

题解

⭕️ 深度优先搜索通过 48 / 56 个测试用例。使用带备忘录的深度优先搜索顺利通过。带备忘录的深度优先搜索,也可以优化成动态规划。

122

794. 有效的井字游戏

题解

✅ 总结提炼判断规则。

123

3099. 哈沙德数

题解

✅ 数学计算

124

300. 最长递增子序列

题解

❌ 动态规划。动态规划+二分查找的解法一脸懵逼,看答案都懵逼!

125

144. 二叉树的前序遍历

题解

✅ 树的 Morris 遍历

126

3115. 质数的最大距离

题解

✅ 质数判断

127

705. 设计哈希集合

题解

✅ 使用开放地址法解决哈希冲突。

128

2800. 包含三个字符串的最短字符串

题解

❌ 先求三个字符串的全排列,然后合并(合并时注意处理首尾相同子串,减少合并字符串的长度),在这些合并后的字符串中选择最短,字典排序最小的字符串。

129

2320. 统计放置房子的方式数

题解

❌ 先只考虑一边的情况,再组合两边的情况。只考虑一边的情况,就是一个斐波那契数列: \(f(i) = f(i-1) + f(i-2)\)。

130

1769. 移动所有球到每个盒子所需的最小操作数

题解

✅ 最简单的解法双重循环。取巧的解法是,利用“前缀和”的思路,分别计算当前节点左右两侧的操作次数,然后再相加。

131

350. 两个数组的交集 II

题解

✅ 最初思路是对两个数组统计次数。其实只需要对一个数组统计次数,另外一个数组遍历时就可以求交集了。

132

392. 判断子序列

题解

✅ 双指针

133

409. 最长回文串

题解

✅ 回文

134

1839. 所有元音按顺序排布的最长子字符串

题解

✅ 滑动窗口。题目不难,只是处理边界条件麻烦。另外,也有取巧解法,可以探索一下。

135

918. 环形子数组的最大和

题解

❌ 理解错题目了。前大,中小,后大,这类子数组也可以产生更多的子数组和。另有“取反”和单调栈解法。

136

1349. 参加考试的最大学生数

题解

❌ 回溯解法通过 50 / 57 个测试用例。动态规划解法太难了!

137

994. 腐烂的橘子

题解

✅ 腐烂加剧+传染。广度优先遍历的解法也挺有意思。

138

14. 最长公共前缀

题解

✅ 解法很多,可以很好地开阔思路!

139

22. 括号生成

题解

✅ 回溯。也可以去掉回溯过程,使用深度优先遍历。

140

24. 两两交换链表中的节点

题解

✅ 链表。增加虚拟节点,极大简化代码。

141

26. 删除有序数组中的重复项

题解

✅ 双指针

142

45. 跳跃游戏 II

题解

✅ 贪心算法。也可以动态规划。

143

80. 删除有序数组中的重复项 II

题解

✅ 双指针,同时需要记录每个元素的次数,相同元素只复制两个。

144

55. 跳跃游戏

题解

✅ 贪心算法。没想到这就是贪心?

145

82. 删除排序链表中的重复元素 II

题解

✅ 快慢指针。

146

83. 删除排序链表中的重复元素

题解

✅ 链表操作

147

91. 解码方法

题解

❌ 动态规划。递推公式还要仔细推敲。

148

2319. 判断矩阵是否是一个 X 矩阵

题解

✅ 遍历对角线设置成负值,检查其他元素,发现有大于 0 的则不成矩阵。

149

1189. “气球” 的最大数量

题解

✅ 哈希

150

3111. 覆盖所有点的最少矩形数目

题解

✅ 贪心。从左边界开始,尽可能多占用横轴。宽度耗尽,则从下一个点开始。

151

1509. 三次操作后最大值与最小值的最小差

题解

✅ 贪心。转变一下题目就是要求如何缩短最大值和最小值直接的差值。看官方题解,可以直接求 \(a(n - 4 + i) - a(i)\) 的最小值。

152

1700. 无法吃午餐的学生数量

题解

153

1457. 二叉树中的伪回文路径

题解

✅ 回溯,深度优先遍历,到叶子节点判断是否可以组成回文。

154

1410. HTML 实体解析器

题解

✅ 哈希 + 字符串

155

1561. 你可以获得的最大硬币数目

题解

✅ 贪心。每次去第二大的数字即可。

156

1325. 删除给定值的叶子节点

题解

✅ 深度优先遍历,在“后序”中做业务处理。

157

1217. 玩筹码

题解

❌ 题目理解错误!position[i] 中的数字是筹码的位置。题目意思是奇数到奇数和偶数到偶数免费,但是紧挨的两个数字移动收费,所以,统计奇偶数的个数,看哪个小就移动哪个。

158

1006. 笨阶乘

题解

✅ 栈。代码写出来了,但是好烂!

159

841. 钥匙和房间

题解

✅ 深度优先遍历或广度优先遍历。

160

890. 查找和替换模式

题解

✅ 映射。建立一个字母映射,并且每个字母只能有一种映射关系。否则就不匹配。

161

1052. 爱生气的书店老板

题解

✅ 先计算没有生气而满意的总数,再计算因为老板憋气而满意的增量用户。

162

1033. 移动石子直到连续

题解

✅ 分类讨论

163

1020. 飞地的数量

题解

✅ 深度优先遍历。有机会尝试一下广度优先遍历。

164

1022. 从根到叶的二进制数之和

题解

✅ 深度优先遍历。

165

915. 分割数组

题解

✅ 两遍遍历。有题解可以不到一遍遍历即可解决问题。

166

1387. 将整数按权重排序

题解

✅ 先计算每个数字的权重,再进行比较:使用集合存储下标,通过下标找到对应的权重。计算权重时,可以递归,也可以直接循环。使用递归时,可以使用备忘录把已经计算的值存储起来,防止重复计算。

167

1496. 判断路径是否相交

题解

✅ 想找个巧办法,结果失败!还是用记录轨迹的办法搞定了。

168

1110. 删点成林

题解

✅ 深度优先遍历,把父节点传到递归参数里,同时标注一下是左子树还是右子树。

169

1442. 形成两个异或相等数组的三元组数目

题解

⭕️ 前缀和。使用官方题解中的异或前缀和解法啦。数学知识还是得补啊!原来的思路是回溯,通过 46 / 47 测试用例。使用回溯应该对,但是加上备忘录后,还是有一个测试用例没通过。(看一个题解,原始解法就是暴力法。是对的。)

170

1400. 构造 K 个回文字符串

题解

⭕️ 统计奇数字母个数,如果个数超过 k 肯定就不满足了。自己的思考已经解决答案了。可惜不够确定,还是参考答案了。

171

900. RLE 迭代器

题解

✅ 使用属性 index 记录 next 到位置,剩下就是在 encoding 的偶数下标上做减法。

172

1362. 最接近的因数

题解

✅ 我的解法是从两边向中间挤压;更优解是找到平方根,然后向外开。

173

865. 具有所有最深节点的最小子树

题解

✅ 深度优先遍历,递归,在“后序”阶段处理业务逻辑。

174

1023. 驼峰式匹配

题解

✅ 双指针

175

1382. 将二叉搜索树变平衡

题解

✅ 二叉搜索树,先中序遍历拿到所有节点,然后递归构造平衡二叉搜索树。

176

1007. 行相等的最少多米诺旋转

题解

✅ 统计每个数字的下标,然后逐个检查每个数字的下标集合是否能完整覆盖原始数字的全部下标。更优解:判断是否可以都变成 tops[0] 或者 bottoms[0]

截止目前,本轮练习一共完成 176 道题。