LeetCode Contest 419

欢迎大家加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;
    }
}