LeetCode 1760 - 袋子里最少的球
题目给你一个整数数组 nums，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations。 你可以进行如下操作至多 maxOperations 次： 选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有正整数个球。比如一个袋子里有 5 个球，可以分成 1 和 4，或者 2 和 3。 你的开销是单个袋子里球数目的最大值，你想要最小化开销。请返回最小开销。 示例 1输入：nums = [9], maxOperations = 2输出：3解释：[9] -> [6,3] -> [3,3,3]，最大值为 3。 示例 2输入：nums = [2,4,8,2], maxOperations = 4输出：2解释：最终可分为 [2,2,2,2,2,2,2,2]，最大值为 2。 示例 3输入：nums = [7,17], maxOperations = 2输出：7 解题思路这道题可以使用二分查找来解决： 题目分析： 我们需要找到一个最小值 x，使得所有袋子里的球数都不超过 x 对于每个袋子，如果球数超过...
LeetCode 740 - 删除并获取点数
题目给你一个整数数组 nums，你可以对它进行一些操作。 每次操作中，选择任意一个 nums[i]，删除它并获得 nums[i] 的点数。之后，你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。 示例 1输入：nums = [3,4,2]输出：6解释：删除 4 获得 4 点数，因此 3 也被删除；之后删除 2 获得 2 点数，总共 6。 示例 2输入：nums = [2,2,3,3,3,4]输出：9解释：删除 3 获得 3 点数，接着要删除两个 2 和 4；之后再次删除 3 获得 3 点数，再删除 3 获得 3 点数，总共 9。 提示 1 <= nums.length <= 2 * 10^4 1 <= nums[i] <= 10^4 解题思路这道题可以转化为打家劫舍问题： 首先统计每个数字出现的次数，记录在数组sum中 sum[i]表示数字i出现的总和（即出现次数 ×...
LeetCode 63 - 不同路径 II
题目描述给定一个 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:...
LeetCode 98 - 验证二叉搜索树
题目描述给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。 有效二叉搜索树定义如下： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 解题思路要验证一个二叉树是否为有效的二叉搜索树，我们需要： 确保当前节点的值大于左子树的所有节点 确保当前节点的值小于右子树的所有节点 递归验证左右子树也满足BST的性质 关键在于维护每个节点值的合法范围。我们可以通过递归时传递上下界来实现这一点。 代码实现123456789101112131415161718192021222324class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass Solution: def isValidBST(self, root: Optional[TreeNode]) ->...
LeetCode 47 - 全排列 II
题目给定一个可包含重复数字的序列 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): #...
LeetCode 90 - 子集 II
题目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会在后续的回溯过程中被修改 #...
LeetCode 50 - Pow(x, n)
题目实现 pow(x, n)，即计算 x 的 n 次幂。 解题思路使用快速幂（分治）： 若 n 为偶数：x^n = (x^(n/2))^2 若 n 为奇数：x^n = x * x^(n-1) 为了处理负指数，把 x 取倒数并将 n 取相反数。 代码实现（Python）123456789101112131415class Solution: def myPow(self, x: float, n: int) -> float: if n == 0: return 1.0 if n < 0: x = 1 / x n = -n result = 1.0 while n > 0: if n & 1: result *= x x *= x n >>= 1 return...
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 +...
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: ...
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 ...
