欢迎大家加QQ群：623375442，可以方便群里面交流。终于手速场了一次。
100622. Maximum Containers on a Ship
给你一个正整数 n，表示船上的一个 n x n 的货物甲板。甲板上的每个单元格可以装载一个重量 恰好 为 w 的集装箱。
然而，如果将所有集装箱装载到甲板上，其总重量不能超过船的最大承载重量 maxWeight。
请返回可以装载到船上的 最大 集装箱数量。
测试样例：
输入：n = 2, w = 3, maxWeight = 15
输出：4
解释：甲板有 4 个单元格，每个集装箱的重量为 3。将所有集装箱装载后，总重量为 12，未超过 maxWeight。
解答：按照甲板可以承载的货物数和最大承载可以达到的货物数，取较小的。
class Solution {
public int maxContainers(int n, int w, int maxWeight) {
int cells = n * n, maxByWeight = maxWeight / w;
return Math.min(cells, maxByWeight);
}
}100615. Properties Graph
给你一个二维整数数组 properties，其维度为 n x m，以及一个整数 k。
定义一个函数 intersect(a, b)，它返回数组 a 和 b 中 共有的不同整数的数量 。
构造一个 无向图，其中每个索引 i 对应 properties[i]。如果且仅当 intersect(properties[i], properties[j]) >= k（其中 i 和 j 的范围为 [0, n - 1] 且 i != j），节点 i 和节点 j 之间有一条边。
返回结果图中 连通分量 的数量。
测试样例：
输入：properties = [[1,2],[1,1],[3,4],[4,5],[5,6],[7,7]], k = 1
输出：3
解释: 生成的图有 3 个连通分量
解答：我们利用每个数字出现的索引来统计任意两数组之间的公共不同数字的数量，并在公共数字数达到 k 时通过并查集合并对应节点。最后统计并查集中不同根节点的数量，即为连通分量的数目。
class Solution {
public int numberOfComponents(int[][] properties, int k) {
// count[i][j] 记录 properties[i] 和 properties[j] 的公共不同数字个数
int[][] count = new int[properties.length][properties.length];
// common[i] 用于存储数字 i 出现在哪些数组中，数字范围为 [1, 100]
List<Integer>[] common = new List[101];
for (int i = 1; i <= 100; ++i) {
common[i] = new ArrayList<>();
}
// 遍历每个数组，统计每个数字在各数组中出现的情况
for (int i = 0; i < properties.length; ++i) {
// 使用 isMet 数组避免对同一数字重复计数
boolean[] isMet = new boolean[101];
for (int n : properties[i]) {
if (isMet[n]) continue; // 避免重复统计同一数字
isMet[n] = true;
// 对于当前数字 n，更新之前出现过的所有数组的计数
for (int t : common[n]) {
count[t][i] += 1;
count[i][t] += 1;
}
// 记录当前数组 i 包含数字 n
common[n].add(i);
}
}
// 使用并查集将公共数字数达到 k 的数组连接在一起
DSU uf = new DSU(properties.length);
for (int i = 0; i < properties.length; ++i) {
for (int j = i + 1; j < properties.length; ++j) {
if (count[i][j] >= k) {
uf.union(i, j);
}
}
}
// 统计连通分量：同一个根节点代表同一连通分量
boolean[] isMet = new boolean[101];
int res = 0;
for (int i = 0; i < properties.length; ++i) {
int f = uf.find(i);
if (!isMet[f]) {
++res;
isMet[f] = true;
}
}
return res;
}
}
// 并查集（Disjoint Set Union）类，用于维护连通分量
class DSU {
int[] parent;
public DSU(int N) {
parent = new int[N];
// 初始化时，每个节点的父节点为自身
for (int i = 0; i < N; ++i) {
parent[i] = i;
}
}
// 查找根节点（同时进行路径压缩）
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
// 合并两个节点所在的集合
public void union(int x, int y) {
parent[find(x)] = find(y);
}
}100603. Find the Minimum Amount of Time to Brew Potions
给你两个长度分别为 n 和 m 的整数数组 skill 和 mana 。
在一个实验室里，有 n 个巫师，他们必须按顺序酿造 m 个药水。每个药水的法力值为 mana[j]，并且每个药水 必须 依次通过 所有 巫师处理，才能完成酿造。第 i 个巫师在第 j 个药水上处理需要的时间为 timeij = skill[i] * mana[j]。
由于酿造过程非常精细，药水在当前巫师完成工作后 必须 立即传递给下一个巫师并开始处理。这意味着时间必须保持 同步，确保每个巫师在药水到达时 马上 开始工作。
返回酿造所有药水所需的 最短 总时间。
测试样例：
输入：skill = [1,5,2,4], mana = [5,1,4,2]
输出：110
解释: 举个例子，为什么巫师 0 不能在时间 t = 52 前开始处理第 1 个药水，假设巫师们在时间 t = 50 开始准备第 1 个药水。时间 t = 58 时，巫师 2 已经完成了第 1 个药水的处理，但巫师 3 直到时间 t = 60 仍在处理第 0 个药水，无法马上开始处理第 1个药水。
解答：我们使用数组 available 来记录每个巫师处理完前一个药水后可开始下一药水的时间。对于每个药水，我们依次计算每个巫师处理当前药水所需的时间，并确保药水传递时不会出现等待延误，最终返回最后一个巫师完成所有药水的时间。
class Solution {
public long minTime(int[] skill, int[] mana) {
// available[i] 表示第 i 个巫师处理完当前药水后可用的时间
long[] available = new long[skill.length];
// 遍历每个药水
for (int m : mana) {
long maxAdd = 0; // 用于记录因等待而需额外延迟的时间
long st = available[0]; // 第一个巫师处理当前药水的起始时间
// 依次模拟每个巫师处理药水的过程
for (int i = 0; i < skill.length; ++i) {
st += skill[i] * m; // 计算当前巫师处理药水后的完成时间
// 保证传递时刻同步，如果下一个巫师还未准备好，则记录等待时间
if (i + 1 < skill.length && st < available[i + 1]) {
maxAdd = Math.max(maxAdd, available[i + 1] - st);
}
}
// 将等待时间加入第一个巫师的起始时间
st = available[0] + maxAdd;
// 更新所有巫师的可用时间，模拟药水的连续处理过程
for (int i = 0; i < skill.length; ++i) {
st += skill[i] * m;
available[i] = st;
}
}
// 最后一个巫师处理完所有药水的时间即为答案
return available[available.length - 1];
}
}
100559. Minimum Operations to Make Array Elements Zero
给你一个二维数组 queries，其中 queries[i] 形式为 [l, r]。每个 queries[i] 表示了一个元素范围从 l 到 r （包括 l 和 r ）的整数数组 nums 。
在一次操作中，你可以：
- 选择一个查询数组中的两个整数 a 和 b。
- 将它们替换为 floor(a / 4) 和 floor(b / 4)。
你的任务是确定对于每个查询，将数组中的所有元素都变为零的 最少 操作次数。返回所有查询结果的总和。
测试样例：
输入：queries = [[1,2],[2,4]]
输出：3
解释: 对于
queries[0]：
- 初始数组为 nums = [1, 2]。
- 在第一次操作中，选择 nums[0] 和 nums[1]。数组变为 [0, 0]。
- 所需的最小操作次数为 1。
对于 queries[1]：- 初始数组为 nums = [2, 3, 4]。
- 在第一次操作中，选择 nums[0] 和 nums[2]。数组变为 [0, 3, 1]。
- 在第二次操作中，选择 nums[1] 和 nums[2]。数组变为 [0, 0, 0]。
- 所需的最小操作次数为 2。
输出为 1 + 2 = 3。
解答：
对每个查询，我们首先计算区间 [l, r] 内每个数字变为 0 所需的“个体操作次数”。对于一个数字 n，其所需操作次数为: ⌊log_4(n)⌋+1
因为数字 n 落在区间 [4^d, 4^(d+1)-1] 时，其操作次数固定为 d+1。统计区间内所有数字的操作次数之和，再每次操作同时处理两个数字，因此最少操作次数为：⌈sumCost/2⌉
我们将 [l, r] 按照 4 的幂次区间分段累加操作次数，最终求得结果。
class Solution {
public long minOperations(int[][] queries) {
long res = 0;
// 遍历每个查询，累计各查询所需的最少操作次数
for (int[] q : queries) {
res += oneTimeCalculate(q);
}
return res;
}
private long oneTimeCalculate(int[] query) {
// 将查询区间 [l, r] 分别赋值给 l 和 r
long l = query[0], r = query[1];
long res = 0; // 用于累计区间内所有数字的操作次数之和
int d = -1; // d 表示当前 4 的幂次区间的索引，初始为 -1，便于第一次循环时递增为 0
long curSt = 1, curEd = 4 * curSt - 1; // 初始化当前区间为 [1, 3]，即 4^0 到 4^1 - 1
// 遍历所有 4 的幂次区间，直到区间的起始值大于 r
while (true) {
if (curSt > r) break; // 当前区间的起始值大于 r，则结束循环
// 计算区间 [l, r] 与当前 4 的幂次区间 [curSt, curEd] 的交集
long left = Math.max(l, curSt);
long right = Math.min(r, curEd);
++d; // 进入下一个区间，d 自增
// 更新下一个 4 的幂次区间的起始和结束值
curSt *= 4;
curEd = 4 * curSt - 1;
if (left > right) continue; // 如果当前交集为空，则跳过本次循环
long count = right - left + 1; // 计算交集中数字的个数
// 每个数字在当前区间需要 (d + 1) 次操作，累计总操作次数
res += count * (d + 1);
}
// 每次操作可以同时处理两个数字，因此最少操作次数为向上取整 (res / 2)
return (res + 1) / 2;
}
}