大家好碘勉，我是小彭垄潮。
昨晚是 LeetCode 第 99 場雙周賽虫蝶，你參加了嗎章咧？這場周賽整體難度很低，第 4 題評論區(qū)普遍認為是 1 字頭能真，純純手速場赁严。
2578. 最小和分割
題目地址
https://leetcode.cn/problems/split-with-minimum-sum/
題目描述
給你一個正整數(shù) num 扰柠，請你將它分割成兩個非負整數(shù) num1 和 num2 ，滿足：
-
num1和num2直接連起來疼约，得到num各數(shù)位的一個排列卤档。- 換句話說，
num1和num2中所有數(shù)字出現(xiàn)的次數(shù)之和等于num中所有數(shù)字出現(xiàn)的次數(shù)程剥。
- 換句話說，
-
num1和num2可以包含前導(dǎo) 0 劝枣。
請你返回 num1 和 num2 可以得到的和的 最小 值。
注意：
-
num保證沒有前導(dǎo) 0 织鲸。 -
num1和num2中數(shù)位順序可以與num中數(shù)位順序不同舔腾。
題解（排序 + 貪心）
第一題相對有點思維。
- 思考 1：越高位的數(shù)字對結(jié)果的影響越大搂擦，所以優(yōu)先排列最小的數(shù)字稳诚；
- 思考 2：如果劃分兩個數(shù)字的長度不均，會放大最終的值瀑踢；
算法：對數(shù)字排序扳还，從小到大分別排列到兩個數(shù)字上。
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()
復(fù)雜度分析：
- 時間復(fù)雜度：
其中
是
數(shù)字的位數(shù)丘损，即
普办。排序時間為
徘钥；
- 空間復(fù)雜度：
呈础。
2579. 統(tǒng)計染色格子數(shù)
題目地址
https://leetcode.cn/problems/count-total-number-of-colored-cells/
題目描述
有一個無窮大的二維網(wǎng)格圖舆驶，一開始所有格子都未染色。給你一個正整數(shù) n 而钞，表示你需要執(zhí)行以下步驟 n 分鐘：
- 第一分鐘沙廉，將 任一 格子染成藍色。
- 之后的每一分鐘臼节，將與藍色格子相鄰的 所有 未染色格子染成藍色撬陵。
下圖分別是 1、2网缝、3 分鐘后的網(wǎng)格圖巨税。
題解（找規(guī)律）
找規(guī)律題。這道題可以用重力加速度類比粉臊，重力加速度的 G 是 9.8m/s草添，而這里的 G 是 4格/s。
- 最開始只有一格扼仲，我們先放到一邊單獨計算远寸，有
抄淑；
- 從 (n = 1) 遞推到 (n = 2) 時的速度為 4，因此
驰后；
- 從 (n = 2) 遞推到 (n = 3) 時的速度為 8肆资，因此
；
- 以此類推倡怎，從 (n - 1) 遞推到 (n) 時的速度是
迅耘，即
。
顯然有：
可以看到监署， 的分支是一個從 0 開始的等差數(shù)列颤专，等差數(shù)列求和公式知道吧，整理得：
class Solution {
fun coloredCells(n: Int): Long {
return 2 * n * n - 2 * n + 1
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
- 空間復(fù)雜度：
2580. 統(tǒng)計將重疊區(qū)間合并成組的方案數(shù)
題目地址
https://leetcode.cn/problems/count-ways-to-group-overlapping-ranges/
題目描述
給你一個二維整數(shù)數(shù)組 ranges 钠乏，其中 ranges[i] = [starti, endi] 表示 starti 到 endi 之間（包括二者）的所有整數(shù)都包含在第 i 個區(qū)間中栖秕。
你需要將 ranges 分成 兩個 組（可以為空），滿足：
- 每個區(qū)間只屬于一個組晓避。
- 兩個有 交集 的區(qū)間必須在 同一個 組內(nèi)簇捍。
如果兩個區(qū)間有至少 一個 公共整數(shù)，那么這兩個區(qū)間是 有交集 的俏拱。
- 比方說暑塑，區(qū)間
[1, 3]和[2, 5]有交集，因為2和3在兩個區(qū)間中都被包含锅必。
請你返回將 ranges 劃分成兩個組的 總方案數(shù) 事格。由于答案可能很大，將它對 109 + 7 取余 后返回搞隐。
題解（排序 + 貪心）
這道題我第一時間想到了這兩道題：
后來在評論區(qū)看到更接近的原題驹愚，好嘛，怪不得印象很深劣纲。
腦海中有閃現(xiàn)過并查集逢捺，但顯然沒有必要。
算法：將區(qū)間看成時間段癞季，先按照開始時間對區(qū)間排序劫瞳，然后在遍歷區(qū)間的同時維護已經(jīng)占用的最晚結(jié)束時間 preEnd。如果當(dāng)前區(qū)間的開始時間早于 preEnd绷柒，說明區(qū)間重合柠新。遍歷完數(shù)組后求出集合個數(shù) m，求 m 個元素放到 2 個位置的方案數(shù)辉巡，顯然每個位置有 m 中可能，因此結(jié)果是 蕊退。
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
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
其中
是
數(shù)組的長度郊楣，
- 空間復(fù)雜度：
排序遞歸椌辉椋空間钥组。
2581. 統(tǒng)計可能的樹根數(shù)目
題目地址
https://leetcode.cn/problems/count-number-of-possible-root-nodes/
題目描述
Alice 有一棵 n 個節(jié)點的樹，節(jié)點編號為 0 到 n - 1 今瀑。樹用一個長度為 n - 1 的二維整數(shù)數(shù)組 edges 表示程梦，其中 edges[i] = [ai, bi] ，表示樹中節(jié)點 ai 和 bi 之間有一條邊橘荠。
Alice 想要 Bob 找到這棵樹的根屿附。她允許 Bob 對這棵樹進行若干次 猜測 。每一次猜測哥童，Bob 做如下事情：
- 選擇兩個 不相等 的整數(shù)
u和v挺份，且樹中必須存在邊[u, v]。 - Bob 猜測樹中
u是v的 父節(jié)點 贮懈。
Bob 的猜測用二維整數(shù)數(shù)組 guesses 表示匀泊，其中 guesses[j] = [uj, vj] 表示 Bob 猜 uj 是 vj 的父節(jié)點。
Alice 非常懶朵你，她不想逐個回答 Bob 的猜測各聘，只告訴 Bob 這些猜測里面 至少 有 k 個猜測的結(jié)果為 true 。
給你二維整數(shù)數(shù)組 edges 抡医，Bob 的所有猜測和整數(shù) k 躲因，請你返回可能成為樹根的 節(jié)點數(shù)目 。如果沒有這樣的樹魂拦，則返回 0毛仪。
題解（記憶化遞歸）
這是換根 DP 問題，這道題相對簡單了芯勘，只要掌握圖的基本結(jié)構(gòu)和遞歸的基本思想就能實現(xiàn)箱靴。
首先是建圖的部分，顯然 edges 是無向圖荷愕，guesses 是有向圖衡怀。我們的算法基本框架應(yīng)該是：枚舉每個根節(jié)點，計算 guesses 中猜測正確的邊的個數(shù)安疗，如果猜測次數(shù) ≥ k 則記錄 1 次結(jié)果∨籽睿現(xiàn)在的問題是如果優(yōu)化查詢的時間復(fù)雜度，我們觀察依次從 0 到 n - 1 修改根節(jié)點會發(fā)生什么荐类？
我們發(fā)現(xiàn)： 每次調(diào)整中只有條邊的結(jié)構(gòu)關(guān)系變化怖现。比如從根 0 調(diào)整到根 1 時，只有 0 → 1 被修改為 1 → 0，而其他邊都沒有變化屈嗤，存在重疊子結(jié)構(gòu) / 重疊子問題潘拨。
定義 表示在 u → v 的子結(jié)構(gòu)中猜測正確的邊數(shù)，例如在示例 2 中饶号，f(1, 2) = 1铁追。顯然在已知 f(1,2) 的結(jié)果后，在以節(jié)點 1 為根節(jié)點的情況中不需要重復(fù)計算茫船，達到了剪枝的目的琅束。
編碼部分有兩個細節(jié)：
- 起點需要特殊處理，我們考慮起點是用 u → v 開始的子結(jié)構(gòu)算谈，起點 u 可以采用特殊值
- 注意空間壓縮，顯然使用領(lǐng)接表比臨接矩陣更優(yōu)濒生。備忘錄可以使用移位壓縮埋泵，Key = u * mod + v，由于題目數(shù)據(jù)范圍是 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]!!) {
// 過濾指向父節(jié)點的邊
if (to == u) continue
// 檢查猜測
if (guessGraph.containsKey(v) && guessGraph[v]!!.contains(to)) count++
// 遞歸
count += dfs(memo, mod, v, to)
}
memo[key] = count
return count
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
其中
數(shù)組的長度，
數(shù)組的長度觉义。建圖占用
雁社，在記憶化遞歸下每條邊的子結(jié)構(gòu)最多訪問 2 次，即總共有 2n 個子問題晒骇，所以查詢的復(fù)雜度是
- 空間復(fù)雜度：
霉撵，備忘錄最多記錄
就說這么多徒坡，今天單周賽加油????。
