leetcode 690. 员工的重要性
2023-03-14 22:51:21 时间
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;
}
};
- 上面的递归解法有一个明显的硬伤计算每一次都需要循环取查找某个对应于当前传入id的员工,查找的过程很费时间,那么有没有什么办法,可以快速查找对应id的员工呢?
- map映射
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;
}
};
- 与上面递归同样,每一次循环查找都很费时间和内存,因此需要用map映射
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;
}
};
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的