LeetCode 双周赛 99，纯纯送分场！

大家好，我是小彭。

昨夜是 LeetCode 第 99 场双周赛，你参与了吗？这场周赛整体难度很低，第 4 题评论区遍及认为是 1 字头，纯纯手速场。

---

2578. 最小和切割

标题地址

leetcode.cn/problems/sp…

标题描绘

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

• num1和num2直接连起来，得到num各数位的一个摆放。
  • 换句话说，num1和num2中一切数字出现的次数之和等于num中一切数字出现的次数。
• num1和num2能够包含前导 0 。

请你回来num1和num2能够得到的和的最小值。

注意：

• num确保没有前导 0 。
• num1和num2中数位次序能够与num中数位次序不同。

题解（排序 + 贪心）

榜首题相对有点思维。

• 考虑 1：越高位的数字对成果的影响越大，所以优先摆放最小的数字；
• 考虑 2：假如区分两个数字的长度不均，会扩大最终的值；

算法：对数字排序，从小到大别离摆放到两个数字上。

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()

复杂度剖析：

• 时刻复杂度：$O(mlgm)$ 其间 $m$ 是 $num$ 数字的位数，即 $m=lgnum$。排序时刻为 $O(mlgm)$，拆分时刻为 $O(m)$；
• 空间复杂度：$O(m)$ 字符串空间为 $O(m)$，排序递归栈空间为 $O(lgm)$。

---

2579. 核算染色格子数

标题地址

leetcode.cn/problems/co…

标题描绘

有一个无穷大的二维网格图，一开端一切格子都未染色。给你一个正整数n，表明你需求执行以下过程n分钟：

• 榜首分钟，将任一格子染成蓝色。
• 之后的每一分钟，将与蓝色格子相邻的一切未染色格子染成蓝色。

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

题解（找规则）

找规则题。这道题能够用重力加速度类比，重力加速度的 G 是 9.8m/s，而这里的 G 是 4格/s。

• 最开端只要一格，咱们先放到一边独自核算，有 $f(1)=1$；
• 从 (n = 1) 递推到 (n = 2) 时的速度为 4，因而 $f(2)=4+1=5$；
• 从 (n = 2) 递推到 (n = 3) 时的速度为 8，因而 $f(3)=8+f(2)=13$；
• 以此类推，从 (n – 1) 递推到 (n) 时的速度是 $4\ast (n-1)$，即 $f(n)=f(n-1)+4(n-1)$。

明显有：

f(n)={1,n=1f(n−1)+4(n−1)n>1f(n)=\begin{cases} 1, &n=1\\ f(n-1) + 4(n-1) & n>1 \end{cases}f(n)={1,f(n−1)+4(n−1)​n=1n>1​

能够看到， $n>1$ 的分支是一个从 0 开端的等差数列，等差数列求和公式知道吧，整理得：f(n)=1+4∗n∗(n−1)/2=2n2−2n+1f(n) = 1 + 4 * n * (n – 1) / 2 = 2n^2 – 2n + 1f(n)=1+4∗n∗(n−1)/2=2n2−2n+1

class Solution {
    fun coloredCells(n: Int): Long {
        return 2 * n * n - 2 * n + 1
    }
}

复杂度剖析：

• 时刻复杂度：$O(1)$
• 空间复杂度：$O(1)$

---

2580. 核算将堆叠区间兼并成组的计划数

标题地址

leetcode.cn/problems/co…

标题描绘

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

你需求将ranges分成两个组（能够为空），满意：

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

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

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

请你回来将ranges区分成两个组的总计划数。由于答案或许很大，将它对109 + 7取余后回来。

题解（排序 + 贪心）

这道题我榜首时刻想到了这两道题：

• 55.跳跃游戏
• 252：会议室

后来在评论区看到更挨近的原题，好嘛，怪不得形象很深。

• 435. 无堆叠区间

脑际中有闪现过并查集，但明显没有必要。

算法：将区间看成时刻段，先按照开端时刻对区间排序，然后在遍历区间的一起保护已经占用的最晚完毕时刻 preEnd。假如当时区间的开端时刻早于 preEnd，说明区间重合。遍历完数组后求出调集个数 m，求 m 个元素放到 2 个方位的计划数，明显每个方位有 m 中或许，因而成果是 2m2^m2m。

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
    }
}

复杂度剖析：

• 时刻复杂度：$O(nlgn+n+lgm)$ 其间 $n$ 是 $nums$ 数组的长度，$m$ 是无交集区间的调集个数，幂运算时刻为 $O(m)$；
• 空间复杂度：$O(lgn)$ 排序递归栈空间。

---

2581. 核算或许的树根数目

标题地址

leetcode.cn/problems/co…

标题描绘

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。

题解（回忆化递归）

这是换根 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 为根节点的状况中不需求重复核算，达到了剪枝的意图。

编码部分有两个细节：

• 起点需求特别处理，咱们考虑起点是用 u → v 开端的子结构，起点 u 能够选用特别值 $n$。
• 注意空间紧缩，明显运用领接表比临接矩阵更优。备忘录能够运用移位紧缩，Key = u * mod + v，由于标题数据范围是 10000，所以 mod 就取 100000。

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
    }
}

复杂度剖析：

• 时刻复杂度：$O(1)$ 其间 $n$ 是 $edges$ 数组的长度，$m$ 是 $guesses$ 数组的长度。建图占用 $O(n+m+2\ast n)$，在回忆化递归下每条边的子结构最多访问 2 次，即总共有 2n 个子问题，所以查询的复杂度是 $O(2\ast n)$
• 空间复杂度：$O(n+m+2\ast n)$ 建图占用 $O(n+m)$，备忘录最多记载 $n$ 条边的两个方向的子结构，递归栈最大为 $n$。

就说这么多，今日单周赛加油。

本文已收录到 AndroidFamily，技能和职场问题，请重视公众号 [彭旭锐] 提问。