⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。
学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭将基于 Java / Kotlin 语言，为你分享常见的数据结构与算法问题，及其解题框架思路。
本文是数据结构与算法系列的第 20 篇文章，完整文章目录请移步到文章末尾~
这道题是 LeetCode 上的 1376. 通知所有员工所需的时间，难度是 Meduium，难度分是 1561。
很不错的搜索模板题，适合精读。这道题初看像最短路问题或拓扑排序问题（如 743.网络延迟时间），其实分析下来没有那么复杂，是一个非加权树形模拟问题。面向初学者，更多递归问题，建议从 LeetCode 学习主页中找到 「二叉树」专题 起手。
标签：DFS、BFS、记忆化搜索
概括问题目标
求通知所有员工紧急消息的时间。
观察问题数据
- 数据 1、员工的 ID 是唯一的，ID 的取值范围是 [0,n) 左闭右开区间；
- 数据 2、总负责人的 ID 是 HeadID，它是消息的起点。
分析问题要件
- 要件 1：在每次操作中，上级员工需要花费 informTime[i] 时间向所有直接下级员工通知紧急消息。
提高抽象程度
-
分析 1：起点：HeadId（总负责人）是消息传递的起点；
-
分析 2：丛属关系：除了总负责人外，每个员工均有一个直接上级，每个员工有零到多个直接下级，这是一个树形结构，同时是稀疏图；
-
分析 3：子问题：当消息传递到员工 i 时，如果员工 i 还有直接下级，那么他需要继续将消息传递给他的下级，这是一个规模更小的相似问题；
-
分析 4：是否为最短路问题 / 拓扑排序问题？由于分析 2 员工的从属关系是一个树形结构，所以消息传递的路径是单向的，唯一的。因此，这不是决策问题，更不会是最短路问题 / 拓扑排序问题，读者可以对比 743. 网络延迟时间 和 207. 课程表 体会其中的区别。
-
分析 5：是否为加权边？在「要件 1」中需要花费 informTime[i] 时间通知下级，这很像是一个加权边？不对，因为 informTime[i] 是向所有下级通知的时间总和，而不是向每个下级通知的时间。
-
总结：这是一个非加权树形模拟问题。
具体化解决手段
如何表示员工的从属关系：
-
手段 1（邻接表）：可以使用「散列表 + 链表」或「数组 + 链表」实现，由于问题的节点数（员工数）是已知的 n，所以后者是简洁的选择；
-
手段 2（邻接矩阵）：结合「分析 2」和「分析 5」，这是一个非加权边问题，且这是一个稀疏图，使用邻接接矩阵没有意义且不是最优选择。
如何解决问题：
-
手段 1（DFS）：从根节点（负责人）开始，使用深度优先搜索向下传递信息（拆分子问题），并根据下级员工的传递时间计算当前员工的传递时间（根据子问题的解计算原问题的解）；
-
手段 2（BFS）：从根节点（负责人）开始，使用广度优先搜索向下传递信息，队列中存储了到达该员工的时间，使用该时间累加得到传递到下级员工的时间；
-
手段 3（记忆化搜索）：自底向上的思路，枚举所有员工，计算从该员工向上寻找到根节点的传递时间，取所有员工传递时间的最大值。由于存在重叠子问题，所以使用记忆化搜索。
是否有优化手段：
- 优化 1（原地数组）：利用输入数据结构，我们使用 manager 数组置 -1 表示该员工问题已经被计算过，使用 informTime 存储该员工问题的解；
题解一（DFS）
class Solution {
fun numOfMinutes(n: Int, headID: Int, manager: IntArray, informTime: IntArray): Int {
if (n == 1) return 0
// 树
val tree = Array(n + 1) { LinkedList<Int>() }
for (i in manager.indices) {
if (manager[i] != -1) tree[manager[i]].add(i)
}
return dfs(tree, informTime, headID)
}
private fun dfs(tree: Array<LinkedList<Int>>, informTime: IntArray, id: Int): Int {
// 终止条件：底层员工 ：）
if (tree[id].isEmpty()) return 0
// 子问题
var maxTime = 0
for (to in tree[id]) {
maxTime = Math.max(maxTime, dfs(tree, informTime, to))
}
return maxTime + informTime[id]
}
}
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n) 递归栈空间 + 树空间
题解二（BFS)
class Solution {
fun numOfMinutes(n: Int, headID: Int, manager: IntArray, informTime: IntArray): Int {
if (n == 1) return 0
// 树
val tree = Array(n + 1) { LinkedList<Int>() }
for (i in manager.indices) {
if (manager[i] == -1) continue
tree[manager[i]].add(i)
}
var ret = 0
// 队列
val queue = LinkedList<IntArray>()
queue.offer(intArrayOf(headID, 0))
// BFS
while (!queue.isEmpty()) {
val node = queue.poll()
val id = node[0]
val time = node[1]
// 更新结果
ret = Math.max(ret, time)
// 子问题
for (to in tree[id]) {
queue.offer(intArrayOf(to, time + informTime[id]))
}
}
return ret
}
}
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n) 队列空间 + 树空间
题解三（记忆化搜索）
class Solution {
fun numOfMinutes(n: Int, headID: Int, manager: IntArray, informTime: IntArray): Int {
if (n == 1) return 0
var ret = 0
// 备忘录
val memo = IntArray(n)
// 枚举员工
for (id in 0 until n) {
ret = Math.max(ret, dfs(id, memo, manager, informTime))
}
return ret
}
private fun dfs(id: Int, memo: IntArray, manager: IntArray, informTime: IntArray): Int {
// 读备忘录
if (0 != memo[id]) return memo[id]
// 终止条件
if (-1 == manager[id]) return informTime[id]
// 寻找父节点
val time = dfs(manager[id], memo, manager, informTime) + informTime[id] /* 题目数据中叶子节点的 informTime[id] 为 0，不需要特殊处理 */
// 存备忘录
memo[id] = time
return time
}
}
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n) 递归栈空间 + 备忘录空间
题解四（记忆化搜索 + 原地数组）
class Solution {
fun numOfMinutes(n: Int, headID: Int, manager: IntArray, informTime: IntArray): Int {
if (n == 1) return 0
var ret = 0
// 枚举员工
for (id in 0 until n) {
ret = Math.max(ret, dfs(id, manager, informTime))
}
return ret
}
private fun dfs(id: Int, manager: IntArray, informTime: IntArray): Int {
// 读备忘录
if (-1 == manager[id]) return informTime[id]
// 寻找父节点
val time = dfs(manager[id], manager, informTime) + informTime[id] /* 题目数据中叶子节点的 informTime[id] 为 0，不需要特殊处理 */
// 存备忘录
manager[id] = -1
informTime[id] = time
return time
}
}
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n) 递归栈空间
推荐阅读
数据结构与算法系列完整目录如下（2023/07/11 更新）：
Java & Android 集合框架系列文章: 跳转阅读
LeetCode 上分之旅系列文章：跳转阅读
⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~
