欢迎大家加QQ群：623375442，可以方便群里面交流。这周题目，太要求仔细了。写起来真的好麻烦。
100525. Maximum Subarray With Equal Products
给你一个由 正整数 组成的数组 nums。
如果一个数组 arr 满足 prod(arr) == lcm(arr) * gcd(arr)，则称其为 乘积等价数组 ，其中：
- prod(arr) 表示 arr 中所有元素的乘积。
- gcd(arr) 表示 arr 中所有元素的最大公因数 (GCD)。
- lcm(arr) 表示 arr 中所有元素的最小公倍数 (LCM)。
返回数组 nums 的 最长 乘积等价子数组 的长度。
子数组 是数组中连续的、非空的元素序列。
术语 gcd(a, b) 表示 a 和 b 的 最大公因数 。
术语 lcm(a, b) 表示 a 和 b 的 最小公倍数 。
测试样例：
输入：nums = [1,2,1,2,1,1,1]
输出：5
解释：按照题意暴力计算。
解答：按照题意，暴力计算。
class Solution {
public int maxLength(int[] nums) {
int res = 1;
for (int i = 0; i < nums.length; ++i) {
long mul = nums[i], gcd = nums[i], lcm = nums[i];
for (int j = i + 1; j < nums.length; ++j) {
gcd = gcd(gcd, nums[j]);
mul *= nums[j];
lcm = lcm * nums[j] / gcd(lcm, nums[j]);
if (gcd * lcm == mul) {
res = Math.max(res, j - i + 1);
} else {
break;
}
}
}
return res;
}
private long gcd(long x, long y) {
while (y != 0) {
long tmp = x % y;
x = y;
y = tmp;
}
return x;
}
}100476. Find Mirror Score of a String
给你一个字符串 s。
英文字母中每个字母的 镜像 定义为反转字母表之后对应位置上的字母。例如，'a' 的镜像是 'z'，'y' 的镜像是 'b'。
最初，字符串 s 中的所有字符都 未标记 。
字符串 s 的初始分数为 0 ，你需要对其执行以下过程：
- 从左到右遍历字符串。
- 对于每个下标 i ，找到距离最近的 未标记 下标 j，下标 j 需要满足 j < i 且 s[j] 是 s[i] 的镜像。然后 标记 下标 i 和 j，总分加上 i - j 的值。
- 如果对于下标 i，不存在满足条件的下标 j，则跳过该下标，继续处理下一个下标，不需要进行标记。
返回最终的总分。
测试样例：
输入： s = "aczzx"
输出：5
解释：所有可能的分割方式为：
- i = 0。没有符合条件的下标 j，跳过。
- i = 1。没有符合条件的下标 j，跳过。
- i = 2。距离最近的符合条件的下标是 j = 0，因此标记下标 0 和 2，然后将总分加上 2 - 0 = 2 。
- i = 3。没有符合条件的下标 j，跳过。
- i = 4。距离最近的符合条件的下标是 j = 1，因此标记下标 1 和 4，然后将总分加上 4 - 1 = 3 。
解答：这周最简单的题目，用栈模拟一下即可。
class Solution {
public long calculateScore(String s) {
long res = 0;
Stack<Integer>[] map = new Stack[26];
for (int i = 0; i < 26; ++i) {
map[i] = new Stack<>();
}
for (int i = 0; i < s.length(); ++i) {
int tmp = s.charAt(i) - 'a';
if (!map[25 - tmp].isEmpty()) {
res += (i - map[25 - tmp].pop());
} else {
map[tmp].push(i);
}
}
return res;
}
}100535. Maximum Coins From K Consecutive Bags
在一条数轴上有无限多个袋子，每个坐标对应一个袋子。其中一些袋子里装有硬币。
给你一个二维数组 coins，其中 coins[i] = [li, ri, ci] 表示从坐标 li 到 ri 的每个袋子中都有 ci 枚硬币。
数组 coins 中的区间互不重叠。
另给你一个整数 k。
返回通过收集连续 k 个袋子可以获得的 最多 硬币数量。
测试样例：
输入：coins = [[8,10,1],[1,3,2],[5,6,4]], k = 4
输出：10
解释：选择坐标为 [3, 4, 5, 6] 的袋子可以获得最多硬币：2 + 0 + 4 + 4 = 10。
解答：稍微脑筋急转弯一下。最大范围一定是从一个区间的左边向后找到最大范围，或者从一个区间的右边向前最大范围。
class Solution {
public long maximumCoins(int[][] coins, long k) {
Arrays.sort(coins, (a, b) -> (Integer.compare(a[0], b[0])));
long res = 0;
{
int left = 0, right = 0;
long cur = 0;
// 锁定左区间，然后向后找最大范围
while (left < coins.length) {
while (right < coins.length && coins[right][1] - coins[left][0] < k) {
cur += (coins[right][1] - coins[right][0] + 1L) * coins[right][2];
++right;
}
if (right < coins.length && coins[right][1] - coins[left][0] >= k && coins[right][0] - coins[left][0] < k) {
res = Math.max(res, cur + (coins[left][0] + k - coins[right][0]) * coins[right][2]);
} else {
res = Math.max(res, cur);
}
if (coins[left][1] - coins[left][0] < k) {
cur -= (coins[left][1] - coins[left][0] + 1L) * coins[left][2];
}
++left;
right = Math.max(right, left);
}
}
{
int left = coins.length - 1, right = coins.length - 1;
long cur = 0;
// 锁定右区间，然后向前找最大范围
while (right >= 0) {
while (left >= 0 && coins[right][1] - coins[left][0] < k) {
cur += (coins[left][1] - coins[left][0] + 1L) * coins[left][2];
--left;
}
if (left >= 0 && coins[right][1] - coins[left][0] >= k && coins[right][1] - coins[left][1] < k) {
res = Math.max(res, cur + (coins[left][1] - coins[right][1] + k) * coins[left][2]);
} else {
res = Math.max(res, cur);
}
if (coins[right][1] - coins[right][0] < k) {
cur -= (coins[right][1] - coins[right][0] + 1L) * coins[right][2];
}
--right;
left = Math.min(left, right);
}
}
return res;
}
}100418. Maximum Score of Non-overlapping Intervals
给你一个二维整数数组 intervals，其中 intervals[i] = [li, ri, weighti]。区间 i 的起点为 li，终点为 ri，权重为 weighti。你最多可以选择 4 个互不重叠 的区间。所选择区间的 得分 定义为这些区间权重的总和。
返回一个至多包含 4 个下标且字典序最小的数组，表示从 intervals 中选中的互不重叠且得分最大的区间。
如果两个区间没有任何重叠点，则称二者 互不重叠 。特别地，如果两个区间共享左边界或右边界，也认为二者重叠。
数组 a 的字典序小于数组 b 的前提是：当在第一个不同的位置上，a 的元素小于 b 的对应元素。如果前 min(a.length, b.length) 个元素均相同，则较短的数组字典序更小。
测试样例：
输入：intervals = [[1,3,2],[4,5,2],[1,5,5],[6,9,3],[6,7,1],[8,9,1]]
输出：[2,3]
解释：可以选择下标为 2 和 3 的区间，其权重分别为 5 和 3。
解答：只能说比昨天的双周赛简单很多。比较标准的俄罗斯套娃娃的改变题目。主要写代码需要仔细一点。我是WA了好几次。
class Solution {
public int[] maximumWeight(List<List<Integer>> _intervals) {
int[][] intervals = new int[_intervals.size()][3];
int pos = 0;
for (List<Integer> interval : _intervals) {
for (int i = 0; i < 3; ++i) {
intervals[pos][i] = interval.get(i);
}
++pos;
}
Integer[] sort = new Integer[intervals.length];
for (int i = 0; i < sort.length; ++i) {
sort[i] = i;
}
Arrays.sort(sort, (a, b) -> (Integer.compare(intervals[a][1], intervals[b][1])));
TreeMap<Integer, List<Integer>[]> mem = new TreeMap<>();
List<Integer>[] res = new List[4];
for (int i = 0; i < 4; ++i) {
res[i] = new ArrayList<>();
}
for (int s : sort) {
Map.Entry<Integer, List<Integer>[]> lowerEntry = mem.lowerEntry(intervals[s][0]);
List<Integer>[] best = new List[4];
if (lowerEntry == null) {
best[0] = new ArrayList<>();
best[0].add(s);
} else {
List<Integer>[] lower = lowerEntry.getValue();
for (int i = 0; i < 4; ++i) {
if (i == 0) {
best[0] = new ArrayList<>();
best[0].add(s);
} else {
best[i] = duplicate(lower[i - 1]);
best[i].add(s);
Collections.sort(best[i]);
}
}
}
res = better(res, best, intervals);
mem.put(intervals[s][1], res);
}
List<Integer> best = null;
for (int i = 3; i >= 0; --i) {
best = better(best, res[i], intervals);
}
int[] resFormat = new int[best.size()];
for (int j = 0; j < resFormat.length; ++j) {
resFormat[j] = best.get(j);
}
return resFormat;
}
private List<Integer>[] better(List<Integer>[] lefts, List<Integer>[] rights, int[][] intervals) {
List<Integer>[] res = new List[4];
for (int i = 0; i < 4; ++i) {
res[i] = better(lefts[i], rights[i], intervals);
}
return res;
}
private List<Integer> better(List<Integer> left, List<Integer> right, int[][] intervals) {
if (left == null) return right;
else if (right == null) return left;
long s1 = 0, s2 = 0;
for (int n : left) {
s1 += intervals[n][2];
}
for (int n : right) {
s2 += intervals[n][2];
}
if (s1 > s2) {
return left;
} else if (s1 < s2) {
return right;
} else {
for (int i = 0; i < Math.min(left.size(), right.size()); ++i) {
int tmp = left.get(i).compareTo(right.get(i));
if (tmp > 0) {
return right;
} else if (tmp < 0) {
return left;
}
}
return right;
}
}
private List<Integer> duplicate(List<Integer> old) {
List<Integer> res = new ArrayList<>(old);
return res;
}
}