Leetcode 第 363 场周赛题解

题目1：2859. 计算 K 置位下标对应元素的和

思路

模拟。

秒杀题。

代码

/** @lc app=leetcode.cn id=2859 lang=cpp** [2859] 计算 K 置位下标对应元素的和*/// @lc code=start
class Solution
{
public:int sumIndicesWithKSetBits(vector<int> &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 code=end

注：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] 小的学生。

枚举选中学生的个数 i，0 <= i <= n，注意特判全选和不选，每次判断能够满足让所有学生保持开心，最终返回分组方法的数目。

代码

/** @lc app=leetcode.cn id=2860 lang=cpp** [2860] 让所有学生保持开心的分组方法数*/// @lc code=start
class Solution
{
public:int countWays(vector<int> &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 // 选中 前 i（1 ~ 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 code=end

复杂度分析

时间复杂度：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 app=leetcode.cn id=2861 lang=cpp** [2861] 最大合金数*/// @lc code=start// 二分查找class Solution
{
public:int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>> &composition, vector<int> &stock, vector<int> &cost){int ans = 0;int mx = *min_element(stock.begin(), stock.end()) + budget;for (vector<int> &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 code=end

复杂度分析

时间复杂度：O(knlogU)，其中 U=min⁡(stock)+budget。

空间复杂度：O(1)。

题目4：完全子集的最大元素和

思路

按照下标的 core 值分组。

定义 core(n) 为 n 除去完全平方因子后的剩余结果，即 n 的所有出现次数为奇数的质因子相乘。

根据题意，如果同一组中有两个数，它们的下标的 core 值不同，那么这两个数相乘，就不是一个完全平方数。

所以，同一组内的数字下标的 core 值必须都一样。

那么按照下标的 core 值分组，累加同一组的元素和，最大元素和即为答案。

代码

/** @lc app=leetcode.cn id=2862 lang=cpp** [2862] 完全子集的最大元素和*/// @lc code=start
class Solution
{
public:long long maximumSum(vector<int> &nums){int n = nums.size();vector<long 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 code=end

复杂度分析

时间复杂度：O($n\sqrt{n}$)，其中 n 为数组 nums 的长度。

空间复杂度：O(n)，其中 n 为数组 nums 的长度。