且听疯吟

leetcode contest 342

2023-04-23

leetcode contest 342

这场周赛算是最近比较简单的周赛了。

6387. 计算列车到站时间

给你一个正整数 arrivalTime 表示列车正点到站的时间（单位：小时），另给你一个正整数 delayedTime 表示列车延误的小时数。

返回列车实际到站的时间。

注意，该问题中的时间采用 24 小时制。

示例 1：

输入：arrivalTime = 15, delayedTime = 5 
输出：20 
解释：列车正点到站时间是 15:00 ，延误 5 小时，所以列车实际到站的时间是 15 + 5 = 20（20:00）。

示例 2：

输入：arrivalTime = 13, delayedTime = 11
输出：0
解释：列车正点到站时间是 13:00 ，延误 11 小时，所以列车实际到站的时间是 13 + 11 = 24（在 24 小时制中表示为 00:00 ，所以返回 0）。

提示：

  • 1 <= arrivaltime < 24
  • 1 <= delayedTime <= 24

地址

https://leetcode.cn/contest/weekly-contest-342/problems/calculate-delayed-arrival-time/

题意

直接枚举

思路

  1. 直接计算即可，感觉是最简单的题目了。
  2. 复杂度分析：
  • 时间复杂度：$O(1)$。
  • 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int findDelayedArrivalTime(int arrivalTime, int delayedTime) {
        return (arrivalTime + delayedTime) % 24;
    }
};

6391. 倍数求和

给你一个正整数 n ，请你计算在 [1，n] 范围内能被 3、5、7 整除的所有整数之和。

返回一个整数，用于表示给定范围内所有满足约束条件的数字之和。

示例 1：

输入：n = 7
输出：21
解释：在 [1, 7] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7 。数字之和为 21 。

示例 2：

输入：n = 10
输出：40
解释：在 [1, 10] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7、9、10 。数字之和为 40 。

示例 3：

输入：n = 9
输出：30
解释：在 [1, 9] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7、9 。数字之和为 30 。

提示：

  • 1 <= n <= 103

地址

https://leetcode.cn/contest/weekly-contest-342/problems/sum-multiples/

题意

暴力枚举

思路

  1. 题目太简单了，直接枚举从 $1$ 到 $n$ 之间可以被 $3,5,7$ 其中任意一个元素整除的元素。另外可以通过容斥定理计算也可以。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 为给定的元素。
  • 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int sumOfMultiples(int n) {
        int res = 0;
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0) {
                res += i;
            } else if (i % 5 == 0) {
                res += i;
            } else if (i % 7 == 0) {
                res += i;
            }
        }
        return res;
    }
};

6390. 滑动子数组的美丽值

给你一个长度为 n 的整数数组 nums ，请你求出每个长度为 k 的子数组的 美丽值 。

一个子数组的 美丽值 定义为：如果子数组中第 x 小整数 是 负数 ，那么美丽值为第 x 小的数，否则美丽值为 0 。

请你返回一个包含 n - k + 1 个整数的数组，依次 表示数组中从第一个下标开始，每个长度为 k 的子数组的 美丽值 。

  • 子数组指的是数组中一段连续 非空 的元素序列。

示例 1：

输入：nums = [1,-1,-3,-2,3], k = 3, x = 2
输出：[-1,-2,-2]
解释：总共有 3 个 k = 3 的子数组。
第一个子数组是 [1, -1, -3] ，第二小的数是负数 -1 。
第二个子数组是 [-1, -3, -2] ，第二小的数是负数 -2 。
第三个子数组是 [-3, -2, 3] ，第二小的数是负数 -2 。

示例 2：

输入：nums = [-1,-2,-3,-4,-5], k = 2, x = 2
输出：[-1,-2,-3,-4]
解释：总共有 4 个 k = 2 的子数组。
[-1, -2] 中第二小的数是负数 -1 。
[-2, -3] 中第二小的数是负数 -2 。
[-3, -4] 中第二小的数是负数 -3 。
[-4, -5] 中第二小的数是负数 -4 。

示例 3：

输入：nums = [-3,1,2,-3,0,-3], k = 2, x = 1
输出：[-3,0,-3,-3,-3]
解释：总共有 5 个 k = 2 的子数组。
[-3, 1] 中最小的数是负数 -3 。
[1, 2] 中最小的数不是负数，所以美丽值为 0 。
[2, -3] 中最小的数是负数 -3 。
[-3, 0] 中最小的数是负数 -3 。
[0, -3] 中最小的数是负数 -3 。

提示：

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= k <= n
  • 1 <= x <= k
  • -50 <= nums[i] <= 50

地址

https://leetcode.cn/contest/weekly-contest-342/problems/sliding-subarray-beauty/

题意

滑动窗口

