LeetCode 316 周赛

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

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

• event1 = [startTime1, endTime1] 且
• event2 = [startTime2, endTime2]

事件的时间为有效的 24 小时制且按 HH:MM 格式给出。

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

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

示例

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

思路

就是求两个区间是否相交。周赛当天我的做法是，将HH:MM的时间归一化为当天的第X分钟，于是某一时刻HH:MM就能用一个数字表示，于是就变成了简单的求两个区间是否相交的问题。

C++：

// C++
class Solution {
public:int parse(string& s) {int h = stoi(s.substr(0, 2));int m = stoi(s.substr(3));return h * 60 + m;}bool haveConflict(vector<string>& event1, vector<string>& event2) {int s1 = parse(event1[0]), e1 = parse(event1[1]);int s2 = parse(event2[0]), e2 = parse(event2[1]);return max(s1, s2) <= min(e1, e2);}
};

Java：

// Java
class Solution {int parse(String s) {String[] ss = s.split(":");return 60 * Integer.parseInt(ss[0]) + Integer.parseInt(ss[1]);}public boolean haveConflict(String[] event1, String[] event2) {int s1 = parse(event1[0]), e1 = parse(event1[1]);int s2 = parse(event2[0]), e2 = parse(event2[1]);// [s1, e1]// [s2, e2]return Math.max(s1, s2) <= Math.min(e1, e2);}
}

其实也可以不用将字符串转化为数字进行比较。这道题目的数据格式，字符串的字典序大小关系，和对应的数字的大小关系是一致的。

// C++
class Solution {
public:bool haveConflict(vector<string>& event1, vector<string>& event2) {string s = max(event1[0], event2[0]);string e = min(event1[1], event2[1]);return s <= e;}
};

// Java
class Solution {public boolean haveConflict(String[] event1, String[] event2) {String s = event1[0].compareTo(event2[0]) > 0 ? event1[0] : event2[0];String e = event1[1].compareTo(event2[1]) < 0 ? event1[1] : event2[1];return s.compareTo(e) <= 0;}
}

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

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

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

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

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i], k <= 10^9

示例

输入：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]

思路

一个子数组中所有元素的最大公因数等于k，含义是：这个子数组中的全部元素，都是k的倍数，并且这些数的最大公约数是k。周赛当天我的想法是，既然都是k的倍数，那我把全部数都先除以个k，那么满足条件的子数组，一定满足如下的性质：

• 子数组中所有元素都不为0
• 子数组中全部数的最大公约数是1

其实这个是否把所有数都除以k，没什么太大区别，如果不除以k的话，子数组需要满足如下性质

• 子数组中所有元素都是k的倍数
• 子数组中全部数的最大公约数是k

此时看了眼这道题的数据范围，n只有1000，那么暴力枚举全部子数组，需要10^6，而每次判断子数组是否满足条件，只需要求个gcd，而gcd的时间复杂度大概在 $O(logn)$级别，那么是不会超时的。并且，我们在枚举子数组的过程中，如果中间遇到了某个元素使得上述2个条件不能满足，则可以提前退出该轮循环，因为子数组要求必须连续，所以暴力法是可以做的。

暴力法的时间复杂度为 $O(n\times (n+logU))$，外层循环是n，内层循环是求n个数的最大公约数。注意求n个数的最大公约数的时间复杂度为 $O(n+logU)$，U是n个数中的最大值。注意并不是 $O(nlogU)$。（至于为什么还没搞清楚）

C++：

