【题解】—— LeetCode一周小结43

🌟欢迎来到 我的博客 —— 探索技术的无限可能！

🌟博客的简介（文章目录）

---

【题解】—— 每日一道题目栏

---

上接：【题解】—— 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

---