本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。
大家好，我是小彭。
昨晚是 LeetCode 第 99 场双周赛，你参加了吗？这场周赛整体难度很低，第 4 题评论区普遍认为是 1 字头，纯纯手速场。
小彭的 Android 交流群 02 群来了，公众号回复 “加群” 加入我们~
https://leetcode.cn/problems/split-with-minimum-sum/
给你一个正整数 num ，请你将它分割成两个非负整数 num1 和 num2 ，满足：
num1 和 num2 直接连起来，得到 num 各数位的一个排列。
num1 和 num2 中所有数字出现的次数之和等于 num 中所有数字出现的次数。num1 和 num2 可以包含前导 0 。请你返回 num1 和 num2 可以得到的和的 最小 值。
注意：
num 保证没有前导 0 。num1 和 num2 中数位顺序可以与 num 中数位顺序不同。
第一题相对有点思维。
算法：对数字排序，从小到大分别排列到两个数字上。
class Solution {
fun splitNum(num: Int): Int {
val array = "$num".toCharArray()
array.sort()
var num1 = 0
var num2 = 0
for (index in array.indices step 2) {
num1 = num1 * 10 + (array[index] - '0')
if (index + 1 < array.size) {
num2 = num2 * 10 + (array[index + 1] - '0')
}
}
return num1 + num2
}
}
简化写法：
class Solution {
fun splitNum(num: Int): Int {
val array = "$num".toCharArray().sorted()
var nums = Array(2) { StringBuilder() }
for (index in array.indices) {
nums[index % 2].append(array[index])
}
return "${nums[0]}".toInt() + "${nums[1]}".toInt()
复杂度分析：
https://leetcode.cn/problems/count-total-number-of-colored-cells/
有一个无穷大的二维网格图，一开始所有格子都未染色。给你一个正整数 n ，表示你需要执行以下步骤 n 分钟：
下图分别是 1、2、3 分钟后的网格图。
找规律题。这道题可以用重力加速度类比，重力加速度的 G 是 9.8m/s，而这里的 G 是 4格/s。
显然有：
$f(n)=\begin{cases}
1, &n=1\
f(n-1) + 4(n-1) & n>1
\end{cases}$
可以看到， $n > 1$ 的分支是一个从 0 开始的等差数列，等差数列求和公式知道吧，整理得：$f(n) = 1 + 4 * n * (n - 1) / 2 = 2n^2 - 2n + 1$
class Solution {
fun coloredCells(n: Int): Long {
return 2 * n * n - 2 * n + 1
}
}
复杂度分析：
https://leetcode.cn/problems/count-ways-to-group-overlapping-ranges/
给你一个二维整数数组 ranges ，其中 ranges[i] = [starti, endi] 表示 starti 到 endi 之间（包括二者）的所有整数都包含在第 i 个区间中。
你需要将 ranges 分成 两个 组（可以为空），满足：
如果两个区间有至少 一个 公共整数，那么这两个区间是 有交集 的。
[1, 3] 和 [2, 5] 有交集，因为 2 和 3 在两个区间中都被包含。请你返回将 ranges 划分成两个组的 总方案数 。由于答案可能很大，将它对 109 + 7 取余 后返回。
这道题我第一时间想到了这两道题：
后来在评论区看到更接近的原题，好嘛，怪不得印象很深。
脑海中有闪现过并查集，但显然没有必要。
算法：将区间看成时间段，先按照开始时间对区间排序，然后在遍历区间的同时维护已经占用的最晚结束时间 preEnd。如果当前区间的开始时间早于 preEnd，说明区间重合。遍历完数组后求出集合个数 m，求 m 个元素放到 2 个位置的方案数，显然每个位置有 m 中可能，因此结果是 $2^m$。
class Solution {
fun countWays(ranges: Array<IntArray>): Int {
val MOD = 1000000007
Arrays.sort(ranges) { e1, e2 ->
e1[0] - e2[0]
}
var m = 0
var preEnd = -1
for (range in ranges) {
if (range[0] > preEnd) {
// 无交集
m++
}
preEnd = Math.max(preEnd, range[1])
}
return pow(2, m, MOD)
}
private fun pow(x: Int, n: Int, mod: Int): Int {
var ans = 1
for (count in 0 until n) {
ans = (ans * x) % mod
}
return ans
}
}
复杂度分析：
https://leetcode.cn/problems/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] 。u 是 v 的 父节点 。Bob 的猜测用二维整数数组 guesses 表示，其中 guesses[j] = [uj, vj] 表示 Bob 猜 uj 是 vj 的父节点。
Alice 非常懒，她不想逐个回答 Bob 的猜测，只告诉 Bob 这些猜测里面 至少 有 k 个猜测的结果为 true 。
给你二维整数数组 edges ，Bob 的所有猜测和整数 k ，请你返回可能成为树根的 节点数目 。如果没有这样的树，则返回 0。
这是换根 DP 问题，这道题相对简单了，只要掌握图的基本结构和递归的基本思想就能实现。
首先是建图的部分，显然 edges 是无向图，guesses 是有向图。我们的算法基本框架应该是：枚举每个根节点，计算 guesses 中猜测正确的边的个数，如果猜测次数 ≥ k 则记录 1 次结果。现在的问题是如果优化查询的时间复杂度，我们观察依次从 0 到 n - 1 修改根节点会发生什么？
我们发现： 每次调整中只有条边的结构关系变化。比如从根 0 调整到根 1 时，只有 0 → 1 被修改为 1 → 0，而其他边都没有变化，存在重叠子结构 / 重叠子问题。
定义 $f(u, v)$ 表示在 u → v 的子结构中猜测正确的边数，例如在示例 2 中，f(1, 2) = 1。显然在已知 f(1,2) 的结果后，在以节点 1 为根节点的情况中不需要重复计算，达到了剪枝的目的。
编码部分有两个细节：
class Solution {
private val graph = HashMap<Int, MutableList<Int>>()
private val guessGraph = HashMap<Int, MutableList<Int>>()
fun rootCount(edges: Array<IntArray>, guesses: Array<IntArray>, k: Int): Int {
// 无向图
for (edge in edges) {
graph.getOrPut(edge[0]) { LinkedList<Int>() }.add(edge[1])
graph.getOrPut(edge[1]) { LinkedList<Int>() }.add(edge[0])
}
// 有向图
for (guess in guesses) {
// 过滤不存在边（题目没有这种用例）
if (!graph.containsKey(guess[0]) || !graph[guess[0]]!!.contains(guess[1])) continue
guessGraph.getOrPut(guess[0]) { LinkedList<Int>() }.add(guess[1])
}
val n = edges.size + 1
// 空间溢出：val memo = Array(n + 1) { IntArray(n) { -1 } }
val memo = HashMap<Long, Int>()
var count = 0
// 枚举所有根
for (root in 0 until n) {
if (dfs(memo, 100000, n, root) >= k) count++
}
return count
}
// 记忆化递归
private fun dfs(memo: HashMap<Long, Int>, mod: Int, u: Int, v: Int): Int {
// 空间压缩
val key = 1L * u * (mod) + v
// 备忘录
if (memo.containsKey(key)) return memo[key]!!
var count = 0
for (to in graph[v]!!) {
// 过滤指向父节点的边
if (to == u) continue
// 检查猜测
if (guessGraph.containsKey(v) && guessGraph[v]!!.contains(to)) count++
// 递归
count += dfs(memo, mod, v, to)
}
memo[key] = count
return count
}
}
复杂度分析：
就说这么多，今天单周赛加油💪🏻。