https://leetcode.com/problems/employee-importance/description/
Problem:
ou are given a data structure of employee information, which includes the employee’s unique id, his importance value and his direct subordinates’ id.
For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct.
Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all his subordinates.
Example 1:
1 2 3 4 5 |
Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1 Output: 11 Explanation: Employee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3. They both have importance value 3. So the total importance value of employee 1 is 5 + 3 + 3 = 11. |
Note:
- One employee has at most one direct leader and may have several subordinates.
- The maximum number of employees won’t exceed 2000.
Idea:
BFS / DFS
Time complexity: O(n)
Space complexity: O(n)
Solution:
C++ / BFS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua // Running time: 13 ms class Solution { public: int getImportance(vector<Employee*> employees, int id) { unordered_map<int, Employee*> es; for (auto e : employees) es.emplace(e->id, e); queue<int> q; q.push(id); int sum = 0; while (!q.empty()) { int eid = q.front(); q.pop(); auto e = es[eid]; sum += e->importance; for (auto rid : e->subordinates) q.push(rid); } return sum; } }; |
C++ / DFS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public: int getImportance(vector<Employee*> employees, int id) { unordered_map<int, Employee*> es; for (auto e : employees) es.emplace(e->id, e); return dfs(id, es); } private: int dfs(int id, const unordered_map<int, Employee*>& es) { const auto e = es.at(id); int sum = e->importance; for (int rid : e->subordinates) sum += dfs(rid, es); return sum; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment