Never Settle

动态规划类题目1. 基础型动态规划 LeetCode 746 使用最小花费爬楼梯 特点：线性DP，每步决策只依赖前两步 状态定义：dp[i]表示到达第i个台阶的最小花费 优化：可以用滚动数组将空间复杂度优化到O(1) LeetCode 119 杨辉三角形 II 特点：组合数学问题，可以用DP优化 技巧：利用滚动数组优化空间复杂度 2. 决策型动态规划 LeetCode 198 打家劫舍 特点：相邻元素不能同时选择 状态定义：dp[i]表示前i个房屋能偷到的最大金额 状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i]) LeetCode 740 删除并获取点数 特点：决策会影响相邻元素，类似打家劫舍 优化：通过计数转化为打家劫舍问题 3. 多维动态规划 LeetCode 2944...

解题思路方法一：哈希表统计12345678910111213def countBalls(self, lowLimit: int, highLimit: int) -> int: # 使用字典存储每个盒子中球的数量 box_count = {} # 遍历每个球的编号 for i in range(lowLimit, highLimit + 1): # 计算数位和 box_num = sum(int(d) for d in str(i)) # 更新盒子中球的数量 box_count[box_num] = box_count.get(box_num, 0) + 1 # 返回最多的球数 return max(box_count.values()) 优点： 实现简单直观 空间复杂度较低 适合小范围数据 方法二：数组统计（优化版）123456789101112131415def countBalls(self, lowLimit: int,...

解题思路这道题可以使用二分查找来解决： 题目分析： 我们需要找到一个最小值 x，使得所有袋子里的球数都不超过 x 对于每个袋子，如果球数超过 x，需要进行分割操作 分割操作次数不能超过 maxOperations 二分查找思路： 对于给定的目标值 x，可以计算需要多少次操作才能使所有袋子的球数 ≤ x 如果操作次数 ≤ maxOperations，说明 x 可能还可以更小 如果操作次数 > maxOperations，说明 x 必须更大 关键点： 二分查找的左边界是 1 右边界是数组中的最大值 对于每个 x，计算需要的操作次数 代码实现1234567891011121314151617181920class Solution: def minimumSize(self, nums: List[int], maxOperations: int) -> int: def check(mid: int) -> bool: # 计算以mid为目标值时需要的操作次数 ...

解题思路这道题可以转化为打家劫舍问题： 首先统计每个数字出现的次数，记录在数组sum中 sum[i]表示数字i出现的总和（即出现次数 × i） 选择某个数字i时： 获得sum[i]的点数 不能选择i-1和i+1 这就变成了：从一个数组中选数字，不能选相邻的数，求最大和 动态规划解法 定义dp[i]表示考虑前i个数字能获得的最大点数 对于数字i，可以选择要或不要： 选择i：dp[i] = dp[i-2] + sum[i] 不选i：dp[i] = dp[i-1] 取两种情况的最大值 Python实现123456789101112131415161718192021222324252627282930313233343536373839404142class Solution: def deleteAndEarn(self, nums: List[int]) -> int: if not nums: return 0 # 步骤1：构建数字和点数的映射 ...

题目描述给定一个 m x n 的整数数组 grid。一个机器人初始位于左上角（即 grid[0][0]）。机器人尝试移动到右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。 网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含任何有障碍物的方格。 返回机器人能够到达右下角的不同路径数量。 测试用例保证答案小于等于 2 * 109。 解题思路这是一个典型的动态规划问题，我们可以这样解决： 创建一个 dp 数组，dp[i][j] 表示到达位置 (i,j) 的不同路径数 初始条件： 如果起点有障碍物，直接返回 0 否则 dp[0][0] = 1 状态转移： 如果当前位置有障碍物，dp[i][j] = 0 否则 dp[i][j] = dp[i-1][j] + dp[i][j-1] 代码实现12345678910111213141516171819202122232425262728class Solution: def uniquePathsWithObstacles(self, obstacleGrid:...

题目描述给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。 有效二叉搜索树定义如下： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 解题思路要验证一个二叉树是否为有效的二叉搜索树，我们需要： 确保当前节点的值大于左子树的所有节点 确保当前节点的值小于右子树的所有节点 递归验证左右子树也满足BST的性质 关键在于维护每个节点值的合法范围。我们可以通过递归时传递上下界来实现这一点。 代码实现123456789101112131415161718192021222324252627282930313233343536373839404142434445464748class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass Solution: def...

题目给定一个可包含重复数字的序列 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): #...

题目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会在后续的回溯过程中被修改 #...

题目描述给定一个非负索引 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 +...