当前位置： 首页 > article >正文

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

article 2024/10/28 7:47:28

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


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

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

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


http://www.kler.cn/news/368416.html

相关文章：

  • pytorh学习笔记——cifar10（六）MobileNet V1网络结构
  • OpenIPC开源FPV之Ardupilot配置
  • 2025考研各省市网上确认时间汇总！
  • python kafka 发送/接收 消息
  • 基于丑萌气质狗--C#的sqlserver学习
  • Linux - 文件描述符 | 文件系统 | 软硬链接
  • 《BLEU: a Method for Automatic Evaluation of Machine Translation》翻译
  • 数据库如何保证主键唯一性
  • Python如何处理zip压缩文件（Python处理zip压缩文件接口源码）
  • ES6面试题：（第二天）
  • 如何使用git上传项目至github。记一次上传github经历
  • Spring IoC DI
  • 基于NERF技术重建学习笔记
  • 算法 - 高精度算法(加减乘除)
  • 计算结构体及其中元素的大小
  • LeetCode Hot 100：二叉树
  • Face Swap API 的整合与使用手册
  • 【jvm】堆的内部结构
  • 【笔记】记一次因Spring版本和Tomcat版本不对应，造成Spring MVC项目启动后页面访问报404的问题
  • 动态规划-子序列问题——1218.最长定差子序列
  • Linux 进程间通信_匿名管道
  • 【c++丨STL】string模拟实现（附源码）
  • 智慧商城项目5-订单结算以及mixins混入与打包
  • vue3父组件控制子组件表单验证及获取子组件数值方法
  • Linux系统下串口AT指令控制EC20连接华为云物联网平台
  • 使用 docker 的方式部署 NFS server 提供文件共享能力