????欢迎来到 我的博客 —— 探索技术的无限可能！
????博客的简介（文章目录）
【题解】—— 每日一道题目栏
上接：【题解】—— LeetCode一周小结42
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 场比赛的第一位玩家
题目链接：3175. 找到连续赢 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
题目链接：3180. 执行操作可获得的最大总奖励 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
题目链接：3181. 执行操作可获得的最大总奖励 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];
}
}
下接：【题解】—— LeetCode一周小结44