「690. 员工的重要性」题解

Kim Yang 5/1/2021 LeetCodeAlgorithm

# 690. 员工的重要性 (opens new window)

# 题目描述

给定一个保存员工信息的数据结构，它包含了员工 唯一的 id ，重要度 和 直系下属的 id 。

比如，员工 1 是员工 2 的领导，员工 2 是员工 3 的领导。他们相应的重要度为 15 , 10 , 5 。那么员工 1 的数据结构是 [1, 15, [2]] ，员工 2 的数据结构是 [2, 10, [3]] ，员工 3 的数据结构是 [3, 5, []] 。注意虽然员工 3 也是员工 1 的一个下属，但是由于 并不是直系 下属，因此没有体现在员工 1 的数据结构中。

现在输入一个公司的所有员工信息，以及单个员工 id ，返回这个员工和他所有下属的重要度之和。

示例：

输入：[[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
输出：11
解释：
员工 1 自身的重要度是 5 ，他有两个直系下属 2 和 3 ，而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5 + 3 + 3 = 11 。

提示：

一个员工最多有一个直系领导，但是可以有多个直系下属
员工数量不超过 2000 。

相关信息：

难度：简单
标签：深度优先搜索、广度优先搜索、哈希表

# 题解

这道题目是五一劳动节当天 LeetCode 的打卡题目，只能说 LeetCode 选题太契合节日，哈哈。题目很清晰的描述了一个树形的数据结构，每个员工至多有一个直系领导，可以有零个或若干个直系下属，所以员工之间的领导和下属关系就构成了树形结构。题目要求计算给定员工及其下属的重要性之和，即要求遍历以给定员工为根的子树并计算所有节点值的和。那么这道题目就转化为了树的遍历问题，其解决方案无非是深度优先搜索或者广度优先搜索。

只是示例有些迷惑性，容易导致考虑不周。在示例中，列举的员工 ID 与数组的下标值正好是加 1 的关系，所以误导了我，没有考虑去保存员工 ID 值。示例数据转换出来的数据对象，大致如下：

const employees = [
  {
    id: 1,
    importance: 5,
    subordinates: [2, 3],
  },
  {
    id: 2,
    importance: 3,
    subordinates: [],
  },
  {
    id: 3,
    importance: 3,
    subordinates: [],
  },
];

# 方法一：深度优先搜索

深度优先搜索是我想到的首要解决方法，比较直观，即根据给定员工 ID 找到其下属，要计算给定员工就先计算其下属的重要性，这样一层层的深入下去，直到没有下属为止，便返回其重要性。然后一层层累计，知道算出最初给定的员工的重要性之和。

//源码来自：https://leetcode-cn.com/problems/employee-importance/solution/yuan-gong-de-zhong-yao-xing-by-leetcode-h6xre/
var GetImportance = function (employees, id) {
  const map = new Map();
  for (const employee of employees) {
    map.set(employee.id, employee); //利用 Map 以 id 为键保存每个员工信息，方便后面查找时快速获取员工信息。
  }
  const dfs = (id) => {
    const employee = map.get(id); //获取当前员工信息
    let total = employee.importance; //获取当前员工重要性
    const subordinates = employee.subordinates; //获取当前员工的下属数组
    for (const subId of subordinates) {
      //遍历每个下属，并通过递归累计重要性之和
      total += dfs(subId);
    }
    return total;
  };

  return dfs(id);
};

上边代码是通过一个 map 保存了所有员工信息，这样虽然能做到随时查阅员工信息，但也增加了空间复杂度。其实利用 for 循环加原始数组也可以实现：

//源码来自：https://leetcode-cn.com/problems/employee-importance/solution/di-gui-xiang-jia-by-tricell/
var GetImportance = function (employees, id) {
  var importance = 0;
  var computeImportance = function (id) {
    for (var i = 0; i < employees.length; i++) {
      if (employees[i].id === id) {
        //查找对应id的员工信息
        importance += employees[i].importance; //累计
        if (employees[i].subordinates.length > 0) {
          //有下属
          for (var j = 0; j < employees[i].subordinates.length; j++) {
            computeImportance(employees[i].subordinates[j]); //递归循环
          }
        }
      }
    }
  };
  computeImportance(id);
  return importance;
};

上面代码每次递归都会通过一个循环来查找员工信息，原本我以为这样的时间复杂度会远远大于之前使用 map 实现的版本。但是经过我实际测试，正是这样最基本的 for 循环，不管是在时间复杂度还是空间复杂度上都打败了看似更易理解的 map 实现的代码。真是很神奇。至于为什么会发生这样的情况，可能与 JavaScript 语言中 Map 对象的 get 方法的具体实现有关。不过我之前有看到这样一句结论，for 循环作为 JavaScript 中最早实现的循环，其本身的优化是所有循环语句中最好的。

# 方法二：广度优先搜索

广度优先就是在上面深度优先的基础上加了一个队列来保存应该立即计算的员工 id，前面深度优先找到一个员工 id，立刻递归调用计算。但是广度优先就是找到了一个员工 id，先不着急递归调用，而是将其保存到一个队列中，每次从队头取出一个 id 值，执行递归调用。

//原代码来自：https://leetcode-cn.com/problems/employee-importance/solution/yuan-gong-de-zhong-yao-xing-by-leetcode-h6xre/
var GetImportance = function (employees, id) {
  const map = new Map();
  for (const employee of employees) {
    map.set(employee.id, employee);
  }
  let total = 0;
  const queue = []; //待处理队列
  queue.push(id);
  while (queue.length) {
    const curId = queue.shift();
    const employee = map.get(curId);
    total += employee.importance;
    const subordinates = employee.subordinates;
    for (const subId of subordinates) {
      queue.push(subId); //保存下属 id
    }
  }
  return total;
};

相比于深度优先，广度优先多建立了一个待处理队列，改变了计算顺序，从递归的实现方式变为了迭代。虽然看起来广度优先搜索的空间复杂度应该更高，但其实差不多哒。

以上就是本题的所有题解啦，感谢你能看到这里，如果本文对你有所帮助的话，别忘了给一个 Star 嗷～如果你对题解中的代码有不一样的优化意见，也欢迎你在 issue 中指出～最重要的是不要忘了点点关注嗷（Github (opens new window)、力扣 (opens new window)），以便获取我最新的题解以及文章通知。

# 参考：

# 全部代码

/*
 * @lc app=leetcode.cn id=690 lang=javascript
 *
 * [690] 员工的重要性
 *
 * https://leetcode-cn.com/problems/employee-importance/description/
 *
 * algorithms
 * Easy (64.63%)
 * Likes:    233
 * Dislikes: 0
 * Total Accepted:    54.5K
 * Total Submissions: 84.3K
 * Testcase Example:  '[[1,5,[2,3]],[2,3,[]],[3,3,[]]]\n1'
 *
 * 给定一个保存员工信息的数据结构，它包含了员工 唯一的 id ，重要度 和 直系下属的 id 。
 * 
 * 比如，员工 1 是员工 2 的领导，员工 2 是员工 3 的领导。他们相应的重要度为 15 , 10 , 5 。那么员工 1 的数据结构是 [1,
 * 15, [2]] ，员工 2的 数据结构是 [2, 10, [3]] ，员工 3 的数据结构是 [3, 5, []] 。注意虽然员工 3 也是员工 1
 * 的一个下属，但是由于 并不是直系 下属，因此没有体现在员工 1 的数据结构中。
 * 
 * 现在输入一个公司的所有员工信息，以及单个员工 id ，返回这个员工和他所有下属的重要度之和。
 * 
 * 
 * 
 * 示例：
 * 
 * 
 * 输入：[[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
 * 输出：11
 * 解释：
 * 员工 1 自身的重要度是 5 ，他有两个直系下属 2 和 3 ，而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5 + 3 + 3 =
 * 11 。
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 一个员工最多有一个 直系 领导，但是可以有多个 直系 下属
 * 员工数量不超过 2000 。
 * 
 * 
 */

// @lc code=start
/**
 * Definition for Employee.
 * function Employee(id, importance, subordinates) {
 *     this.id = id;
 *     this.importance = importance;
 *     this.subordinates = subordinates;
 * }
 */

/**
 * @param {Employee[]} employees
 * @param {number} id
 * @return {number}
 */
 var GetImportance = function(employees, id) {
    const map = new Map();
    for (const employee of employees) {
        map.set(employee.id, employee);//利用 Map 以 id 为键保存每个员工信息，方便后面查找时快速获取员工信息。
    }
    const dfs = (id) => {
        const employee = map.get(id);//获取当前员工信息
        let total = employee.importance;//获取当前员工重要性
        const subordinates = employee.subordinates;//获取当前员工的下属数组
        for (const subId of subordinates) {
          //遍历每个下属，并通过递归累计重要性之和
            total += dfs(subId);
        }
        return total;
        
    }

    return dfs(id);
};
// @lc code=end

var GetImportance = function (employees, id) {
    var importance = 0;
    var computeImportance = function (id) {
      for (var i = 0; i < employees.length; i++) {
        if (employees[i].id === id) {//查找对应id的员工信息
          importance += employees[i].importance;//累计
          if (employees[i].subordinates.length > 0) {//有下属
            for (var j = 0; j < employees[i].subordinates.length; j++) {
              computeImportance(employees[i].subordinates[j])//递归循环
            }
          }
        }
      }
    }
    computeImportance(id)
    return importance;
  };

//原代码来自：https://leetcode-cn.com/problems/employee-importance/solution/yuan-gong-de-zhong-yao-xing-by-leetcode-h6xre/
var GetImportance = function(employees, id) {
    const map = new Map();
    for (const employee of employees) {
        map.set(employee.id, employee);
    }
    let total = 0;
    const queue = [];//待处理队列
    queue.push(id);
    while (queue.length) {
        const curId = queue.shift();
        const employee = map.get(curId);
        total += employee.importance;
        const subordinates = employee.subordinates;
        for (const subId of subordinates) {
            queue.push(subId);//保存下属 id
        }
    }
    return total;
};

「70. 爬楼梯」题解「1779. 找到最近的有相同 X 或 Y 坐标的点」题解

Kim's Blog

Choose mode