以下是按照常见算法标签将题目进行归类的列表:
1. 动态规划
10. 正则表达式匹配
1143. 最长公共子序列
115. 不同的子序列
120. 三角形最小路径和
121. 买卖股票的最佳时机
123. 买卖股票的最佳时机 III
131. 分割回文串
152. 乘积最大子数组
188. 买卖股票的最佳时机 IV
198. 打家劫舍
213. 打家劫舍 II
221. 最大正方形
256. 粉刷房子
279. 完全平方数
300. 最长上升子序列
309. 最佳买卖股票时机含冷冻期
322. 零钱兑换
337. 打家劫舍 III
343. 整数拆分
376. 摆动序列
395. 至少有K个重复字符的最长子串
410. 分割数组的最大值
416. 分割等和子集
494. 目标和
509. 斐波那契数
516. 最长回文子序列
518. 零钱兑换 II
53. 最大子数组和
55. 跳跃游戏
72. 编辑距离
85. 最大矩形
91. 解码方法
95. 不同的二叉搜索树 II
96. 不同的二叉搜索树
221. 最大正方形
647. 回文子串
673. 最长递增子序列的个数
剑指 Offer 42. 连续子数组的最大和
面试题 17.24. 最大子矩阵
2. 哈希表
1. 两数之和
128. 最长连续序列
138. 复制带随机指针的链表
149. 直线上最多的点数
217. 存在重复元素
242. 有效的字母异位词
347. 前 K 个高频元素
349. 两个数组的交集
454. 四数相加 II
560. 和为K的子数组
剑指 Offer 03. 数组中重复的数字
剑指 Offer 48. 最长不含重复字符的子字符串
554. 砖墙
3. 双指针
11. 盛最多水的容器
15. 三数之和
16. 最接近的三数之和
19. 删除链表的倒数第N个节点
26. 删除排序数组中的重复项
27. 移除元素
28. 实现 strStr()
30. 串联所有单词的子串
42. 接雨水
61. 旋转链表
75. 颜色分类
141. 环形链表
142. 环形链表 II
143. 重排链表
167. 两数之和 II - 输入有序数组
209. 长度最小的子数组
283. 移动零
344. 反转字符串
524. 通过删除字母匹配到字典里最长单词
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
剑指 Offer 22. 链表中倒数第k个节点
4. 贪心
11. 盛最多水的容器
45. 跳跃游戏 II
55. 跳跃游戏
134. 加油站
135. 分发糖果
179. 最大数
392. 判断子序列
406. 根据身高重建队列
452. 用最少数量的箭引爆气球
621. 任务调度器
763. 划分字母区间
5. 回溯
17. 电话号码的字母组合
22. 括号生成
37. 解数独
39. 组合总和
40. 组合总和 II
46. 全排列
47. 全排列 II
51. N 皇后
52. N 皇后 II
78. 子集
79. 单词搜索
93. 复原 IP 地址
131. 分割回文串
140. 单词拆分 II
216. 组合总和 III
401. 二进制手表
剑指 Offer 34. 二叉树中和为某一值的路径
6. 排序
4. 寻找两个正序数组的中位数
56. 合并区间
75. 颜色分类
88. 合并两个有序数组
148. 排序链表
164. 最大间距
179. 最大数
215. 数组中的第K个最大元素
347. 前 K 个高频元素
剑指 Offer 40. 最小的k个数
补充题4. 手撕快速排序
补充题5. 手撕归并排序
7. 数组
11. 盛最多水的容器
26. 删除排序数组中的重复项
27. 移除元素
31. 下一个排列
33. 搜索旋转排序数组
34. 在排序数组中查找元素的第一个和最后一个位置
36. 有效的数独
41. 缺失的第一个正数
48. 旋转图像
53. 最大子序和
54. 螺旋矩阵
59. 螺旋矩阵 II
66. 加一
73. 矩阵置零
74. 搜索一个二维矩阵
118. 杨辉三角
119. 杨辉三角 II
121. 买卖股票的最佳时机
122. 买卖股票的最佳时机 II
128. 最长连续序列
189. 旋转数组
209. 长度最小的子数组
238. 除自身以外数组的乘积
283. 移动零
287. 寻找重复数
剑指 Offer 04. 二维数组中的查找
剑指 Offer 29. 顺时针打印矩阵
8. 树
94. 二叉树的中序遍历
95. 不同的二叉搜索树 II
96. 不同的二叉搜索树
100. 相同的树
101. 对称二叉树
102. 二叉树的层序遍历
103. 二叉树的锯齿形层次遍历
104. 二叉树的最大深度
105. 从前序与中序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树
110. 平衡二叉树
111. 二叉树的最小深度
112. 路径总和
114. 二叉树展开为链表
129. 求根到叶子节点数字之和
144. 二叉树的前序遍历
145. 二叉树的后序遍历
199. 二叉树的右视图
222. 完全二叉树的节点个数
236. 二叉树的最近公共祖先
剑指 Offer 26. 树的子结构
剑指 Offer 27. 二叉树的镜像
剑指 Offer 33. 二叉搜索树的后序遍历序列
剑指 Offer 34. 二叉树中和为某一值的路径
剑指 Offer 36. 二叉搜索树与双向链表
剑指 Offer 54. 二叉搜索树的第k大节点
9. 链表
2. 两数相加
19. 删除链表的倒数第N个节点
21. 合并两个有序链表
23. 合并K个排序链表
24. 两两交换链表中的节点
25. K 个一组翻转链表
82. 删除排序链表中的重复元素 II
83. 删除排序链表中的重复元素
138. 复制带随机指针的链表
141. 环形链表
142. 环形链表 II
143. 重排链表
160. 相交链表
206. 反转链表
234. 回文链表
445. 两数相加 II
剑指 Offer 22. 链表中倒数第k个节点
剑指 Offer 52. 两个链表的第一个公共节点
10. 二分查找
4. 寻找两个正序数组的中位数
33. 搜索旋转排序数组
34. 在排序数组中查找元素的第一个和最后一个位置
35. 搜索插入位置
69. x 的平方根
74. 搜索二维矩阵
81. 搜索旋转排序数组 II
153. 寻找旋转排序数组中的最小值
154. 寻找旋转排序数组中的最小值 II
162. 寻找峰值
240. 搜索二维矩阵 II
378. 有序矩阵中第K小的元素
剑指 Offer 11. 旋转数组的最小数字
剑指 Offer 53 - I. 在排序数组中查找数字 I
11. 栈
20. 有效的括号
32. 最长有效括号
42. 接雨水
84. 柱状图中最大的矩形
85. 最大矩形
155. 最小栈
224. 基本计算器
225. 用队列实现栈
232. 用栈实现队列
331. 验证二叉树的前序序列化
394. 字符串解码
剑指 Offer 09. 用两个栈实现队列
剑指 Offer 33. 二叉搜索树的后序遍历序列
12. 数学
7. 整数反转
8. 字符串转换整数 (atoi)
9. 回文数
12. 整数转罗马数字
13. 罗马数字转整数
29. 两数相除
50. Pow(x, n)
67. 二进制求和
1281. 整数的各位积和之差
剑指 Offer 62. 圆圈中最后剩下的数字
13. 字符串
5. 最长回文子串
6. Z 字形变换
14. 最长公共前缀
22. 括号生成
28. 实现 strStr()
49. 字母异位词分组
58. 最后一个单词的长度
67. 二进制求和
125. 验证回文串
151. 翻转字符串里的单词
394. 字符串解码
剑指 Offer 48. 最长不含重复字符的子字符串
14. 图
133. 克隆图
207. 课程表
210. 课程表 II
329. 矩阵中的最长递增路径
剑指 Offer 26. 树的子结构
15. 设计
146. LRU缓存机制
155. 最小栈
225. 用队列实现栈
232. 用栈实现队列
380. 常数时间插入、删除和获取随机元素
460. LFU缓存
剑指 Offer 09. 用两个栈实现队列
剑指 Offer 36. 二叉搜索树与双向链表
16. 递归
21. 合并两个有序链表
23. 合并K个排序链表
95. 不同的二叉搜索树 II
96. 不同的二叉搜索树
98. 验证二叉搜索树
101. 对称二叉树
104. 二叉树的最大深度
剑指 Offer 34. 二叉树中和为某一值的路径
剑指 Offer 36. 二叉搜索树与双向链表
剑指 Offer 62. 圆圈中最后剩下的数字
17. 贪心
11. 盛最多水的容器
45. 跳跃游戏 II
55. 跳跃游戏
134. 加油站
135. 分发糖果
140. 单词拆分 II
179. 最大数
406. 根据身高重建队列
452. 用最少数量的箭引爆气球
621. 任务调度器
763. 划分字母区间
18. 并查集
130. 被围绕的区域
200. 岛屿数量
261. 以图判树
323. 无向图中连通分量的数目
剑指 Offer 26. 树的子结构
剑指 Offer 62. 圆圈中最后剩下的数字
19. 位运算
136. 只出现一次的数字
137. 只出现一次的数字 II
190. 颠倒二进制位
191. 位1的个数
231. 2的幂
剑指 Offer 39. 数组中出现次数超过一半的数字
剑指 Offer 62. 圆圈中最后剩下的数字
这些题目被归类到了不同的算法标签下,可以帮助你更好地理解和掌握每种算法的应用场景。
当然可以!动态规划(DP)在不同类型的题目中应用广泛,通常根据问题的性质,可以进一步将动态规划问题归类为以下几种常见类型:
1. 线性 DP
这些问题的状态转移一般是基于一个或多个前面的状态,常见的有数组、字符串相关的题目。
53. 最大子数组和
62. 不同路径
63. 不同路径 II
70. 爬楼梯
198. 打家劫舍
213. 打家劫舍 II
221. 最大正方形
300. 最长上升子序列
309. 最佳买卖股票时机含冷冻期
376. 摆动序列
413. 等差数列划分
509. 斐波那契数
518. 零钱兑换 II
剑指 Offer 10- I. 斐波那契数列
剑指 Offer 10- II. 青蛙跳台阶问题
剑指 Offer 42. 连续子数组的最大和
2. 背包问题
背包问题的核心是如何选择一些物品,使得总价值最大或满足某个条件。经典的背包问题有0-1背包、完全背包、多重背包等。
416. 分割等和子集
518. 零钱兑换 II
3. 区间 DP
区间 DP 常用于需要考虑多个区间组合的优化问题,如字符串的编辑距离、矩阵连乘问题等。
516. 最长回文子序列
312. 戳气球
4. 子序列/子数组 DP
这类问题通常是求解数组或字符串中的某个子序列、子数组的最优解,如最长递增子序列、最长公共子序列等。
1143. 最长公共子序列
300. 最长上升子序列
392. 判断子序列
647. 回文子串
673. 最长递增子序列的个数
5. 树形 DP
树形 DP 通常应用于树结构的问题,解决方法是通过递归或自底向上地进行动态规划。
337. 打家劫舍 III
剑指 Offer 34. 二叉树中和为某一值的路径
6. 字符串 DP
字符串 DP 问题处理的是字符串的各种匹配、变换问题,如编辑距离、正则匹配等。
10. 正则表达式匹配
44. 通配符匹配
72. 编辑距离
97. 交错字符串
115. 不同的子序列
131. 分割回文串
139. 单词拆分
140. 单词拆分 II
7. 数位 DP
数位 DP 是一种特殊的动态规划问题,通常用于解决数字相关的问题,比如计算满足某些条件的数字个数。
233. 数字 1 的个数
8. 状态压缩 DP
状态压缩 DP 主要用于解决涉及多个条件或状态的组合问题,常见于图论中的最短路径问题或集合覆盖问题。
691. 贴纸拼词
9. 博弈 DP
博弈 DP 主要用于求解两个人(或多个人)在一个游戏中的最优策略问题。
464. 我能赢吗
877. 石子游戏
10. 矩阵 DP
矩阵 DP 通常用来解决二维表格或矩阵中的最优解问题,如最大正方形、路径问题等。
120. 三角形最小路径和
221. 最大正方形
64. 最小路径和
11. 记忆化搜索
记忆化搜索是一种将递归与动态规划结合的方法,通过保存中间结果来避免重复计算。
329. 矩阵中的最长递增路径
12. 其他 DP 问题
一些问题可能不完全归属于上述某一类,但依然可以使用动态规划的思想来解决。
887. 鸡蛋掉落
通过上述归类,你可以更好地理解不同类型的动态规划问题及其应用场景。随着练习的深入,你会逐渐掌握每种类型的解题思路,并在遇到新问题时迅速识别并应用合适的动态规划技巧。
标签:II,Offer,分类,链表,算法,codetop,二叉树,数组,DP From: https://www.cnblogs.com/jaqennnnn/p/18399300