思路

  1. 题目的关键在于给定的整数的大小只有 $[-50, 50]$，此时我们可以将每个元素都加上 $50$，则每个元素的范围为 $[0,100]$。此时即转换为可变换的元素了，我们将用数组来统计每个元素的出现的次数，每次滑动窗口时，我们只统计窗口的元素出现的个数，此时我们很快即可在 $[0,100]$ 的区间内找到窗口排名为 $x$ 的元素，此时：
  • 如果排名为 $x$ 的元素大于 $50$，则我们直接记为 $0$；
  • 如果排名为 $x$ 的元素小于 $50$，则我们直接记为 $50 - value$；
  1. 复杂度分析：
  • 时间复杂度：$O(nU)$，其中 $n$ 为数组的长度， $U$ 表示数组中的最大元素。
  • 空间复杂度：$O(U)$，其中 $n$ 为数组的长度， $U$ 表示数组中的最大元素。

代码

class Solution {
public:
    vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
        int n = nums.size();
        vector<int> res;
        vector<int> cnt(101);
        for (int i = 0; i < n; i++) {
            cnt[nums[i] + 50]++;
            int tot = 0;
            if (i >= k - 1) {
                for (int j = 0; j <= 100; j++) {
                    if (tot <= x && tot + cnt[j] >= x) {
                        if (j < 50) {
                            res.emplace_back(j - 50);
                        } else {
                            res.emplace_back(0);
                        }
                        break;
                    }
                    tot += cnt[j];
                }
                cnt[nums[i - k + 1] + 50]--;
            }
        }
        return res;
    }
};

6392. 使数组所有元素变成 1 的最少操作次数

给你一个下标从 0 开始的 正 整数数组 nums 。你可以对数组执行以下操作 任意 次：

  • 选择一个满足 0 <= i < n - 1 的下标 i ，将 nums[i] 或者 nums[i+1] 两者之一替换成它们的最大公约数。

请你返回使数组 nums 中所有元素都等于 1 的 最少 操作次数。如果无法让数组全部变成 1 ，请你返回 -1 。

两个正整数的最大公约数指的是能整除这两个数的最大正整数。

示例 1：

输入：nums = [2,6,3,4]
输出：4
解释：我们可以执行以下操作：
- 选择下标 i = 2 ，将 nums[2] 替换为 gcd(3,4) = 1 ，得到 nums = [2,6,1,4] 。
- 选择下标 i = 1 ，将 nums[1] 替换为 gcd(6,1) = 1 ，得到 nums = [2,1,1,4] 。
- 选择下标 i = 0 ，将 nums[0] 替换为 gcd(2,1) = 1 ，得到 nums = [1,1,1,4] 。
- 选择下标 i = 2 ，将 nums[3] 替换为 gcd(1,4) = 1 ，得到 nums = [1,1,1,1] 。

示例 2：

输入：nums = [2,10,6,14]
输出：-1
解释：无法将所有元素都变成 1 。

提示：

  • 2 <= nums.length <= 50
  • 1 <= nums[i] <= 106

地址

https://leetcode.cn/contest/weekly-contest-342/problems/minimum-number-of-operations-to-make-all-array-elements-equal-to-1/

题意

数学

思路

  1. 题目其实挺简单的，我们仔细观察一下即可发现：
  • 如果题目中存在 $1$ 个 $1$，此时剩余所有的元素都与 $1$ 计算并替换为 $1$，此时需要 $n-1$ 次替换即可；
  • 如果数组所有元素的最大公约数大于 $1$，则一定不可能将数组中的某个元素变为 $1$；
  • 本质上如果我们能够找到最少的操作方法将其中某个元素变为 $1$，则剩余的元素还需要 $n-1$ 次操作即可将其变为 $1$，如果能够将某个元素变为 $1$，如果连续的 $m$ 个元素的最大公约数为 $1$，此时我们一定可以通过 $m$ 次操作将其中一个元素变为 $1$；
  • 已经变为 $1$ 的元素我们可以将其剔除掉；
  1. 复杂度分析：
  • 时间复杂度：$O(n^2)$，其中 $n$ 为数组的元素的数目；
  • 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        int val = nums[0];
        for (auto v : nums) {
            val = __gcd(val, v);
        }
        if (val > 1) {
            return -1;
        }
        vector<int> arr;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 1) {
                arr.emplace_back(i);
            }
        }
        if (arr.size() > 0) {
            return n - arr.size();
        }
        int tot = n;
        for (int i = 0; i < n; i++) {
            int val = nums[i];
            for (int j = i; j < n; j++) {
                val = __gcd(val, nums[j]);
                if (val == 1) {
                    tot = min(tot, j - i);
                    break;
                }
            }
        }
        return tot + n - 1;
    }
};

欢迎关注和打赏，感谢支持！

Tags: 力扣周赛 题解
← leetcode contest 340 leetcode spring LCCUP →

扫描二维码，分享此文章