🌟欢迎来到 我的博客 —— 探索技术的无限可能！
14.鸡蛋掉落
题目链接：887. 鸡蛋掉落
给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
示例 1：
输入：k = 1, n = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。
如果它没碎，那么肯定能得出 f = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。
示例 2：
输入：k = 2, n = 6
输出：3
示例 3：
输入：k = 3, n = 14
输出：4
提示：
1 <= k <= 100
1 <= n <= 104
题解：
方法：递归搜索 + 保存递归返回值 = 记忆化搜索
class Solution { public int superEggDrop(int k, int n) { int[][] memo = new int[n + 1][]; for (int i = 1; ; i++) { memo[i] = new int[k + 1]; // 动态创建 memo if (dfs(i, k, memo) >= n) { return i; } } } private int dfs(int i, int j, int[][] memo) { if (i == 0 || j == 0) { return 0; } if (memo[i][j] != 0) { // 之前计算过 return memo[i][j]; } return memo[i][j] = dfs(i - 1, j, memo) + dfs(i - 1, j - 1, memo) + 1; } }
15.三角形的最大高度
题目链接：3200. 三角形的最大高度
给你两个整数 red 和 blue，分别表示红色球和蓝色球的数量。你需要使用这些球来组成一个三角形，满足第 1 行有 1 个球，第 2 行有 2 个球，第 3 行有 3 个球，依此类推。
每一行的球必须是 相同 颜色，且相邻行的颜色必须 不同。
返回可以实现的三角形的 最大 高度。
示例 1：
输入： red = 2, blue = 4
输出： 3
解释：
上图显示了唯一可能的排列方式。
示例 2：
输入： red = 2, blue = 1
输出： 2
解释：
上图显示了唯一可能的排列方式。
示例 3：
输入： red = 1, blue = 1
输出： 1
示例 4：
输入： red = 10, blue = 1
输出： 2
解释：
上图显示了唯一可能的排列方式。
提示：
1 <= red, blue <= 100
题解：
方法：枚举
class Solution { public int maxHeightOfTriangle(int red, int blue) { int[] cnt = new int[2]; for (int i = 1; ; i++) { cnt[i % 2] += i; if ((cnt[0] > red || cnt[1] > blue) && (cnt[0] > blue || cnt[1] > red)) { return i - 1; } } } }
16.最小元素和最大元素的最小平均值
你有一个初始为空的浮点数数组 averages。另给你一个包含 n 个整数的数组 nums，其中 n 为偶数。
你需要重复以下步骤 n / 2 次：
从 nums 中移除 最小 的元素 minElement 和 最大 的元素 maxElement。
将 (minElement + maxElement) / 2 加入到 averages 中。
返回 averages 中的 最小 元素。
示例 1：
输入： nums = [7,8,3,4,15,13,4,1]
输出： 5.5
解释：
| 步骤 | nums | averages |
| 0 | [7,8,3,4,15,13,4,1] | [] |
| 1 | [7,8,3,4,13,4] | [8] |
| 2 | [7,8,4,4] | [8,8] |
| 3 | [7,4] | [8,8,6] |
| 4 | [] | [8,8,6,5.5] |
返回 averages 中最小的元素，即 5.5。
示例 2：
输入： nums = [1,9,8,3,10,5]
输出： 5.5
解释：
| 步骤 | nums | averages |
| 0 | [1,9,8,3,10,5] | [] |
| 1 | [9,8,3,5] | [5.5] |
| 2 | [8,5] | [5.5,6] |
| 3 | [] | [5.5,6,6.5] |
示例 3：
输入： nums = [1,2,3,7,8,9]
输出： 5.0
解释：
| 步骤 | nums | averages |
| 0 | [1,2,3,7,8,9] | [] |
| 1 | [2,3,7,8] | [5] |
| 2 | [3,7] | [5,5] |
| 3 | [] | [5,5,5] |
提示：
2 <= n == nums.length <= 50
n 为偶数。
1 <= nums[i] <= 50
题解：
方法：排序+遍历
class Solution { public double minimumAverage(int[] nums) { Arrays.sort(nums); int ans = Integer.MAX_VALUE; int n = nums.length; for (int i = 0; i < n / 2; i++) { ans = Math.min(ans, nums[i] + nums[n - 1 - i]); } return ans / 2.0; } }
17.统计逆序对的数目
题目链接：3193. 统计逆序对的数目
给你一个整数 n 和一个二维数组 requirements ，其中 requirements[i] = [endi, cnti] 表示这个要求中的末尾下标和 逆序对 的数目。
整数数组 nums 中一个下标对 (i, j) 如果满足以下条件，那么它们被称为一个 逆序对 ：
i < j 且 nums[i] > nums[j]
请你返回 [0, 1, 2, …, n - 1] 的
排列
perm 的数目，满足对 所有 的 requirements[i] 都有 perm[0…endi] 恰好有 cnti 个逆序对。
由于答案可能会很大，将它对 109 + 7 取余 后返回。
示例 1：
输入：n = 3, requirements = [[2,2],[0,0]]
输出：2
解释：
两个排列为：
[2, 0, 1]
前缀 [2, 0, 1] 的逆序对为 (0, 1) 和 (0, 2) 。
前缀 [2] 的逆序对数目为 0 个。
[1, 2, 0]
前缀 [1, 2, 0] 的逆序对为 (0, 2) 和 (1, 2) 。
前缀 [1] 的逆序对数目为 0 个。
示例 2：
输入：n = 3, requirements = [[2,2],[1,1],[0,0]]
输出：1
解释：
唯一满足要求的排列是 [2, 0, 1] ：
前缀 [2, 0, 1] 的逆序对为 (0, 1) 和 (0, 2) 。
前缀 [2, 0] 的逆序对为 (0, 1) 。
前缀 [2] 的逆序对数目为 0 。
示例 3：
输入：n = 2, requirements = [[0,0],[1,0]]
输出：1
解释：
唯一满足要求的排列为 [0, 1] ：
前缀 [0] 的逆序对数目为 0 。
前缀 [0, 1] 的逆序对为 (0, 1) 。
提示：
2 <= n <= 300
1 <= requirements.length <= n
requirements[i] = [endi, cnti]
0 <= endi <= n - 1
0 <= cnti <= 400
输入保证至少有一个 i 满足 endi == n - 1 。
输入保证所有的 endi 互不相同。
题解：
方法：递归
class Solution { public int numberOfPermutations(int n, int[][] requirements) { final int MOD = 1_000_000_007; int[] req = new int[n]; Arrays.fill(req, -1); req[0] = 0; int m = 0; for (int[] p : requirements) { req[p[0]] = p[1]; m = Math.max(m, p[1]); } if (req[0] > 0) { return 0; } int[] f = new int[m + 1]; f[0] = 1; for (int i = 1; i < n; i++) { int mx = req[i] < 0 ? m : req[i]; int r = req[i - 1]; if (r >= 0) { Arrays.fill(f, 0, r, 0); Arrays.fill(f, r + 1, Math.min(i + r, mx) + 1, f[r]); Arrays.fill(f, Math.min(i + r, mx) + 1, m + 1, 0); } else { for (int j = 1; j <= mx; j++) { // 计算前缀和 f[j] = (f[j] + f[j - 1]) % MOD; } for (int j = mx; j > i; j--) { // 计算子数组和 f[j] = (f[j] - f[j - i - 1] + MOD) % MOD; } } } return f[req[n - 1]]; } }
18.使二进制数组全部等于 1 的最少操作次数 I
题目链接：3191. 使二进制数组全部等于 1 的最少操作次数 I
给你一个二进制数组 nums 。
你可以对数组执行以下操作 任意 次（也可以 0 次）：
选择数组中 任意连续 3 个元素，并将它们 全部反转 。
反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。
请你返回将 nums 中所有元素变为 1 的 最少 操作次数。如果无法全部变成 1 ，返回 -1 。
示例 1：
输入：nums = [0,1,1,1,0,0]
输出：3
解释： 我们可以执行以下操作：
选择下标为 0 ，1 和 2 的元素并反转，得到 nums = [1,0,0,1,0,0] 。
选择下标为 1 ，2 和 3 的元素并反转，得到 nums = [1,1,1,0,0,0] 。
选择下标为 3 ，4 和 5 的元素并反转，得到 nums = [1,1,1,1,1,1] 。
示例 2：
输入：nums = [0,1,1,1]
输出：-1
解释：
无法将所有元素都变为 1 。
提示：
3 <= nums.length <= 105
0 <= nums[i] <= 1
题解：
方法：位运算 贪心
class Solution { public int minOperations(int[] nums) { int n = nums.length; int ans = 0; for (int i = 0; i < n - 2; i++) { if (nums[i] == 0) { // 必须操作 nums[i + 1] ^= 1; nums[i + 2] ^= 1; ans++; } } return nums[n - 2] != 0 && nums[n - 1] != 0 ? ans : -1; } }
19.使二进制数组全部等于 1 的最少操作次数 II
题目链接：3192. 使二进制数组全部等于 1 的最少操作次数 II
给你一个二进制数组 nums 。
你可以对数组执行以下操作 任意 次（也可以 0 次）：
选择数组中 任意 一个下标 i ，并将从下标 i 开始一直到数组末尾 所有 元素 反转 。
反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。
请你返回将 nums 中所有元素变为 1 的 最少 操作次数。
示例 1：
输入：nums = [0,1,1,0,1]
输出：4
解释：
我们可以执行以下操作：
选择下标 i = 1 执行操作，得到 nums = [0,0,0,1,0] 。
选择下标 i = 0 执行操作，得到 nums = [1,1,1,0,1] 。
选择下标 i = 4 执行操作，得到 nums = [1,1,1,0,0] 。
选择下标 i = 3 执行操作，得到 nums = [1,1,1,1,1] 。
示例 2：
输入：nums = [1,0,0,0]
输出：1
解释：
我们可以执行以下操作：
选择下标 i = 1 执行操作，得到 nums = [1,1,1,1] 。
提示：
1 <= nums.length <= 105
0 <= nums[i] <= 1
题解：
方法：比较相邻元素
class Solution { public int minOperations(int[] nums) { int ans = nums[0] ^ 1; for (int i = 1; i < nums.length; i++) { ans += nums[i - 1] ^ nums[i]; } return ans; } }
20.最小差值 I
题目链接：908. 最小差值 I
给你一个整数数组 nums，和一个整数 k 。
在一个操作中，您可以选择 0 <= i < nums.length 的任何索引 i 。将 nums[i] 改为 nums[i] + x ，其中 x 是一个范围为 [-k, k] 的任意整数。对于每个索引 i ，最多 只能 应用 一次 此操作。
nums 的 分数 是 nums 中最大和最小元素的差值。
在对 nums 中的每个索引最多应用一次上述操作后，返回 nums 的最低 分数 。
示例 1：
输入：nums = [1], k = 0
输出：0
解释：分数是 max(nums) - min(nums) = 1 - 1 = 0。
示例 2：
输入：nums = [0,10], k = 2
输出：6
解释：将 nums 改为 [2,8]。分数是 max(nums) - min(nums) = 8 - 2 = 6。
示例 3：
输入：nums = [1,3,6], k = 3
输出：0
解释：将 nums 改为 [4,4,4]。分数是 max(nums) - min(nums) = 4 - 4 = 0。
提示：
1 <= nums.length <= 104
0 <= nums[i] <= 104
0 <= k <= 104
题解：
方法：图
class Solution { public int smallestRangeI(int[] nums, int k) { int mn = nums[0]; int mx = nums[0]; for (int x : nums) { mn = Math.min(mn, x); mx = Math.max(mx, x); } return Math.max(mx - mn - 2 * k, 0); } }
