2578. 最小和分割
给你一个正整数 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 <= 10^9解答：贪心，a,b谁小就加当前的值
class Solution {
public int splitNum(int num) {
int[] res=new int[10];
int len=0;
while(num>0){
int a=num%10;
res[a]++;
len++;
num/=10;
}
int a=0,b=0;
while(len-->0){
for(int i=0;i<=9;i++){
if(res[i]==0)continue;
if(a<=b){
a=a*10+i;
}
else b=b*10+i;
res[i]--;
break;
}
}
return a+b;
}
}2579. 统计染色格子数
有一个无穷大的二维网格图，一开始所有格子都未染色。给你一个正整数 n ，表示你需要执行以下步骤 n 分钟：
第一分钟，将 任一 格子染成蓝色。
之后的每一分钟，将与蓝色格子相邻的 所有 未染色格子染成蓝色。
下图分别是 1、2、3 分钟后的网格图。
请你返回 n 分钟之后 被染色的格子 数目。
示例 1：
输入：n = 1
输出：1
解释：1 分钟后，只有 1 个蓝色的格子，所以返回 1 。
示例 2：
输入：n = 2
输出：5
解释：2 分钟后，有 4 个在边缘的蓝色格子和 1 个在中间的蓝色格子，所以返回 5 。
提示：
1 <= n <= 10^5解答：找规律。
class Solution {
public long coloredCells(int n) {
if(n==1)return 1;
long res=1;
for(int i=2;i<=n;i++){
res+=(i-1)*4;
}
return res;
}
}2580. 统计将重叠区间合并成组的方案数
给你一个二维整数数组 ranges ，其中 ranges[i] = [starti, endi] 表示 starti 到 endi 之间（包括二者）的所有整数都包含在第 i 个区间中。
你需要将 ranges 分成 两个 组（可以为空），满足：
每个区间只属于一个组。
两个有 交集 的区间必须在 同一个 组内。
如果两个区间有至少 一个 公共整数，那么这两个区间是 有交集 的。
比方说，区间 [1, 3] 和 [2, 5] 有交集，因为 2 和 3 在两个区间中都被包含。
请你返回将 ranges 划分成两个组的 总方案数 。由于答案可能很大，将它对 10^9 + 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 <= 10^5
ranges[i].length == 2
0 <= starti <= endi <= 10^9解答：排序+合并区间
class Solution {
public int countWays(int[][] ranges) {
int MOD = 1000000007;
int n = ranges.length;
Arrays.sort(ranges,(a,b)->a[0]-b[0]);
int res=2;
int l=ranges[0][0],r=ranges[0][1];
for (int i = 1; i < n; i++) {
int left=ranges[i][0],right=ranges[i][1];
if(r<left){
l=left;
res=(res*2)%MOD;
}
r=Math.max(r,right);
}
return res;
}
}2581. 统计可能的树根数目
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 <= 10^5
1 <= guesses.length <= 10^5
0 <= ai, bi, uj, vj <= n - 1
ai != bi
uj != vj
edges 表示一棵有效的树。
guesses[j] 是树中的一条边。
guesses 是唯一的。
0 <= k <= guesses.length解答：换根DP
class Solution {
private List<Integer>[] g;
private Set<Long> s = new HashSet<>();
private int k, ans, cnt0;
public int rootCount(int[][] edges, int[][] guesses, int k) {
this.k = k;
g = new ArrayList[edges.length + 1];
Arrays.setAll(g, e -> new ArrayList<>());
for (var e : edges) {
int x = e[0], y = e[1];
g[x].add(y);
g[y].add(x); // 建图
}
for (var e : guesses) // guesses 转成哈希表
s.add((long) e[0] << 32 | e[1]); // 两个 4 字节数压缩成一个 8 字节数
dfs(0, -1);
reroot(0, -1, cnt0);
return ans;
}
private void dfs(int x, int fa) {
for (var y : g[x])
if (y != fa) {
if (s.contains((long) x << 32 | y)) // 以 0 为根时，猜对了
++cnt0;
dfs(y, x);
}
}
private void reroot(int x, int fa, int cnt) {
if (cnt >= k) ++ans; // 此时 cnt 就是以 x 为根时的猜对次数
for (var y : g[x])
if (y != fa) {
int c = cnt;
if (s.contains((long) x << 32 | y)) --c; // 原来是对的，现在错了
if (s.contains((long) y << 32 | x)) ++c; // 原来是错的，现在对了
reroot(y, x, c);
}
}
}
