且听疯吟

leetcode weekly contest 316

2022-11-01

leetcode weekly contest 316

第三题和第四题还算有点意思，但是确实不太需要技巧的题目，只需要思考的题目即可。

6214. 判断两个事件是否存在冲突

题目

给你两个字符串数组 event1 和 event2 ，表示发生在同一天的两个闭区间时间段事件，其中：

  • event1 = [startTime1, endTime1] 且
  • event2 = [startTime2, endTime2]
    事件的时间为有效的 24 小时制且按 HH:MM 格式给出。

当两个事件存在某个非空的交集时（即，某些时刻是两个事件都包含的），则认为出现 冲突 。

如果两个事件之间存在冲突，返回 true ；否则，返回 false 。

示例 1：

输入：event1 = ["01:15","02:00"], event2 = ["02:00","03:00"]
输出：true
解释：两个事件在 2:00 出现交集。

示例 2：

输入：event1 = ["01:00","02:00"], event2 = ["01:20","03:00"]
输出：true
解释：两个事件的交集从 01:20 开始，到 02:00 结束。

示例 3：

输入：event1 = ["10:00","11:00"], event2 = ["14:00","15:00"]
输出：false
解释：两个事件不存在交集。

提示：

  • evnet1.length == event2.length == 2.
  • event1[i].length == event2[i].length == 5
  • startTime1 <= endTime1
  • startTime2 <= endTime2
  • 所有事件的时间都按照 HH:MM 格式给出

地址

https://leetcode.cn/contest/weekly-contest-316/problems/determine-if-two-events-have-conflict/

题意

数学

思路

  1. 我们直接将时间转换为分钟的区间 $[l,r]$, 此时即转换为检测两个区间是否存在交集，这就非常简单的判断即可。
  2. 复杂度分析：
  • 时间复杂度：$O(1)$。
  • 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int change(string &s) {
        int h = (s[0] - '0') * 10 + s[1] - '0';
        int m = (s[3] - '0') * 10 + s[4] - '0';
        return h * 60 + m;
    }
    bool haveConflict(vector<string>& event1, vector<string>& event2) {
        int s1 = change(event1[0]), t1 = change(event1[1]);
        int s2 = change(event2[0]), t2 = change(event2[1]);
        if (t1 < s2 || t2 < s1) {
            return false;
        } else {
            return true;
        }
    }
};

6224. 最大公因数等于 K 的子数组数目

题目

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。

子数组 是数组中一个连续的非空序列。

数组的最大公因数 是能整除数组中所有元素的最大整数。

示例 1：

输入：nums = [9,3,1,2,6,3], k = 3
输出：4
解释：nums 的子数组中，以 3 作为最大公因数的子数组如下：
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]

示例 2：

输入：nums = [4], k = 7
输出：0
解释：不存在以 7 作为最大公因数的子数组。

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i], k <= 109

地址

https://leetcode.cn/contest/weekly-contest-316/problems/number-of-subarrays-with-gcd-equal-to-k/

题意

遍历

思路

  1. 由于题目给定的数量太小，感觉直接可以遍历所有可能的连续子数组，并求出连续子数组的最大公约数即可。感觉毫无难度的题目。
  2. 复杂度分析：
  • 时间复杂度：时间复杂度为 $O(n^2)$，其中 $n$ 表示给定的数组的长度。
  • 空间复杂度：空间复杂度为 $O(1)$。

代码

class Solution {
public:
    int subarrayGCD(vector<int>& nums, int k) {
        int n = nums.size();
        int res = 0;
        for (int i = 0; i < nums.size(); i++) {
            int x = nums[i];
            for (int j = i; j < n; j++) {
                x = __gcd(x, nums[j]);
                if (x == k) {
                    res++;
                }
            }
        }
        return res;
    }
};

6216. 使数组相等的最小开销

题目

给你两个下标从 0 开始的数组 nums 和 cost ，分别包含 n 个 正 整数。

你可以执行下面操作 任意 次：

  • 将 nums 中 任意 元素增加或者减小 1 。
  • 对第 i 个元素执行一次操作的开销是 cost[i] 。

请你返回使 nums 中所有元素 相等 的 最少 总开销。

示例 1：

输入：nums = [1,3,5,2], cost = [2,3,1,14]
输出：8
解释：我们可以执行以下操作使所有元素变为 2 ：
- 增加第 0 个元素 1 次，开销为 2 。
- 减小第 1 个元素 1 次，开销为 3 。
- 减小第 2 个元素 3 次，开销为 1 + 1 + 1 = 3 。
总开销为 2 + 3 + 3 = 8 。
这是最小开销。

示例 2：

输入：nums = [2,2,2,2,2], cost = [4,2,8,1,3]
输出：0
解释：数组中所有元素已经全部相等，不需要执行额外的操作。

提示：

  • n == nums.length == cost.length
  • 1 <= n <= 105
  • 1 <= nums[i], cost[i] <= 106

地址

https://leetcode.cn/contest/weekly-contest-316/problems/minimum-cost-to-make-array-equal/

题意

前缀和 + 滑动窗口

思路

  1. 给某个题目非常相似的解法，只是稍微的变形即可，首先我们假设如果 $cost[i] = 1$ 时，此时题目则转换为了找到一个 $x$ 使得所有元素到 $x$ 的距离之和最小，而此时我们知道数组的中位数距离到所有元素的距离最小。当然我们可以很容易的证明最终重的元素相等一定可以为数组中的某个元素，这个就非常容易证明，再此不再描述，此时我们只需要遍历出将数组中的所有元素依次变为 $nums[i]$ 的最小变换操作次数即可。
  2. 根据上面的描述，此时我们需要用到前缀和的操作，首先我们需要将数组中的元素按照从小到大进行排序，设 $sum[i][j]$ 表示数组元素从 $i$ 到 $j$ 的开销之和，即 $sum[i][j] = \sum \limits {k=i}^{j}cost[k]$, 此时我们知道所有元素变为 $nums[0]$ 的代价为 $\sum \limits{i = 1}^{n-1}(nums[i] - nums[0])\times cost[i]$，此时假如目标位置移动到 $nums[1]$，此时右边减少的开销之和为 $sum[1][n-1] \times (nums[1] - nums[0])$，左边增加的开销为 $sum[0][0] \times (nums[1] - nums[0])$，此时总的开销变为 $\sum \limits_{i = 1}^{n-1}(nums[i] - nums[0])\times cost[i] - sum[1][n-1] \times (nums[1] - nums[0]) + sum[0][0] \times (nums[1] - nums[0])$，我们可以观察到向右移动到 $nums[i]$，则当前的开销增加的内容为 $sum[0][i-1] \times (nums[i] - nums[i-1]) - sum[i][n] \times (nums[i] - nums[i-1])$，我们依次向右滑动即可。
  3. 复杂度分析
  • 时间复杂度：时间复杂度为 $O(n \log n)$，$n$ 为数组的长度。
  • 空间复杂度：时间复杂度为 $O(n)$。

代码

class Solution {
public:
    long long minCost(vector<int>& nums, vector<int>& cost) {
        int n = nums.size();
        vector<pair<int, int>> arr;
        vector<long long> sum(n + 1);
        for (int i = 0; i < n; i++) {
            arr.emplace_back(nums[i], cost[i]);
        }
        sort(arr.begin(), arr.end());
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + arr[i].second;
        }
        long long curr = 0;
        long long ans = LONG_MAX;
        for (int i = 1; i < n; i++) {
            curr += (long long)(arr[i].first - arr[0].first) * arr[i].second;
        }
        ans = min(ans, curr);
        for (int i = 1; i < n; i++) {
            long long dist = arr[i].first - arr[i - 1].first;
            curr = curr - dist * (sum[n] - sum[i]) + sum[i] * dist;
            ans = min(ans, curr);
        }
        return ans;
    }
};

6217. 使数组相似的最少操作次数

题目

给你两个正整数数组 nums 和 target ，两个数组长度相等。

