Never Settle

题目给定一个数组 position 表示球的位置，以及整数 m 表示要放的球数。把 m 个球放入这些位置，使任意两球间的最小磁力（距离）最大。返回这个最大值。 解题思路 先对位置排序。 对“最小间距”进行二分搜索：假设最小间距为 d，检查能否放下 m 个球。 检查方式：从最左位置开始贪心放球，尽量保持相邻球间距 ≥ d，统计能放下的球数。 如果能放下 m 个球，说明 d 可行，尝试更大；否则缩小。 代码实现（Python）1234567891011121314151617181920212223242526from typing import Listclass Solution: def maxDistance(self, position: List[int], m: int) -> int: position.sort() def can_place(dist: int) -> bool: count = 1 last = position[0] for x i...

题目请你设计一个数据结构，它能求出给定子数组内一个给定值的频率。 子数组中一个值的频率指的是这个子数组中这个值的出现次数。 请你实现 RangeFreqQuery 类： RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。 int query(int left, int right, int value) 返回子数组 arr[left...right] 中 value 的频率。 示例 1输入： 12["RangeFreqQuery", "query", "query"][[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]] 输出： 1[null, 1, 2] 解释： 123RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]);...

题目用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。 箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角，可以将球导向左侧或者右侧。 将球导向右侧的挡板跨过左上角和右下角，在网格中用 1 表示。将球导向左侧的挡板跨过右上角和左下角，在网格中用 -1 表示。在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 “V” 形图案，或者被一块挡导向到箱子的任意一侧边上，就会卡住。 返回一个大小为 n 的数组 answer ，其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标，如果球卡在盒子里，则返回 -1 。 思路 构造一个长度为球数的数组 result，记录每个球当前所在的列。 如果某个球无法进入下一行，则将对应位置设为 -1。 遍历每一行时，只更新 result 中不为 -1 的球。 代码实现12345678910111213141516171819202122232425262728class Solution: def findBal...

动态规划类题目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 购买水果需要的最少金币数 特点：需要考虑多个维度的状态 状态定义：dp[i][free_until]表示考虑到第i个水果时的最小花费 记忆化搜索：使用装饰器优化重复计算 深度优先搜索(DFS) 深度优先遍历问题 应用：二叉树最...

题目你在一家生产小球的玩具厂工作，有 n 个小球，编号从 lowLimit 开始，到 highLimit 结束（包括 lowLimit 和 highLimit，即 n == highLimit - lowLimit + 1）。另有无限数量的盒子，编号从 1 到 infinity。 你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。例如，编号 321 的小球应当放入编号 3 + 2 + 1 = 6 的盒子，而编号 10 的小球应当放入编号 1 + 0 = 1 的盒子。 给你两个整数 lowLimit 和 highLimit，返回放有最多小球的盒子中的小球数量。如果有多个盒子都满足放有最多小球，只需返回其中任一盒子的小球数量。 解题思路方法一：哈希表统计12345678910111213def countBalls(self, lowLimit: int, highLimit: int) -> int: # 使用字典存储每个盒子中球的数量 box_count = {} # 遍历每个球的编号 for ...

题目给你一个整数数组 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 对于每个袋子，如果球数超过 x，需要进行分割操作 ...

题目给你一个整数数组 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出现的总和（即出现次数 × i） 选择某个数字i时： 获得sum[i]的点数 不能选择i-1和i+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的性质 关键在于维护每个节点值的合法范围。我们可以通过递归时传递上下界来实现这一点。 代码实现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]) -> ...

题目给定一个可包含重复数字的序列 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): # 当start等于end时，说明已经处理...