Never Settle

给你两个整数 n 和 k 。 对于一个由 不同 正整数组成的数组，如果其中不存在任何求和等于 k 的不同元素对，则称其为 k-avoiding 数组。 返回长度为 n 的 k-avoiding 数组的可能的最小总和。 示例 1： 输入：n = 5, k = 4输出：18解释：设若 k-avoiding 数组为 [1,2,4,5,6] ，其元素总和为 18 。可以证明不存在总和小于 18 的 k-avoiding 数组。示例 2： 输入：n = 2, k = 6输出：3解释：可以构造数组 [1,2] ，其元素总和为 3 。可以证明不存在总和小于 3 的 k-avoiding 数组。 提示： 1 <= n, k <= 50 解法一：暴力遍历从1开始构造正整数数组，判断新增元素是否满足条件。 1234567891011121314151617class Solution: def minimumSum(self, n: int, k: int) -> int: result = [] ...

...

数组列表中的最大距离中等相关标签相关企业给定 m 个数组，每个数组都已经按照升序排好序了。 现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。 返回最大距离。 示例 1： 输入：[[1,2,3],[4,5],[1,2,3]]输出：4解释：一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1，同时从第二个数组中选择 5 。示例 2： 输入：arrays = [[1],[1]]输出：0 提示： m == arrays.length2 <= m <= 1051 <= arrays[i].length <= 500-104 <= arrays[i][j] <= 104arrays[i] 以 升序 排序。所有数组中最多有 105 个整数。 思路0：遍历每个数组，获取最大和最小值。遍历完后相减。 错原因：题目中要求不同数组。思路1: 遍历每个数组 ...

思路0：数组变为有序，依次放置，小球。最先两个球，放在首尾。然后用二分查找方式，查找中间小球放置的位置。中间位置查找标准为，距离首部或者尾部的球，引力最大，找到这个引力最大值的位置，就是这个小球的位置 1234567891011121314151617181920212223242526272829class Solution: def maxDistance(self, position: List[int], m: int) -> int: position.sort() n = len(position) left,right = 0,n-1 def bitsect(self,left,right): left,right = 0,n-1 while left<right: mid = (left+right)//2 if (position[mid]-position[left])...

1.直接遍历2.增加缓存3.使用hash 表存储每个数字的位置 bisect_left(a, x)： 在有序序列 a 中查找 x返回第一个大于等于 x 的元素位置如果所有元素都小于 x，返回 len(a)bisect_right(a, x)： 在有序序列 a 中查找 x返回第一个大于 x 的元素位置如果所有元素都小于等于 x，返回 len(a) 1234567891011121314151617181920212223class RangeFreqQuery: def __init__(self, arr: List[int]): self.list_dict = defaultdict(list) for i,num in enumerate(arr): self.list_dict[num].append(i) def query(self, left: int, right: int, value: int) -> int: if value not in self.list_dict：...

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

动态规划类题目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：构建数字和点数的映射 ...