算法练习16：员工的重要性（leetcode 690）

题目

给定一个保存员工信息的数据结构，它包含了员工 唯一的 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 。

员工的构造方法

// 员工节点
function Employee(id, importance, subordinates) {
  this.id = id;
  this.importance = importance;
  this.subordinates = subordinates;
}

// 根据数组创建employees对象
function createEmployees(arr) {
  let employees = []
  for(let i = 0; i < arr.length; i++) {
    employees.push(new Employee(arr[i][0], arr[i][1], arr[i][2]))
  }
  return employees
}

• 考察点：
  我们可以看到员工的构造其实和树的节点差不多，所以我们比较容易想到的是树相关的内容。员工和下属之间关系就是父节点和子节点之间的关系，求员工的所有下属的某和，其实就是求这棵树的遍历和。树的遍历，大致有深度优先和广度优先两种。
  但无论是广度，还是深度优先遍历，都应该使用一个哈希表来存储当前员工的员工信息，避免重复计算。

深度优先算法

采用递归方式，先得出当前员工的权重，然后再分别对其子员工的权重相加，直到没有子员工为止

• 时间复杂度：O(n)
• 空间复杂度：O(n)

var GetImportance = function(employees, id) {
  let map = new　Map()
  // 哈希表存放每个员工对应的员工关系表
  for(let i = 0; i < employees.length; i++) {
    map.set(employees[i].id, employees[i])
  }
  console.log(map)
  // 采用深度优先遍历
  function dfs(id) {
    let employee = map.get(id)
    let sum = employee.importance
    let subEm = employee.subordinates
    if(subEm.length) {
      for(let i = 0; i < subEm.length; i++) {
        sum += dfs(subEm[i])
      }
    }
    
    return sum;
  }
  return dfs(id)
};

广度优先算法

采用队列，初始权重totalIm为0，每次将当前员工id入队，就将队列的第一个员工出队，将出队员工的权重加上，并将其下属都入队，只要队列不为空，就继续这个循环，直到最后得出此员工的所有下属权重

• 时间复杂度：O(n)
• 空间复杂度：O(n)

var GetImportance = function(employees, id) {
  let map = new　Map()
  // 哈希表存放每个员工对应的员工关系表
  for(let i = 0; i < employees.length; i++) {
    map.set(employees[i].id, employees[i])
  }
  let queue = []
  let totalIm = 0
  queue.push(id)
  while(queue.length) {
      let curId = queue.shift()
      let emp = map.get(curId)
      totalIm += emp.importance
      if(emp.subordinates.length) {
          queue = [...queue, ...emp.subordinates]
      }
  }
  return totalIm
};

let arr2 = createEmployees([[1,5,[2,3]],[2,3,[4]],[3,4,[]],[4,1,[]]])

let res = GetImportance(arr2, 1)
console.log(res) // 13