leetcode weekly biweekly contest 99

最近几场的比赛质量确实很高。

6312. 最小和分割

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

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

请你返回 num1 和 num2 可以得到的和的最小值。

注意：

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

示例 1：

输入：num = 4325
输出：59
解释：我们可以将 4325 分割成 num1 = 24 和 num2 = 35 ，和为 59 ，59 是最小和。

示例 2：

输入：num = 687
输出：75
解释：我们可以将 687 分割成 num1 = 68 和 num2 = 7 ，和为最优值 75 。

提示：

10 <= num <= 109

地址

https://leetcode.cn/contest/biweekly-contest-99/problems/split-with-minimum-sum/

题意

贪心法

思路

如使得合最小则应该使得两个数的最高位之和尽可能的小，因此我们直接可以将两个数的按照奇偶位分开即可；
复杂度分析：

时间复杂度：$O(\log n)$，其中 $n$ 为给定的数。
空间复杂度：$O(\log n)$。

代码

class Solution {
public:
    int splitNum(int num) {
        string s = to_string(num);
        sort(s.begin(), s.end());
        int n = s.size();
        string s1, s2;
        for (int i = 0; i < n; i += 2) {
            s1.push_back(s[i]);
        }
        for (int i = 1; i < n; i += 2) {
            s2.push_back(s[i]);
        }
        return stoi(s1) + stoi(s2);
    }
};

6311. 统计染色格子数

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

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

下图分别是 1、2、3 分钟后的网格图。

请你返回 n 分钟之后 被染色的格子 数目。

示例 1：

输入：n = 1
输出：1
解释：1 分钟后，只有 1 个蓝色的格子，所以返回 1 。

示例 2：

输入：n = 2
输出：5
解释：2 分钟后，有 4 个在边缘的蓝色格子和 1 个在中间的蓝色格子，所以返回 5 。

提示：

1 <= n <= 105

地址

https://leetcode.cn/contest/biweekly-contest-99/problems/count-total-number-of-colored-cells/

题意

数学

思路

我们可以观察到一下按照列分布，每一列的长度刚好为 $(1,3,5, 2 * n - 1, 2 * n - 2, \cdots, 5, 3 ,1)$。本质为两个等差数列，我们直接按照等差数列求和公式计算即可。
我们可以得到它的计算公式为 :
$$
tot = 2 * n - 1 + (n - 1) * (1 + 2 * n - 3) \
= 2 * n - 1 + 2 * (n - 1)^{2}
$$
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 为字符串的长度。
空间复杂度：$O(n)$，主要为排序需要空间。

代码

class Solution {
public:
    long long coloredCells(int n) {
        return 2 * n - 1 + 2 * (long long)(n - 1) * (n - 1);
    }
};

6313. 统计将重叠区间合并成组的方案数

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

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

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

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

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

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

示例 1：

输入：ranges = [[6,10],[5,15]]
输出：2
解释：
两个区间有交集，所以它们必须在同一个组内。
所以有两种方案：
- 将两个区间都放在第 1 个组中。
- 将两个区间都放在第 2 个组中。

示例 2：

输入：ranges = [[1,3],[10,20],[2,5],[4,8]]
输出：4
解释：
区间 [1,3] 和 [2,5] 有交集，所以它们必须在同一个组中。
同理，区间 [2,5] 和 [4,8] 也有交集，所以它们也必须在同一个组中。
所以总共有 4 种分组方案：
- 所有区间都在第 1 组。
- 所有区间都在第 2 组。
- 区间 [1,3] ，[2,5] 和 [4,8] 在第 1 个组中，[10,20] 在第 2 个组中。
- 区间 [1,3] ，[2,5] 和 [4,8] 在第 2 个组中，[10,20] 在第 1 个组中。

提示：

1 <= ranges.length <= 105
ranges[i].length == 2
0 <= starti <= endi <= 109

地址

https://leetcode.cn/contest/biweekly-contest-99/problems/count-ways-to-group-overlapping-ranges/

题意

排序 + 取模

思路

我们对所有有重叠的区间进行连续合并，统计合并后的区间的数目，这些合并后的区间之间是不存在交集的，他们之间可以在两个分组中任意选择，因此可能的分组数目为 $2^n$ 个，其中 $n$ 表示合并后不想交的区间的总数。
复杂度分析：

时间复杂度：$O(n \log n)$，其中 $n$ 为区间的数目。
空间复杂度：$O(\log n)$。

