关于android:LeetCode-双周赛-99纯纯送分场

7次阅读

共计 4931 个字符，预计需要花费 13 分钟才能阅读完成。

本文已收录到 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 中数位程序不同。

第一题绝对有点思维。

思考 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 = lg\,num$。排序工夫为 $O(mlgm)$，拆分工夫为 $O(m)$；
空间复杂度：$O(m)$ 字符串空间为 $O(m)$，排序递归栈空间为 $O(lgm)$。

https://leetcode.cn/problems/count-total-number-of-colored-ce…

有一个无穷大的二维网格图，一开始所有格子都未染色。给你一个正整数 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 *(n – 1)$，即 $f(n) = f(n – 1) + 4(n – 1)$。

显然有：

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

复杂度剖析：

工夫复杂度：$O(1)$
空间复杂度：$O(1)$

https://leetcode.cn/problems/count-ways-to-group-overlapping-…

给你一个二维整数数组 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 中可能，因而后果是 $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
    }
}

复杂度剖析：

工夫复杂度：$O(nlgn + n + lgm)$ 其中 $n$ 是 $nums$ 数组的长度，$m$ 是无交加区间的汇合个数，幂运算工夫为 $O(m)$；
空间复杂度：$O(lgn)$ 排序递归栈空间。

https://leetcode.cn/problems/count-number-of-possible-root-no…

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*n)$，在记忆化递归下每条边的子结构最多拜访 2 次，即总共有 2n 个子问题，所以查问的复杂度是 $O(2*n)$
空间复杂度：$O(n + m + 2*n)$ 建图占用 $O(n + m)$，备忘录最多记录 $n$ 条边的两个方向的子结构，递归栈最大为 $n$。

就说这么多，明天单周赛加油💪🏻。

正文完

android

发表至： android

2023-03-05

0

关于android:Android-11-正式发布-开发者们的舞台已就绪

关于android:使用Data-Ability读取系统设置项

关于android:Android-开发技术周报-Issue292

关于android:从零学习SDK5SDK文档的学习和参考

关于数据库:数据库系统概论王珊第九章关系查询与关系优化习题

关于android:LeetCode-双周赛-99纯纯送分场

2578. 最小和宰割

题目地址

题目形容

题解（排序 + 贪婪）

2579. 统计染色格子数

题目地址

题目形容

题解（找法则）

2580. 统计将重叠区间合并成组的计划数

题目地址

题目形容

题解（排序 + 贪婪）

2581. 统计可能的树根数目

题目地址

题目形容

题解（记忆化递归）

站内搜索