在一次操作中，你可以选择两个 不同 的下标 i 和 j ，其中 0 <= i, j < nums.length ，并且：

  • 令 nums[i] = nums[i] + 2 且
  • 令 nums[j] = nums[j] - 2 。
    如果两个数组中每个元素出现的频率相等，我们称两个数组是 相似 的。

请你返回将 nums 变得与 target 相似的最少操作次数。测试数据保证 nums 一定能变得与 target 相似。

示例 1：

输入：nums = [8,12,6], target = [2,14,10]
输出：2
解释：可以用两步操作将 nums 变得与 target 相似：
- 选择 i = 0 和 j = 2 ，nums = [10,12,4] 。
- 选择 i = 1 和 j = 2 ，nums = [10,14,2] 。
2 次操作是最少需要的操作次数。

示例 2：

输入：nums = [1,2,5], target = [4,1,3]
输出：1
解释：一步操作可以使 nums 变得与 target 相似：
- 选择 i = 1 和 j = 2 ，nums = [1,4,3] 。

示例 3：

输入：nums = [1,1,1,1,1], target = [1,1,1,1,1]
输出：0
解释：数组 nums 已经与 target 相似。

提示：

  • n == nums.length == target.length
  • 1 <= n <= 105
  • 1 <= nums[i], target[i] <= 106
  • nums 一定可以变得与 target 相似。

地址

https://leetcode.cn/contest/weekly-contest-316/problems/minimum-number-of-operations-to-make-arrays-similar/

题意

数学问题

思路

  1. 题目出的比较有想象力，仅需要基本的数学思考即可。首先我们观察一下题目，对应每个数 $nums[i]$ 它的变化只能为加 $2$ 或者减 $2$,这个就意味：
  • $nums[i]$ 如果为奇数，则其变化后仍然为奇数；
  • $nums[i]$ 如果为偶数，则其变化后仍然为偶数；
    根据题意可以知道 $nums$ 与 $target$ 中的奇数与偶数的数目肯定相等，要不然无法变为相似，首先如果在
  • 偶数范围内如果一个数需要变大或者变小，则我们需要在偶数或者奇数范围找到一个相应的数变小或者变大；
  • 奇数范围内如果一个数需要变大或者变小，则我们需要在奇数或者范围找到一个相应的数变小或者变大；
    按照题意要求的匹配规则，则将 $nums$ 与 $target$ 分别按照从小到大进行排序，根据贪心规则，$nums$ 中最小的元素应该变为 $target$ 中最小元素，否则变换的次数则并不为最小，由于我们知道所有的数字变大的次数与变小的次数一定相等，所有我们找到所有偶数部分中变大的次数与奇数部分中变大的次数之和即为最小的变换次数。
  1. 复杂度分析：
  • 时间复杂度：$O(n \log n)$，其中 $n$ 表示给定的数组的长度。
  • 空间复杂度：$O(n)$，其中 $n$ 表示给定的数组的长度。

代码

class Solution {
public:
    long long makeSimilar(vector<int>& nums, vector<int>& target) {
        int n = nums.size();
        long long res = 0;
        vector<int> arr1, arr2;
        vector<int> brr1, brr2;
        for (int i = 0; i < n; i++) {
            if (nums[i] % 2 == 0) {
                arr1.emplace_back(nums[i]);
            } else {
                arr2.emplace_back(nums[i]);
            }
            if (target[i] % 2 == 0) {
                brr1.emplace_back(target[i]);
            } else {
                brr2.emplace_back(target[i]);
            }
        }
        sort(arr1.begin(), arr1.end());
        sort(arr2.begin(), arr2.end());
        sort(brr1.begin(), brr1.end());
        sort(brr2.begin(), brr2.end());
        long long x = 0, y = 0;
        for (int i = 0; i < arr1.size(); i++) {
            if (arr1[i] < brr1[i]) {
                x += brr1[i] - arr1[i];
            }
        }
        for (int i = 0; i < arr2.size(); i++) {
            if (arr2[i] < brr2[i]) {
                y += brr2[i] - arr2[i];
            }
        }
        return (x + y) / 2;
    }
};

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

Tags: 力扣周赛
← leetcode biweekly contest 294 leetcode contest 312 →

扫描二维码，分享此文章