6354. K Items With the Maximum Sum
袋子中装有一些物品，每个物品上都标记着数字 1 、0 或 -1 。
给你四个非负整数 numOnes 、numZeros 、numNegOnes 和 k 。
袋子最初包含：
- numOnes 件标记为 1 的物品。
- numZeroes 件标记为 0 的物品。
- numNegOnes 件标记为 -1 的物品。
现计划从这些物品中恰好选出 k 件物品。返回所有可行方案中，物品上所标记数字之和的最大值。
测试样例
输入：numOnes = 3, numZeros = 2, numNegOnes = 0, k = 2
输出：2
解答：这道题目从1->0->-1这个顺序寻找
class Solution {
public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
int res = Math.min(numOnes, k);
k -= res;
if (k > 0) {
int d = Math.min(numZeros, k);
k -= d;
}
if (k > 0) {
res -= k;
}
return res;
}
}6355. Prime Subtraction Operation
给你一个下标从 0 开始的整数数组 nums ，数组长度为 n 。
你可以执行无限次下述运算：
- 选择一个之前未选过的下标 i ，并选择一个 严格小于 nums[i] 的质数 p ，从 nums[i] 中减去 p 。
如果你能通过上述运算使得 nums 成为严格递增数组，则返回 true ；否则返回 false 。
严格递增数组 中的每个元素都严格大于其前面的元素。
测试样例：
输入：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 。
解答: 需要仔细阅读题目，比如之前未选过的下标 i....其他就是贪婪了
class Solution {
private static final int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};
public boolean primeSubOperation(int[] nums) {
int last = 0;
for (int n : nums) {
if (n <= last) {
return false;
}
int best = -1;
for (int p : primes) {
if (p < n && n - p > last) {
best = n - p;
} else {
break;
}
}
if (best == -1) {
best = n;
}
last = best;
}
return true;
}
}6357. Minimum Operations to Make All Array Elements Equal
给你一个正整数数组 nums 。
同时给你一个长度为 m 的整数数组 queries 。第 i 个查询中，你需要将 nums 中所有元素变成 queries[i] 。你可以执行以下操作 任意 次：
- 将数组里一个元素 增大 或者 减小 1 。
请你返回一个长度为 m 的数组 answer ，其中 answer[i]是将 nums 中所有元素变成 queries[i] 的 最少 操作次数。
注意，每次查询后，数组变回最开始的值。
测试样例
输入：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 。
解答：这道题目本质是前缀和。将nums和queries排序后，然后寻找小于queries[i]部分。这时候前缀为需要增加部分，后缀为需要减去部分。
class Solution {
public List<Long> minOperations(int[] nums, int[] queries) {
Arrays.sort(nums);
long sum = 0;
for (int i : nums) sum += i;
List<Long> res = new ArrayList<>();
Integer[] sort = new Integer[queries.length];
for (int i = 0; i < sort.length; ++i) {
sort[i] = i;
res.add(0L);
}
Arrays.sort(sort, (a, b) -> (queries[a] - queries[b]));
int p = 0;
long preSum = 0;
for (int i : sort) {
long q = queries[i];
while (p < nums.length && nums[p] < q) {
preSum += nums[p];
++p;
}
long diff = (sum - preSum) - q * (nums.length - p) + q * p - (preSum);
res.set(i, diff);
}
return res;
}
}6356. Collect Coins in a Tree
给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，1 表示节点 i 处有一个金币。
一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：
- 收集距离当前节点距离为 2 以内的所有金币，或者
- 移动到树中一个相邻节点。
你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。
如果你多次经过一条边，每一次经过都会给答案加一。
测试样例
输入：coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：
从节点 2 出发，收集节点 0 处的金币，移动到节点 3 ，收集节点 5 处的金币，然后移动回节点 2 。
nums 的 MEX 是 4 。可以证明 4 是可以取到的最大 MEX 。
解答：这道题目周赛的时候确实没想到，看了别人解答，就贴一下我的理解吧。
这道题目一共分成3步：
- 去除所有不存在金币的叶子节点
- 从已经是叶子节点的金币点开始回溯2格
- 由于题目要求返回根节点，所有经过第二步留下的节点所对应的边都需要遍历2次
class Solution {
public int collectTheCoins(int[] coins, int[][] edges) {
HashSet<Integer> sets[] = new HashSet[coins.length], set = new HashSet<>();
for (int i = 0; i < coins.length; i++) {
sets[i] = new HashSet<>();
}
for (int[] edge : edges) {
sets[edge[0]].add(edge[1]);
sets[edge[1]].add(edge[0]);
}
int count = coins.length * 2 - 2;
for (int i = 0, j; i < coins.length; i++) {
for (j = i; sets[j].size() == 1 && coins[j] == 0; count -= 2) {
int tmp = sets[j].iterator().next();
sets[tmp].remove(j);
sets[j].remove(tmp);
j = tmp;
}
if (sets[j].size() == 1) {
set.add(j);
}
}
for (int i = 0; i < 2; i++) {
HashSet<Integer> next = new HashSet<>();
for (int j : set) {
if (sets[j].size() == 1) {
int tmp = sets[j].iterator().next();
sets[tmp].remove(j);
if (sets[tmp].size() == 1) {
next.add(tmp);
}
sets[j].remove(tmp);
count -= 2;
}
}
set = next;
}
return count;
}
}