🌟欢迎来到 我的博客 —— 探索技术的无限可能！
21.最小差值 II
题目链接：910. 最小差值 II
给你一个整数数组 nums，和一个整数 k 。
对于每个下标 i（0 <= i < nums.length），将 nums[i] 变成 nums[i] + k 或 nums[i] - k 。
nums 的 分数 是 nums 中最大元素和最小元素的差值。
在更改每个下标对应的值之后，返回 nums 的最小 分数 。
示例 1：
输入：nums = [1], k = 0
输出：0
解释：分数 = max(nums) - min(nums) = 1 - 1 = 0 。
示例 2：
输入：nums = [0,10], k = 2
输出：6
解释：将数组变为 [2, 8] 。分数 = max(nums) - min(nums) = 8 - 2 = 6 。
示例 3：
输入：nums = [1,3,6], k = 3
输出：3
解释：将数组变为 [4, 6, 3] 。分数 = max(nums) - min(nums) = 6 - 3 = 3 。
提示：
1 <= nums.length <= 104
0 <= nums[i] <= 104
0 <= k <= 104
题解：
方法：贪心 枚举 排序
class Solution { public int smallestRangeII(int[] nums, int k) { Arrays.sort(nums); int n = nums.length; int ans = nums[n - 1] - nums[0]; for (int i = 1; i < n; i++) { int mx = Math.max(nums[i - 1] + k, nums[n - 1] - k); int mn = Math.min(nums[0] + k, nums[i] - k); ans = Math.min(ans, mx - mn); } return ans; } }
22.构成整天的下标对数目 I
题目链接：3184. 构成整天的下标对数目 I
给你一个整数数组 hours，表示以 小时 为单位的时间，返回一个整数，表示满足 i < j 且 hours[i] + hours[j] 构成 整天 的下标对 i, j 的数目。
整天 定义为时间持续时间是 24 小时的 整数倍 。
例如，1 天是 24 小时，2 天是 48 小时，3 天是 72 小时，以此类推。
示例 1：
输入： hours = [12,12,30,24,24]
输出： 2
解释：
构成整天的下标对分别是 (0, 1) 和 (3, 4)。
示例 2：
输入： hours = [72,48,24,3]
输出： 3
解释：
构成整天的下标对分别是 (0, 1)、(0, 2) 和 (1, 2)。
提示：
1 <= hours.length <= 100
1 <= hours[i] <= 109
题解：
方法：数组
class Solution { public long countCompleteDayPairs(int[] hours) { final int H = 24; long ans = 0; int[] cnt = new int[H]; for (int t : hours) { // 先查询 cnt，再更新 cnt，因为题目要求 i < j // 如果先更新，再查询，就把 i = j 的情况也考虑进去了 ans += cnt[(H - t % H) % H]; cnt[t % H]++; } return ans; } }
23.构成整天的下标对数目 II
题目链接：3185. 构成整天的下标对数目 II
给你一个整数数组 hours，表示以 小时 为单位的时间，返回一个整数，表示满足 i < j 且 hours[i] + hours[j] 构成 整天 的下标对 i, j 的数目。
整天 定义为时间持续时间是 24 小时的 整数倍 。
例如，1 天是 24 小时，2 天是 48 小时，3 天是 72 小时，以此类推。
示例 1：
输入： hours = [12,12,30,24,24]
输出： 2
解释：
构成整天的下标对分别是 (0, 1) 和 (3, 4)。
示例 2：
输入： hours = [72,48,24,3]
输出： 3
解释：
构成整天的下标对分别是 (0, 1)、(0, 2) 和 (1, 2)。
提示：
1 <= hours.length <= 5 * 105
1 <= hours[i] <= 109
题解：
方法：数组
class Solution { public long countCompleteDayPairs(int[] hours) { final int H = 24; long ans = 0; int[] cnt = new int[H]; for (int t : hours) { // 先查询 cnt，再更新 cnt，因为题目要求 i < j // 如果先更新，再查询，就把 i = j 的情况也考虑进去了 ans += cnt[(H - t % H) % H]; cnt[t % H]++; } return ans; } }
24.找到连续赢 K 场比赛的第一位玩家
有 n 位玩家在进行比赛，玩家编号依次为 0 到 n - 1 。
给你一个长度为 n 的整数数组 skills 和一个 正 整数 k ，其中 skills[i] 是第 i 位玩家的技能等级。skills 中所有整数 互不相同 。
所有玩家从编号 0 到 n - 1 排成一列。
比赛进行方式如下：
队列中最前面两名玩家进行一场比赛，技能等级 更高 的玩家胜出。
比赛后，获胜者保持在队列的开头，而失败者排到队列的末尾。
这个比赛的赢家是 第一位连续 赢下 k 场比赛的玩家。
请你返回这个比赛的赢家编号。
示例 1：
输入：skills = [4,2,6,3,9], k = 2
输出：2
解释：
一开始，队列里的玩家为 [0,1,2,3,4] 。比赛过程如下：
玩家 0 和 1 进行一场比赛，玩家 0 的技能等级高于玩家 1 ，玩家 0 胜出，队列变为 [0,2,3,4,1] 。
玩家 0 和 2 进行一场比赛，玩家 2 的技能等级高于玩家 0 ，玩家 2 胜出，队列变为 [2,3,4,1,0] 。
玩家 2 和 3 进行一场比赛，玩家 2 的技能等级高于玩家 3 ，玩家 2 胜出，队列变为 [2,4,1,0,3] 。
玩家 2 连续赢了 k = 2 场比赛，所以赢家是玩家 2 。
示例 2：
输入：skills = [2,5,4], k = 3
输出：1
解释：
一开始，队列里的玩家为 [0,1,2] 。比赛过程如下：
玩家 0 和 1 进行一场比赛，玩家 1 的技能等级高于玩家 0 ，玩家 1 胜出，队列变为 [1,2,0] 。
玩家 1 和 2 进行一场比赛，玩家 1 的技能等级高于玩家 2 ，玩家 1 胜出，队列变为 [1,0,2] 。
玩家 1 和 0 进行一场比赛，玩家 1 的技能等级高于玩家 0 ，玩家 1 胜出，队列变为 [1,2,0] 。
玩家 1 连续赢了 k = 3 场比赛，所以赢家是玩家 1 。
提示：
n == skills.length
2 <= n <= 105
1 <= k <= 109
1 <= skills[i] <= 106
skills 中的整数互不相同。
题解：
方法：脑筋急转弯
class Solution { public int findWinningPlayer(int[] skills, int k) { int n = skills.length; k = Math.min(k, n - 1); int i = 0, cnt = 0; for (int j = 1; j < n; ++j) { if (skills[i] < skills[j]) { i = j; cnt = 1; } else { ++cnt; } if (cnt == k) { break; } } return i; } }
25.执行操作可获得的最大总奖励 I
给你一个整数数组 rewardValues，长度为 n，代表奖励的值。
最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：
从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。
以整数形式返回执行最优操作能够获得的 最大 总奖励。
示例 1：
输入：rewardValues = [1,1,3,3]
输出：4
解释：
依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。
示例 2：
输入：rewardValues = [1,6,4,3,2]
输出：11
解释：
依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。
提示：
1 <= rewardValues.length <= 2000
1 <= rewardValues[i] <= 2000
题解：
方法：排序 记忆化搜索 二分查找
class Solution { private int[] nums; private Integer[] f; public int maxTotalReward(int[] rewardValues) { nums = rewardValues; Arrays.sort(nums); int n = nums.length; f = new Integer[nums[n - 1] << 1]; return dfs(0); } private int dfs(int x) { if (f[x] != null) { return f[x]; } int i = Arrays.binarySearch(nums, x + 1); i = i < 0 ? -i - 1 : i; int ans = 0; for (; i < nums.length; ++i) { ans = Math.max(ans, nums[i] + dfs(x + nums[i])); } return f[x] = ans; } }
26.执行操作可获得的最大总奖励 II
给你一个整数数组 rewardValues，长度为 n，代表奖励的值。
最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：
从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。
以整数形式返回执行最优操作能够获得的 最大 总奖励。
示例 1：
输入：rewardValues = [1,1,3,3]
输出：4
解释：
依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。
示例 2：
输入：rewardValues = [1,6,4,3,2]
输出：11
解释：
依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。
提示：
1 <= rewardValues.length <= 5 * 104
1 <= rewardValues[i] <= 5 * 104
题解：
方法：动态规划 位运算
import java.math.BigInteger; import java.util.Arrays; class Solution { public int maxTotalReward(int[] rewardValues) { int[] nums = Arrays.stream(rewardValues).distinct().sorted().toArray(); BigInteger f = BigInteger.ONE; for (int v : nums) { BigInteger mask = BigInteger.ONE.shiftLeft(v).subtract(BigInteger.ONE); BigInteger shifted = f.and(mask).shiftLeft(v); f = f.or(shifted); } return f.bitLength() - 1; } }
27.冗余连接
题目链接：684. 冗余连接
树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。
示例 1：
输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]
示例 2：
输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
提示:
n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
edges 中无重复元素
给定的图是连通的
题解：
方法：并查集
class Solution { private int[] p; public int[] findRedundantConnection(int[][] edges) { int n = edges.length; p = new int[n]; for (int i = 0; i < n; ++i) { p[i] = i; } for (int i = 0;; ++i) { int pa = find(edges[i][0] - 1); int pb = find(edges[i][1] - 1); if (pa == pb) { return edges[i]; } p[pa] = pb; } } private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } }
