查公司的国家网站有哪些,电脑从做系统怎么找回以前登录的网站,网站的用户体验,wordpress指定文章评论Leetcode 第 366 场周赛题解 Leetcode 第 366 场周赛题解题目1#xff1a;2894. 分类求和并作差思路代码复杂度分析 题目2#xff1a;2895. 最小处理时间思路代码复杂度分析 题目3#xff1a;2896. 执行操作使两个字符串相等思路代码复杂度分析 题目4#xff1a;2897. 对数… Leetcode 第 366 场周赛题解 Leetcode 第 366 场周赛题解题目12894. 分类求和并作差思路代码复杂度分析 题目22895. 最小处理时间思路代码复杂度分析 题目32896. 执行操作使两个字符串相等思路代码复杂度分析 题目42897. 对数组执行操作使平方和最大思路代码复杂度分析 Leetcode 第 366 场周赛题解
题目12894. 分类求和并作差
思路
模拟
代码
/** lc appleetcode.cn id2894 langcpp** [2894] 分类求和并作差*/// lc codestart
// class Solution
// {
// public:
// int differenceOfSums(int n, int m)
// {
// int num1 0, num2 0;
// for (int i 1; i n; i)
// {
// if (i % m 0)
// num2 i;
// else
// num1 i;
// }
// return num1 - num2;
// }
// };class Solution
{
public:int differenceOfSums(int n, int m){// total num1 num2// ans num1 - num2 total - 2 * num2int num 0;for (int i 1; i n; i)if (i % m 0)num i;return (1 n) * n / 2 - 2 * num;}
};
// lc codeendone-line code
return n * (n 1) / 2 - n / m * (n / m 1) * m;复杂度分析
时间复杂度O(n)。
空间复杂度O(1)。
题目22895. 最小处理时间
思路
贪心。
直觉上来说最早空闲时间越大的处理器处理 tasks 越小的任务那么完成时间越早。
我们可以把 processorTime 从小到大排序tasks 从大到小排序那么答案就是 processorTime[i] tasks[4 * i] 的最大值。
代码
/** lc appleetcode.cn id2895 langcpp** [2895] 最小处理时间*/// lc codestart
class Solution
{
public:int minProcessingTime(vectorint processorTime, vectorint tasks){int n processorTime.size();int min_time INT_MIN;sort(processorTime.begin(), processorTime.end());sort(tasks.begin(), tasks.end(), greaterint());for (int i 0; i n; i){int process_max_time processorTime[i] tasks[4 * i];min_time max(min_time, process_max_time);}return min_time;}
};
// lc codeend复杂度分析
时间复杂度O(nlogn)其中 n 为数组 processorTime 的长度。
空间复杂度O(1)。
题目32896. 执行操作使两个字符串相等
思路
两种操作都不会改变字符串中 1 和 0 的个数的奇偶性。
特判
s1 s2无需操作返回0。s1中1的个数的奇偶性不等于s2中1的个数的奇偶性无法让二者相等返回-1。
遍历两个字符串将字符不同的索引保存在数组 pos 中。
若字符不同的索引数为 pos.size()那么有 pos.size()/2 对字符需要进行翻转。我们先只考虑操作一将每两个下标都进行操作一翻转那么总的操作代价为 x∗pos.size()/2。
然后遍历数组 pos查看两个相邻下标进行操作二的翻转是否比进行操作一的翻转所需要的代价还小。如果还小则把答案更新为两个相邻下标进行操作二翻转时的代价。
当一个下标和相邻的下标进行操作二翻转时它只和前面的下标或者后面的下标组成一对进行翻转但不能和前面的下标和后面的下标同时进行翻转。
在下面的代码中cur 表示的是当前下标和前面下标不做操作二时的最优解pre 表示前一个下标和前前一个下标不做操作二翻转时的最优解 prepos[i]−pos[i−1]−x 表示前一个下标和前前一个下标不做操作二翻转但和当前下标做操作二翻转时的最优解。
代码
/** lc appleetcode.cn id2896 langcpp** [2896] 执行操作使两个字符串相等*/// lc codestart
class Solution
{
public:int minOperations(string s1, string s2, int x){// 特判if (s1 s2)return 0;if (count(s1.begin(), s1.end(), 1) % 2 ! count(s2.begin(), s2.end(), 1) % 2)return -1;int n s1.size();vectorint pos;for (int i 0; i n; i)if (s1[i] ! s2[i])pos.push_back(i);int cur pos.size() / 2 * x, pre cur;for (int i 1; i pos.size(); i){int next min(cur, pre pos[i] - pos[i - 1] - x);pre cur;cur next;}return cur;}
};
// lc codeend
复杂度分析
时间复杂度O(n)其中 n 是字符串 s1 的长度。
空间复杂度O(n)其中 n 是字符串 s1 的长度。
题目42897. 对数组执行操作使平方和最大
思路
位运算贪心
考虑两个数 a 和 b 的二进制表示讨论二进制第 i 位在 a 和 b 中是否为 1 的情况
若 a 和 b 的第 i 位都是 0那么 a AND b 和 a OR b 的第 i 位也都是 0。若 a 和 b 的第 i 位恰有一个 1那么 a AND b 的第 i 位是 0a OR b 的第 i 位是 1。若 a 和 b 的第 i 位都是 1那么 a AND b 和 a OR b 的第 i 位也都是 1。
所以操作等价于把一个数的 0 和另一个数的同一个比特位上的 1 交换。
令 f(a) 表示 a 的二进制表示中有几个 1。
我们发现f(a) f(b) f(a AND b) f(a OR b)。只不过所有的 1 首先都被 a OR b “抢”了剩下的 1 才会留给 a AND b。也就是说每个二进制位中1 的总数不变。我们可以通过任意次操作把 1 都集中在某个数里。
设交换前两个数是 x 和 yx y把小的数上的 1 给大的数假设交换后 x 增加了 d那么 y 也减少了 d。
交换前x2y2
交换后(xd)2(y-d)2x2y22d(x-y)2d2x2y2
这说明应该通过交换让一个数越大越好。
相当于把 1 都聚集在一个数中比分散到不同的数更好。
因此做法就是统计每个二进制位里有多少 1然后每次用这些 1 拼出尽可能大的数即可。
代码
/** lc appleetcode.cn id2897 langcpp** [2897] 对数组执行操作使平方和最大*/// lc codestart
class Solution
{
private:const int MOD 1e9 7;public:int maxSum(vectorint nums, int k){vectorint count(32, 0);for (const int num : nums){for (int i 0; i 32; i)count[i] (num i) 01;}long long ans 0;for (int i 0; i k; i){int x 0;for (int i 0; i 32; i)if (count[i] 0){x 1 i;count[i]--;}ans (ans (long long)x * x) % MOD;}return ans;}
};
// lc codeend
复杂度分析
时间复杂度O(nlogU)其中 n 为数组 nums 的长度U 为数组 nums 的最大值。
空间复杂度O(logU)其中 U 为数组 nums 的最大值。
