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

⭐️ 本文已收录到 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 更新）：

• #1 链表问题总结

• #2 链表相交 & 成环问题总结

• #3 核算器与逆波兰表达式总结

• #4 高楼丢鸡蛋问题总结

• #5 为什么你学不会递归？谈谈我的经验

• #6 回溯算法解题结构总结

• #7 下次面试遇到二分查找，别再写错了

• #8 什么是二叉树？

• #9 什么是二叉堆 & Top K 问题

• #10 运用前缀和数组处理 “区间和查询” 问题

• #11 面试遇到线段树，已经这么卷了吗？

• #12 运用单调行列处理 “滑动窗口最大值” 问题

• #13 运用单调栈处理 “下一个更大元素” 问题

• #14 运用并查集处理 “朋友圈” 问题

• #15 怎么完成一个优秀的 HashTable 散列表

• #16 简答一波 HashMap 常见面试题

• #17 二叉树高频题型汇总

• #18 下跳棋，极富想象力的同向双指针模仿

• #19 ChatGPT 经过谷歌算法面试，年薪 18.3 万美金

• #20 不难但极其经典的查找模仿

Java & Android 集合结构系列文章: 跳转阅读

LeetCode 上分之旅系列文章：跳转阅读

⭐️ 永远信任美好的工作即将产生，欢迎加入小彭的 Android 沟通社群~