Leetcode 第 372 场周赛题解
- Leetcode 第 372 场周赛题解
- 题目1：2937. 使三个字符串相等
- 思路
- 代码
- 复杂度分析
- 题目2：2938. 区分黑球与白球
- 思路
- 代码
- 复杂度分析
- 题目3：2939. 最大异或乘积
- 思路
- 代码
- 复杂度分析
- 题目4：2940. 找到 Alice 和 Bob 可以相遇的建筑
- 思路
- 代码
- 复杂度分析
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;
else
black++;
}
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 另一个是 0
long long one = mask ^ left; // 无需分配：a XOR x 和 b XOR x 均为 1
ax |= one; // 先加到异或结果中
bx |= one;
// 现在要把 left 分配到 ax 和 bx 中
// 根据基本不等式（均值定理），分配后应当使 ax 和 bx 尽量接近，乘积才能尽量大
if (left > 0 && ax == bx)
{
// 尽量均匀分配，例如把 1111 分成 1000 和 0111
long 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++) { // 从小到大枚举下标 i
while (!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+qlogq)，其中 n 为 heights 的长度，q 为 queries 的长度。
空间复杂度：O(n+q)。
