dede部署两个网站,wordpress添加版权信息,wordpress 开源,集团网站建设服务平台Leetcode 第 363 场周赛题解 Leetcode 第 363 场周赛题解题目1#xff1a;2859. 计算 K 置位下标对应元素的和思路代码复杂度分析 题目2#xff1a;让所有学生保持开心的分组方法数思路#xff1a;排序 枚举代码复杂度分析 题目3#xff1a;最大合金数思路#xff1a;二分… Leetcode 第 363 场周赛题解 Leetcode 第 363 场周赛题解题目12859. 计算 K 置位下标对应元素的和思路代码复杂度分析 题目2让所有学生保持开心的分组方法数思路排序 枚举代码复杂度分析 题目3最大合金数思路二分查找代码复杂度分析 题目4完全子集的最大元素和思路代码复杂度分析 Leetcode 第 363 场周赛题解
题目12859. 计算 K 置位下标对应元素的和
思路
模拟。
秒杀题。
代码
/** lc appleetcode.cn id2859 langcpp** [2859] 计算 K 置位下标对应元素的和*/// lc codestart
class Solution
{
public:int sumIndicesWithKSetBits(vectorint nums, int k){int sum 0;for (int i 0; i nums.size(); i)if (countOne(i) k)sum nums[i];return sum;}// 辅函数 - 求整数 x 的置位1的个数int countOne(int x){int count 0;while (x){count x % 2;x / 2;}return count;}
};
// lc codeend注STL函数 __builtin_popcount(i) 可以代替 countOne(i)。
复杂度分析
时间复杂度O(n)其中 n 是数组 nums 的长度。
空间复杂度O(1)。
题目2让所有学生保持开心的分组方法数
思路排序 枚举
条件1这位学生被选中并且被选中的学生人数严格大于 nums[i]。
说明 nums[i] 越小越能满足这个条件。
条件2这位学生没有被选中并且被选中的学生人数 严格小于 nums[i].
说明nums[i] 越大越能满足这个条件。
所以我们将数组 nums 从小到大排序优先选择 nums[i] 小的学生。
枚举选中学生的个数 i0 i n注意特判全选和不选每次判断能够满足让所有学生保持开心最终返回分组方法的数目。
代码
/** lc appleetcode.cn id2860 langcpp** [2860] 让所有学生保持开心的分组方法数*/// lc codestart
class Solution
{
public:int countWays(vectorint nums){int n nums.size();int way 0; // 分组方法的数目sort(nums.begin(), nums.end());// 枚举选中学生个数for (int i 0; i n; i){if (i 0) // 不选学生{// 将 0 与数组的最小值nums[0]比较if (0 nums[0])way;}else if (i n) // 全选学生{// 将 n 与数组的最大值nums[n - 1]比较if (n nums[n - 1])way;}else // 选中 前 i1 ~ n - 1 个学生{// 选中学生的最大值为 nums[i - 1]未选中学生的最小值为 nums[i]// i 必须位于 (nums[i - 1], nums[i]) 才行if (i nums[i - 1] i nums[i])way;}}return way;}
};
// lc codeend复杂度分析
时间复杂度O(nlogn)其中 n 为数组 nums 的长度。瓶颈在排序上。
空间复杂度O(1)。
题目3最大合金数
思路二分查找
拆分成 k 个子问题每台机器最多可以制造多少份合金。
子问题中假设要制造 num 份合金由于 num 越小花费的钱越少num 越多花费的钱越多有单调性可以二分。
对于第 j 份金属
如果 composition[i][j] * num ≤ stock[j]那么无需购买额外的金属。如果 composition[i][j] * num stock[j]那么需要购买额外的金属花费为 (composition[i][j]⋅num−stock[j])⋅cost[j]。
如果总花费超过 budget则无法制造 num 份合金否则可以制造。
确定二分查找的上下界 二分下界0。 二分上界粗略计算一下假设 composition[i] 和 cost[j] 都是 1此时可以制造最多的合金个数为 *min_element(stock.begin(), stock.end()) budget。
代码
/** lc appleetcode.cn id2861 langcpp** [2861] 最大合金数*/// lc codestart// 二分查找class Solution
{
public:int maxNumberOfAlloys(int n, int k, int budget, vectorvectorint composition, vectorint stock, vectorint cost){int ans 0;int mx *min_element(stock.begin(), stock.end()) budget;for (vectorint com : composition){auto check [](long long num) - bool{long long money 0;for (int i 0; i n; i){if (stock[i] com[i] * num){money (com[i] * num - stock[i]) * cost[i];if (money budget)return false;}}return true;};int left 0, right mx 1;while (left right){int mid (left right) / 2;if (check(mid)){ans max(ans, mid);left mid 1;}elseright mid;}}return ans;}
};
// lc codeend
复杂度分析
时间复杂度O(knlogU)其中 Umin(stock)budget。
空间复杂度O(1)。
题目4完全子集的最大元素和
思路
按照下标的 core 值分组。
定义 core(n) 为 n 除去完全平方因子后的剩余结果即 n 的所有出现次数为奇数的质因子相乘。
根据题意如果同一组中有两个数它们的下标的 core 值不同那么这两个数相乘就不是一个完全平方数。
所以同一组内的数字下标的 core 值必须都一样。
那么按照下标的 core 值分组累加同一组的元素和最大元素和即为答案。
代码
/** lc appleetcode.cn id2862 langcpp** [2862] 完全子集的最大元素和*/// lc codestart
class Solution
{
public:long long maximumSum(vectorint nums){int n nums.size();vectorlong long sum(n 1, 0);for (int i 1; i n; i)sum[core(i)] nums[i - 1];return *max_element(sum.begin(), sum.end());}// 辅函数 - 得到 n 除去完全平方因子后的剩余结果 resint core(int n){int res 1;for (int i 2; i * i n; i){int count 0;while (n % i 0){count;n / i;}if (count % 2 1)res * i;}if (n 1)res * n;return res;}
};
// lc codeend复杂度分析
时间复杂度O( n n n\sqrt{n} nn )其中 n 为数组 nums 的长度。
空间复杂度O(n)其中 n 为数组 nums 的长度。
