leetcode biweekly contest 96

双周赛的题目果真质量高很多，非常不错的题目，几个题目都非常有数学的意味。

2540. 最小公共值

给你两个整数数组 nums1 和 nums2 ，它们已经按非降序排序，请你返回两个数组的 最小公共整数 。如果两个数组 nums1 和 nums2 没有公共整数，请你返回 -1 。

如果一个整数在两个数组中都 至少出现一次 ，那么这个整数是数组 nums1 和 nums2 公共 的。

示例 1：

输入：nums1 = [1,2,3], nums2 = [2,4]
输出：2
解释：两个数组的最小公共元素是 2 ，所以我们返回 2 。

示例 2：

输入：nums1 = [1,2,3,6], nums2 = [2,3,4,5]
输出：2
解释：两个数组中的公共元素是 2 和 3 ，2 是较小值，所以返回 2 。

提示：

• 1 <= nums1.length, nums2.length <= 105
• 1 <= nums1[i], nums2[j] <= 109
• nums1 和 nums2 都是 非降序 的。

地址

https://leetcode.cn/contest/biweekly-contest-96/problems/minimum-common-value/

题意

双指针

思路

1. 由于两个数组都已经按照从小到大进行排序，所以我们只需遍历两个数组即可，其中 $l_1$ 指向数组 $nums_1$，$l_2$ 指向数组 $nums_2$，则此时移动如下：

• 如果 $nums_1[l_1] < nums_2[l_2]$ 时，则移动 $l_1$;
• 如果 $nums_1[l_1] > nums_2[l_2]$ 时，则移动 $l_2$;
• 如果 $nums_1[l_1] = nums_2[l_2]$ 时，则直接返回 $nums_1[l_1]$；

2. 复杂度分析：

• 时间复杂度：$O(n + m)$。其中 $m, n$ 表示两个数组的长度。
• 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int getCommon(vector<int>& nums1, vector<int>& nums2) {
        int l1 = 0, l2 = 0;
        while (l1 < nums1.size() && l2 < nums2.size()) {
            if (nums1[l1] > nums2[l2]) {
                l2++;
            } else if (nums1[l1] < nums2[l2]) {
                l1++;
            } else {
                return nums1[l1];
            }
        }
        return -1;
    }
};

2541. 使数组中所有元素相等的最小操作数 II

给你两个整数数组 nums1 和 nums2 ，两个数组长度都是 n ，再给你一个整数 k 。你可以对数组 nums1 进行以下操作：

• 选择两个下标 i 和 j ，将 nums1[i] 增加 k ，将 nums1[j] 减少 k 。换言之，nums1[i] = nums1[i] + k 且 nums1[j] = nums1[j] - k 。

如果对于所有满足 0 <= i < n 都有 num1[i] == nums2[i] ，那么我们称 nums1 等于 nums2 。

请你返回使 nums1 等于 nums2 的 最少 操作数。如果没办法让它们相等，请你返回 -1 。

示例 1：

输入：nums1 = [4,3,1,4], nums2 = [1,3,7,1], k = 3
输出：2
解释：我们可以通过 2 个操作将 nums1 变成 nums2 。
第 1 个操作：i = 2 ，j = 0 。操作后得到 nums1 = [1,3,4,4] 。
第 2 个操作：i = 2 ，j = 3 。操作后得到 nums1 = [1,3,7,1] 。
无法用更少操作使两个数组相等。

示例 2：

输入：nums1 = [3,8,5,2], nums2 = [2,4,1,6], k = 1
输出：-1
解释：无法使两个数组相等。

提示：

• n == nums1.length == nums2.length
• 2 <= n <= 105
• 0 <= nums1[i], nums2[j] <= 109
• 0 <= k <= 105

地址

https://leetcode.cn/contest/biweekly-contest-96/problems/minimum-operations-to-make-array-equal-ii/

题意

数学

思路

1. 题目我想的过于复杂了，实际非常简单，首先我们知道对于位置 $i$ 时，此时 $|nums_1[i] - nums_2[i]|$ 一定能被 $k$ 整除，否则无论如何都无法满足相等：

• $nums_1[i] > nums_2[i]$ 时，此时第 $i$ 位上的数字需要减少 $\frac{|nums_1[i] - nums_2[i]|}{k}$ 次；
• $nums_1[i] < nums_2[i]$ 时，此时第 $i$ 位上的数字需要增加 $\frac{|nums_1[i] - nums_2[i]|}{k}$ 次；
• 我们计算整个数组中增加的次数与减少的次数是否相等即可；

