LeetCode Biweekly Contest 99

这周双周赛，我觉得题目不是很好。基本都是脑经急转弯，非常不友好。

6312. Split With Minimum Sum

给你一个正整数 num ，请你将它分割成两个非负整数 num1 和 num2 ，满足：

• num1 和 num2 直接连起来，得到 num 各数位的一个排列。
  换句话说，num1 和 num2 中所有数字出现的次数之和等于 num 中所有数字出现的次数。
• num1 和 num2 可以包含前导 0 。
  请你返回 num1 和 num2 可以得到的和的 最小 值。

注意：

• num 保证没有前导 0 。
• num1 和 num2 中数位顺序可以与 num 中数位顺序不同。

测试样例

输入：num = 4325

输出：59

解释：

我们可以将 4325 分割成 num1 = 24 和 num2 = 35 ，和为 59 ，59 是最小和。

解答：由于只能分成2个数，那么每个数的低位尽量放较大的数字

class Solution {
    public int splitNum(int num) {
        int[] mem = new int[10];
        while (num != 0) {
            mem[num % 10] += 1;
            num /= 10;
        }
        int l = 1, r = 1, res = 0;
        for (int i = 9; i >= 0; --i) {
            for (int j = 0; j < mem[i]; ++j) {
                if (l <= r) {
                    res += l * i;
                    l *= 10;
                } else {
                    res += r * i;
                    r *= 10;
                }
            }
        }
        return res;
    }
}

6311. Count Total Number of Colored Cells

有一个无穷大的二维网格图，一开始所有格子都未染色。给你一个正整数 n ，表示你需要执行以下步骤 n 分钟：

• 第一分钟，将 任一 格子染成蓝色。
• 之后的每一分钟，将与蓝色格子相邻的 所有 未染色格子染成蓝色。

测试样例：

输入：1

输出：1

解释：

1 分钟后，只有 1 个蓝色的格子，所以返回 1 。

解答: 找规律题

class Solution {
    public long coloredCells(int n) {
        if (n == 1) return 1;
        long res = 1, add = 4;
        for (int i = 1; i < n; ++i) {
            res += add;
            add += 4;
        }
        return res;
    }
}

6313. Count Ways to Group Overlapping Ranges

给你一个二维整数数组 ranges ，其中 ranges[i] = [starti, endi] 表示 starti 到 endi 之间（包括二者）的所有整数都包含在第 i 个区间中。

你需要将 ranges 分成 两个 组（可以为空），满足：

• 每个区间只属于一个组。
• 两个有 交集 的区间必须在 同一个 组内。

如果两个区间有至少 一个 公共整数，那么这两个区间是 有交集 的。

• 比方说，区间 [1, 3] 和 [2, 5] 有交集，因为 2 和 3 在两个区间中都被包含。

请你返回将 ranges 划分成两个组的 总方案数 。由于答案可能很大，将它对 10^9 + 7 取余 后返回。

测试样例：

输入：ranges = [[6,10],[5,15]]

输出：2

解释：

两个区间有交集，所以它们必须在同一个组内。
所以有两种方案：

• 将两个区间都放在第 1 个组中。
• 将两个区间都放在第 2 个组中。

解答: 排序之后寻找必然重叠的组。然后每个毫无重叠的小组，都能放入1和2两种可能，2整数幂

class Solution {
    private static final int mod = 1_000_000_007;

    public int countWays(int[][] ranges) {
        Arrays.sort(ranges, (a, b) -> (a[0] - b[0]));
        int distinct = 0, max = -1;
        for (int i = 0; i < ranges.length; ++i) {
            if (ranges[i][0] > max) {
                ++distinct;
            }
            max = Math.max(max, ranges[i][1]);
        }
        int res = 1;
        for (int i = 0; i < distinct; ++i) {
            res = res * 2 % mod;
        }
        return res;
    }
}

6314. Count Number of Possible Root Nodes

Alice 有一棵 n 个节点的树，节点编号为 0 到 n - 1 。树用一个长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [ai, bi] ，表示树中节点 ai 和 bi 之间有一条边。

