当前位置：首页 > news >正文

【C++BFS】690. 员工的重要性

news 2026/5/12 16:55:46

本文涉及知识点

C++BFS算法

LeetCode690. 员工的重要性

你有一个保存员工信息的数据结构，它包含了员工唯一的 id ，重要度和直系下属的 id 。
给定一个员工数组 employees，其中：
employees[i].id 是第 i 个员工的 ID。
employees[i].importance 是第 i 个员工的重要度。
employees[i].subordinates 是第 i 名员工的直接下属的 ID 列表。
给定一个整数 id 表示一个员工的 ID，返回这个员工和他所有下属的重要度的总和。
示例 1：

输入：employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1
输出：11
解释：
员工 1 自身的重要度是 5 ，他有两个直系下属 2 和 3 ，而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5 + 3 + 3 = 11 。

示例 2：

输入：employees = [[1,2,[5]],[5,-3,[]]], id = 5
输出：-3
解释：员工 5 的重要度为 -3 并且没有直接下属。
因此，员工 5 的总重要度为 -3。

提示：
1 <= employees.length <= 2000
1 <= employees[i].id <= 2000
所有的 employees[i].id 互不相同。
-100 <= employees[i].importance <= 100
一名员工最多有一名直接领导，并可能有多名下属。
employees[i].subordinates 中的 ID 都有效。

C++BFS

根据生活常识，我们假定没有任何两位员工互为领导。如果互为领导，本题无法计算。
我们令本人是自己的0层下属，直接下属是1层下属，直接下属的直接下属是二级下属…
leves[i]记录id 的i层下属。
BFS的状态表示：cur。
BFS的后续状态：cur的直接下属。
BFS的初始状态：leves[0] = {id};
BFS的返回值，所有的cur重要性之和。
BFS的重复处理：根据生活常识，无需处理重复。
预处理：向量vIDtoPtr记录各id对应的员工信息。

代码

核心代码

classEmployee{public:intid;intimportance;vector<int>subordinates;};classSolution{public:intgetImportance(vector<Employee*>employees,intid){vector<Employee*>vIDToPtr(2000+1);for(auto&ptr:employees){vIDToPtr[ptr->id]=ptr;}queue<int>que;que.emplace(id);intret=0;while(que.size()){intcur=que.front();que.pop();autoptr=vIDToPtr[cur];ret+=ptr->importance;for(constauto&next:ptr->subordinates){que.emplace(next);}}returnret;}};

单元测试

namespaceLeetCode690{//LeetCode690. 员工的重要性TEST_CLASS(LeetCode690){public:classEmployee{public:intid;intimportance;vector<int>subordinates;};classSolution{public:intgetImportance(vector<Employee*>employees,intid){vector<Employee*>vIDToPtr(2000+1);for(auto&ptr:employees){vIDToPtr[ptr->id]=ptr;}queue<int>que;que.emplace(id);intret=0;while(que.size()){intcur=que.front();que.pop();autoptr=vIDToPtr[cur];ret+=ptr->importance;for(constauto&next:ptr->subordinates){que.emplace(next);}}returnret;}};vector<Employee>employees;vector<Employee*>ToPtr(vector<Employee>&employees){vector<Employee*>ret;for(auto&e:employees){ret.emplace_back(&e);}returnret;}intid;TEST_METHOD(TestMethod1){employees={{1,5,{2,3}},{2,3,{}},{3,3,{}}},id=1;autores=Solution().getImportance(ToPtr(employees),id);AssertEx(11,res);}TEST_METHOD(TestMethod2){employees={{1,2,{5}},{5,-3,{}}},id=5;autores=Solution().getImportance(ToPtr(employees),id);AssertEx(-3,res);}};}

扩展阅读

我想对大家说的话
亲士工具箱：支持AutoCad2013及以上
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
活到老，学到老。明朝中后期，大约50%的进士能当上堂官(副部及更高)；能当上堂官的举人只有十余人。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。