leetcode weekly contest 338

第四题的换根 dp 还是比较难的题目

6354. K 件物品的最大和

袋子中装有一些物品，每个物品上都标记着数字 1 、0 或 -1 。

给你四个非负整数 numOnes 、numZeros 、numNegOnes 和 k 。

袋子最初包含：

numOnes 件标记为 1 的物品。
numZeroes 件标记为 0 的物品。
numNegOnes 件标记为 -1 的物品。

现计划从这些物品中恰好选出 k 件物品。返回所有可行方案中，物品上所标记数字之和的最大值。

示例 1：

输入：numOnes = 3, numZeros = 2, numNegOnes = 0, k = 2
输出：2
解释：袋子中的物品分别标记为 {1, 1, 1, 0, 0} 。取 2 件标记为 1 的物品，得到的数字之和为 2 。
可以证明 2 是所有可行方案中的最大值。

示例 2：

输入：numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4
输出：3
解释：袋子中的物品分别标记为 {1, 1, 1, 0, 0} 。取 3 件标记为 1 的物品，1 件标记为 0 的物品，得到的数字之和为 3 。
可以证明 3 是所有可行方案中的最大值。

提示：

0 <= numOnes, numZeros, numNegOnes <= 50
0 <= k <= numOnes + numZeros + numNegOnes

地址

https://leetcode.cn/contest/weekly-contest-338/problems/k-items-with-the-maximum-sum/

题意

直接模拟

思路

直接模拟即可
复杂度分析：

时间复杂度：$O(1)$。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        if (numOnes >= k) {
            return k;
        } else if (numOnes + numZeros >= k) {
            return numOnes;
        } else {
            return numOnes - (k - numOnes - numZeros);
        }
    }
};

6355. 质数减法运算

给你一个下标从 0 开始的整数数组 nums ，数组长度为 n 。

你可以执行无限次下述运算：

选择一个之前未选过的下标 i ，并选择一个 严格小于 nums[i] 的质数 p ，从 nums[i] 中减去 p 。

如果你能通过上述运算使得 nums 成为严格递增数组，则返回 true ；否则返回 false 。

严格递增数组 中的每个元素都严格大于其前面的元素。

示例 1：

输入：nums = [4,9,6,10]
输出：true
解释：
在第一次运算中：选择 i = 0 和 p = 3 ，然后从 nums[0] 减去 3 ，nums 变为 [1,9,6,10] 。
在第二次运算中：选择 i = 1 和 p = 7 ，然后从 nums[1] 减去 7 ，nums 变为 [1,2,6,10] 。
第二次运算后，nums 按严格递增顺序排序，因此答案为 true 。

示例 2：

输入：nums = [6,8,11,12]
输出：true
解释：nums 从一开始就按严格递增顺序排序，因此不需要执行任何运算。

示例 3：

输入：nums = [5,8,3]
输出：false
解释：可以证明，执行运算无法使 nums 按严格递增顺序排序，因此答案是 false 。

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 1000
nums.length == n

地址

https://leetcode.cn/contest/weekly-contest-338/problems/prime-subtraction-operation/

题意

贪心

思路

简单的贪心思路即可，由于数组中的每个元素只能减去一次质数，因此我们尽可能的选择与 $nums[i]$ 最接近的质数相减，且需满足 $nums[i] - p > nums[i - 1]$，我们依次按照上述的贪心算法模拟即可。
我们可以提前用欧拉法筛选出所有的素数，然后利用二分查找即可即可在 $O(n \log n)$ 的时间复杂度内完成检测操作。
- 当我们发现减去最小的质数仍然不能满足题目要求时，此时我们需要判断 $nums[i] > nums[i-1]$，如果满足则跳过；
- 如果不满足，则认为无法完成操作。
复杂度分析：

时间复杂度：$O(n \log U)$，其中 $n$ 为数组的长度。
空间复杂度：$O(U)$，其中 $U$ 表示数组的最大元素。

代码

class Solution {
public:
    bool primeSubOperation(vector<int>& nums) {
        int n = nums.size();
        int m = *max_element(nums.begin(), nums.end());
        vector<int> prime;
        vector<bool> vis(m + 1, false);
        for (int i = 2; i <= m; i++) {
            if (!vis[i]) {
                prime.emplace_back(i);
                for (int j = i; j <= m; j += i) {
                    vis[j] = true;
                }
            }
        }
        int pre = 0;
        for (int i = 0; i < n; i++) {
            auto it = lower_bound(prime.begin(), prime.end(), nums[i] - pre);
            if (it == prime.begin()) {
                if (nums[i] <= pre) {
                    return false;
                }
            } else {
                it--;
                nums[i] -= *it;
            }
            pre = nums[i];
        }
        return true;
    }
};

6357. 使数组元素全部相等的最少操作次数

给你一个正整数数组 nums 。

同时给你一个长度为 m 的整数数组 queries 。第 i 个查询中，你需要将 nums 中所有元素变成 queries[i] 。你可以执行以下操作任意次：

将数组里一个元素增大或者减小 1 。

请你返回一个长度为 m 的数组 answer ，其中 answer[i]是将 nums 中所有元素变成 queries[i] 的最少操作次数。

注意，每次查询后，数组变回最开始的值。

示例 1：