Alice 想要 Bob 找到这棵树的根。她允许 Bob 对这棵树进行若干次 猜测 。每一次猜测，Bob 做如下事情：

• 选择两个 不相等 的整数 u 和 v ，且树中必须存在边 [u, v] 。
• Bob 猜测树中 u 是 v 的 父节点 。

Bob 的猜测用二维整数数组 guesses 表示，其中 guesses[j] = [uj, vj] 表示 Bob 猜 uj 是 vj 的父节点。

Alice 非常懒，她不想逐个回答 Bob 的猜测，只告诉 Bob 这些猜测里面 至少 有 k 个猜测的结果为 true 。

给你二维整数数组 edges ，Bob 的所有猜测和整数 k ，请你返回可能成为树根的 节点数目 。如果没有这样的树，则返回 0。

测试样例：

输入：edges = [[0,1],[1,2],[1,3],[4,2]], guesses = [[1,3],[0,1],[1,0],[2,4]], k = 3

输出：3

解释：

• 根为节点 0 ，正确的猜测为 [1,3], [0,1], [2,4]
• 根为节点 1 ，正确的猜测为 [1,3], [1,0], [2,4]
• 根为节点 2 ，正确的猜测为 [1,3], [1,0], [2,4]
• 根为节点 3 ，正确的猜测为 [1,0], [2,4]
• 根为节点 4 ，正确的猜测为 [1,3], [1,0]

节点 0 ，1 或 2 为根时，可以得到 3 个正确的猜测。

解答：需要脑经急转弯一下。首先以0作为根，计算一下符合要求的guesses数。然后以0节点为根开始递归这颗树。

这道题目比较tricky的地方，就是在递归树的时候，就能以这个节点作为根节点，并且计算当前的guesses满足数。原因是：当你在递归的过程中，除了父节点和当前节点的guesses边会收到影响，其他都保持不变。

class Solution {
    private long n;
    private int[][] guesses;
    private List<Integer>[] tree;
    private HashMap<Long, List<Integer>> guessesMap;

    public int rootCount(int[][] edges, int[][] guesses, int k) {
        n = edges.length + 1;
        this.guesses = guesses;
        tree = new List[edges.length + 1];
        for (int i = 0; i < n; ++i) {
            tree[i] = new ArrayList<>();
        }
        for (int[] e : edges) {
            tree[e[0]].add(e[1]);
            tree[e[1]].add(e[0]);
        }

        this.guessesMap = new HashMap<>();
        for (int i = 0; i < guesses.length; ++i) {
            long key = getKey(guesses[i][0], guesses[i][1]);
            if (!guessesMap.containsKey(key)) {
                guessesMap.put(key, new ArrayList<>());
            }
            guessesMap.get(key).add(i);
        }

        int initialCount = findZeroCount(0, -1);
        int[] res = {0};
        findAns(0, -1, initialCount, k, res);
        return res[0];
    }

    private long getKey(int x, int y) {
        return Math.min(x, y) * n + Math.max(x, y);
    }

    private int findZeroCount(int n, int l) {
        int res = 0;
        for (int i : tree[n]) {
            if (i != l) {
                long key = getKey(i, n);
                if (guessesMap.containsKey(key)) {
                    for (int g : guessesMap.get(key)) {
                        if (guesses[g][0] == n && guesses[g][1] == i) {
                            ++res;
                        }
                    }
                }
                res += findZeroCount(i, n);
            }
        }
        return res;
    }

    private void findAns(int n, int l, int curAns, int k, int[] res) {
        if (curAns >= k) {
            res[0] += 1;
        }
        for (int i : tree[n]) {
            if (i != l) {
                long key = getKey(i, n);
                int diff = 0;
                if (guessesMap.containsKey(key)) {
                    for (int g : guessesMap.get(key)) {
                        if (guesses[g][0] == i && guesses[g][1] == n) {
                            --diff;
                        } else {
                            ++diff;
                        }
                    }
                }
                findAns(i, n, curAns - diff, k, res);
            }
        }
    }
}