Leetcode 第 372 场周赛题解

Leetcode 第 372 场周赛题解

题目1：2937. 使三个字符串相等

思路

枚举。

设 len1、len2、len3 分别为字符串 s1、s2、s3 的长度。

min_len 是 3 个字符串长度的最小值。

枚举 len = min_len 到 len = 1，设 t1、t2、t3 分别是字符串 s1、s2、s3 的从 0 开始、长度为 len 的子串。

如果 t1 == t2 == t3，说明可以通过操作（选择其中一个长度至少为 2 的字符串并删除其最右位置上的字符）使这三个字符串相等，最小操作次数 = len1 + len2 + len3 - 3 * len。

否则，返回 -1。

代码

/** @lc app=leetcode.cn id=2937 lang=cpp** [2937] 使三个字符串相等*/// @lc code=start
class Solution
{
public:int findMinimumOperations(string s1, string s2, string s3){int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();int min_len = min(len1, min(len2, len3));for (int len = min_len; len >= 1; len--){string t1 = s1.substr(0, len), t2 = s2.substr(0, len), t3 = s3.substr(0, len);if (t1 == t2 && t2 == t3)return len1 + len2 + len3 - 3 * len;}return -1;}
};
// @lc code=end

复杂度分析

时间复杂度：O(min_len)，其中 min_len 为三个字符串中的最短字符串的长度。

空间复杂度：O(1)。

题目2：2938. 区分黑球与白球

思路

贪心。

类似于冒泡排序的思想，把 ‘0’ 挪到相应的位置。

一次遍历，累加操作次数。

示例：

代码

/** @lc app=leetcode.cn id=2938 lang=cpp** [2938] 区分黑球与白球*/// @lc code=start
class Solution
{
public:long long minimumSteps(string s){int white = 0;long long steps = 0;for (int i = 0; i < s.length(); i++){if (s[i] == '0'){steps += (long long)(i - white);white++;}}return steps;}
};
// @lc code=end

另解：操作次数 = Σ(每个 ‘0’ 左边的 ‘1’ 的个数)。

代码：

/** @lc app=leetcode.cn id=2938 lang=cpp** [2938] 区分黑球与白球*/// @lc code=start
// class Solution
// {
// public:
//     long long minimumSteps(string s)
//     {
//         int white = 0;
//         long long steps = 0;
//         for (int i = 0; i < s.length(); i++)
//         {
//             if (s[i] == '0')
//             {
//                 steps += (long long)(i - white);
//                 white++;
//             }
//         }
//         return steps;
//     }
// };class Solution
{
public:long long minimumSteps(string s){int black = 0;long long steps = 0;for (int i = 0; i < s.length(); i++){if (s[i] == '0')steps += black;elseblack++;}return steps;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，其中 n 是字符串 s 的长度。

空间复杂度：O(1)。

题目3：2939. 最大异或乘积

思路

位运算。

题解：O(1) 做法！位运算的巧妙运用！（Python/Java/C++/Go）

代码

/** @lc app=leetcode.cn id=2939 lang=cpp** [2939] 最大异或乘积*/// @lc code=start
class Solution
{
public:int maximumXorProduct(long long a, long long b, int n){if (a < b){swap(a, b); // 保证 a >= b}long long mask = (1LL << n) - 1;long long ax = a & ~mask; // 第 n 位及其左边，无法被 x 影响，先算出来long long bx = b & ~mask;a &= mask; // 低于第 n 位，能被 x 影响b &= mask;long long left = a ^ b;      // 可分配：a XOR x 和 b XOR x 一个是 1 另一个是 0long long one = mask ^ left; // 无需分配：a XOR x 和 b XOR x 均为 1ax |= one;                   // 先加到异或结果中bx |= one;// 现在要把 left 分配到 ax 和 bx 中// 根据基本不等式（均值定理），分配后应当使 ax 和 bx 尽量接近，乘积才能尽量大if (left > 0 && ax == bx){// 尽量均匀分配，例如把 1111 分成 1000 和 0111long long high_bit = 1LL << (63 - __builtin_clzll(left));ax |= high_bit;left ^= high_bit;}// 如果 a & ~mask 更大，则应当全部分给 bx（注意最上面保证了 a>=b）bx |= left;const long long MOD = 1'000'000'007;return ax % MOD * (bx % MOD) % MOD; // 注意不能直接 LL * LL，否则溢出}
};
// @lc code=end

复杂度分析

时间复杂度：O(1)。

空间复杂度：O(1)。

题目4：2940. 找到 Alice 和 Bob 可以相遇的建筑

思路

题解：两种方法：离线+最小堆/在线+线段树二分（Python/Java/C++/Go）

代码

class Solution {
public:vector<int> leftmostBuildingQueries(vector<int> &heights, vector<vector<int>> &queries) {vector<int> ans(queries.size(), -1);vector<vector<pair<int, int>>> left(heights.size());for (int qi = 0; qi < queries.size(); qi++) {int i = queries[qi][0], j = queries[qi][1];if (i > j) {swap(i, j); // 保证 i <= j}if (i == j || heights[i] < heights[j]) {ans[qi] = j; // i 直接跳到 j} else {left[j].emplace_back(heights[i], qi); // 离线}}priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;for (int i = 0; i < heights.size(); i++) { // 从小到大枚举下标 iwhile (!pq.empty() && pq.top().first < heights[i]) {ans[pq.top().second] = i; // 可以跳到 i（此时 i 是最小的）pq.pop();}for (auto &p: left[i]) {pq.emplace(p); // 后面再回答}}return ans;}
};

复杂度分析

时间复杂度：O(n+qlog⁡q)，其中 n 为 heights 的长度，q 为 queries 的长度。
空间复杂度：O(n+q)。