2. 复杂度分析：

• 时间复杂度：$O(n)$，其中 $n$ 为给定数组的长度。
• 空间复杂度：$O(n^2)$。

代码

class Solution {
public:
    long long minOperations(vector<int>& nums1, vector<int>& nums2, int k) {
        long long sum1 = accumulate(nums1.begin(), nums1.end(), 0LL);
        long long sum2 = accumulate(nums2.begin(), nums2.end(), 0LL);
        if (sum1 != sum2) {
            return -1;
        }
        int n = nums1.size();
        long long res = 0;
        for (int i = 0; i < n; i++) {
            long long x = nums1[i] - nums2[i];
            if (k == 0) {
                if (x != 0) {
                    return -1;
                } 
                continue;
            }
            if (x % k != 0) {
                return -1;
            }
            if (x > 0) {
                res += x / k;
            }
        }
        return res;
    }
};

2542. 最大子序列的分数

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都是 n ，再给你一个正整数 k 。你必须从 nums1 中选一个长度为 k 的 子序列 对应的下标。

对于选择的下标 i0 ，i1 ，…， ik - 1 ，你的 分数 定义如下：

• nums1 中下标对应元素求和，乘以 nums2 中下标对应元素的 最小值 。
• 用公示表示： (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]) 。

请你返回 最大 可能的分数。

一个数组的 子序列 下标是集合 {0, 1, ..., n-1} 中删除若干元素得到的剩余集合，也可以不删除任何元素。

示例 1：

输入：nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
输出：12
解释：
四个可能的子序列分数为：
- 选择下标 0 ，1 和 2 ，得到分数 (1+3+3) * min(2,1,3) = 7 。
- 选择下标 0 ，1 和 3 ，得到分数 (1+3+2) * min(2,1,4) = 6 。
- 选择下标 0 ，2 和 3 ，得到分数 (1+3+2) * min(2,3,4) = 12 。
- 选择下标 1 ，2 和 3 ，得到分数 (3+3+2) * min(1,3,4) = 8 。
所以最大分数为 12 。

示例 2：

输入：nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
输出：30
解释：
选择下标 2 最优：nums1[2] * nums2[2] = 3 * 10 = 30 是最大可能分数。

提示：

• n == nums1.length == nums2.length
• 1 <= n <= 105
• 0 <= nums1[i], nums2[j] <= 105
• 1 <= k <= n

地址

https://leetcode.cn/contest/biweekly-contest-96/problems/maximum-subsequence-score/

题意

优先队列

思路

1. 本题与703. 数据流中的第 K 大元素题几乎一模一样。我们可以枚举 $nums_2$ 中的最小值，我们将两个数组进行排序按照 $nums_2$ 中的元素从大到小进行排序即可：

• 我们从 $ j \in [k - 1, n - 1]$ 开始枚举 $nums_2$，此时我们只需求出 $nums_1$ 中前 $j$ 个元素中的最大的 $k$ 个元素的和即可；
• 我们按照上述方法进行枚举即可，我们用优先队列处理经典的 $topk$ 问题即可。

2. 复杂度分析

• 时间复杂度：时间复杂度为 $O(n \log k)$，$n$ 表示数组的长度，$k$ 表示给定的数字。
• 空间复杂度：时间复杂度为 $O(n)$。

代码

class Solution {
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        int n = nums1.size();
        vector<pair<int,int>> arr;
        for (int i = 0; i < n; i++) {
            arr.emplace_back(nums2[i], nums1[i]);
        }
        sort(arr.begin(), arr.end(), [&](pair<int, int> &a, pair<int, int> &b) {
            if (a.first == b.first) {
               return a.second < b.second;
            } 
            return a.first < b.first;
        });
        long long sum = 0;
        long long res = 0;
        priority_queue<int, vector<int>, greater<int>> pq;
        for (int i = n - 1; i >= 0; i--) {
            pq.emplace(arr[i].second);
            sum += arr[i].second;
            if (pq.size() >= k) {
                res = max(res, sum * arr[i].first);
                int curr = pq.top();
                pq.pop();
                sum -= curr;
            }
        }
        return res;
    }
};

2543. 判断一个点是否可以到达

给你一个无穷大的网格图。一开始你在 (1, 1) ，你需要通过有限步移动到达点 (targetX, targetY) 。

