12-周赛338总结
前三题做的很快，第三题先超时了一次又因为数据WA了一次，看到第四题，果断放弃，然后恶补了一下拓扑排序
最近事情好多，加油！！
K 件物品的最大和【LC2600】
袋子中装有一些物品，每个物品上都标记着数字 1 、0 或 -1 。
给你四个非负整数 numOnes 、numZeros 、numNegOnes 和 k 。
袋子最初包含：
numOnes件标记为1的物品。numZeroes件标记为0的物品。numNegOnes件标记为-1的物品。
现计划从这些物品中恰好选出 k 件物品。返回所有可行方案中，物品上所标记数字之和的最大值。
- 思路：贪心
每次优先取数字较大的数字，取完了再取次大的，保证最终数字之和最大 - 实现
class Solution { public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) { if (k <= numOnes){ return k; }else if (k > numOnes && k <= numOnes + numZeros){ return numOnes; }else{ return numOnes - (k - numOnes - numZeros); } } }
质数减法运算【LC2601】
给你一个下标从 0 开始的整数数组
nums，数组长度为n。你可以执行无限次下述运算：
- 选择一个之前未选过的下标
i，并选择一个 严格小于nums[i]的质数p，从nums[i]中减去p
如果你能通过上述运算使得 nums 成为严格递增数组，则返回 true ；否则返回 false 。
严格递增数组 中的每个元素都严格大于其前面的元素
倒序遍历
- 思路：贪心+枚举
class Solution { public boolean primeSubOperation(int[] nums) { int n = nums.length; for (int i = n - 2; i >= 0; i--){ if (nums[i] >= nums[i + 1]){// nums[i]需要至少减小至 nums[i+1] - 1 nums[i] - (nums[i+1] - 1) boolean flag = false; for (int j = nums[i] - (nums[i+1] - 1); j < nums[i]; j++){ if (isPrime(j)){ nums[i] -= j; flag = true; break; } } if (!flag) return false; } } return true; } public boolean isPrime(int num){ if (num <= 1) return false; for (int i = 2; i < num; i++){ if (num % i == 0){ return false; } } return true; } }
class Solution { private final static int MX = 1000; private final static int[] primes = new int[169]; static { var np = new boolean[MX + 1]; int pi = 1; // primes[0] = 0 避免二分越界 for (int i = 2; i <= MX; ++i) if (!np[i]) { primes[pi++] = i; // 预处理质数列表 for (int j = i; j <= MX / i; ++j) np[i * j] = true; } } public boolean primeSubOperation(int[] nums) { int pre = 0; for (int x : nums) { if (x <= pre) return false; int j = lowerBound(primes, x - pre); pre = x - primes[j - 1]; } return true; } // 见 https://www.bilibili.com/video/BV1AP41137w7/ private int lowerBound(int[] nums, int target) { int left = -1, right = nums.length; // 开区间 (left, right) while (left + 1 < right) { // 区间不为空 // 循环不变量： // nums[left] < target // nums[right] >= target int mid = left + (right - left) / 2; if (nums[mid] < target) left = mid; // 范围缩小到 (mid, right) else right = mid; // 范围缩小到 (left, mid) } return right; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/prime-subtraction-operation/solutions/2191560/jian-ji-xie-fa-shai-zhi-shu-er-fen-cha-z-wj7i/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
使数组元素全部相等的最少操作次数【LC2602】
给你一个正整数数组
nums。同时给你一个长度为
m的整数数组queries。第i个查询中，你需要将nums中所有元素变成queries[i]。你可以执行以下操作 任意 次：
- 将数组里一个元素 增大 或者 减小
1。请你返回一个长度为
m的数组answer，其中answer[i]是将nums中所有元素变成queries[i]的 最少 操作次数。注意，每次查询后，数组变回最开始的值。
class Solution { public List<Long> minOperations(int[] nums, int[] queries) { List<Long> res = new ArrayList<>(); Long sum = 0L; int n = nums.length; long[] preSum = new long[n + 1]; Arrays.sort(nums); for (int i = 0; i < n; i++){ preSum[i + 1] = preSum[i] + nums[i]; } for (int q : queries){ int index = binarySearch(nums, q); long low = preSum[index + 1]; long high = preSum[n] - preSum[index + 1]; long count1 = (long)q * (index + 1) - low; long count2 = high - (long)q * (n - index - 1); res.add(count1 + count2); } return res; } public int binarySearch(int[] nums, int target){ int l = 0, r = nums.length - 1; while (l <= r){ int mid = (l + r) >> 1; if (nums[mid] <= target){ l = mid + 1; }else{ r = mid - 1; } } return r; } }
收集树中金币【LC2603】
给你一个
n个节点的无向无根树，节点编号从0到n - 1。给你整数n和一个长度为n - 1的二维整数数组edges，其中edges[i] = [ai, bi]表示树中节点ai和bi之间有一条边。再给你一个长度为n的数组coins，其中coins[i]可能为0也可能为1，1表示节点i处有一个金币。
一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：
- 收集距离当前节点距离为
2以内的所有金币，或者 - 移动到树中一个相邻节点。
你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。
如果你多次经过一条边，每一次经过都会给答案加一。
思路：拓扑排序
- 首先，我们可以去掉不包含金币的子树，因为访问其中任何一个点都毫无意义。
- 如果所有在叶子上的金币全部都能收集到，那么我们可以收集到树上所有金币。因此可以去除两轮叶子，剩余的结点即为必须经过的结点【两轮拓扑排序】
- 从距离叶子为2的节点处出发【局部最优】，收集树中所有的金币，并且回到出发节点时经过的边数最少【全局最优】。
- 实现
- 无向图，节点度为1时为叶子
class Solution { public int collectTheCoins(int[] coins, int[][] edges) { int n = coins.length; List<Integer> g[] = new ArrayList[n]; Arrays.setAll(g, e -> new ArrayList<>()); var deg = new int[n]; for (var e : edges) { int x = e[0], y = e[1]; g[x].add(y); g[y].add(x); // 建图 ++deg[x]; ++deg[y]; } // 用拓扑排序「剪枝」：去掉没有金币的子树 var q = new ArrayDeque<Integer>(); for (int i = 0; i < n; ++i) if (deg[i] == 1 && coins[i] == 0) // 无金币叶子 q.add(i); while (!q.isEmpty()) { int x = q.peek(); q.pop(); for (int y : g[x]) if (--deg[y] == 1 && coins[y] == 0) q.add(y); } // 再次拓扑排序 for (int i = 0; i < n; ++i) if (deg[i] == 1 && coins[i] == 1) // 有金币叶子 q.add(i); if (q.size() <= 1) return 0; // 至多一个有金币的叶子，直接收集 var time = new int[n]; while (!q.isEmpty()) { int x = q.peek(); q.pop(); for (int y : g[x]) if (--deg[y] == 1) { time[y] = time[x] + 1; // 记录入队时间 q.add(y); } } // 统计答案 int ans = 0; for (var e : edges) if (time[e[0]] >= 2 && time[e[1]] >= 2) ans += 2; return ans; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/collect-coins-in-a-tree/solutions/2191371/tuo-bu-pai-xu-ji-lu-ru-dui-shi-jian-pyth-6uli/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 升级：如果把题目中的 2 换成 0,1,2,3,⋯ ,n−1，你能把这些情况对应的答案全部算出来吗？
遍历所有的边，如果两个节点的入队时间均大于q（最大距离），那么表示这条边必须要经过，结果+2