代码

class Solution {
public:
    int countWays(vector<vector<int>>& ranges) {
        int n = ranges.size();
        sort(ranges.begin(), ranges.end());
        int last = 0, cnt = 0;
        for (int i = 0; i < n; ) {
            last = ranges[i][1];
            while (i < n && ranges[i][0] <= last) {
                last = max(last, ranges[i][1]);
                i++;
            }
            cnt++;
        }
        long long ans = 1, curr = 2;
        long long mod = 1e9 + 7;
        while (cnt) {
            if (cnt & 1) {
                ans = (ans * curr) % mod;
            }
            cnt >>= 1;
            curr = (curr * curr) % mod;
        }
        return ans;
    }
};

6314. 统计可能的树根数目

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。

示例 1：

输入：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 个正确的猜测。

示例 2：

输入：edges = [[0,1],[1,2],[2,3],[3,4]], guesses = [[1,0],[3,4],[2,1],[3,2]], k = 1
输出：5
解释：
根为节点 0 ，正确的猜测为 [3,4]
根为节点 1 ，正确的猜测为 [1,0], [3,4]
根为节点 2 ，正确的猜测为 [1,0], [2,1], [3,4]
根为节点 3 ，正确的猜测为 [1,0], [2,1], [3,2], [3,4]
根为节点 4 ，正确的猜测为 [1,0], [2,1], [3,2]
任何节点为根，都至少有 1 个正确的猜测。

提示：

edges.length == n - 1
2 <= n <= 105
1 <= guesses.length <= 105
0 <= ai, bi, uj, vj <= n - 1
ai != bi
uj != vj
edges 表示一棵有效的树。
guesses[j] 是树中的一条边。
0 <= k <= guesses.length

地址

https://leetcode.cn/contest/biweekly-contest-99/problems/count-number-of-possible-root-nodes/

题意

树形 dp

思路

题目初看起来好像很麻烦，没有思路，实际上比较还不算很难，力扣上有类似的题目，本题与之前的某个题目非常相似834. 树中距离之和，题目本身思考还是非常有意思的，我们假设当前根为 $x$，根的孩子节点为 $y$，此时 $[x,y]$ 则为合法的关系，而当我们仅仅转换到以 $y$ 为根时，此时树中父亲与孩子节点的对应关系，实际仅仅只有 $(x,y)$ 变为 $(y,x)$，其余的父亲与孩子节点的对应关系实际均保持不变的。因此我们每次进行遍历时，则换一次根即可，快速得到当前的合法关系的数目。
复杂度分析：

时间复杂度：$O(V + E)$，其中 $V$ 为树中节点的数目,$E$ 表示边的数目。
空间复杂度：$O(m + n)$，其中 $V$ 为树中节点的数目,$E$ 表示边的数目。

代码

class Solution {
public:
    long long hash(int x, int y) {
        return  ((long long) x << 32) | y;
    }
    
    int rootCount(vector<vector<int>>& edges, vector<vector<int>>& guesses, int k) {
        int n = edges.size() + 1, m = guesses.size();
        vector<vector<int>> adj(n);
        unordered_set<long long> cnt;
        int res = 0;
        for (auto v : edges) {
            adj[v[0]].emplace_back(v[1]);
            adj[v[1]].emplace_back(v[0]);
        }  
        for (auto v : guesses) {
            cnt.emplace(hash(v[0], v[1]));
        }
        int valid = 0;
        function<void(int, int)> dfs1 = [&](int parent, int vertex) {
            for (auto neg : adj[vertex]) {
                if (neg != parent) {
                    valid += cnt.count(hash(vertex, neg));
                    dfs1(vertex, neg);
                }
            }
        };
        function<void(int, int)> dfs2 = [&](int parent, int vertex) {
            for (auto neg : adj[vertex]) {
                if (neg != parent) {
                    valid -= cnt.count(hash(vertex, neg));
                    valid += cnt.count(hash(neg, vertex));
                    if (valid >= k) {
                        res++;
                    }
                    dfs2(vertex, neg);
                    valid += cnt.count(hash(vertex, neg));
                    valid -= cnt.count(hash(neg, vertex));
                }
            }
        };
        
        dfs1(-1, 0);
        if (valid >= k) {
            res++;
        }
        dfs2(-1, 0);
        return res;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://whistle-wind.com/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛题解

← leetcode weekly contest 334 leetcode weekly contest 335 →

扫描二维码，分享此文章