欢迎大家加QQ群：623375442。这次题目比昨天双周赛简单太多了。
100635. Minimum Cost to Reach Every Position
给你一个长度为 n 的整数数组 cost 。当前你位于位置 n（队伍的末尾），队伍中共有 n + 1 人，编号从 0 到 n 。
你希望在队伍中向前移动，但队伍中每个人都会收取一定的费用才能与你 交换位置。与编号 i 的人交换位置的费用为 cost[i] 。
你可以按照以下规则与他人交换位置：
- 如果对方在你前面，你 必须 支付 cost[i] 费用与他们交换位置。
- 如果对方在你后面，他们可以免费与你交换位置。
- 返回一个大小为 n 的数组 answer，其中 answer[i] 表示到达队伍中每个位置 i 所需的 最小 总费用。
测试样例：
输入：cost = [5,3,4,1,3,2]
输出：[5,3,3,1,1,1]
解释: 我们可以通过以下方式到达每个位置：
- i = 0。可以花费 5 费用与编号 0 的人交换位置。
- i = 1。可以花费 3 费用与编号 1 的人交换位置。
- i = 2。可以花费 3 费用与编号 1 的人交换位置，然后免费与编号 2 的人交换位置。
- i = 3。可以花费 1 费用与编号 3 的人交换位置。
- i = 4。可以花费 1 费用与编号 3 的人交换位置，然后免费与编号 4 的人交换位置。
- i = 5。可以花费 1 费用与编号 3 的人交换位置，然后免费与编号 5 的人交换位置。
解答：该解法的思路是：从位置 0 开始，每个位置的最小费用等于当前位置费用和前面位置最小费用的较小值。
class Solution {
public int[] minCosts(int[] cost) {
int len = cost.length;
int[] res = new int[len]; // 用于存储到达每个位置的最小费用
// 位置 0 的费用直接就是 cost[0]
res[0] = cost[0];
// 从位置 1 开始更新最小费用：当前位置费用和前一个位置的最小费用之间取较小者
for (int i = 1; i < res.length; ++i) {
res[i] = Math.min(res[i - 1], cost[i]);
}
return res;
}
}100614. Longest Palindrome After Substring Concatenation II
给你两个字符串 s 和 t。
你可以从 s 中选择一个子串（可以为空）以及从 t 中选择一个子串（可以为空），然后将它们 按顺序 连接，得到一个新的字符串。
返回可以由上述方法构造出的 最长 回文串的长度。
回文串 是指正着读和反着读都相同的字符串。
子字符串 是指字符串中的一个连续字符序列。
测试样例：
输入：s = "a", t = "a"
输出：2
解释: 从 s 中选择 "a"，从 t 中选择 "a"，拼接得到 "aa"，这是一个长度为 2 的回文串。
解答：给定两个字符串 s 和 t，允许分别从中选取一个子串并按顺序拼接，求拼接后能构造出的最长回文串的长度。解题思路主要包括：对 s 中所有子串预处理哈希值，并记录其后续能扩展出的最长回文长度；对 t 取反后匹配 s 的子串，尝试组合成回文串。
class Solution {
// 模数和质数用于哈希计算
private static final int mod = 1_000_000_007, prime = 31;
public int longestPalindrome(String s, String t) {
// map 存储 s 中每个子串的哈希值，以及对应长度的最大可扩展回文长度
HashMap<Long, HashMap<Integer, Integer>> map = new HashMap<>();
// 将 t 反转，便于与 s 中子串对应形成回文
t = new StringBuilder(t).reverse().toString();
// 预处理 s 和反转后的 t 中，每个位置出发的最长回文长度
int[] sMax = oneBest(s), tMax = oneBest(t);
// 枚举 s 中所有子串，计算其哈希值，并记录后续能扩展的回文长度信息
for (int i = 0; i < s.length(); ++i) {
long mul = 1, cur = 0;
for (int j = i; j < s.length(); ++j) {
int v = s.charAt(j) - 'a';
cur = (cur + v * mul) % mod;
mul = (mul * prime) % mod;
// 如果当前哈希值未出现，则初始化映射
if (!map.containsKey(cur)) {
map.put(cur, new HashMap<>());
}
HashMap<Integer, Integer> curMap = map.get(cur);
// 对于子串长度 (j-i)，记录其对应的最大扩展回文长度
if (!curMap.containsKey(j - i)) {
curMap.put(j - i, j + 1 < s.length() ? sMax[j + 1] : 0);
} else {
curMap.put(j - i, Math.max(curMap.get(j - i), j + 1 < s.length() ? sMax[j + 1] : 0));
}
}
}
int res = 0;
// 单独考虑 s 和 t 内部的最长回文子串
for (int n : sMax) {
res = Math.max(res, n);
}
for (int n : tMax) {
res = Math.max(res, n);
}
// 枚举反转后的 t 中的子串，与 s 中的子串进行匹配，组合出更长的回文串
for (int i = 0; i < t.length(); ++i) {
long mul = 1, cur = 0;
for (int j = i; j < t.length(); ++j) {
int v = t.charAt(j) - 'a';
cur = (cur + v * mul) % mod;
mul = (mul * prime) % mod;
// 如果 s 中存在相同哈希值的子串
if (map.containsKey(cur)) {
HashMap<Integer, Integer> curMap = map.get(cur);
if (curMap.containsKey(j - i)) {
// 当前匹配的子串组成的回文串长度
int curLen = (j - i + 1) * 2;
// 选取最大可能的扩展长度
int sPos = Math.max(curMap.get(j - i), j + 1 < t.length() ? tMax[j + 1] : 0);
res = Math.max(res, curLen + sPos);
}
} else {
// 如果没有匹配，则提前结束内层循环
break;
}
}
}
return res;
}
// 辅助函数：计算从每个位置出发能获得的最长回文子串长度
private int[] oneBest(String s) {
int len = s.length();
int[] res = new int[s.length()];
// valid[i][j] 表示子串 s[i...j] 是否为回文
boolean[][] valid = new boolean[len][len];
// 枚举所有可能的中心位置
for (int i = 0; i < s.length(); ++i) {
int st = 0, ed = i;
// 依次扩展窗口 [st, ed]
while (ed < s.length()) {
if (s.charAt(st) == s.charAt(ed)) {
if (i <= 1) {
valid[st][ed] = true;
} else {
valid[st][ed] = valid[st + 1][ed - 1];
}
}
// 如果是回文，则更新从 st 出发的最大回文长度
if (valid[st][ed]) {
res[st] = Math.max(res[st], i + 1);
}
++st;
++ed;
}
}
return res;
}
}100537. Minimum Operations to Make Elements Within K Subarrays Equa
给你一个整数数组 nums 和两个整数 x 和 k。你可以执行以下操作任意次（包括零次）：
- 将 nums 中的任意一个元素加 1 或减 1。
返回为了使 nums 中 至少 包含 k 个长度 恰好 为 x 的不重叠子数组（每个子数组中的所有元素都相等）所需要的 最少 操作数。
子数组 是数组中连续、非空的一段元素。
测试样例：
输入：nums = [5,-2,1,3,7,3,6,4,-1], x = 3, k = 2
输出：8
解释:
- 进行 3 次操作，将 nums[1] 加 3；进行 2 次操作，将 nums[3] 减 2。得到的数组为 [5, 1, 1, 1, 7, 3, 6, 4, -1]。
- 进行 1 次操作，将 nums[5] 加 1；进行 2 次操作，将 nums[6] 减 2。得到的数组为 [5, 1, 1, 1, 7, 4, 4, 4, -1]。
- 现在，子数组 [1, 1, 1]（下标 1 到 3）和 [4, 4, 4]（下标 5 到 7）中的所有元素都相等。总共进行了 8 次操作，因此输出为 8。
解答：
- 使用滑动窗口计算每个长度为 x 的子数组调整为中位数所需的操作数（最小化调整代价）。
- 利用动态规划（dp）来选取不重叠子数组，使总调整代价最小。
- 辅助数据结构 MedianFinder 用于在线维护窗口内的中位数和调整代价。
class Solution {
public long minOperations(int[] nums, int x, int k) {
// medianCost[i] 表示将 nums[i...i+x-1] 子数组调整为中位数所需的操作数
long[] medianCost = new long[nums.length - x + 1];
MedianFinder medianFinder = new MedianFinder();
// 滑动窗口遍历 nums 数组
for (int i = 0; i < nums.length; ++i) {
// 将当前元素加入 MedianFinder 结构
medianFinder.add(nums[i]);
// 当窗口大小达到 x 后，计算该窗口的调整代价
if (i >= x - 1) {
// 获取窗口内的中位数（left 部分的最大值即为中位数）
long median = medianFinder.left.map.lastKey();
// 计算调整代价：左半部分将所有数调整到 median 的代价 + 右半部分调整的代价
long diff = median * medianFinder.left.count - medianFinder.left.sum
+ medianFinder.right.sum - median * medianFinder.right.count;
medianCost[i - x + 1] = diff;
// 窗口向右滑动，移除最左边的元素
medianFinder.remove(nums[i - x + 1]);
}
}
// dp[i] 表示从下标 i 开始构造剩余子数组所需的最小操作数
long[] dp = new long[nums.length];
// 对于需要构造的子数组数量从 1 到 k 进行 DP 计算
for (int i = 1; i <= k; ++i) {
long[] nextDp = new long[nums.length];
// st 表示从当前位置开始，剩余位置至少可以容纳 i 个长度为 x 的子数组
int st = nums.length - x * i;
// 倒序遍历以确保子数组不重叠
for (int j = st; j >= 0; --j) {
if (i == 1) {
// 如果只需要一个子数组，则 dp 值就是对应的 medianCost
nextDp[j] = medianCost[j];
} else {
// 否则为当前窗口调整代价加上后续窗口的最小代价
nextDp[j] = medianCost[j] + dp[j + x];
}
// 保持 dp[j] 为 j 到 st 区间内的最小值
if (j != st) {
nextDp[j] = Math.min(nextDp[j + 1], nextDp[j]);
}
}
dp = nextDp;
}
return dp[0];
}
}
// 辅助类 MedianFinder：利用两个堆（用 TreeMap 实现）维护数据流的中位数及其调整代价。
// left 为大根堆（存储较小的一半数值），right 为小根堆（存储较大的一半数值）。
class MedianFinder {
Item left, right;
public MedianFinder() {
left = new Item();
right = new Item();
}
// 添加数字 key 到数据结构中
public void add(int key) {
// 先将 key 加入 right 部分
right.add(key);
// 再将 right 部分的最小值移入 left 以平衡两个堆
left.add(right.removeSmallest());
// 如果 left 数量比 right 多出超过 1 个，则平衡之
if (left.count - right.count > 1) {
right.add(left.removeLargest());
}
}
// 从数据结构中移除数字 key
public void remove(int key) {
if (left.contains(key)) {
left.remove(key);
// 如果 left 元素减少后比 right 少，则从 right 移动最小值到 left
if (left.count < right.count) {
left.add(right.removeSmallest());
}
} else if (right.contains(key)) {
right.remove(key);
// 重新平衡两个堆，确保 left 数量始终不超过 right 多 1 个
if (left.count - right.count > 1) {
right.add(left.removeLargest());
}
}
}
}
// 辅助类 Item：利用 TreeMap 来模拟堆的功能，同时记录堆内元素的和（sum）和数量（count）。
class Item {
TreeMap<Integer, Integer> map;
long sum; // 堆内所有元素之和
int count; // 堆内元素个数
public Item() {
map = new TreeMap<>();
sum = 0;
count = 0;
}
// 移除并返回堆中的最大值（适用于 left 堆）
public int removeLargest() {
int key = map.lastKey();
return remove(key);
}
// 移除并返回堆中的最小值（适用于 right 堆）
public int removeSmallest() {
int key = map.firstKey();
return remove(key);
}
// 向堆中添加元素 key
public void add(int key) {
map.put(key, map.getOrDefault(key, 0) + 1);
sum += key;
count += 1;
}
// 判断堆中是否包含元素 key
public boolean contains(int key) {
return map.containsKey(key);
}
// 从堆中移除一个 key，并返回该 key
public int remove(int key) {
sum -= key;
count -= 1;
int t = map.get(key);
if (t == 1) {
map.remove(key);
} else {
map.put(key, t - 1);
}
return key;
}
}