每一步 ，你可以从点 (x, y) 移动到以下点之一：

• (x, y - x)
• (x - y, y)
• (2 * x, y)
• (x, 2 * y)

给你两个整数 targetX 和 targetY ，分别表示你最后需要到达点的 X 和 Y 坐标。如果你可以从 (1, 1) 出发到达这个点，请你返回true ，否则返回 false 。

示例 1：

输入：targetX = 6, targetY = 9
输出：false
解释：没法从 (1,1) 出发到达 (6,9) ，所以返回 false 。

示例 2：

输入：targetX = 4, targetY = 7
输出：true
解释：你可以按照以下路径到达：(1,1) -> (1,2) -> (1,4) -> (1,8) -> (1,7) -> (2,7) -> (4,7) 。

提示：

• 1 <= targetX, targetY <= 109

地址

https://leetcode.cn/contest/biweekly-contest-96/problems/check-if-point-is-reachable/

题意

数学

思路

1. 确实是非常棒的数学题目，根据题意可以知道 $(x,y)$ 经过一步变换可以到达 $(g(x), g(y))$:

• $(x, y - x), (x - y, x)$，此时 $\gcd(x, y-x) = \gcd(x, y),\gcd(x - y, y) = \gcd(x, y)$，则可以知道如果向下移动或者向左移动则二者的最大公约数保持不变；
• $(x, 2y), (2x, y)$，此时若变为 $(x,2y)$ 时，如果 $y$ 为奇数时，$x$ 为偶数此时 $\gcd(x, 2y) = 2\gcd(x,y)$，则此时有可能会将二者的公约数的倍数乘以 $2$，要么继续保持不变；
• 因此综上我们可以推理出来经过上述的变换二者的公约数要么保持不变，要么最大公约数为原来的 $2$ 倍，由于 $(1,1)$ 的公约数不变，综上我们可以知道 $(targetX, targetY)$ 的最大公约数要么为 $1$，要么为 $2$ 的倍数；

此时我们也可以反向思考，可以参考「题解」。我们进行反向模拟，此时 $(x, y)$ 的坐标需要逐步缩小，$(x,y)$ 经过一步变换后变为:

• $(x, x + y), (x + y, x)$，此时二者的最大公约数保持不变，即 $\gcd(x, y) = \gcd(x, x + y) = \gcd(x + y, y)$；
• $(x, \frac{y}{2})$ 或者 $(\frac{x}{2}, y)$，此时二者的公约数要么继续保持不变，要么二者的公约数为 $\gcd(x,y)$ 的一半。
• 如果 $(x, y)$ 中存在任意的数位偶数，我们总可以通过除法变换，将 $(x,y)$ 全部变为奇数，此时我们分类讨论:
  • 如果 $x = y$，则此时我们无论通过何种变换都无法再将坐标进行缩小；
  • 如果 $x \neq y$，假设 $x < y$，则我们可以将 $(x,y)$ 变换为 $(x, \frac{x + y}{2})$，此时 $\frac{x + y}{2} < y$，这样我们就将纵坐标进行了缩小，同时我们此时可以得到 $\gcd(x,y) = \gcd(x, \frac{x + y}{2}) = 1$；同理如果 $x > y$，我们可以将横坐标缩小；
    我们直接通过上述的模拟方法即可判断坐标是否可以完成还原。

2. 我觉得如果要证明这个结论正确的话，需要分为两步:

• 如果 $(targetX, targetY) = 2^k$，则此时一定可以到达 $(1,1)$；
• 如果 $(targetX, targetY) \neq 2^k$，则此时一定不能到达 $(1,1)$；

3. 复杂度分析：

• 时间复杂度：$O(\log n)$。
• 空间复杂度：$O(1)$。

代码

1. 数学计算

   class Solution { public: bool isReachable(int targetX, int targetY) { int x = __gcd(targetX, targetY); return (x & (x - 1)) == 0; } };

2. 模拟

   class Solution { public: bool isReachable(int targetX, int targetY) { if ((targetX & 1) == 0) { return isReachable(targetX / 2, targetY); } else if ((targetY & 1) == 0) { return isReachable(targetX, targetY / 2); } else { if (targetX == targetY) { return targetX == 1; } else { if (targetX > targetY) { return isReachable((targetX + targetY) / 2, targetY); } else { return isReachable(targetX, (targetX + targetY) / 2); } } } } };

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

• 关注我的博客: http://whistle-wind.com/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