This is the seventh day of my participation in the More text Challenge. For details, see more text Challenge

The Importance of Employees (Question number 690)

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, and 5. So 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 of a company, as well as the individual employee ID, and return the sum of the importance of that employee and all of his subordinates.

Example:

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

Tip:

  • An employee can have at most one direct leader, but can have multiple direct subordinates
  • The number of employees does not exceed 2000

link

Leetcode-cn.com/problems/em…

explain

This question is actually relatively simple, belong to the kind of problem that you know the answer at a glance, there are many kinds of solutions.

The core is to search multiple subordinates of the leader for several times. Recursion and iteration can be used. With Map, subordinates can be found faster, but it will take up extra space.

Your own answer (Map+ iteration)

First look at the code 👇 :

var GetImportance = function (employees, id) {
  var obj = new Map()
      res = 0
      root = [id]
  for (const item of employees) {
    obj.set(item.id, item)
  }
  while (root.length) {
    var item = obj.get(root.pop())
    res += item.importance
    root = root.concat(item.subordinates)
  }
  return res
};
Copy the code

First, make a for loop, and then use ID as key to transform all employees into a Map. Then, start from the given ID, and continue to aggregate the subordinates of the current element into root, so as to continuously find subordinates.

The execution time of this solution is fast, but the memory consumption is large, but there is no way, after all, a new Map is created to store employee data, which is a typical space-for-time solution.

Your own answer (pure iteration)

The code is simpler than the previous solution 👇 :

var GetImportance = function (employees, id) {
  var res = 0
      root = [id]
  while (root.length) {
    var activeId = root.pop()
        item = employees.find(item => item.id === activeId)
    res += item.importance
    root = root.concat(item.subordinates)
  }
  return res
};
Copy the code

Remove the memory Map, the process of using array every time find methods to find operations, so dependent on, the bottom 30% execution time directly, but the memory footprint directly by more than 90%, because in addition to the root and res, did not add any variables, if you need to use time in space, this can be a kind of practice, and from less the amount of code.

Your own answer (Map+ recursion)

Similar to the core logic of iteration, except that iteration is replaced by recursion, i.e., depth-first search 👇 :

var GetImportance = function (employees, id) {
  var obj = new Map()
      res = 0
  for (const item of employees) {
    obj.set(item.id, item)
  }
  function dfs(id) {
    const { importance,  subordinates} = obj.get(id)
    var total = importance
    for (const itemId of subordinates) {
      total += dfs(itemId)
    }
    return total
  }
  return dfs(id)
};
Copy the code

Not much to say, the effect is similar to that of Map+ iteration, the running time is similar, both are fast, but both use a lot of memory.

Your own answer (pure recursion)

The logic of pure recursion is similar to that of pure iteration, using the array find method 👇 :

var GetImportance = function (employees, id) { function dfs(id) { const { importance, subordinates} = employees.find(item => item.id === id) var total = importance for (const itemId of subordinates) { total  += dfs(itemId) } return total } return dfs(id) };Copy the code

What surprises people is that this method is actually the most compromise method, the speed is not the fastest, the memory is not the most, but are about 70% 👇 :

You can use this method if you need to compromise.

A better answer

There is no




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