数据结构与算法 #20 不难但极其经典的搜索模拟

站长

2024年04月12日 14:35 · 阅读数 4

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭将基于 Java / Kotlin 语言，为你分享常见的数据结构与算法问题，及其解题框架思路。

本文是数据结构与算法系列的第 20 篇文章，完整文章目录请移步到文章末尾~

这道题是 LeetCode 上的 1376. 通知所有员工所需的时间，难度是 Meduium，难度分是 1561。

很不错的搜索模板题，适合精读。这道题初看像最短路问题或拓扑排序问题（如 743.网络延迟时间），其实分析下来没有那么复杂，是一个非加权树形模拟问题。面向初学者，更多递归问题，建议从 LeetCode 学习主页中找到「二叉树」专题起手。

标签：DFS、BFS、记忆化搜索

数据结构与算法 #20 不难但极其经典的搜索模拟

概括问题目标

求通知所有员工紧急消息的时间。

观察问题数据

数据 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) 递归栈空间

⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~

数据结构与算法 #20 不难但极其经典的搜索模拟