欢迎大家加QQ群：623375442。周赛题解都会在周日下午3点左右发布。双周赛第四题太难了，不会做。
3587. Minimum Adjacent Swaps to Alternate Parity
给你一个由互不相同的整数组成的数组 nums 。
在一次操作中，你可以交换任意两个 相邻 元素。
在一个排列中，当所有相邻元素的奇偶性交替出现，我们认为该排列是 有效排列。这意味着每对相邻元素中一个是偶数，一个是奇数。
请返回将 nums 变成任意一种 有效排列 所需的最小相邻交换次数。
如果无法重排 nums 来获得有效排列，则返回 -1。
测试样例：
输入：nums = [2,4,6,5,7]
输出：3
解释：将 5 和 6 交换，数组变成 [2,4,5,6,7]。将 5 和 4 交换，数组变成 [2,5,4,6,7]。将 6 和 7 交换，数组变成 [2,5,4,7,6]。此时是一个有效排列。因此答案是 3。
解答：
- 分类记录：遍历 nums，分别把偶数和奇数的位置索引记录到 evens 和 odds 列表中。
2， 可行性判断：若数组长度为 n，要形成交替排列有两种可能：- 偶数数量 = ⌈n/2⌉，奇数数量 = ⌊n/2⌋，让偶数出现在下标 0,2,4,...（从偶数开始）。
- 奇数数量 = ⌈n/2⌉，偶数数量 = ⌊n/2⌋，让奇数出现在下标 0,2,4,...（从奇数开始）。
- 计算交换次数：若选择某种模式（例如偶数做主），把 evens[i] 期望放到位置 2*i，需要的交换次数等于它和目标位置的距离之和。对所有元素求和即为总交换次数。取两种可能中的最小值即可；若两种都不可行，则返回 -1。
class Solution {
public int minSwaps(int[] nums) {
// 分别记录偶数和奇数在原数组中的索引
List<Integer> evens = new ArrayList<>();
List<Integer> odds = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if ((nums[i] & 1) == 0) evens.add(i); // 偶数下标
else odds.add(i); // 奇数下标
}
int n = nums.length, e = evens.size(), o = odds.size();
long ans = Long.MAX_VALUE;
// 尝试偶数放在偶数下标位置 0,2,4,...
if (e == (n + 1) / 2 && o == n / 2) {
ans = Math.min(ans, calc(evens));
}
// 尝试奇数放在偶数下标位置 0,2,4,...
if (o == (n + 1) / 2 && e == n / 2) {
ans = Math.min(ans, calc(odds));
}
// 若无可行方案返回 -1，否则返回最小交换次数
return ans == Long.MAX_VALUE ? -1 : (int) ans;
}
// 计算将列表 pos 中的元素依次移动到 0,2,4,... 位置所需的交换次数
private long calc(List<Integer> pos) {
long res = 0;
for (int i = 0; i < pos.size(); i++) {
// 期望位置为 2*i，与当前下标之差即交换次数
res += Math.abs(pos.get(i) - 2 * i);
}
return res;
}
}3588. Find Maximum Area of a Triangle
给你一个二维数组 coords，大小为 n x 2，表示一个无限笛卡尔平面上 n 个点的坐标。
找出一个 最大 三角形的 两倍 面积，其中三角形的三个顶点来自 coords 中的任意三个点，并且该三角形至少有一条边与 x 轴或 y 轴平行。严格地说，如果该三角形的最大面积为 A，则返回 2 * A。
如果不存在这样的三角形，返回 -1。
注意，三角形的面积 不能 为零。
测试样例：
输入：x = nums = [6,3,6]
输出：1
解释：唯一的特殊三元组是 (i, j, k) = (0, 1, 2)
解答：
- 预处理横纵坐标映射：
- 用 xMap 保存每个相同 x 值的点在 y 轴上的最小和最大 y。
- 用 yMap 保存每个相同 y 值的点在 x 轴上的最小和最大 x。
- 两种方向分别计算：要三角形至少一条边与 x 轴平行，或与 y 轴平行，两者对称。
- 内部计算：
- 对于固定 x = k 的所有点，若它的 y 范围 (minY, maxY) 不相等，且 k 不是整个点集的最小或最大 x，则可以用这条竖边与横向跨度 (maxX - k) 或 (k - minX) 构造三角形，面积 = 边长乘积的一半，返回的值是两倍面积，即 d1 * d2。
- 取两种方向中的最大值，若都无可行三角形则返回 -1。
class Solution {
public long maxArea(int[][] coords) {
// 全局最小/最大 x, y
int xMin = Integer.MAX_VALUE, xMax = Integer.MIN_VALUE;
int yMin = Integer.MAX_VALUE, yMax = Integer.MIN_VALUE;
// xMap: key=x，value=[该 x 对应的最小 y, 最大 y]
Map<Integer, int[]> xMap = new HashMap<>(), yMap = new HashMap<>();
for (int[] c : coords) {
xMin = Math.min(xMin, c[0]);
xMax = Math.max(xMax, c[0]);
yMin = Math.min(yMin, c[1]);
yMax = Math.max(yMax, c[1]);
// 更新 xMap
if (!xMap.containsKey(c[0])) {
xMap.put(c[0], new int[]{c[1], c[1]}); // 初始化 minY = maxY = c[1]
} else {
int[] tmp = xMap.get(c[0]);
tmp[0] = Math.min(tmp[0], c[1]);
tmp[1] = Math.max(tmp[1], c[1]);
}
// 更新 yMap（同理）
if (!yMap.containsKey(c[1])) {
yMap.put(c[1], new int[]{c[0], c[0]});
} else {
int[] tmp = yMap.get(c[1]);
tmp[0] = Math.min(tmp[0], c[0]);
tmp[1] = Math.max(tmp[1], c[0]);
}
}
// 分别计算 x 方向、y 方向的最大两倍面积
return Math.max(getMax(xMap, xMin, xMax), getMax(yMap, yMin, yMax));
}
// map: key=固定坐标值，value=[该直线上点的最小坐标, 最大坐标]
// min, max：对应另一维度的全局最小/最大
private long getMax(Map<Integer, int[]> map, int min, int max) {
long res = -1;
for (Map.Entry<Integer, int[]> kv : map.entrySet()) {
int k = kv.getKey();
int[] v = kv.getValue();
// 直线上的点不都在同一位置，且该直线不是整体的边界
if (v[0] != v[1] && (k != min || k != max)) {
long d1 = v[1] - v[0]; // 边与轴平行的那条边长
long d2 = Math.max(k - min, max - k); // 与另一条边可能的最大跨度
res = Math.max(res, d1 * d2); // 两倍面积 = d1 * d2
}
}
return res;
}
}3589. Count Prime-Gap Balanced Subarrays
给定一个整数数组 nums 和一个整数 k。
子数组 被称为 质数间隔平衡，如果：
- 其包含 至少两个质数，并且
- 该 子数组 中 最大 和 最小 质数的差小于或等于 k。
返回 nums 中质数间隔平衡子数组的数量。
注意：
- 子数组 是数组中连续的 非空 元素序列。
- 质数是大于 1 的自然数，它只有两个因数，即 1 和它本身。
测试样例：
输入：nums = [1,2,3], k = 1
输出：2
解释：质数间隔平衡子数组有：
- [2,3]：包含 2 个质数（2 和 3），最大值 - 最小值 = 3 - 2 = 1 <= k。
- [1,2,3]：包含 2 个质数（2 和 3）最大值 - 最小值 = 3 - 2 = 1 <= k。
因此，答案为 2。
解答：
- 线段树预处理：构建一个支持区间最大/最小查询的线段树，树中只保留是质数的元素，非质数位置存入操作的初始值（对于最小树是 +∞，最大树是 −∞）。
- 双指针 + 最后两次出现：
- 遍历数组，维护最近两次出现的质数下标 first, second。
- 当第二个质数出现后，若两者之差 > k，则当前窗口不再有效；否则，尝试左指针 left 向右移动，保证窗口中最大/最小质数的差 ≤ k（利用线段树的 range(left, i)）。
- 对于固定 i，窗口内以 left 起点、以 first 结束的所有子数组都满足条件，累计到结果中。
- 时间复杂度约为 O(n · log n)。
class Solution {
public int primeSubarray(int[] nums, int k) {
// 分别维护区间最小值/最大值线段树，只对质数位置有效
SegmentTree min = new SegmentTree(nums, new MinOperation()), max = new SegmentTree(nums, new MaxOperation());
int first = -1, second = -1;
int left = 0;
int res = 0;
for (int i = 0; i < nums.length; ++i) {
if (SegmentTree.isPrime[nums[i]]) {
first = second;
second = i; // 更新最近两次质数出现位置
}
if (first != -1) { // 至少已经出现两个质数
// 若当前两质数差值超出 k，则不计入
if (Math.abs(nums[first] - nums[second]) > k) {
continue;
}
// 调整 left，保证区间 [left,i] 中的最大质数-最小质数 ≤ k
while (left <= first) {
int m = min.range(left, i), x = max.range(left, i);
if (x - m > k) {
++left;
} else {
break;
}
}
// 对于当前 i，所有以 left...first 为起点的子数组都合法
res += (first - left + 1);
}
}
return res;
}
}
// 操作接口
interface Operation {
int operate(int x, int y);
int getInitial();
}
class MinOperation implements Operation {
@Override
public int operate(int x, int y) { return Math.min(x, y); }
@Override
public int getInitial() { return Integer.MAX_VALUE; }
}
class MaxOperation implements Operation {
@Override
public int operate(int x, int y) { return Math.max(x, y); }
@Override
public int getInitial() { return Integer.MIN_VALUE; }
}
class SegmentTree {
int[] tree;
int n;
Operation operation;
// 预先筛好 0..50000 内的质数
static final boolean[] isPrime = new boolean[5_00_01];
static {
Arrays.fill(isPrime, true);
isPrime[0] = false;
isPrime[1] = false;
for (int i = 2; i * i <= 50000; ++i) {
if (isPrime[i]) {
int st = i * i;
while (st <= 50000) {
isPrime[st] = false;
st += i;
}
}
}
}
public SegmentTree(int[] nums, Operation operation) {
if (nums.length > 0) {
this.operation = operation;
n = nums.length;
tree = new int[n * 2];
buildTree(nums);
}
}
// 建树：叶子节点存 nums[j]（若质数），否则存 operation.getInitial()
private void buildTree(int[] nums) {
for (int i = n, j = 0; i < 2 * n; i++, j++)
tree[i] = isPrime[nums[j]] ? nums[j] : operation.getInitial();
for (int i = n - 1; i > 0; --i)
tree[i] = operation.operate(tree[i * 2], tree[i * 2 + 1]);
}
// 区间查询 [l,r]
public int range(int l, int r) {
l += n;
r += n;
int res = operation.getInitial();
while (l <= r) {
if ((l % 2) == 1) {
res = operation.operate(res, tree[l]);
l++;
}
if ((r % 2) == 0) {
res = operation.operate(res, tree[r]);
r--;
}
l /= 2;
r /= 2;
}
return res;
}
}双周赛的第四题先空一下，还不会做。
Q1. Check if Any Element Has Prime Frequency
给你一个整数数组 nums。
如果数组中任一元素的 频次 是 质数，返回 true；否则，返回 false。
元素 x 的 频次 是它在数组中出现的次数。
质数是一个大于 1 的自然数，并且只有两个因数：1 和它本身。
测试样例：
输入：nums = [1,2,3,4,5,4]
输出：true
解释：数字 4 的频次是 2，而 2 是质数。
解答：
- 计数：统计每个数字出现的次数，范围在 [0,100]。
- 判断质数：对于出现次数 n>1，尝试从 2 遍历到 √n，看是否能整除，若不能则 n 为质数，立即返回 true。
- 若所有元素频次都不是质数，则返回 false。
class Solution {
public boolean checkPrimeFrequency(int[] nums) {
// 数值 <=100，直接用定长数组计数
int[] count = new int[101];
for (int n : nums) {
count[n] += 1;
}
// 遍历频次
for (int n : count) {
if (n <= 1) continue; // 频次 ≤1 不可能是质数
boolean isValid = true;
// 判断 n 是否为质数
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
isValid = false;
break;
}
}
// 一旦找到质数频次，直接返回 true
if (isValid) {
return true;
}
}
return false;
}
}3592. Inverse Coin Change
给你一个 从 1 开始计数 的整数数组 numWays，其中 numWays[i] 表示使用某些 固定 面值的硬币（每种面值可以使用无限次）凑出总金额 i 的方法数。每种面值都是一个 正整数 ，并且其值 最多 为 numWays.length。
然而，具体的硬币面值已经 丢失 。你的任务是还原出可能生成这个 numWays 数组的面值集合。
返回一个按从小到大顺序排列的数组，其中包含所有可能的 唯一 整数面值。
如果不存在这样的集合，返回一个 空 数组。
测试样例：
输入：numWays = [0,1,0,2,0,3,0,4,0,5]
输出：[2,4,6]
解释： 金额 方法数 解释 1 0 无法用硬币凑出总金额 1。 2 1 唯一的方法是 [2]。 3 0 无法用硬币凑出总金额 3。 4 2 可以用 [2, 2] 或 [4]。 5 0 无法用硬币凑出总金额 5。 6 3 可以用 [2, 2, 2]、[2, 4] 或 [6]。 7 0 无法用硬币凑出总金额 7。 8 4 可以用 [2, 2, 2, 2]、[2, 2, 4]、[2, 6] 或 [4, 4]。 9 0 无法用硬币凑出总金额 9。 10 5 可以用 [2, 2, 2, 2, 2]、[2, 2, 2, 4]、[2, 4, 4]、[2, 2, 6] 或 [4, 6]。
解答：
- 动态规划重现方法数：已知 numWays[i] 表示凑成金额 i+1 的方法数。我们要恢复可用的硬币面值集合 res。
- 贪心添加新面值：
- 如果 numWays[i] == 1 且当前 res 为空，则推断面值必为 i+1，加入 res。
- 否则，使用已有的 res 对金额 i+1 做经典的“完全背包”方法数重算 dp[i]。若重算后 dp[i] == numWays[i] - 1，说明新增了一个新面值 i+1；加入 res；若既不等于 numWays[i] 也不等于 numWays[i] - 1，则无解，返回空列表。
- 最终返回按升序排列的面值列表；若不存在方案，则返回空。
class Solution {
private static final List<Integer> failed = new ArrayList<>();
public List<Integer> findCoins(int[] numWays) {
List<Integer> res = new ArrayList<>();
for (int i = 1; i <= numWays.length; ++i) {
if (numWays[i - 1] == 1 && res.isEmpty()) {
// 第一个出现方法数为 1，推断面值一定是 i
res.add(i);
} else {
// 用已有面值集合 res 重新计算凑成金额 i 的方法数
int[] dp = new int[i + 1];
dp[0] = 1;
for (int d : res) {
for (int j = d; j <= i; ++j) {
dp[j] += dp[j - d];
}
}
// 若多出一种新方案，说明新增面值 i
if (dp[i] == numWays[i - 1] - 1) {
res.add(i);
} else if (dp[i] != numWays[i - 1]) {
// 与期望不符，则无解
return failed;
}
}
}
return res;
}
}Q3. Minimum Increments to Equalize Leaf Paths
给你一个整数 n，以及一个无向树，该树以节点 0 为根节点，包含 n 个节点，节点编号从 0 到 n - 1。这棵树由一个长度为 n - 1 的二维数组 edges 表示，其中 edges[i] = [ui, vi] 表示节点 ui 和节点 vi 之间存在一条边。
每个节点 i 都有一个关联的成本 cost[i]，表示经过该节点的成本。
路径得分 定义为路径上所有节点成本的总和。
你的目标是通过给任意数量的节点 增加 成本（可以增加任意非负值），使得所有从根节点到叶子节点的路径得分 相等 。
返回需要增加成本的节点数的 最小值 。
测试样例：
输入：n = 3, edges = [[0,1],[0,2]], cost = [2,1,3]
输出：1
解释：树中有两条从根到叶子的路径：
- 路径 0 → 1 的得分为 2 + 1 = 3。
- 路径 0 → 2 的得分为 2 + 3 = 5。
为了使所有路径的得分都等于 5，可以将节点 1 的成本增加 2。仅需增加一个节点的成本，因此输出为 1。
解答：
- 建图：把无向边列表转为邻接表 graph。
- 深度优先搜索：
- 对每个节点 cur，递归返回其所在子树中「根 → 叶」的最大路径和 tmp。
- 同时，对于当前节点的所有子路径中，记录最大值 max 及出现该最大值的子树数 maxCount，以及子树总数 total。
- 若 total != maxCount，说明有些子路径不达最大，需要对那些不足的路径上的对应节点做增量处理，计数累加 total - maxCount。
- 返回 max + cost[cur] 给父节点，以便上层计算。
- 答案：全局累加需要增量的节点数 res[0]。
class Solution {
public int minIncrease(int n, int[][] edges, int[] cost) {
// 构建邻接表
List<Integer>[] graph = new List[n];
for (int i = 0; i < n; ++i) {
graph[i] = new ArrayList<>();
}
for (int[] e : edges) {
graph[e[0]].add(e[1]);
graph[e[1]].add(e[0]);
}
int[] res = {0};
// 从根节点 0 开始 DFS
path(0, -1, graph, cost, res);
return res[0];
}
// 返回以 cur 为根的子树「根 → 叶」的最大路径权值
private long path(int cur, int pre, List<Integer>[] graph, int[] cost, int[] res) {
long max = 0;
int maxCount = 0, total = 0;
// 遍历所有子节点
for (int ne : graph[cur]) {
if (ne != pre) {
long tmp = path(ne, cur, graph, cost, res);
++total;
if (tmp == max) {
++maxCount;
} else if (tmp > max) {
max = tmp;
maxCount = 1;
}
}
}
// 如果不是所有子路径都等于最大，需要对其余路径上的节点做增量
if (total != maxCount) {
res[0] += total - maxCount;
}
// 返回当前节点加上最大子路径
return max + cost[cur];
}
}3594. Minimum Time to Transport All Individuals
有 n 名人员在一个营地，他们需要使用一艘船过河到达目的地。这艘船一次最多可以承载 k 人。渡河过程受到环境条件的影响，这些条件以 周期性 的方式在 m 个阶段内变化。
每个阶段 j 都有一个速度倍率 mul[j]：
- 如果 mul[j] > 1，渡河时间会变长。
- 如果 mul[j] < 1，渡河时间会缩短。
每个人 i 都有一个划船能力，用 time[i] 表示，即在中性条件下（倍率为 1 时）单独渡河所需的时间（以分钟为单位）。
规则：
- 从阶段 j 出发的一组人 g 渡河所需的时间（以分钟为单位）为组内成员的 最大 time[i]，乘以 mul[j] 。
- 该组人渡河所需的时间为 d，阶段会前进 floor(d) % m 步。
- 如果还有人留在营地，则必须有一人带着船返回。设返回人的索引为 r，返回所需时间为 time[r] × mul[current_stage]，记为 return_time，阶段会前进 floor(return_time) % m 步。
返回将所有人渡河所需的 最少总时间 。如果无法将所有人渡河，则返回 -1。
测试样例：
输入：n = 1, k = 1, m = 2, time = [5], mul = [1.0,1.3]
输出：5.00000
解释：第 0 个人从阶段 0 出发，渡河时间 = 5 × 1.00 = 5.00 分钟。所有人已经到达目的地，因此总时间为 5.00 分钟。
解答：
- 特殊情况：若船一次只能载 1 人，则只能单人来回。如果 n == 1，返回该人的时间乘以初始倍率；否则无法渡河，返回 -1。
- 状态定义：用位掩码 key 表示哪些人已经过河，用 stage 表示当前的阶段（环境倍率索引）。
- 预计算：
- minMaxTime[i]：当位掩码 i 表示的集合人数 ≤ k 时，该集合渡河所需的基础时间（最大单人时间）。
- 动态规划表 dp[key][stage] 存储到达该状态的最小累计时间。
- Dijkstra 样的枚举：
- 从状态 (0,0) 开始，将未过河的某个组合 i（大小 ≤ k）一起过河；计算正向时间 forwardTime = maxTime * mul[stage]，更新阶段 forwardStage。
- 若所有人都过河，更新答案；否则必须选一个成员带船返程，计算返程时间及新阶段，更新新状态 (nextKey, finalStage) 的 dp 值。
- 最终返回最小值。
class Solution {
public double minTime(int n, int k, int m, int[] time, double[] mul) {
// 若船只载一个人
if (k == 1) {
if (n == 1) {
// 只有一个人，直接一次渡河
return time[0] * mul[0];
} else {
// 多人无法渡河来回
return -1;
}
}
Data data = new Data(k, time, mul);
// 用 TreeSet 实现带优先级的状态抽取（类似 Dijkstra）
TreeSet<int[]> set = new TreeSet<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
Double d1 = data.dp[o1[0]][o1[1]], d2 = data.dp[o2[0]][o2[1]];
if (d1 == null && d2 == null) {
} else if (d1 == null) {
return 1;
} else if (d2 == null) {
return -1;
} else if (Double.compare(d1, d2) != 0) {
return Double.compare(d1, d2);
}
for (int i = 0; i < 2; ++i) {
if (o1[i] != o2[i]) {
return Integer.compare(o1[i], o2[i]);
}
}
return 0;
}
});
set.add(new int[]{0,0}); // 初始状态：无人过河，阶段 0
double res = Double.MAX_VALUE;
while (!set.isEmpty()) {
int[] r = set.removeFirst();
int key = r[0], stage = r[1];
// 枚举一组未过河的人 i（人数 ≤ k）
for (int i = 1; i < data.max; ++i) {
if (data.minMaxTime[i] != null && (key & i) == 0) {
int max = data.minMaxTime[i];
// 若此组人就是所有人，更新答案
if ((key | i) == data.max - 1) {
res = Math.min(res, max * data.mul[stage] + data.dp[key][stage]);
} else {
// 正向渡河
double forwardTime = max * data.mul[stage];
int forwardStage = data.getNextStage(stage, forwardTime);
// 必须有人返程
for (int member = 0; member < data.n; ++member) {
if (Data.isUsed(i | key, member)) {
double backwardTime = data.time[member] * data.mul[forwardStage];
int finalStage = data.getNextStage(forwardStage, backwardTime);
int nextKey = (key | i) ^ (1 << member);
// 更新新状态 dp
if (data.dp[nextKey][finalStage] == null ||
data.dp[nextKey][finalStage] > forwardTime + backwardTime + data.dp[key][stage]) {
int[] sort = {nextKey, finalStage};
set.remove(sort);
data.dp[nextKey][finalStage] = forwardTime + backwardTime + data.dp[key][stage];
set.add(sort);
}
}
}
}
}
}
}
return res;
}
}
// 存储预计算数据和 DP 状态
class Data {
int n, k, m, max;
int[] time;
double[] mul;
Integer[] minMaxTime; // 对应位掩码的最大单人时间（若人数 ≤ k）
Double[][] dp; // dp[key][stage]：到达状态的最小累计时间
public Data(int k, int[] time, double[] mul) {
this.k = k;
n = time.length;
m = mul.length;
this.time = time;
this.mul = mul;
this.max = 1 << n;
dp = new Double[max][m];
minMaxTime = new Integer[max];
// 预计算每个子集的最大时间（若子集大小 ≤ k）
for (int i = 1; i < max; ++i) {
int maxTime = Integer.MIN_VALUE;
int count = 0;
for (int j = 0; j < n; ++j) {
if (isUsed(i, j)) {
++count;
maxTime = Math.max(maxTime, time[j]);
}
}
if (count <= k) {
minMaxTime[i] = maxTime;
} else {
minMaxTime[i] = null;
}
}
dp[0][0] = 0.0; // 初始无人过河，阶段 0，时间 0
}
// 判断位掩码 key 中第 offset 位是否为 1（是否包含该成员）
public static boolean isUsed(int key, int offset) {
int tmp = (key >> offset) & 1;
return tmp == 1;
}
// 根据经过的时间前进若干阶段
public int getNextStage(int curStage, double time) {
return (curStage + (int) Math.floor(time)) % m;
}
}