做视频链接网站,十大免费ppt网站软件,网络app推广是什么工作,简约网页设计本文涉及知识点
CBFS算法
LeetCode690. 员工的重要性
你有一个保存员工信息的数据结构#xff0c;它包含了员工唯一的 id #xff0c;重要度和直系下属的 id 。 给定一个员工数组 employees#xff0c;其中#xff1a; employees[i].id 是第 i 个员工的 ID。 employees[…本文涉及知识点
CBFS算法
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 都有效。
CBFS
根据生活常识我们假定没有任何两位员工互为领导。如果互为领导本题无法计算。 我们令 本人是自己的0层下属直接下属是1层下属直接下属的直接下属是二级下属… leves[i]记录id 的i层下属。 BFS的状态表示cur。 BFS的后续状态cur的直接下属。 BFS的初始状态leves[0] {id}; BFS的返回值所有的cur重要性之和。 BFS的重复处理根据生活常识无需处理重复。 预处理向量vIDtoPtr记录 各id对应的员工信息。
代码
核心代码
class Employee {public:int id;int importance;vectorint subordinates;};class Solution {public:int getImportance(vectorEmployee* employees, int id) {vectorEmployee* vIDToPtr(2000 1);for ( auto ptr : employees) {vIDToPtr[ptr-id] ptr;}queueint que;que.emplace(id);int ret 0;while (que.size()) {int cur que.front();que.pop();auto ptr vIDToPtr[cur];ret ptr-importance;for (const auto next : ptr-subordinates) {que.emplace(next);}}return ret;}};单元测试
namespace LeetCode690
{//LeetCode690. 员工的重要性TEST_CLASS(LeetCode690){public:class Employee {public:int id;int importance;vectorint subordinates;};class Solution {public:int getImportance(vectorEmployee* employees, int id) {vectorEmployee* vIDToPtr(2000 1);for ( auto ptr : employees) {vIDToPtr[ptr-id] ptr;}queueint que;que.emplace(id);int ret 0;while (que.size()) {int cur que.front();que.pop();auto ptr vIDToPtr[cur];ret ptr-importance;for (const auto next : ptr-subordinates) {que.emplace(next);}}return ret;}};vectorEmployee employees;vectorEmployee* ToPtr(vectorEmployee employees) {vectorEmployee* ret;for (auto e : employees) {ret.emplace_back(e);}return ret;}int id;TEST_METHOD(TestMethod1){employees { {1,5,{2,3}},{2,3,{}},{3,3,{}} }, id 1;auto res Solution().getImportance(ToPtr(employees), id);AssertEx(11, res);}TEST_METHOD(TestMethod2){employees { {1,2,{5}},{5,-3,{}} }, id 5;auto res Solution().getImportance(ToPtr(employees), id);AssertEx(-3, res);}};
}如果有不明白的请加文末QQ群。
扩展阅读
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关推荐
我想对大家说的话《喜缺全书算法册》以原理、正确性证明、总结为主。按类别查阅鄙人的算法文章请点击《算法与数据汇总》。有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
