建造自己的网站,phpcms v9网站导航,邢路桥建设总公司网站,荆门哪里做网站Leetcode 第 372 场周赛题解 Leetcode 第 372 场周赛题解题目1#xff1a;2937. 使三个字符串相等思路代码复杂度分析 题目2#xff1a;2938. 区分黑球与白球思路代码复杂度分析 题目3#xff1a;2939. 最大异或乘积思路代码复杂度分析 题目4#xff1a;2940. 找到 Alice 和… Leetcode 第 372 场周赛题解 Leetcode 第 372 场周赛题解题目12937. 使三个字符串相等思路代码复杂度分析 题目22938. 区分黑球与白球思路代码复杂度分析 题目32939. 最大异或乘积思路代码复杂度分析 题目42940. 找到 Alice 和 Bob 可以相遇的建筑思路代码复杂度分析 Leetcode 第 372 场周赛题解
题目12937. 使三个字符串相等
思路
枚举。
设 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 appleetcode.cn id2937 langcpp** [2937] 使三个字符串相等*/// lc codestart
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 codeend复杂度分析
时间复杂度O(min_len)其中 min_len 为三个字符串中的最短字符串的长度。
空间复杂度O(1)。
题目22938. 区分黑球与白球
思路
贪心。
类似于冒泡排序的思想把 ‘0’ 挪到相应的位置。
一次遍历累加操作次数。
示例 代码
/** lc appleetcode.cn id2938 langcpp** [2938] 区分黑球与白球*/// lc codestart
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 codeend另解操作次数 Σ(每个 ‘0’ 左边的 ‘1’ 的个数)。
代码
/** lc appleetcode.cn id2938 langcpp** [2938] 区分黑球与白球*/// lc codestart
// 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 codeend复杂度分析
时间复杂度O(n)其中 n 是字符串 s 的长度。
空间复杂度O(1)。
题目32939. 最大异或乘积
思路
位运算。
题解O(1) 做法位运算的巧妙运用Python/Java/C/Go
代码
/** lc appleetcode.cn id2939 langcpp** [2939] 最大异或乘积*/// lc codestart
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注意最上面保证了 abbx | left;const long long MOD 1000000007;return ax % MOD * (bx % MOD) % MOD; // 注意不能直接 LL * LL否则溢出}
};
// lc codeend复杂度分析
时间复杂度O(1)。
空间复杂度O(1)。
题目42940. 找到 Alice 和 Bob 可以相遇的建筑
思路
题解两种方法离线最小堆/在线线段树二分Python/Java/C/Go
代码
class Solution {
public:vectorint leftmostBuildingQueries(vectorint heights, vectorvectorint queries) {vectorint ans(queries.size(), -1);vectorvectorpairint, 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_queuepairint, int, vectorpairint, 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(nqlogq)其中 n 为 heights 的长度q 为 queries 的长度。 空间复杂度O(nq)。
