网站制作找云优化,关于普通话的手抄报,网站开发与应用总结,wordpress+视频边栏Leetcode 第 382 场周赛题解 Leetcode 第 382 场周赛题解题目1#xff1a;3019. 按键变更的次数思路代码复杂度分析 题目2#xff1a;3020. 子集中元素的最大数量思路代码复杂度分析 题目3#xff1a;3021. Alice 和 Bob 玩鲜花游戏思路代码复杂度分析 题目4#xff1a;302… Leetcode 第 382 场周赛题解 Leetcode 第 382 场周赛题解题目13019. 按键变更的次数思路代码复杂度分析 题目23020. 子集中元素的最大数量思路代码复杂度分析 题目33021. Alice 和 Bob 玩鲜花游戏思路代码复杂度分析 题目43022. 给定操作次数内使剩余元素的或值最小思路代码复杂度分析 Leetcode 第 382 场周赛题解
题目13019. 按键变更的次数
思路
双指针。
给你一个下标从 0 开始的字符串 s 该字符串由用户输入。按键变更的定义是使用与上次使用的按键不同的键。例如 s “ab” 表示按键变更一次而 s “bBBb” 不存在按键变更。
返回用户输入过程中按键变更的次数。
注意shift 或 caps lock 等修饰键不计入按键变更也就是说如果用户先输入字母 ‘a’ 然后输入字母 ‘A’ 不算作按键变更。
使用双指针指向字符串中两个相邻的字符 s[i] 和 s[j]0ijs.length()ji1将它们先转为小写再判断是否相等。若不相等则计入按键变更否则不计入。一直遍历、判断到字符串末尾。
最后返回按键变更计数。
代码
/** lc appleetcode.cn id100215 langcpp** [100215] 按键变更的次数*/// lc codestart
class Solution
{
public:int countKeyChanges(string s){// 特判if (s.empty())return 0;int n s.length();int count 0;for (int i 0, j 1; i n j n; i, j)if (tolower(s[i]) ! tolower(s[j]))count;return count;}
};
// lc codeend复杂度分析
时间复杂度O(n)其中 n 是字符串 s 的长度。
空间复杂度O(1)。
题目23020. 子集中元素的最大数量
思路
用一个哈希表统计数组 nums 中的元素及其出现次数。
暴力枚举数组中的数作为 x然后不断看 x2,x4,⋯ 在数组中的个数。直到个数不足 2 个为止退出循环。
注意模式的正中间的数字只取一个。如果最后 x 有一个那么个数加一否则个数减一。
注意特判 x1 的情况。
代码
/** lc appleetcode.cn id100206 langcpp** [100206] 子集中元素的最大数量*/// lc codestart
class Solution
{
public:int maximumLength(vectorint nums){// 特判if (nums.empty())return 0;unordered_maplong long, int cnt;for (int num : nums)cnt[num];// 特判 x1 的情况int ans cnt[1] - (cnt[1] % 2 0);cnt.erase(1);for (auto [num, _] : cnt){int res 0;long long x;for (x num; cnt.contains(x) cnt[x] 1; x * x)res 2;if (cnt.contains(x))res;elseres--;ans max(ans, res);}return ans;}
};
// lc codeend复杂度分析
时间复杂度O(nloglogU)其中 n 为数组 nums 的长度Umax(nums)。
空间复杂度O(n)。
题目33021. Alice 和 Bob 玩鲜花游戏
思路
数学。
Alice 和 Bob 在一个长满鲜花的环形草地玩一个回合制游戏。环形的草地上有一些鲜花Alice 到 Bob 之间顺时针有 x 朵鲜花逆时针有 y 朵鲜花。
游戏过程如下
Alice 先行动。每一次行动中当前玩家必须选择顺时针或者逆时针然后在这个方向上摘一朵鲜花。一次行动结束后如果所有鲜花都被摘完了那么当前玩家抓住对手并赢得游戏的胜利。
给你两个整数 n 和 m 你的任务是求出满足以下条件的所有 (x, y) 对
按照上述规则Alice 必须赢得游戏。Alice 顺时针方向上的鲜花数目 x 必须在区间 [1,n] 之间。Alice 逆时针方向上的鲜花数目 y 必须在区间 [1,m] 之间。
请你返回满足题目描述的数对 (x, y) 的数目。
显然因为是 Alice 先行动当 xy 为奇数时Alice 会摘完最后一朵鲜花抓住对手并赢得游戏的胜利。
xy 为奇数有两种情况
x 为奇数y 为偶数x 为偶数y 为奇数
在 [1,n] 区间内有 n/2 个偶数(n1)/2 个奇数。
所以最终答案为 (n / 2) * ((m 1) / 2) ((n 1) / 2) * (m / 2)。
更进一步把这道题想象成一个网格。 枚举一下 x 和 y 的奇偶性得出答案为 n*m/2。
代码
/** lc appleetcode.cn id3021 langcpp** [3021] Alice 和 Bob 玩鲜花游戏*/// lc codestart// 数学class Solution
{
public:long long flowerGame(int n, int m){return (long long)n * m / 2;}
};// Time Limit Exceeded// class Solution
// {
// public:
// long long flowerGame(int n, int m)
// {
// long long count 0;
// for (int x 1; x n; x)
// for (int y 1; y m; y)
// if ((x y) ^ 0x1)
// count;
// return count / 2;
// }
// };// class Solution
// {
// public:
// long long flowerGame(int n, int m)
// {
// return (long long)(n / 2) * ((m 1) / 2)
// (long long)((n 1) / 2) * (m / 2);
// }
// };
// lc codeend复杂度分析
时间复杂度O(1)。
空间复杂度O(1)。
题目43022. 给定操作次数内使剩余元素的或值最小
思路
位运算 试填法。
题解试填法Python/Java/C/Go
代码
/** lc appleetcode.cn id3022 langcpp** [3022] 给定操作次数内使剩余元素的或值最小*/// lc codestart
class Solution
{
public:int minOrAfterOperations(vectorint nums, int k){int ans 0, mask 0;// 从高位到低位一次枚举for (int b 29; b 0; b--){mask | 1 b;int cnt 0;// -1 在二进制下全为 1所以可以省去特判每一段第一个数int and_res -1;for (int x : nums){and_res x mask;if (and_res){// 合并 x操作次数加一cnt;}else{// 准备合并下一段省去特判每一段的第一个数and_res -1;}}if (cnt k){ans | 1 b; // 答案的这个比特位必须是 1// 后面不考虑这个比特位这一位一定为 1消除这一位的影响mask ^ 1 b;}}return ans;}
};
// lc codeend复杂度分析
时间复杂度O(nlogU)其中 n 为数组 nums 的长度Umax(nums)。
空间复杂度O(1)。
