1.深度优先搜索
class Solution {
public:
int getImportance(vector<Employee*> employees, int id)
{
//注意employees容器里面存放的员工信息不是按照id大小顺序排列,即下标为0的地方对应的id不一定为1
for (Employee* e : employees)
{
if (e->id == id)
{
if (e->subordinates.empty())//如果当前员工没有下属,说明到达累加重要性的结束条件,那么返回当前员工自身的重要性即可
return e->importance;
//遍历当前员工所有附属的员工,计算他们及他们附属员工的重要性,然后累加到total计数器上
for (int subId : e->subordinates)
e->importance += getImportance(employees, subId);//累加起点值是算上当前员工自身的重要性
return e->importance;
}
}
return 0;
}
};
class Solution {
public:
unordered_map<int, Employee*> mp;
int getImportance(vector<Employee*> employees, int id)
{
//先把每个员工对应id,映射到map容器中,方便通过id快速查找到某个员工
for (auto& employer : employees)
{
mp[employer->id] = employer;
}
return dfs(id);
}
int dfs(int id)
{
Employee* em = mp[id];//获取当前id对应的员工
if (em->subordinates.size() == 0)
return em->importance;
for (auto& subId : em->subordinates)
em->importance += dfs(subId);
return em->importance;
}
};
2.广度优先搜索
class Solution {
public:
//unordered_map<int, Employee*> mp;
int getImportance(vector<Employee*> employees, int id)
{
queue<Employee*> q;
//可以看出,通过循环查找,很耗费时间
for (auto& em : employees)
{
if (em->id == id)
{
q.push(em);//先把对应员工id为传入id的放入队列中
break;
}
}
int total = 0;//累加器
while (!q.empty())
{
Employee* employer = q.front();
q.pop();
total += employer->importance;
//把当前员工直属的附属员工放入队列中
for (auto& subId : employer->subordinates)
{
for (auto& em : employees)
{
if (em->id == subId)
{
q.push(em);
break;
}
}
}
}
return total;
}
};
class Solution {
public:
int getImportance(vector<Employee *> employees, int id) {
unordered_map<int, Employee *> mp;
for (auto &employee : employees) {
mp[employee->id] = employee;
}
int total = 0;
queue<int> que;
que.push(id);
while (!que.empty()) {
int curId = que.front();
que.pop();
Employee *employee = mp[curId];
total += employee->importance;
for (int subId : employee->subordinates) {
que.push(subId);
}
}
return total;
}
};