欢迎大家加QQ群：623375442。感觉双周赛还挺麻烦的。第二题是找规律，第四题又是板子题。
100648. Minimum Operations to Make Array Sum Divisible by K
给你一个整数数组 nums 和一个整数 k。你可以执行以下操作任意次：
- 选择一个下标 i，并将 nums[i] 替换为 nums[i] - 1。
返回使数组元素之和能被 k 整除所需的最小操作次数。
测试样例：
输入：nums = [3,9,7], k = 5
输出：4
解释：
- 对 nums[1] = 9 执行 4 次操作。现在 nums = [3, 5, 7]。
- 数组之和为 15，可以被 5 整除。
解答：这道题目要求我们通过最小化操作次数，使得数组元素之和能够被给定的整数 k 整除。操作的方式是通过将数组中某个元素减去 1 来改变数组元素之和。
首先，我们计算出数组 nums 的元素总和 sum。然后，求出 sum % k 的余数。这个余数表示当前数组和与 k 整除的差距。为了使数组和能被 k 整除，我们需要通过减小某些元素，使得 sum 减少到一个能够被 k 整除的值。具体来说，最小的操作次数就是 sum % k，因为我们可以通过减少某个元素的值，减少总和的余数，使得数组和恰好能够被 k 整除。
class Solution {
public int minOperations(int[] nums, int k) {
int sum = 0;
// 计算数组 nums 的总和
for (int n : nums) {
sum += n;
}
// 返回数组和除以 k 后的余数
// 如果余数为0，表示已经可以被 k 整除，不需要额外操作
return sum % k;
}
}
100628. Number of Unique XOR Triplets I
给你一个长度为 n 的整数数组 nums，其中 nums 是范围 [1, n] 内所有数的 排列 。
XOR 三元组 定义为三个元素的异或值 nums[i] XOR nums[j] XOR nums[k]，其中 i <= j <= k。
返回所有可能三元组 (i, j, k) 中 不同 的 XOR 值的数量。
排列 是一个集合中所有元素的重新排列。
测试样例：
输入：nums = [1,2]
输出：2
解释: 所有可能的 XOR 三元组值为：、
- (0, 0, 0) → 1 XOR 1 XOR 1 = 1
- (0, 0, 1) → 1 XOR 1 XOR 2 = 2
- (0, 1, 1) → 1 XOR 2 XOR 2 = 1
- (1, 1, 1) → 2 XOR 2 XOR 2 = 2
不同的 XOR 值为 {1, 2}，因此输出为 2。
解答：这道题目要求我们计算出所有可能的三元组 (i, j, k) 的不同异或值的数量，其中 nums 数组是范围 [1, n] 内的排列。三元组是指从数组中选择三个不同的元素，通过计算它们的异或值来得到一个结果。需要计算所有不同的异或值的个数。
由于数组 nums 是一个排列，其中的元素是从 1 到 n 的连续整数，可以通过二进制的方法来计算每个可能的异或值。通过计算 nums 数组长度的二进制位数，得到所有可能的不同异或值的个数。最终，返回所有可能的异或值的数量。这个问题的关键点在于 nums 是一个排列，因此我们能够直接根据长度来推测异或值的个数。
class Solution {
public int uniqueXorTriplets(int[] nums) {
int len = nums.length;
// 如果数组长度小于3，则无法形成三元组，直接返回长度
if (len < 3) {
return len;
}
// 计算 nums 长度的二进制位数
int d = 32 - Integer.numberOfLeadingZeros(len);
// 返回 2 的 d 次方，表示不同的三元组个数
return 1 << d;
}
}
100624. Number of Unique XOR Triplets II
给你一个整数数组 nums 。
XOR 三元组 定义为三个元素的异或值 nums[i] XOR nums[j] XOR nums[k]，其中 i <= j <= k。
返回所有可能三元组 (i, j, k) 中 不同 的 XOR 值的数量。
测试样例：
输入：nums = [1,2]
输出：2
解释: 所有可能的 XOR 三元组值为：、
- (0, 0, 0) → 1 XOR 1 XOR 1 = 1
- (0, 0, 1) → 1 XOR 1 XOR 2 = 2
- (0, 1, 1) → 1 XOR 2 XOR 2 = 1
- (1, 1, 1) → 2 XOR 2 XOR 2 = 2
解答：这道题目和上一题类似，但需要考虑更多的细节，尤其是如何高效地计算异或三元组的不同值。具体来说，我们需要遍历所有的三元组 (i, j, k)，并计算它们的异或值。为了确保每个异或值的唯一性，我们需要用一个布尔数组来记录每个异或值是否已经出现过。
通过双重遍历，我们首先计算出每两个元素之间的异或值，并记录这些值。然后，我们再次遍历所有可能的异或值，结合当前元素计算出新的异或值，并检查这个值是否已经出现过。如果没有出现过，则将其记录，并增加结果的计数。这个过程需要通过巧妙的数组操作来避免重复计算，从而提高效率。
class Solution {
public int uniqueXorTriplets(int[] nums) {
// 定义两个布尔数组来记录异或值是否有效
boolean[] isValid1 = new boolean[2048], isValid2 = new boolean[2048];
int res = 0;
// 遍历每个元素
for (int i = 0; i < nums.length; ++i) {
// 计算当前元素与之前所有元素的异或值
for (int j = 0; j <= i; ++j) {
isValid1[nums[i] ^ nums[j]] = true;
}
// 检查每个已记录的异或值，并更新结果
for (int j = 0; j < 2048; ++j) {
if (isValid1[j]) {
// 计算当前异或值与当前元素的异或值
int tmp = j ^ nums[i];
// 如果这个值未出现过，则记录并增加结果计数
if (!isValid2[tmp]) {
isValid2[tmp] = true;
++res;
}
}
}
}
return res;
}
}
100632. Shortest Path in a Weighted Tree
给你一个整数 n 和一个以节点 1 为根的无向带权树，该树包含 n 个编号从 1 到 n 的节点。它由一个长度为 n - 1 的二维数组 edges 表示，其中 edges[i] = [ui, vi, wi] 表示一条从节点 ui 到 vi 的无向边，权重为 wi。
同时给你一个二维整数数组 queries，长度为 q，其中每个 queries[i] 为以下两种之一：
- [1, u, v, w'] – 更新 节点 u 和 v 之间边的权重为 w'，其中 (u, v) 保证是 edges 中存在的边。
- [2, x] – 计算 从根节点 1 到节点 x 的 最短 路径距离。
返回一个整数数组 answer，其中 answer[i] 是对于第 i 个 [2, x] 查询，从节点 1 到 x 的最短路径距离。
测试样例：
输入：n = 2, edges = [[1,2,7]], queries = [[2,2],[1,1,2,4],[2,2]]
输出：[7,4]
解释: 查询 [2,2]：从根节点 1 到节点 2 的最短路径为 7。操作 [1,1,2,4]：边 (1,2) 的权重从 7 变为 4。查询 [2,2]：从根节点 1 到节点 2 的最短路径为 4。最长的特殊路径是 1 -> 2 -> 4 和 1 -> 3 -> 6 -> 8，两者的长度都是 9。所有最长特殊路径中最小的节点数是 3 。
解答：这道题目涉及到一个无向带权树，其中每条边有一个权重。我们需要处理两种类型的查询：
- 更新一条边的权重；
- 计算从根节点到某个节点的最短路径距离。
为了高效地处理这些查询，首先我们可以通过深度优先遍历（DFS）预处理树的基本信息，如每个节点的入度、初始距离、深度等。同时，我们使用二进制索引树（BIT）来优化权重更新和最短路径查询的效率。
在处理更新操作时，我们通过计算权重差异来调整二进制索引树（BIT）。在处理查询操作时，我们使用 BIT 来高效地计算从根节点到指定节点的最短路径。通过这种方式，我们能够在每次查询时快速获取最短路径距离，而无需重新遍历整棵树。
总结来说，这道题目的关键点是如何利用树的结构和二进制索引树（BIT）来处理动态的权重更新和路径查询。
class Solution {
public int[] treeQueries(int n, int[][] _edges, int[][] queries) {
// 初始化数据
Data data = new Data(n, _edges);
// 深度优先遍历树，计算每个节点的入度、距离、深度等信息
dfs(1, 0, 0, 0, data);
// 初始化一个二进制索引树（BIT）来优化查询操作
BIT bit = new BIT(n + 1);
List<Integer> res = new ArrayList<>();
// 处理所有查询
for (int[] query : queries) {
if (query[0] == 1) {
// 更新操作：修改边的权重
int u = query[1], v = query[2], newWeight = query[3];
int child;
// 根据深度判断哪个节点是子节点
if (data.depth[u] > data.depth[v]) {
child = u;
} else {
child = v;
}
// 计算权重差异，并更新 BIT
int diff = newWeight - data.edgeWeight[child];
if (diff != 0) {
bit.update(data.in[child], diff);
bit.update(data.out[child], -diff);
data.edgeWeight[child] = newWeight;
}
} else if (query[0] == 2) {
// 查询操作：计算从根节点到指定节点的最短路径距离
int x = query[1];
int curDist = data.initDist[x] + bit.query(data.in[x]);
res.add(curDist);
}
}
// 返回查询结果
int[] resArr = new int[res.size()];
for (int i = 0; i < resArr.length; ++i) {
resArr[i] = res.get(i);
}
return resArr;
}
// 深度优先遍历树，记录每个节点的入度、深度、初始距离等信息
private void dfs(int node, int parent, int dist, int d, Data data) {
data.in[node] = data.timer++;
data.initDist[node] = dist;
data.depth[node] = d;
for (int[] n : data.edges[node]) {
int nextNode = n[0];
int weight = n[1];
if (nextNode == parent) continue;
data.edgeWeight[nextNode] = weight;
dfs(nextNode, node, dist + weight, d + 1, data);
}
data.out[node] = data.timer;
}
}
// 二进制索引树（BIT）的实现，用于快速更新和查询
class BIT {
int n;
int[] tree;
BIT(int n) {
this.n = n;
tree = new int[n + 1];
}
// 更新操作
public void update(int i, int val) {
while (i <= n) {
tree[i] += val;
i += i & -i;
}
}
// 查询操作
public int query(int i) {
int sum = 0;
while (i > 0) {
sum += tree[i];
i -= i & -i;
}
return sum;
}
}
// 存储树的相关数据结构
class Data {
int[] in, out, depth;
int[] initDist;
int timer = 1;
int[] edgeWeight;
List<int[]>[] edges;
public Data(int n, int[][] _edges) {
in = new int[n + 1];
out = new int[n + 1];
depth = new int[n + 1];
initDist = new int[n + 1];
edgeWeight = new int[n + 1];
edges = new List[n + 1];
for (int i = 1; i <= n; i++) {
edges[i] = new ArrayList<>();
}
// 初始化树的边信息
for (int[] e : _edges) {
int u = e[0], v = e[1], w = e[2];
edges[u].add(new int[]{v, w});
edges[v].add(new int[]{u, w});
}
}
}