// C++ 8ms 还挺快
class Solution {
public:int gcd(int a, int b) {return !b ? a : gcd(b, a % b);}int subarrayGCD(vector<int>& nums, int k) {int n = nums.size(), ans = 0;// 枚举全部的子数组for (int i = 0; i < n; i++) {// 枚举所有左端点为i的子数组if (nums[i] % k != 0) continue; // 如果第一个位置都不是k的倍数, 直接跳过, 其实这一行也可以不写int g = 0;for (int j = i; j < n; j++) {if (nums[j] % k != 0) break; // 从这里断掉了, 后面的不用枚举了,因为子数组必须连续g = gcd(nums[j], g); // 更新一下[i, j]所有数的最大公约数if (g == k) ans++; // 找到一个满足条件的子数组}}return ans;}
};

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

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

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

• 将 nums 中 任意 元素增加或者减小 1 。

对第 i 个元素执行一次操作的开销是 cost[i] 。

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

提示：

• n == nums.length == cost.length
• 1 <= n <= 10^5
• 1 <= nums[i], cost[i] <= 10^6

示例

输入：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 。
这是最小开销。

思路

中位数贪心/枚举

可以先把nums的所有数字从小到大排个序，因为我们操作的最终结果，是使所有数都相等，不妨设最终的这个数为x，那么所有的数最后都要变成x。我们来考虑x的取值。假设nums从小到大排好序后是：[1,2,3,5,9,11,20]，绘制一个折线图如下

我们考虑最终的x是否一定能取到nums中的某个值。假设x不是nums中的某个值。假设x = 8，将每个元素大小到x的距离设为di，每个元素操作一次的代价为ci

< x的元素共有4个，大于x的元素有3个。

小于x的元素全部变为x的总代价是：d1 * c1 + d2 * c2 + d3 * c3 + d4 * c4

大于x的元素全部变为x的总代价是：d5 * c5 + d6 * c6 + d7 * c7

我们尝试把x变小，让他与相邻最近的nums[4]相等，设x与下面的nums[4]的距离为d，那么看看将x变小为nums[4]时，对总的代价会有什么变化。

首先对于左侧小于x的元素，因为距离变得近了，其总代价会变少，变少了这么多：d * (c1 + c2 + c3 + c4)

对于右侧大于x的元素，其总代价会变多，变多了这么多：d * (c5 + c6 + c7)

我们设c1 + c2 + c3 + c4 = left，c5 + c6 + c7 = right。

那么代价的变化是：d * right - d * left = ▲。

而right和left之间肯定有个大小关系，若right > left，则代价的变化 ▲ > 0；若right = left，则▲ = 0；若right < left，则▲ < 0。

容易得知这样的结论，若x取到两个数中间时，总代价最少，那么有

• 若right > left，我们一定能将x往上移，使得总代价变得更小
• 若right < left，我们一定能将x往下移，使得总代价变得更小
• 若right = left，则我们将x往上移，往下移，总代价都保持不变

所以，最终使得总代价最小的方案，所取的x，一定能够取到nums中的某个值。

我们只需要求解x取到哪个值即可。

我们先随便将x设为排好序的nums中的某个位置的数，然后我们考虑把x往左挪一个位置，或者往右挪一个位置，观察一下总的开销的变化情况。设x所在的下标为i，即，x = nums[i]，则x左侧，即所有下标位于区间[0, i - 1]的数的操作开销为：

leftCost = (nums[0] - x) * cost[0] + (nums[1] - x) * cost[1] + ... + (nums[i - 1] - x) * cost[ i - 1]

简化一下，我们将nums[k]与x之间的距离用d[k]表示，则

leftCost = d[0] * cost[0] + d[1] * cost[1] + ... + d[i - 1] * cost[i - 1]

同理，x右侧，即所有下标位于区间[i + 1, n - 1]的数的操作开销为

rightCost = d[i + 1] * cost[i + 1] + ... + d[n - 1] * cost[n - 1]

我们考虑将x往左挪一个位置，即取x = nums[i - 1]，来看一下左右两侧的开销变化。

由于我们对nums按照从小到大排了序，则x左侧的元素都是小于x的。当把x往左挪一个位置，则左侧所有点离最终x的距离，变小了，变小的幅度是 nums[i] - nums[i - 1]，右侧所有点离最终x的距离，变大了，变大的幅度也是nums[i] - nums[i - 1]，我们设

d = nums[i] - nums[i - 1]

则左侧全部元素，减小的开销为：d * (cost[0] + cost[1] + ... + cost[i - 1])

右侧全部元素，增大的开销为：d * (cost[i] + cost[i + 1] + cost[i + 1] + ... + cost[n - 1])

所以，若左侧的 ${\sum }_{k=0}^{k=i-1}cos{t}_k$ 若小于右侧的 ${\sum }_{k=i}^{k=n-1}cos{t}_k$，说明把x从位置i变到i - 1，减小的开销小于增加的开销，总开销是增大的。所以此时不能将x的位置往左移动，只能往右移动。同理，若左侧的 ${\sum }_{k=0}^{k=i-1}cos{t}_k$ 大于右侧的 ${\sum }_{k=i}^{k=n-1}cos{t}_k$，那么x的位置应当往左移动。我们可以根据这个性质，找到一个位置，使得其往左或往右移动都不能使得总开销变得更小，那么这个位置就是最终的x的位置。我们可以直接从第0个位置开始累加，当累加的cost刚好超过总数的一半，则停止。或者对cost数组计算一个前缀和，用二分查找来找x的位置。

确定x的位置后，再遍历一次依次累加各个元素的代价即可。

C++：

// C++
typedef long long LL;
class Solution {
public:void quick_sort(vector<int>& n, vector<int>& c, int l, int r) {if (l >= r) return ;int x = n[l + r >>1], i = l - 1, j = r + 1;while (i < j) {do i++; while (n[i] < x);do j--; while (n[j] > x);if (i < j) {swap(n[i], n[j]);swap(c[i], c[j]);}}quick_sort(n, c, l, j);quick_sort(n, c, j + 1, r);}LL minCost(vector<int>& nums, vector<int>& cost) {int n = nums.size();// 按照nums从小到大排序quick_sort(nums, cost, 0, n - 1);vector<LL> s(n + 1);// 求一个cost的前缀和for (int i = 0; i < n; i++) s[i + 1] = s[i] + cost[i];// 二分中位数的位置int l = 1, r = n;while (l < r) {int mid = l + r >> 1;// 找到第一个左侧 >= 右侧的位置if (s[mid] >= s[n] - s[mid]) r = mid;else l = mid + 1;}//l是最终的位置int x = nums[l - 1];LL ans = 0;for (int i = 0; i < n; i++) {ans += (LL) abs(nums[i] - x) * cost[i];}return ans;}
};

或者通过枚举也可以找到答案，首先，我们上面证明了，使得总开销最小的值x，一定是能取到nums中的某个数。那么我们还是先按照nums从小到大排序，然后先设x = nums[0]，计算出一个总开销出来。然后置x = nums[1]，计算变化的开销量，再置x = nums[2]计算变化的开销量，一直枚举到最后，每次对计算出来的总开销取一个min即可。

// C++
typedef long long LL;
typedef pair<int, int> PII;
class Solution {
public:LL minCost(vector<int>& nums, vector<int>& cost) {int n = nums.size();// nums和cost合在一起排序, 按照nums从小到大vector<PII> v(n);for (int i = 0; i < n; i++) v[i] = {nums[i], cost[i]};sort(v.begin(), v.end());// 计算前缀和, 并计算x = nums[0]时的总开销LL cur = 0;vector<LL> s(n + 1);for (int i = 0; i < n; i++) {s[i + 1] = s[i] + v[i].second;cur += (LL) abs(v[i].first - v[0].first) * v[i].second;}// 依次计算 x = nums[i]时的总开销, 并更新ansLL ans = cur;for (int i = 1; i < n; i++) {int d = v[i].first - v[i - 1].first;// 左侧开销变大, 右侧变小LL l = s[i] * d, r = (s[n] - s[i]) * d;cur += l - r;ans = min(ans, cur);}return ans;}
};

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

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

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

• 令 nums[i] = nums[i] + 2 且
• 令 nums[j] = nums[j] - 2 。

如果两个数组中每个元素出现的频率相等，我们称两个数组是 相似 的。

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

提示：

• n == nums.length == target.length
• 1 <= n <= 10^5
• 1 <= nums[i], target[i] <= 10^6
• nums 一定可以变得与 target 相似。

示例

输入：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，另一个元素-2。由此可知，经过数次操作后，偶数还是偶数，奇数还是奇数。元素的奇偶性不会改变。我们可以先把全部元素按照奇偶性分成两组。（扩展，如果题目变形成+3和-3，同理，所有模3余0的数，经过数次操作后，模3还是余0，模3余1的同理，所以可以根据模3的余数，将元素分为3类：x mod 3 = 0，x mod 3 = 1，x mod 3 = 2，对于+k -k，就是分为k - 1组）。

由于题目保证nums一定能变得与target相似，那么我们来考虑下如何转换能使得操作次数最小。

我们对nums和target中的数先按奇偶性进行分组，nums分为o_odd，o_even，target分为t_odd，t_even。

对o_odd，t_odd从小到大排个序。

由于无论如何操作，奇数都只能变成奇数。所以o_odd中每个数，经过操作后，需要变成t_odd中的每个数。排完序后，我们观察能够发现，把o_odd的每个位置挨个变成t_odd每个位置的数，能够使得操作次数最少。

于是很简单的，我们可以依次统计每个位置的数的差，然后除以2，就是这个位置上的数需要操作的次数。我们对奇偶两组数分别统计完成后，得到的总的统计次数，再除以个2，就是最终答案。

至于该贪心策略的正确性，这里略过。

// C++
class Solution {
public:long long makeSimilar(vector<int>& nums, vector<int>& target) {// 先分组vector<int> o_odd, o_even;vector<int> t_odd, t_even;for (int& i : nums) {if (i % 2) o_odd.push_back(i);else o_even.push_back(i);}for (int& i : target) {if (i % 2) t_odd.push_back(i);else t_even.push_back(i);}// 排序sort(o_odd.begin(), o_odd.end());sort(o_even.begin(), o_even.end());sort(t_odd.begin(), t_odd.end());sort(t_even.begin(), t_even.end());long long ans = 0;for (int i = 0; i < o_odd.size(); i++) ans += abs(o_odd[i] - t_odd[i]) / 2;for (int i = 0; i < o_even.size(); i++) ans += abs(o_even[i] - t_even[i]) / 2;return ans / 2;}
};

总结

本周周赛太拉跨，只做出了2题。T3一直坐牢到比赛结束。当时看了下T3和T4都是hard，心理也生出了些许畏惧。

今天重做时，发现T4也并不难。可惜！

T1模拟；T2暴力枚举GCD；T3贪心，T4贪心