100231. Minimum Operations to Exceed Threshold Value I
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一次操作中，你可以删除 nums 中的最小元素。
你需要使数组中的所有元素都大于或等于 k ，请你返回需要的 最少 操作次数。
测试样例：
输入：nums = [2,11,10,1,3], k = 10
输出：3
解释：第一次操作后，nums 变为 [2, 11, 10, 3] 。第二次操作后，nums 变为 [11, 10, 3] 。第三次操作后，nums 变为 [11, 10] 。此时，数组中的所有元素都大于等于 10 ，所以我们停止操作。使数组中所有元素都大于等于 10 需要的最少操作次数为 3 。
解答：这题只是单纯寻找所有小于k的数个数。
class Solution {
public int minOperations(int[] nums, int k) {
int count = 0;
for (int n : nums) {
if (n < k) {
++count;
}
}
return count;
}
}100211. Apply Operations to Make String Empty
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一次操作中，你将执行：
- 选择 nums 中最小的两个整数 x 和 y 。
- 将 x 和 y 从 nums 中删除。
- 将 min(x, y) * 2 + max(x, y) 添加到数组中的任意位置。
注意，只有当 nums 至少包含两个元素时，你才可以执行以上操作。
你需要使数组中的所有元素都大于或等于 k ，请你返回需要的 最少 操作次数。
测试样例：
输入：nums = [2,11,10,1,3], k = 10
输出：2
解释：第一次操作中，我们删除元素 1 和 2 ，然后添加 1 2 + 2 到 nums 中，nums 变为 [4, 11, 10, 3] 。第二次操作中，我们删除元素 3 和 4 ，然后添加 3 2 + 4 到 nums 中，nums 变为 [10, 11, 10] 。此时，数组中的所有元素都大于等于 10 ，所以我们停止操作。使数组中所有元素都大于等于 10 需要的最少操作次数为 2 。
解答：这题保证了，答案一定存在。每次运行必然会减少一个数，最多的操作个数不会大于nums.length。所以我们直接利用优先队列暴力计算次数。
class Solution {
public int minOperations(int[] nums, int k) {
PriorityQueue<Long> queue = new PriorityQueue<>();
for (int n : nums) {
queue.add((long)n);
}
int res = 0;
while (queue.peek() < k) {
long m1 = queue.poll(), m2 = queue.poll();
long next= Math.min(m1, m2) * 2 + Math.max(m1, m2);
queue.add(next);
++res;
}
return res;
}
}100220. Maximum Number of Operations With the Same Score II
给你一棵无根带权树，树中总共有 n 个节点，分别表示 n 个服务器，服务器从 0 到 n - 1 编号。同时给你一个数组 edges ，其中 edges[i] = [ai, bi, weighti] 表示节点 ai 和 bi 之间有一条双向边，边的权值为 weighti 。再给你一个整数 signalSpeed 。
如果两个服务器 a ，b 和 c 满足以下条件，那么我们称服务器 a 和 b 是通过服务器 c 可连接的 ：
- a < b ，a != c 且 b != c 。
- 从 c 到 a 的距离是可以被 signalSpeed 整除的。
- 从 c 到 b 的距离是可以被 signalSpeed 整除的。
- 从 c 到 b 的路径与从 c 到 a 的路径没有任何公共边。
请你返回一个长度为 n 的整数数组 count ，其中 count[i] 表示通过服务器 i 可连接 的服务器对的 数目 。
测试样例：
输入：edges = [[0,1,1],[1,2,5],[2,3,13],[3,4,9],[4,5,2]], signalSpeed = 1
输出：[0,4,6,6,4,0]
解释：由于 signalSpeed 等于 1 ，count[c] 等于所有从 c 开始且没有公共边的路径对数目。在输入图中，count[c] 等于服务器 c 左边服务器数目乘以右边服务器数目。
解答：这题的描述很差，我看了几遍题目也没看到距离是怎么定义的（虽然看到例子，能够理解是和weight累加有关）。因为题目范围也不大，可以利用暴力。因为从 c 到 b 的路径与从 c 到 a 的路径没有任何公共边，所以我们就一个个点遍历，同时也是一条分支一条分支累加。
class Solution {
private class InternalStructure {
List<Integer>[] edges;
int[][] score;
int signalSpeed;
int curZero, totalZero;
public InternalStructure(int[][] _edges, int _signalSpeed) {
int n = _edges.length + 1;
edges = new List[n];
score = new int[n][n];
signalSpeed = _signalSpeed;
for (int i = 0; i < n; ++i) {
edges[i] = new ArrayList<>();
Arrays.fill(score[i], -1);
}
for (int[] e : _edges) {
edges[e[0]].add(e[1]);
edges[e[1]].add(e[0]);
score[e[0]][e[1]] = e[2];
score[e[1]][e[0]] = e[2];
}
}
}
public int[] countPairsOfConnectableServers(int[][] edges, int signalSpeed) {
int n = edges.length + 1;
InternalStructure structure = new InternalStructure(edges, signalSpeed);
int[] res = new int[n];
for (int i = 0; i < n; ++i) {
int add = 0;
structure.curZero = 0;
structure.totalZero = 0;
for (int nn : structure.edges[i]) {
add += helper(nn, i, 0, structure);
structure.totalZero += structure.curZero;
structure.curZero = 0;
}
res[i] = add;
}
return res;
}
private int helper(int cur, int pre, int sum, InternalStructure structure) {
sum += structure.score[cur][pre];
int res = 0;
if (sum % structure.signalSpeed == 0) {
res += structure.totalZero;
structure.curZero += 1;
}
for (int nn : structure.edges[cur]) {
if (nn != pre) {
res += helper(nn, cur, sum, structure);
}
}
return res;
}
}100210. Find the Maximum Sum of Node Values
给你一棵 n 个节点的 无向 树，节点从 0 到 n - 1 编号。树以长度为 n - 1 下标从 0 开始的二维整数数组 edges 的形式给你，其中 edges[i] = [ui, vi] 表示树中节点 ui 和 vi 之间有一条边。同时给你一个 正 整数 k 和一个长度为 n 下标从 0 开始的 非负 整数数组 nums ，其中 nums[i] 表示节点 i 的 价值 。
日增哥哥想 最大化 树中所有节点价值之和。为了实现这一目标，日增哥哥可以执行以下操作 任意 次（包括 0 次）：
- 选择连接节点 u 和 v 的边 [u, v] ，并将它们的值更新为：
- nums[u] = nums[u] XOR k
- nums[v] = nums[v] XOR k
请你返回日增哥哥通过执行以上操作 任意次 后，可以得到所有节点 价值之和 的 最大值 。
测试样例：
输入：nums = [1,2,1], k = 3, edges = [[0,1],[0,2]]
输出：6
解释：日增哥哥可以通过一次操作得到最大价值和 6 ：选择边 [0,2] 。nums[0] 和 nums[2] 都变为：1 XOR 3 = 2 ，数组 nums 变为：[1,2,1] -> [2,2,2] 。所有节点价值之和为 2 + 2 + 2 = 6 。6 是可以得到最大的价值之和。
解答：比起上周周赛，双周赛的题目真的简单好多。这题需要利用到动态规划，每个点都需要记录它进入前是被XOR或者非XOR 2种状态。利用点+2种状态完成动态规划的计算。对于递推关系，其中又是一个小的动态规划。当前节点和它的节点可以选择操作或者不做操作，这样会进一步转换当前节点的值。所以我们利用一个小的动态规划，记录当前节点被操作/不被操作时的最大的值。
class Solution {
private class InternalStructure {
int[] nums;
int k;
List<Integer>[] edges;
long[][] mem;
public InternalStructure(int[] _nums, int _k, int[][] _edges) {
nums = _nums;
k = _k;
edges = new List[nums.length];
for (int i = 0; i < nums.length; ++i) {
edges[i] = new ArrayList<>();
}
for (int[] e : _edges) {
edges[e[0]].add(e[1]);
edges[e[1]].add(e[0]);
}
mem = new long[nums.length][2];
for (int i = 0; i < nums.length; ++i) {
mem[i][0] = -1;
mem[i][1] = -1;
}
}
}
public long maximumValueSum(int[] nums, int k, int[][] edges) {
InternalStructure structure = new InternalStructure(nums, k, edges);
dfs(0, 0, -1, structure);
return structure.mem[0][0];
}
private long dfs(int cur, int offset, int pre, InternalStructure structure) {
if (structure.mem[cur][offset] == -1) {
if (structure.edges[cur].size() == 1 && pre != -1) {
structure.mem[cur][offset] = getNum(cur, offset, structure);
} else {
long[] tmp = {0, Integer.MIN_VALUE};
for (int n : structure.edges[cur]) {
if (pre != n) {
long b0 = dfs(n, 0, cur, structure), b1 = dfs(n, 1, cur, structure);
long[] next = {0, 0};
next[0] = Math.max(tmp[0] + b0, tmp[1] + b1);
next[1] = Math.max(tmp[1] + b0, tmp[0] + b1);
tmp = next;
}
}
structure.mem[cur][offset] = Math.max(tmp[0] + getNum(cur, offset, structure)
, tmp[1] + getNum(cur, offset ^ 1, structure));
}
}
return structure.mem[cur][offset];
}
private int getNum(int cur, int offset, InternalStructure structure) {
return offset == 1 ? (structure.nums[cur] ^ structure.k) : (structure.nums[cur]);
}
}