LeetCode题目分类总结
动态规划类题目
1. 基础型动态规划
-
- 特点：线性DP，每步决策只依赖前两步
- 状态定义：dp[i]表示到达第i个台阶的最小花费
- 优化：可以用滚动数组将空间复杂度优化到O(1)
-
- 特点：组合数学问题，可以用DP优化
- 技巧：利用滚动数组优化空间复杂度
2. 决策型动态规划
-
- 特点：相邻元素不能同时选择
- 状态定义：dp[i]表示前i个房屋能偷到的最大金额
- 状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
-
- 特点：决策会影响相邻元素，类似打家劫舍
- 优化：通过计数转化为打家劫舍问题
3. 多维动态规划
- LeetCode 2944 购买水果需要的最少金币数
- 特点：需要考虑多个维度的状态
- 状态定义：dp[i][free_until]表示考虑到第i个水果时的最小花费
- 记忆化搜索：使用装饰器优化重复计算
深度优先搜索(DFS)
- 深度优先遍历问题
- 应用：二叉树最大深度
- 递归实现
- 时间复杂度：O(n)
- 空间复杂度：O(h)，h为树的高度
解题技巧总结
1. 动态规划问题解题步骤
- 定义状态
- 写出状态转移方程
- 确定初始条件和边界情况
- 确定计算顺序
- 考虑空间优化
2. 常见优化方法
- 滚动数组
- 记忆化搜索
- 状态压缩
- 预处理数据
3. 代码实现要点
- 考虑边界情况
- 注意数组越界
- 善用Python内置函数
- 合理使用缓存装饰器
总结
动态规划是最常见的算法类型，关键在于：
- 正确定义状态
- 找出状态间的转移关系
- 考虑空间优化
深度优先搜索常用于：
- 树结构问题
- 图的遍历
- 回溯问题
解题技巧：
- 先画图分析
- 考虑特殊情况
- 寻找问题间的相似性
- 注意代码的简洁性和可读性
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Never Settle！
相关推荐
2025-01-21
LeetCode 746 - 使用最小花费爬楼梯
LeetCode 746 - 使用最小花费爬楼梯题目描述给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你计算并返回达到楼梯顶部的最低花费。 1. 问题分析这是爬楼梯问题的变体，主要区别是： 每个台阶都有一个花费 可以从索引0或1开始 目标是到达顶部（数组长度位置）的最小花费 2. 解题思路状态定义dp[i] 表示：到达第i个台阶的最小花费 状态转移方程dp[i] = min(dp[i-1], dp[i-2]) + cost[i] 解释：到达第i个台阶可以从： 第i-1个台阶爬1步上来 第i-2个台阶爬2步上来 选择这两种方式中花费较小的一种 代码实现和详细解释1234567891011121314151617181920212223242526272829303132333435363738class Solution: def minCostClimbingStairs(self,...
2025-01-30
LeetCode 119 - 杨辉三角形 II
题目描述给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。 在「杨辉三角」中，每个数是它左上方和右上方的数的和。 示例示例 1: 输入: rowIndex = 3 输出: [1,3,3,1] 示例 2: 输入: rowIndex = 0 输出: [1] 示例 3: 输入: rowIndex = 1 输出: [1,1] 提示: 0 <= rowIndex <= 33 解题思路1. 递推解法（空间复杂度 O(k²)） 创建二维数组存储所有行 每个位置的值是上一行相邻两个数的和 边界位置都是1 12345678910111213141516171819202122232425262728293031323334353637#递推解法（空间复杂度O(k^2)）class Solution: def getRow(self, rowIndex: int) -> List[int]: C = [[1] * (i + 1) for i in range(rowIndex +...
2025-01-30
LeetCode 219 - 存在重复元素 II
题目描述给你一个整数数组 nums 和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，满足： nums[i] == nums[j] abs(i - j) <= k 解题思路1. 滑动窗口 + 集合使用大小为 k 的滑动窗口和集合来解决： 维护一个最大长度为 k 的集合 遍历数组，对于每个元素： 如果当前元素在集合中已存在，返回 true 将当前元素加入集合 如果集合大小超过 k，移除最早加入的元素 2. 代码实现123456789def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: num_set = set() for i in range(len(nums)): if nums[i] in num_set: return True num_set.add(nums[i]) if len(num_set) > k: ...
2025-01-30
LeetCode 350 - 两个数组的交集
题目描述1. 考虑重复元素的交集给你两个整数数组 nums1 和 nums2，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（取较小值）。 2. 不考虑重复元素的交集给定两个数组，返回它们的交集。输出结果中的每个元素一定是唯一的。 解题思路1. 考虑重复元素（排序 + 双指针）12345678910111213141516def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: nums1.sort() # 先排序 nums2.sort() i, j = 0, 0 # 双指针 res = [] while i < len(nums1) and j < len(nums2): if nums1[i] == nums2[j]: # 相等时添加到结果 res.append(nums1[i]) i += 1 ...
2025-02-05
leetcode90子集2
题目90. 子集 II 给你一个整数数组 nums，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。 解题思路1. 回溯12345678910111213141516171819202122232425262728293031323334class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: # 1. 首先对数组排序，使相同的元素相邻 nums.sort() res = [] # 存储最终结果 def backtrack(start: int, path: List[int]): # 2. 将当前路径加入结果集 # path[:] 创建一个新的列表，是当前path的浅拷贝 # 为什么要拷贝？因为path会在后续的回溯过程中被修改 #...
2025-02-06
leetcode47全排列2
题目给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。 示例 1：输入：nums = [1,1,2]输出：[[1,1,2], [1,2,1], [2,1,1]] 示例 2：输入：nums = [1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 解题思路1. 基本回溯法 使用交换的方式生成排列 每次固定一个位置，然后递归处理剩余位置 但这种方法会产生重复的排列 2. 回溯法+剪枝 在基本回溯的基础上添加剪枝条件 通过判断是否已经使用过相同的数字来避免重复 需要先对数组排序，使相同的数字相邻 代码实现1. 基本回溯法12345678910111213141516class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: def backtrack(nums, start, end): #...
评论
