本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 发问。
大家好，我是小彭。
上周末有单双周赛，双周赛咱们讲过了，单周赛那天早上有事没加入，前面做了虚构比赛，而后整个人就不好了。前 3 题非常简单，但第 4 题有点货色啊，差点就放弃了。最初，被折磨了一个下午和一个大夜总算把第 4 题做进去了，除了新学的 Tarjon 离线算法，这道题还波及到树上差分、前缀和、DFS、图论等基础知识，几度被折磨得想要放弃。这种感觉，仿佛和当年在 LeetCode 上做前 10 题的时候差不多哈哈。
加油吧，没有什么教训是随随便便可能取得的，默默致力，愿君共勉。
周赛纲要
2643. 一最多的行（Easy）
简略模拟题，无需解释。
- 模仿：$O(nm)$
2644. 找出可整除性得分最大的整数（Easy）
简略模拟题，和 Q1 简直雷同，这场周赛出的不好。
- 模仿：$O(nm)$
2645. 结构无效字符串的起码插入数（Medium）
中等模拟题，不难。
- 模仿：$O(n)$
2646. 最小化旅行的价格总和（Hard）
这道题的考点十分多，难度也十分高。先把握暴力 DFS 的解法，再剖析暴力解法中反复计算的环节，最初推出树上差分和离线 Tarjan 算法。这道题十分非常复杂，
- 递归中递和归的思维，再了解一下：为什么你学不会递归？谈谈我的教训
- 并查集问题，不要错过：如何应用并查集解决朋友圈问题？
- 差分数组问题，这个点还没有写，同系列的前缀和数组能够参考：应用前缀和数组解决“区间和查问”问题
- 题解 1：暴力 DFS $O(nm)$
- 题解 2：树上差分 + Tarjan 离线 LCA + DFS $O(n + \alpha m)$
2643. 一最多的行（Easy）
题目地址
https://leetcode.cn/problems/row-with-maximum-ones/
题目形容
给你一个大小为 m x n 的二进制矩阵 mat，请你找出蕴含最多 1 的行的下标（从 0 开始）以及这一行中 1 的数目。
如果有多行蕴含最多的 1，只须要抉择 行下标最小 的那一行。
返回一个由行下标和该行中 1 的数量组成的数组。
题解（模仿）
简略模拟题。
class Solution {fun rowAndMaximumOnes(mat: Array<IntArray>): IntArray {
var maxIndex = 0
var maxCount = 0
for (i in 0 until mat.size) {
var count = 0
for (j in 0 until mat[0].size) {count += mat[i][j]
}
if (count > maxCount) {
maxCount = count
maxIndex = i
}
}
return intArrayOf(maxIndex, maxCount)
}
}复杂度剖析：
- 工夫复杂度：$O(nm)$
- 空间复杂度：$O(1)$
2644. 找出可整除性得分最大的整数（Easy）
题目地址
https://leetcode.cn/problems/find-the-maximum-divisibility-sc…
题目形容
给你两个下标从 0 开始的整数数组 nums 和 divisors。
divisors[i] 的 可整除性得分 等于满足 nums[j] 能被 divisors[i] 整除的下标 j 的数量。
返回 可整除性得分 最大的整数 divisors[i]。如果有多个整数具备最大得分，则返回数值最小的一个。
题解（模仿）
简略模拟题。
class Solution {fun maxDivScore(nums: IntArray, divisors: IntArray): Int {
var maxDivisor = 0
var maxCount = -1
for (divisor in divisors) {
var count = 0
for (num in nums) {if (num % divisor == 0) count++
}
if (count > maxCount || count == maxCount && divisor < maxDivisor) {
maxDivisor = divisor
maxCount = count
}
}
return maxDivisor
}
}复杂度剖析：
- 工夫复杂度：$O(nm)$
- 空间复杂度：$O(1)$
2645. 结构无效字符串的起码插入数（Medium）
题目地址
https://leetcode.cn/problems/minimum-additions-to-make-valid-…
题目形容
给你一个字符串 word，你能够向其中任何地位插入 “a”、”b” 或 “c” 任意次，返回使 word 无效 须要插入的起码字母数。
如果字符串能够由 “abc” 串联屡次失去，则认为该字符串 无效 。
题解（模仿）
保护以后状态与指标状态，当两个状态存在偏差时，插入偏差的字符数。
class Solution {fun addMinimum(word: String): Int {
val n = word.length
var targetStatus = 0
var index = 0
var ret = 0
while (index < n) {
// 以后状态
val curStatus = word[index] - 'a'
// 插入
ret += (curStatus + 3 - targetStatus) % 3
// 指标状态
targetStatus = (curStatus + 1) % 3
index++
}
ret += when (targetStatus) {
0 -> 0
1 -> 2
2 -> 1
else -> 0
}
return ret
}
}复杂度剖析：
- 工夫复杂度：$O(n)$
- 空间复杂度：$O(1)$
2646. 最小化旅行的价格总和（Hard）
题目地址
https://leetcode.cn/problems/minimize-the-total-price-of-the-…
题目形容
现有一棵无向、无根的树，树中有 n 个节点，按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ai, bi] 示意树中节点 ai 和 bi 之间存在一条边。
每个节点都关联一个价格。给你一个整数数组 price，其中 price[i] 是第 i 个节点的价格。
给定门路的 价格总和 是该门路上所有节点的价格之和。
另给你一个二维整数数组 trips，其中 trips[i] = [starti, endi] 示意您从节点 starti 开始第 i 次旅行，并通过任何你喜爱的门路返回节点 endi。
在执行第一次旅行之前，你能够抉择一些 非相邻节点 并将价格减半。
返回执行所有旅行的最小价格总和。
问题剖析
剖析 1：题目的数据结构是树而不是图，所以节点之间的最短路是惟一的，不须要应用最短路算法。从节点 start 到节点 end 的最优门路是 start 到最近公共先人（LCA）+ 最近公共先人（LCA）到 end；
剖析 2：题目能够抉择将一些节点的价格减半，显然价格越高的节点越应该减半，或者拜访次数越多的节点越应该减半。所以咱们能够先对每个 trips[i] 跑一次 DFS，并统计每个节点的拜访次数 cnts[i]，将每个节点的价格更新为 prices[i] * cnts[i]
剖析 3：相似于 337. 打家劫舍 III，如果咱们抉择将节点 x 减半（偷窃），那么与 x 相邻的节点便不能减半（偷窃）：
- 如果 prices[x] 减半，那么 x 的最近子节点不能减半；
- 如果 prices[x] 不变，那么 x 的最近子节点能够减半，也能够不减半，抉择两种状况的更优解。
题解一（暴力 DFS）
依据问题剖析，咱们的算法是：
- 1、先枚举每种旅途，统计每个节点的拜访次数（总共跑 m 次 DFS）；
- 2、更新每个节点的价格权重为 prices[i] * cnts[i]；
- 3、任意抉择一个节点为根节点跑一次 DFS，在每一层递归中通过子问题的解得出原问题的解，每个子问题的解有「减半」和「不减半」两种后果；
- 4、最终，依据根节点的问题求出最终解。
class Solution {fun minimumTotalPrice(n: Int, edges: Array<IntArray>, price: IntArray, trips: Array<IntArray>): Int {
// 建树
val graph = Array(n) {LinkedList<Int>() }
for (edge in edges) {graph[edge[0]].add(edge[1])
graph[edge[1]].add(edge[0])
}
// 统计节点拜访次数
val cnts = IntArray(n)
for (trip in trips) {cntDfs(graph, cnts, trip[0], trip[1], -1)
}
// 更新价格
for (i in 0 until n) {price[i] *= cnts[i]
}
// DFS（打家劫舍）val ret = priceDfs(graph, price, 0, -1)
return Math.min(ret[0], ret[1])
}
// return：是否找到指标节点
private fun cntDfs(graph: Array<LinkedList<Int>>, cnts: IntArray, cur: Int, target: Int, parent: Int): Boolean {
// 终止条件（指标节点）if (cur == target) {cnts[cur]++
return true
}
// 枚举子节点（树的个性：每个方向最多只会拜访一次，不须要应用 visit 数组）for (to in graph[cur]) {
// 防止回环
if (to == parent) continue
// 未找到
if (!cntDfs(graph, cnts, to, target, cur)) continue
// 找到指标门路，不须要再查看其余方向
cnts[cur]++
return true
}
return false
}
// return：以 cur 为根节点的子树的最大价格 <cur 不变, cur 减半 >
private fun priceDfs(graph: Array<LinkedList<Int>>, price: IntArray, cur: Int, parent: Int): IntArray {
val ret = intArrayOf(price[cur], // x 不变
price[cur] / 2 // x 减半
)
// 枚举子节点（树的个性：每个方向最多只会拜访一次，不须要应用 visit 数组）for (to in graph[cur]) {
// 防止回环
if (to == parent) continue
// 子树后果
val childRet = priceDfs(graph, price, to, cur)
ret[0] += Math.min(childRet[0], childRet[1])
ret[1] += childRet[0]
}
return ret
}
}复杂度剖析：
- 工夫复杂度：$O(nm)$ 其中 m 为 trips 数组的长度，每轮 DFS 的工夫是 $O(n)$，计数工夫为 $O(nm)$，打家劫舍 DFS 的工夫为 $O(n)$；
- 空间复杂度：$O(n + m)$ 树空间 + DFS 递归栈空间，递归深度最大为 n。
题解一的瓶颈在于 cntDfs 中的 m 次 DFS 搜寻，如何优化？
准备常识：差分数组
在 cntDfs 中的每一次 DFS 搜寻中，咱们须要将 [start, end] 门路上的节点拜访次数 +1，这正好相似于在数组上将 [start, end] 区间的地位 + 1，合乎“差分数组”的利用场景。咱们能够在树上做差分，再通过一次 DFS 搜寻中计算节点的拜访次数。
例如在示例 1 中，咱们的门路是 (0, 3)，那么门路相当于 [0] + [1,3]，针对这两条门路的差分为：
- [0]：diff[0]++，diff[father[0]] —，即 diff[1] —
- [1, 3]：diff[3]++，diff[father[1]] —，即 diff[2]—
那怎么计算拜访次数呢？跟差分数组一样，对差分数组计算前缀和就能够取得节点的拜访次数，咱们在归的过程中累加差分值，例如 节点 1 的拜访次数就是 +1 + 1 – 1 等于 1 次。
题解二（树上差分 + Tarjan 离线 LCA + DFS）
思考到旅行门路列表是固定的，咱们能够应用 Tarjan 离线算法，事后求出所有旅行门路端点的最近公共先人。反之，如果旅行门路列表是动静的，那么离线算法就力不从心了，须要应用复杂度更高的在线算法。
参考资料：
- LCA 最近公共先人（Tarjan 离线算法）
- 图论 · LCA 最近公共先人
在题解一中，咱们须要破费 m 次 DFS 搜寻来解决 m 个 LCA 问题，Tarjan 算法的外围思路是在一次 DFS 搜寻的过程中解决所有 LCA 查问问题：
- 1、任选一个点为根节点，从根节点开始。
- 2、「递」的过程（合成子问题）：遍历该点 u 所有子节点 v，并标记这些子节点 v 已被拜访过，若是 v 还有子节点，返回 2 持续「递」；
- 3、「归」的过程：寻找与 u 有查问关系的点 k。如果 k 节点曾经被拜访过，那么 u 和 k 的最近公共先人就是以后 u 和 k 所在的分组根节点；
- 4、 节点 u 的问题完结后，将 节点 u 合并到父节点的汇合上。
细节阐明：Tarjan 算法递的过程是寻找查问关系，当门路的两个端点都拜访过，那么这两个端点必然处在同一个分组中，而它们的分组根节点正好就是最近公共组件；
细节阐明：为什么分组根节点正好就是最近公共组件？因为归是依照 DFS 的搜寻程序回归的；
细节阐明：如何合并 v 到 u 的汇合上？这是并查集的操作，咱们定义 parent[x] 示意 x 节点的所处的分组，初始状态 parent[x] = x；
细节阐明：如何查问与 u 有查问关系的点 k？预处理筹备映射表；
细节阐明：为了辨别阶段状态，咱们定义 color[x] 示意节点 x 的状态，0 示意未拜访、1 示意处于递归栈中，2 示意完结。
更多细节，看代码吧。
class Solution {fun minimumTotalPrice(n: Int, edges: Array<IntArray>, price: IntArray, trips: Array<IntArray>): Int {
// 建树
val graph = Array(n) {LinkedList<Int>() }
for (edge in edges) {graph[edge[0]].add(edge[1])
graph[edge[1]].add(edge[0])
}
// 查问关系
val search = Array(n) {LinkedList<Int>() }
for (trip in trips) {search[trip[0]].add(trip[1])
// 当门路两端雷同时，防止反复
if (trip[0] != trip[1]) search[trip[1]].add(trip[0])
}
val unionFind = UnionFind(n, graph, search)
unionFind.tarjan(0, -1/* 无父节点 */)
// DFS（打家劫舍）val ret = priceDfs(graph, price, unionFind.diff, 0, -1)
return Math.min(ret[0], ret[1])
}
// 并查集
private class UnionFind(val n: Int, val graph: Array<LinkedList<Int>>, val search: Array<LinkedList<Int>>) {
// 并查集数据结构
private val parent = IntArray(n) {it}
// 树上的父节点
private val father = IntArray(n)
// Tarjan 状态
private val colors = IntArray(n) // 示意未拜访、1 示意处于递归栈中，2 示意完结
// 树上差分
val diff = IntArray(n)
private fun find(x: Int): Int {
// 门路压缩
if (x != parent[x]) parent[x] = find(parent[x])
return parent[x]
}
// 这道题的合并不能应用按秩合并，必须将子节点 x 合并到 y 的汇合中
private fun merge(x: Int, y: Int) {
// 按秩合并
val rootX = find(x)
val rootY = find(y)
if (rootX != rootY) parent[rootX] = rootY
}
fun tarjan(u: Int, fa: Int) {
// 记录父节点
father[u] = fa
// 标记已拜访
colors[u] = 1
// 递的过程：遍历 u 的所有子节点 v
for (v in graph[u]) {if (0 != colors[v]) continue // 拜访过
// 持续递的过程
tarjan(v, u)
}
// 枚举查问关系
for (k in search[u]) {if (k == u || colors[k] == 2) {
// 找到 u 和 k 的查问关系，更新树上差分
val lca = find(k)
diff[u]++
diff[lca]--
diff[k]++
val lcaParent = father[lca]
if (lcaParent >= 0) diff[lcaParent]--
}
}
// 完结
colors[u] = 2
if(fa != -1) merge(u, fa) // 将子节点 u 合并到 fa 的汇合中
}
}
// return：以 cur 为根节点的子树的最大价格 <cur 不变, cur 减半 >
private fun priceDfs(graph: Array<LinkedList<Int>>, price: IntArray, diff: IntArray, cur: Int, parent: Int): IntArray {val ret = intArrayOf(0, 0, diff[cur])
// 枚举子节点（树的个性：每个方向最多只会拜访一次，不须要应用 visit 数组）for (to in graph[cur]) {
// 防止回环
if (to == parent) continue
// 子树后果
val childRet = priceDfs(graph, price, diff, to, cur)
ret[0] += Math.min(childRet[0], childRet[1])
ret[1] += childRet[0]
ret[2] += childRet[2] // 累加前缀和
}
ret[0] += price[cur] * ret[2]
ret[1] += price[cur] * ret[2] / 2
return ret
}
}复杂度剖析：
- 工夫复杂度：$O(n + \alpha m)$ 其中 m 为 trips 数组的长度，$\alpha$ 是并查集的反阿克曼函数，近似于线性函数；
- 空间复杂度：$O(n + m)$ 树空间 + DFS 递归栈空间，递归深度最大为 n。