输入：nums = [3,1,6,8], queries = [1,5]
输出：[14,10]
解释：第一个查询，我们可以执行以下操作：
- 将 nums[0] 减小 2 次，nums = [1,1,6,8] 。
- 将 nums[2] 减小 5 次，nums = [1,1,1,8] 。
- 将 nums[3] 减小 7 次，nums = [1,1,1,1] 。
第一个查询的总操作次数为 2 + 5 + 7 = 14 。
第二个查询，我们可以执行以下操作：
- 将 nums[0] 增大 2 次，nums = [5,1,6,8] 。
- 将 nums[1] 增大 4 次，nums = [5,5,6,8] 。
- 将 nums[2] 减小 1 次，nums = [5,5,5,8] 。
- 将 nums[3] 减小 3 次，nums = [5,5,5,5] 。
第二个查询的总操作次数为 2 + 4 + 1 + 3 = 10 。

示例 2：

输入：nums = [2,9,6,3], queries = [10]
输出：[20]
解释：我们可以将数组中所有元素都增大到 10 ，总操作次数为 8 + 1 + 4 + 7 = 20 。

提示：

n == nums.length
m == queries.length
1 <= n, m <= 105
1 <= nums[i], queries[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-338/problems/minimum-operations-to-make-all-array-elements-equal/

题意

前缀和

思路

本题为经典题目，已经出现过很多次的题目了，利用排序和前缀和，还有二分查找即可。
首先我们将数组进行排序，并求出数组的前缀和，每次查询元素为 $x$ 时，此时我们利用二分查找很快可以找到比 $x$ 大的元素的个数，以及比 $x$ 小的元素的个数，此时我们利用前缀和求出所有小于 $x$ 的元素之和以及所有大于 $x$ 的元素之和，然后就很快利用前缀和计算出来。
复杂度分析：

时间复杂度：$O(n \log n)$，其中 $n$ 为数组的长度。
空间复杂度：$O(n)$，其中 $n$ 为数组的长度。

代码

class Solution {
public:
    vector<long long> minOperations(vector<int>& nums, vector<int>& queries) {
        int n = nums.size();
        int m = queries.size();
        vector<long long> res(m);
        sort(nums.begin(), nums.end());
        vector<long long> sum(n + 1);
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
        for (int i = 0; i < m; i++) {
            auto it = upper_bound(nums.begin(), nums.end(), queries[i]);
            int x = it - nums.begin();
            res[i] = (long long)x * queries[i] + sum[n] - 2 * sum[x] - (long long)(n - x) * queries[i];
        }
        return res;
    }
};

6356. 收集树中金币

给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，1 表示节点 i 处有一个金币。

一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：

收集距离当前节点距离为 2 以内的所有金币，或者
移动到树中一个相邻节点。

你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。

如果你多次经过一条边，每一次经过都会给答案加一。

示例 1：

输入：coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：从节点 2 出发，收集节点 0 处的金币，移动到节点 3 ，收集节点 5 处的金币，然后移动回节点 2 。

示例 2：

输入：coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]
输出：2
解释：从节点 0 出发，收集节点 4 和 3 处的金币，移动到节点 2 处，收集节点 7 处的金币，移动回节点 0 。

提示：

n == coins.length
1 <= n <= 3 * 104
0 <= coins[i] <= 1
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges 表示一棵合法的树。

地址

https://leetcode.cn/contest/weekly-contest-338/problems/collect-coins-in-a-tree/

题意

拓扑排序

思路

首先我们将所有不带金币的叶子节点全部去掉，我们用拓扑排序即可，每次将不含金币且为叶子节点的节点加入到队列中，我们即可将所有的叶子节点全部去掉；任意一点为根的欧拉回路长度都是 边数 * 2
由于每个节点最多只能去掉最外面的两层，因此我们将最外面的两层用拓扑排序去掉，此时剩余未访问的节点为 $m$ 个，此时 $m$ 个节点构成的边数为 $m-1$ 条边，由于此时需要回到起点，此时每次边都需要访问两次，因此此时需要的操作次数为 $2 * (m - 1)$ 次。
复杂度分析：

时间复杂度：$O(n)$，其中$ n$ 表示节点的数目。
空间复杂度：$O(n + m)$，其中$ n$ 表示节点的数目。

代码

class Solution {
public:
    int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
        int n = coins.size();
        int m = edges.size();
        vector<int> degree(n);
        vector<unordered_set<int>> adj(n);

        for (auto v : edges) {
            int x = v[0], y = v[1];
            adj[x].emplace(y);
            adj[y].emplace(x);
            degree[x]++;
            degree[y]++;
        }

        /* 去掉所有不含金币的叶子节点*/
        queue<int> qu;
        vector<bool> visit(n, false);
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1 && coins[i] == 0) {
                qu.emplace(i);
                degree[i]--;
            }
        }
        while (!qu.empty()) {
            int curr = qu.front();
            visit[curr] = true;
            qu.pop();
            for (auto v : adj[curr]) {
                degree[v]--;
                if (degree[v] == 1 && coins[v] == 0) {
                    qu.emplace(v);
                }
            }
        }

        /* 再次拓扑排序，去掉最外面的两层 */
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1 && coins[i] == 1) {
                qu.emplace(i);
                degree[i]--;
                visit[i] = true;
            }
        }
        for (int i = 0; i < 2; i++) {
            int sz = qu.size();
            for (int j = 0; j < sz; j++) {
                int curr = qu.front();
                visit[curr] = true;
                qu.pop();
                for (auto v : adj[curr]) {
                    degree[v]--;
                    if (degree[v] == 1) {
                        qu.emplace(v);
                    }
                }
            }
        }
        int tot = 0;
        /* 统计未访问过的节点即可*/
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                tot++;
            }
        }
        return tot == 0 ? 0 : (tot - 1) * 2;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://whistle-wind.com/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛题解

← 【2023】新年计划 leetcode biweekly contest 101 →

扫描二维码，分享此文章