/leetcode

记录一下我的刷题之旅

Primary LanguageGoMIT LicenseMIT

Leetcode刷题记录

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

Tips

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

Contact

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

目录

题目 类型 代码 难度 备注
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++ **