欢迎大家加QQ群：623375442。最近LeetCode的周赛着实太垃圾了，时不时unrate。不想准时起来做了。以后双周赛和周赛题解都会在周日下午3点左右发布。欢迎继续关注。
3572. Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values
给你两个整数数组 x 和 y，长度均为 n。你必须选择三个 不同 的下标 i ，j 和 k，满足以下条件：
- x[i] != x[j]
- x[j] != x[k]
- x[k] != x[i]
你的目标是在满足这些条件下 最大化 y[i] + y[j] + y[k] 的值。返回通过选择这样一组三元组下标所能获得的 最大 可能和。
如果不存在这样的三元组，返回 -1。
测试样例：
输入：x = [1,2,1,3,2], y = [5,3,4,6,2]
输出：14
解释：选择 i = 0（x[i] = 1，y[i] = 5），j = 1（x[j] = 2，y[j] = 3），k = 3（x[k] = 3，y[k] = 6）。选出的三个 x 中的值互不相同。5 + 3 + 6 = 14 是我们能获得的最大值。因此输出为 14。
解答：
- 遍历所有 (x[i], y[i])，用哈希表 map 记录每个不同 x 对应的最大 y。
- 如果不同的 x 少于 3 个，无法取到三元组，返回 -1。
- 把 map 中所有 y 值放入一个大小为 3 的小根堆，维护堆中始终保留 3 个最大的 y。
- 最后堆中元素之和即为答案。
class Solution {
public int maxSumDistinctTriplet(int[] x, int[] y) {
// 用 map 存储每个 x 值对应的最大 y 值
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < x.length; ++i) {
if (map.containsKey(x[i])) {
// 如果该 x 已存在，则更新为更大的 y
map.put(x[i], Math.max(map.get(x[i]), y[i]));
} else {
// 否则直接插入
map.put(x[i], y[i]);
}
}
// 如果不同 x 的数量不足 3，无法选出三元组
if (map.size() < 3) return -1;
// 小根堆，用于保留最大的 3 个 y 值
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (Map.Entry<Integer, Integer> kv : map.entrySet()) {
queue.add(kv.getValue());
// 保证堆中最多只有 3 个元素
if (queue.size() > 3) {
queue.poll();
}
}
// 将堆中剩下的三个 y 值相加
int res = 0;
for (int n : queue) {
res += n;
}
return res;
}
}3573. Best Time to Buy and Sell Stock V
给你一个整数数组 prices，其中 prices[i] 是第 i 天股票的价格（美元），以及一个整数 k。
你最多可以进行 k 笔交易，每笔交易可以是以下任一类型：
- 普通交易：在第 i 天买入，然后在之后的第 j 天卖出，其中 i < j。你的利润是 prices[j] - prices[i]。
- 做空交易：在第 i 天卖出，然后在之后的第 j 天买回，其中 i < j。你的利润是 prices[i] - prices[j]。
注意：你必须在开始下一笔交易之前完成当前交易。此外，你不能在已经进行买入或卖出操作的同一天再次进行买入或卖出操作。
通过进行 最多 k 笔交易，返回你可以获得的最大总利润。
测试样例：
输入：prices = [1,7,9,8,2], k = 2
输出：14
解释：我们可以通过 2 笔交易获得 14 美元的利润：一笔普通交易：第 0 天以 1 美元买入，第 2 天以 9 美元卖出。一笔做空交易：第 3 天以 8 美元卖出，第 4 天以 2 美元买回。
解答：
- 最多可做 k 笔交易，每笔交易可以是 买入-卖出 或 卖出-买入（做空）。
- 我们将状态分成 2*k 个阶段，每个阶段又分为「持仓买入」和「持仓卖出」两种子状态，使用动态规划 dp[i][0/1] 保存当前阶段的最大利润。
- 对每个价格 n，从后向前枚举阶段，更新「买入」和「卖出」两种状态。
- 最终在所有「已完成交易后可持仓」的状态中取最大值。
class Solution {
public long maximumProfit(int[] prices, int k) {
// dp[阶段][0=持仓买入,1=持仓卖出]
long[][] dp = new long[2 * k][2];
// 初始化为很小的值，避免误用未经过更新的状态
for (int i = 0; i < dp.length; ++i) {
Arrays.fill(dp[i], Long.MIN_VALUE / 2);
}
for (int n : prices) {
// 从后向前，保证当日每个阶段只用前一天的状态更新
for (int i = dp.length - 1; i >= 0; --i) {
if (i == 0) {
// 第一个阶段：首次买入或卖出（相当于空手卖出获得负债）
dp[0][0] = Math.max(dp[0][0], -n);
dp[0][1] = Math.max(dp[0][1], n);
} else if (i % 2 == 0) {
// 偶数阶段可从上一个阶段「不持仓」过渡到「持仓」后买入卖出
long max = Math.max(dp[i - 1][0], dp[i - 1][1]);
dp[i][0] = Math.max(dp[i][0], max - n);
dp[i][1] = Math.max(dp[i][1], max + n);
} else {
// 奇数阶段表示在一次交易内的持仓切换
dp[i][0] = Math.max(dp[i][0], dp[i - 1][0] + n);
dp[i][1] = Math.max(dp[i][1], dp[i - 1][1] - n);
}
}
}
long res = 0;
// 在所有完成交易的「可持仓」状态中取最大利润
for (int i = 1; i < dp.length; i += 2) {
long[] t = dp[i];
res = Math.max(res, Math.max(t[0], t[1]));
}
return res;
}
}3574. Maximize Subarray GCD Score
给你一个正整数数组 nums 和一个整数 k。
你最多可以执行 k 次操作。在每次操作中，你可以选择数组中的一个元素并将其值 翻倍 。每个元素 最多 只能翻倍一次。
连续 子数组 的 分数 定义为其所有元素的最大公约数 (GCD) 与子数组长度的 乘积 。
你的任务是返回修改后数组中选择一个连续子数组可以获得的最大 分数 。
注意：
- 子数组 是数组中连续的元素序列。
- 数组的 最大公约数 (GCD) 是能整除数组所有元素的最大整数。
测试样例：
输入：nums = [2,4], k = 1
输出：8
解释:
- 使用一次操作将 nums[0] 翻倍到 4。修改后的数组变为 [4, 4]。
- 子数组 [4, 4] 的 GCD 是 4，长度是 2。
- 因此，最大可能分数是 2 × 4 = 8。
解答：
- 每个数最多只能翻倍一次，我们预处理出每个数 nums[i] 被 2 除的次数 two[i]。
- 枚举所有子数组 [i..j]：维护当前子数组的最小翻倍次数 min、出现该最小次数的数量 count 以及子数组中去除公共 2 因子的基数 n（用于计算 GCD）。
- 如果 count <= k，意味着可以将最少因子那部分再多翻一次；否则只能按原次数计算。
- 计算当前子数组长度乘以 GCD 并更新答案。
class Solution {
public long maxGCDScore(int[] nums, int k) {
int[] two = new int[nums.length];
// 预处理：计算每个 nums[i] 可被 2 除几次
for (int i = 0; i < nums.length; ++i) {
two[i] = twoDiv(nums[i]);
}
long res = 0;
// 枚举子数组起点
for (int i = 0; i < nums.length; ++i) {
// 基数：去掉所有 2 因子后的值
int n = nums[i] / (1 << two[i]);
int min = two[i], count = 0;
// 枚举子数组终点
for (int j = i; j < nums.length; ++j) {
int tmp = nums[j] / (1 << two[j]);
// 更新最小翻倍次数及计数
if (two[j] < min) {
min = two[j];
count = 1;
} else if (two[j] == min) {
++count;
}
// 更新公共基数 GCD
n = gcd(n, tmp);
long rg;
if (count <= k) {
// 如果最小因子个数 <= k，可以再翻一次
rg = (1L << (min + 1)) * n;
} else {
// 否则只能按原次数计算
rg = (1L << min) * n;
}
// 更新答案：GCD * 子数组长度
res = Math.max(res, rg * (j - i + 1));
}
}
return res;
}
// 计算最大公约数
private int gcd(int x, int y) {
while (y != 0) {
int tmp = x % y;
x = y;
y = tmp;
}
return x;
}
// 统计 x 可被 2 除的次数
private int twoDiv(int x) {
int res = 0;
while (x % 2 == 0) {
x /= 2;
++res;
}
return res;
}
}3575. Maximum Good Subtree Score
给你一个根节点为 0 的无向树，包含 n 个节点，编号从 0 到 n - 1。每个节点 i 都有一个整数值 vals[i]，其父节点为 par[i] 。
从一个节点 子树 内选取部分节点，它们的数值组成一个 子集 ，如果所选数值的十进制表示中，从 0 到 9 每个数字在所有数的数位最多出现一次，那么我们称它是 好 子集。
一个好子集的 分数 是其节点值的总和。
定义一个长度为 n 的数组 maxScore，其中 maxScore[u] 表示以节点 u 为根的子树（包括 u 本身及其所有后代）中，好子集的最大可能值总和。
返回 maxScore 中所有值的总和。
由于答案可能很大，请将其对 10^9 + 7 取模 后返回。
数组的 子集 是选取数组中元素得到的集合（可能为空）。
测试样例：
输入：vals = [2,3], par = [-1,0]
输出：8
解释:
- 以节点 0 为根的子树包括节点 {0, 1}。子集 {2, 3} 是 好的，因为数字 2 和 3 只出现一次。此子集的分数是 2 + 3 = 5。
- 以节点 1 为根的子树只包括节点 {1}。子集 {3} 是 好的。此子集的分数是 3。
- maxScore 数组为 [5, 3]，并且 maxScore 中所有值的总和是 5 + 3 = 8。因此，答案是 8。
解答：
- 树的每个节点值拆成「数字掩码」marks[i]，如果该值含重复数字则标记为 -1（不可取）。
- 对于每棵子树，dfs(u) 返回一个长度 1024 的数组 res，res[mask] 表示在该子树中选取能合并出数字集合为 mask 的最大总和。
- 通过位运算合并左右子树的 res，只保留没有数字冲突 ((mask1 & mask2)==0) 的情况。
- 每次 DFS 完后，从 res 中取最大值累加到总体结果 data.res。
class Solution {
private static final int mod = 1_000_000_007;
public int goodSubtreeSum(int[] vals, int[] par) {
Data data = new Data(vals, par);
// 从根节点 0 开始 DFS
dfs(0, data);
return data.res;
}
private long[] dfs(int cur, Data data) {
// res[mask] 初始化为极小值
long[] res = new long[1024];
Arrays.fill(res, Integer.MIN_VALUE);
// 空集对应和为 0
res[0] = 0;
// 如果当前节点合法，则设其掩码处的值为节点值
if (data.marks[cur] != -1) {
res[data.marks[cur]] = data.vals[cur];
}
// 遍历所有子节点，合并子树结果
for (int n : data.tree[cur]) {
merge(res, dfs(n, data));
}
// 取当前子树所有掩码的最大值累加到全局
long max = 0;
for (int i = 0; i < 1024; ++i) {
max = Math.max(max, res[i]);
}
data.res = (int) ((data.res + max) % mod);
return res;
}
private void merge(long[] res, long[] right) {
// 枚举两个掩码，只有无冲突时才合并
for (int i = 0; i < 1024; ++i) {
if (right[i] == Integer.MIN_VALUE) continue;
for (int j = 0; j < 1024; ++j) {
if ((i & j) == 0) {
res[i | j] = Math.max(res[i | j], res[j] + right[i]);
}
}
}
}
}
// 辅助数据结构
class Data {
int[] vals, marks;
List<Integer>[] tree;
int res;
public Data(int[] vals, int[] par) {
int len = vals.length;
this.vals = vals;
// 构建子树邻接表
tree = new List[len];
for (int i = 0; i < len; ++i) {
tree[i] = new ArrayList<>();
}
for (int i = 0; i < par.length; ++i) {
if (par[i] != -1) {
tree[par[i]].add(i);
}
}
// 预处理每个节点的数字掩码
marks = new int[len];
for (int i = 0; i < len; ++i) {
marks[i] = digitMark(vals[i]);
}
res = 0;
}
// 将 val 转换为数字位掩码，若有重复则返回 -1
private int digitMark(int n) {
int mark = 0;
while (n > 0) {
int tmp = n % 10;
if (isUsed(mark, tmp)) {
return -1;
}
mark += (1 << tmp);
n /= 10;
}
return mark;
}
// 检查某位是否已被占用
private boolean isUsed(int n, int offset) {
int tmp = (n >> offset) & 1;
return tmp == 1;
}
}3576. Transform Array to All Equal Elements
给你一个大小为 n 的整数数组 nums，其中只包含 1 和 -1，以及一个整数 k。
你可以最多进行 k 次以下操作：
- 选择一个下标 i（0 <= i < n - 1），然后将 nums[i] 和 nums[i + 1] 同时 乘以 -1。
注意：你可以在 不同 的操作中多次选择相同的下标 i。
如果在最多 k 次操作后可以使数组的所有元素相等，则返回 true；否则，返回 false。
测试样例：
输入：nums = [1,-1,1,-1,1], k = 3
输出：true
解释：我们可以通过以下两次操作使数组的所有元素相等：
- 选择下标 i = 1，将 nums[1] 和 nums[2] 同时乘以 -1。此时 nums = [1,1,-1,-1,1]。
- 选择下标 i = 2，将 nums[2] 和 nums[3] 同时乘以 -1。此时 nums = [1,1,1,1,1]。
解答：
- 尝试将数组最终都变成 1 或都变成 -1 两种情况。
- 对每种目标，用贪心：从左向右遍历，若当前位置不为目标且还剩操作次数 k，则对 (i, i+1) 同时翻倍。
- 若最后一位也满足目标则返回 true，否则返回 false。
class Solution {
public boolean canMakeEqual(int[] nums, int k) {
// 两种目标情况：1 或 -1
return cal(nums, k, 1) || cal(nums, k, -1);
}
private boolean cal(int[] nums, int k, int target) {
// 复制一份数组进行尝试
int[] dup = Arrays.copyOf(nums, nums.length);
for (int i = 0; i < dup.length; ++i) {
if (i == dup.length - 1) {
// 最后一位时，检查是否已达到目标
return dup[i] == target;
} else if (dup[i] != target) {
// 若当前位置未达目标，且没有剩余操作，失败
if (k == 0) return false;
// 对 dup[i] 和 dup[i+1] 同时乘以 -1
dup[i] *= -1;
dup[i + 1] *= -1;
--k;
}
}
return false;
}
}3577. Count the Number of Computer Unlocking Permutations
给你一个长度为 n 的数组 complexity。
在房间里有 n 台 上锁的 计算机，这些计算机的编号为 0 到 n - 1，每台计算机都有一个 唯一 的密码。编号为 i 的计算机的密码复杂度为 complexity[i]。
编号为 0 的计算机密码已经 解锁 ，并作为根节点。其他所有计算机必须通过它或其他已经解锁的计算机来解锁，具体规则如下：
- 可以使用编号为 j 的计算机的密码解锁编号为 i 的计算机，其中 j 是任何小于 i 的整数，且满足 complexity[j] < complexity[i]（即 j < i 并且 complexity[j] < complexity[i]）。
- 要解锁编号为 i 的计算机，你需要事先解锁一个编号为 j 的计算机，满足 j < i 并且 complexity[j] < complexity[i]。
求共有多少种 [0, 1, 2, ..., (n - 1)] 的排列方式，能够表示从编号为 0 的计算机（唯一初始解锁的计算机）开始解锁所有计算机的有效顺序。
由于答案可能很大，返回结果需要对 10^9 + 7 取余数。
注意：编号为 0 的计算机的密码已解锁，而 不是 排列中第一个位置的计算机密码已解锁。
排列 是一个数组中所有元素的重新排列。
测试样例：
输入：complexity = [1,2,3]
输出：2
解释：
有效的排列有：
- [0, 1, 2]: 首先使用根密码解锁计算机 0。使用计算机 0 的密码解锁计算机 1，因为 complexity[0] < complexity[1]。使用计算机 1 的密码解锁计算机 2，因为 complexity[1] < complexity[2]。
- [0, 2, 1]: 首先使用根密码解锁计算机 0。使用计算机 0 的密码解锁计算机 2，因为 complexity[0] < complexity[2]。使用计算机 0 的密码解锁计算机 1，因为 complexity[0] < complexity[1]。
解答：
- 编号为 0 的计算机已解锁，其余必须满足 j < i 且 complexity[j] < complexity[i] 才能解锁。
- 由于每次新解锁的顺序，只要保证初始 complexity[0] 最小，后续不需要依赖先后关系，所有剩余 n-1 台都可任意顺序，只要都大于 complexity[0]。
- 统计 complexity[i] <= complexity[0] 的情况直接返回 0，否则答案是 (n-1)!。
class Solution {
private static final int mod = 1_000_000_007;
public int countPermutations(int[] complexity) {
// 如果有比根节点复杂度更小或相等的，无法解锁
for (int i = 1; i < complexity.length; ++i) {
if (complexity[i] <= complexity[0]) {
return 0;
}
}
long res = 1;
// (n-1)! 对 mod 取余
for (int i = complexity.length - 1; i >= 1; --i) {
res = res * i;
res %= mod;
}
return (int) res;
}
}3578. Count Partitions With Max-Min Difference at Most K
给你一个整数数组 nums 和一个整数 k。你的任务是将 nums 分割成一个或多个 非空 的连续子段，使得每个子段的 最大值 与 最小值 之间的差值 不超过 k。
返回在此条件下将 nums 分割的总方法数。
由于答案可能非常大，返回结果需要对 10^9 + 7 取余数。
测试样例：
输入：nums = [9,4,1,3,7], k = 4
输出：4
解释: 共有 6 种有效的分割方式，使得每个子段中的最大值与最小值之差不超过 k = 4：
- [[9], [4], [1], [3], [7]]
- [[9], [4], [1], [3, 7]]
- [[9], [4], [1, 3], [7]]
- [[9], [4, 1], [3], [7]]
- [[9], [4, 1], [3, 7]]
- [[9], [4, 1, 3], [7]]
解答：
- 动态规划 mem[i] 表示前 i 个元素的分割方案数。
- 使用双指针 [left, right) 加上一个平衡树 map 维护当前子段的最大/最小。
- 当 max-min > k 时，左指针右移，并从 sum 中减去 mem[left]。
- mem[right+1] = sum；sum 累加 mem[right+1]。最终 mem[n] 即为答案。
class Solution {
private static final int mod = 1_000_000_007;
public int countPartitions(int[] nums, int k) {
int len = nums.length;
// mem[i] 表示前 i 个元素的分割方法数
int[] mem = new int[len + 1];
mem[0] = 1;
int left = 0, right = 0, sum = 1;
// 用 TreeMap 维护当前窗口的频次及最大/最小
TreeMap<Integer, Integer> map = new TreeMap<>();
while (right < len) {
map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
// 若 max-min 超过 k，则左指针右移收缩
while (map.lastKey() - map.firstKey() > k) {
int r = nums[left];
int c = map.get(r);
if (c == 1) {
map.remove(r);
} else {
map.put(r, c - 1);
}
// 移除位置 left 的方案数
sum = (sum - mem[left] + mod) % mod;
++left;
}
// 此时 [left..right] 窗口内所有分割都合法
mem[right + 1] = sum;
// 更新 sum 为下一轮可用
sum = (sum + mem[right + 1]) % mod;
++right;
}
return mem[len];
}
}3579. Minimum Steps to Convert String with Operations
给你两个长度相等的字符串 word1 和 word2。你的任务是将 word1 转换成 word2。
为此，可以将 word1 分割成一个或多个连续子字符串。对于每个子字符串 substr，可以执行以下操作：
- 替换：将 substr 中任意一个索引处的字符替换为另一个小写字母。
- 交换：交换 substr 中任意两个字符的位置。
. 反转子串：将 substr 进行反转。每种操作计为 一次 ，并且每个子串中的每个字符在每种操作中最多只能使用一次（即任何字符的下标不能参与超过一次替换、交换或反转操作）。
返回将 word1 转换为 word2 所需的 最小操作数 。
子串 是字符串中任意一个连续且非空的字符序列。
测试样例：
输入：word1 = "abcdf", word2 = "dacbe"
输出：4
解释: 将 word1 分割为 "ab"、"c" 和 "df"。操作如下：
- 对于子串 "ab"：
- 执行类型 3 的操作："ab" -> "ba"。
- 执行类型 1 的操作："ba" -> "da"。
- 对于子串 "c"：无需操作。
- 对于子串 "df"：
- 执行类型 1 的操作："df" -> "bf"。
- 执行类型 1 的操作："bf" -> "be"。
解答：
- 将 word1 分割成若干后缀，每个后缀分别计算最小操作数再加上递归结果，用 dp[pos] 记忆化。
- 对每个子串，用三种操作（替换、交换、反转）分别统计转换成本：
- 检查是否已相同 dir1
- 是否反转后相同 dir2
- 不同则统计替换与交换带来的操作次数
- 在所有分割点中取最小值。
class Solution {
public int minOperations(String word1, String word2) {
int len = word1.length();
// dp[pos] 存储从 pos 开始到末尾的最小操作数
int[] dp = new int[len];
Arrays.fill(dp, Integer.MAX_VALUE);
return helper(word1, word2, 0, dp);
}
private int helper(String word1, String word2, int pos, int[] dp) {
if (pos == word1.length()) {
// 到达末尾，无需操作
return 0;
} else if (dp[pos] == Integer.MAX_VALUE) {
StringBuilder l1 = new StringBuilder(), l2 = new StringBuilder();
// 枚举从 pos 到 i 的子串
for (int i = pos; i < word1.length(); ++i) {
l1.append(word1.charAt(i));
l2.append(word2.charAt(i));
// 子串转换成本 + 后续递归成本
dp[pos] = Math.min(dp[pos], min(l1, l2) + helper(word1, word2, i + 1, dp));
}
}
return dp[pos];
}
// 计算将 str1 变成 str2 的最少操作数
private int min(StringBuilder str1, StringBuilder str2) {
boolean dir1 = true, dir2 = true;
// count1/count2 统计逐位与镜像比较后的替换需求
int[][] count1 = new int[26][26], count2 = new int[26][26];
for (int i = 0, j = str1.length() - 1; i < str1.length(); ++i, --j) {
if (str1.charAt(i) != str2.charAt(i)) {
dir1 = false;
}
if (str1.charAt(i) != str2.charAt(j)) {
dir2 = false;
}
count1[str1.charAt(i) - 'a'][str2.charAt(i) - 'a'] += 1;
count2[str1.charAt(i) - 'a'][str2.charAt(j) - 'a'] += 1;
}
// 完全相同，无需操作
if (dir1) return 0;
// 仅需一次反转即可
if (dir2) return 1;
int r1 = 0, r2 = 1;
// 统计替换与交换成本
for (int i = 0; i < 26; ++i) {
for (int j = i + 1; j < 26; ++j) {
{
int min = Math.min(count1[i][j], count1[j][i]), max = Math.max(count1[i][j], count1[j][i]);
r1 += min;
r1 += (max - min);
}
{
int min = Math.min(count2[i][j], count2[j][i]), max = Math.max(count2[i][j], count2[j][i]);
r2 += min;
r2 += (max - min);
}
}
}
// 返回两种策略的最小值
return Math.min(r1, r2);
}
}