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;
                }
                else
                    right = 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 除去完全平方因子后的剩余结果 res
    int 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 的长度。