文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
Employee Importance
2. Solution
- Non-recurrent
/*
// Employee info
class Employee {
public:
// It's the unique ID of each node.
// unique id of this employee
int id;
// the importance value of this employee
int importance;
// the id of direct subordinates
vector<int> subordinates;
};
*/
class Solution {
public:
int getImportance(vector<Employee*> employees, int id) {
int value = 0;
queue<int> ids;
map<int, Employee*> hashId;
for(int i = 0; i < employees.size(); i++) {
hashId[employees[i]->id] = employees[i];
}
ids.push(id);
while(!ids.empty()) {
Employee* current = hashId[ids.front()];
ids.pop();
value += current->importance;
if(!current->subordinates.empty()) {
for(int i = 0; i < current->subordinates.size(); i++) {
ids.push(current->subordinates[i]);
}
}
}
return value;
}
};
- Recurrent
/*
// Employee info
class Employee {
public:
// It's the unique ID of each node.
// unique id of this employee
int id;
// the importance value of this employee
int importance;
// the id of direct subordinates
vector<int> subordinates;
};
*/
class Solution {
public:
int getImportance(vector<Employee*> employees, int id) {
int value = 0;
map<int, Employee*> hashId;
for(int i = 0; i < employees.size(); i++) {
hashId[employees[i]->id] = employees[i];
}
addImportance(hashId, id, value);
return value;
}
private:
void addImportance(map<int, Employee*>& hashId, int id, int& value) {
Employee* current = hashId[id];
value += current->importance;
if(!current->subordinates.empty()) {
for(int i = 0; i < current->subordinates.size(); i++) {
addImportance(hashId, current->subordinates[i], value);
}
}
}
};
