“This is the 28th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

690. The importance of employees

The title

Given a data structure that holds employee information, it contains the employee’s unique ID, importance, and direct subordinate ids.

For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. Their corresponding importance is 15, 10, 5. Therefore, the data structure of employee 1 is [1, 15, [2]], that of employee 2 is [2, 10, [3]], and that of employee 3 is [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, it is not reflected in employee 1’s data structure because it is not a direct subordinate.

Now enter the information of all employees in a company, along with a single employee ID, and return the sum of the importance of that employee and all of his subordinates.

The sample

Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []], 1 Output: 11 Explanation: The importance of Employee 1 is 5, he has two direct subordinates 2 and 3, and the importance of 2 and 3 is 3. So the total importance of employee 1 is 5 + 3 + 3 = 11.Copy the code

prompt

  • An employee can have at most one direct leader, but can have more than one direct subordinate
  • The number of employees does not exceed 2000.

Answer key

BFS

  • Enumerates employee arrays to store employee data in the hash table mapMapMap
  • In mapMapMap, employee ididid is used as keyKeyKey, employee importance and employee subordinate are used as Valuevaluevalue
  • Create a search queue listlistList, starting with startstartStart, to start breadth-first search from the employee
  • Then the employee ididid is fetched from the search queue listlistList, and the employee information is queried in the hash table mapmapMap based on the obtained IDIdid
  • For each traversed employee, add its importance to the sum and query all subordinates of that employee, pushing the subordinates ididid into the queue listListList
  • Until the search queue listlistList length is 0; The end of the search
  • Returns the result

Edit the code as follows:

var GetImportance = function (employees, id) {
  const len = employees.length;
  let map = {};
  for (let i = 0; i < len; i++) {
    const {id,importance,subordinates} = employees[i];
    map[id] = [importance, subordinates];
  }
  let list = [id];
  let result = 0;
  while (list.length) {
    const key = list.pop();
    const[n, next] = map[key]; result += n; list.push(... (next || [])); }return result;
};
Copy the code

DFS

As with BFS, employee data is stored in the hash table MapMapMap. Search for subordinates of the current employee starting from the entry ID. If there are subordinates, search for subordinates of the current employee based on the subordinate ID until the employee has no subordinates, and return to the employee’s superior. Until the search for all subordinates of ID is completed

var GetImportance = function (employees, id) {
  const len = employees.length;
  let map = {};
  for (let i = 0; i < len; i++) {
    const { id, importance, subordinates } = employees[i];
    map[id] = [importance, subordinates];
  }
  let result = 0;
  dfs(id);
  return result;
  function dfs(k) {
    if (map[k] === undefined) return;
    const [n, next] = map[k];
    result += n;
    for (let i = 0; i < next.length; i++) { dfs(next[i]); }}};Copy the code