欢迎大家加QQ群：623375442，可以方便群里面交流。这周题目着实很难。第一题和第四题一样，我就只放第四题题解了。
100373. K-th Largest Perfect Subtree Size in Binary Tree
给你一棵 二叉树 的根节点 root 和一个整数k。
返回第 k 大的 完美二叉子树 的大小，如果不存在则返回 -1。
完美二叉树 是指所有叶子节点都在同一层级的树，且每个父节点恰有两个子节点。
子树 是指树中的某一个节点及其所有后代形成的树。
测试样例：
输入：root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2
输出：3
解释：完美二叉子树的根节点在图中以黑色突出显示。它们的大小按降序排列为 [3, 3, 1, 1, 1, 1, 1, 1]。
第 2 大的完美二叉子树的大小是 3。
解答：两个条件，一个是叶子结点深度一样，且所有每个父节点恰有两个子节点。这样我们dfs遍历这棵树，寻找到符合要求结点，然后存入一个list中。这题空间范围不大，直接排序取第k大。
class Solution {
public int kthLargestPerfectSubtree(TreeNode root, int k) {
List<Integer> list = new ArrayList<>();
child(root, list);
if (list.size() < k) {
return -1;
}
Collections.sort(list, (a, b) -> (b.compareTo(a)));
return list.get(k - 1);
}
private int[] child(TreeNode node, List<Integer> res) {
if (node == null) {
return null;
} else if (node.left == null && node.right == null) {
res.add(1);
return new int[]{1,1};
} else {
int[] left = child(node.left, res), right = child(node.right, res);
// 左右都是完美二叉树，且深度一致。则当前也是完美二叉树
if (left == null || right == null || left[1] != right[1]) {
return null;
} else {
int[] tmp = {left[0] + right[0] + 1, left[1] + 1};
res.add(tmp[0]);
return tmp;
}
}
}
}100439. Count The Number of Winning Sequences
Alice 和 Bob 正在玩一个幻想战斗游戏，游戏共有 n 回合，每回合双方各自都会召唤一个魔法生物：火龙（F）、水蛇（W）或地精（E）。每回合中，双方 同时 召唤魔法生物，并根据以下规则得分：
- 如果一方召唤火龙而另一方召唤地精，召唤 火龙 的玩家将获得一分。
- 如果一方召唤水蛇而另一方召唤火龙，召唤 水蛇 的玩家将获得一分。
- 如果一方召唤地精而另一方召唤水蛇，召唤 地精 的玩家将获得一分。
- 如果双方召唤相同的生物，那么两个玩家都不会获得分数。
给你一个字符串 s，包含 n 个字符 'F'、'W' 和 'E'，代表 Alice 每回合召唤的生物序列：
- 如果 s[i] == 'F'，Alice 召唤火龙。
- 如果 s[i] == 'W'，Alice 召唤水蛇。
- 如果 s[i] == 'E'，Alice 召唤地精。
Bob 的出招序列未知，但保证 Bob 不会在连续两个回合中召唤相同的生物。如果在 n 轮后 Bob 获得的总分 严格大于 Alice 的总分，则 Bob 战胜 Alice。
返回 Bob 可以用来战胜 Alice 的不同出招序列的数量。
由于答案可能非常大，请返回答案对 10^9 + 7 取余 后的结果。
测试样例：
输入：s = "FFF"
输出：3
解释：Bob 可以通过以下 3 种出招序列战胜 Alice："WFW"、"FWF" 或 "WEW"。注意，其他如 "WWE" 或 "EWW" 的出招序列是无效的，因为 Bob 不能在连续两个回合中使用相同的生物。
解答：动态规划，当前保存Bob最后选择的情况，和当前情况的分数。
class Solution {
private static final int mod = 1_000_000_007;
public int countWinningSequences(String s) {
int len = s.length();
int score = 2 * len + 1;
int[][] last = new int[3][score];
{
int current = getCurrent(s.charAt(0));
int win = getWin(s.charAt(0));
for (int i = 0; i < 3; ++i) {
if (i == current) {
last[i][len] = 1;
} else if (i == win) {
last[i][len + 1] = 1;
} else {
last[i][len - 1] = 1;
}
}
}
for (int n = 1; n < s.length(); ++n) {
int[][] next = new int[3][score];
int current = getCurrent(s.charAt(n));
int win = getWin(s.charAt(n));
for (int i = 0; i < 3; ++i) {
for (int j = 0; j <= 2 * len; ++j) {
if (last[i][j] != 0) {
for (int other = 0; other < 3; ++other) {
// 不能连续相同
if (other == i) continue;
if (other == current) {
// 与当前Alice相同，则分数不变
next[other][j] = (next[other][j] + last[i][j]) % mod;
} else if (other == win) {
// 与胜利选项，则分数+1
next[other][j + 1] = (next[other][j + 1] + last[i][j]) % mod;
} else {
// 与失败选项，则分数+1
next[other][j - 1] = (next[other][j - 1] + last[i][j]) % mod;
}
}
}
}
}
last = next;
}
int res = 0;
for (int i = 0; i < 3; ++i) {
for (int j = len + 1; j <= 2 * len; ++j) {
res = (res + last[i][j]) % mod;
}
}
return res;
}
private int getWin(char c) {
return switch (c) {
case 'F' -> 1;
case 'W' -> 2;
case 'E' -> 0;
default -> -1;
};
}
private int getCurrent(char c) {
return switch (c) {
case 'F' -> 0;
case 'W' -> 1;
case 'E' -> 2;
default -> -1;
};
}
}
100442. Find X-Sum of All K-Long Subarrays II
给你一个由 n 个整数组成的数组 nums，以及两个整数 k 和 x。
数组的 x-sum 计算按照以下步骤进行：
- 统计数组中所有元素的出现次数。
- 仅保留出现次数最多的前 x 个元素的每次出现。如果两个元素的出现次数相同，则数值 较大 的元素被认为出现次数更多。
- 计算结果数组的和。
注意，如果数组中的不同元素少于 x 个，则其 x-sum 是数组的元素总和。
返回一个长度为 n - k + 1 的整数数组 answer，其中 answer[i] 是 子数组 nums[i..i + k - 1] 的 x-sum。
子数组 是数组内的一个连续 非空 的元素序列。
测试样例：
输入：nums = [1,1,2,2,3,4,2,3], k = 6, x = 2
输出：[6,10,12]
解释：
- 对于子数组 [1, 1, 2, 2, 3, 4]，只保留元素 1 和 2。因此，answer[0] = 1 + 1 + 2 + 2。
- 对于子数组 [1, 2, 2, 3, 4, 2]，只保留元素 2 和 4。因此，answer[1] = 2 + 2 + 2 + 4。注意 4 被保留是因为其数值大于出现其他出现次数相同的元素（3 和 1）。
- 对于子数组 [2, 2, 3, 4, 2, 3]，只保留元素 2 和 3。因此，answer[2] = 2 + 2 + 2 + 3 + 3。
解答：这题和数字流中选择最大的N个数逻辑差不多。动态变动两个红黑树。
class Solution {
public long[] findXSum(int[] nums, int k, int x) {
long[] res = new long[nums.length - k + 1];
TopCount count = new TopCount(x);
for (int i = 0; i < nums.length; ++i) {
count.addNum(nums[i]);
if (i >= k - 1) {
res[i - k + 1] = count.getResult();
count.removeNum(nums[i - k + 1]);
}
}
return res;
}
}
class TopCount {
public TreeSet<int[]> valid, buffer;
public HashMap<Integer, Integer> count;
private long res;
private int x;
public TopCount(int x) {
// 记录需要保存的x个数
valid = new TreeSet<>((a, b) -> (a[1] != b[1] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0])));
// 记录需要未的x个数
buffer = new TreeSet<>((a, b) -> (a[1] != b[1] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0])));
count = new HashMap<>();
res = 0;
this.x = x;
}
public void addNum(int num) {
int old = count.getOrDefault(num, 0);
count.put(num, old + 1);
if (old > 0) {
int[] key = {num, old};
if (buffer.contains(key)) {
buffer.remove(key);
} else if (valid.contains(key)) {
// 已经是valid的数字，就不用进行数据流变动了（增加不会造成valid的数字变成非法）
valid.remove(key);
res += num;
key[1] += 1;
valid.add(key);
return;
}
}
if (!valid.isEmpty()) {
int[] tmp = valid.pollFirst();
res -= (long) tmp[0] * tmp[1];
buffer.add(tmp);
}
// 更新完，开始转动数据流
buffer.add(new int[]{num, old + 1});
while (valid.size() < x && !buffer.isEmpty()) {
int[] tmp = buffer.pollLast();
res += (long) tmp[0] * tmp[1];
valid.add(tmp);
}
}
public void removeNum(int num) {
int old = count.get(num);
if (old == 1) {
count.remove(num);
} else {
count.put(num, old - 1);
}
int[] key = {num, old};
if (buffer.contains(key)) {
// 删除数字类似。不valid的数字，删除后没办法变得valid
buffer.remove(key);
key[1] -= 1;
if (key[1] > 0) {
buffer.add(key);
}
return;
} else if (valid.contains(key)) {
valid.remove(key);
res -= (long) key[0] * key[1];
}
if (old - 1 > 0) {
key[1] -= 1;
buffer.add(key);
}
while (valid.size() < x && !buffer.isEmpty()) {
int[] tmp = buffer.pollLast();
res += (long) tmp[0] * tmp[1];
valid.add(tmp);
}
}
public long getResult() {
return res;
}
}