本文涉及知識點

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對應的員工信息。

代碼

核心代碼

class Employee {public:int id;int importance;vector<int> subordinates;};class Solution {public:int getImportance(vector<Employee*> employees, int id) {vector<Employee*> vIDToPtr(2000 + 1);for ( auto& ptr : employees) {vIDToPtr[ptr->id] = ptr;}queue<int > 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;vector<int> subordinates;};class Solution {public:int getImportance(vector<Employee*> employees, int id) {vector<Employee*> vIDToPtr(2000 + 1);for ( auto& ptr : employees) {vIDToPtr[ptr->id] = ptr;}queue<int > 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;}};vector<Employee> employees;vector<Employee*> ToPtr(vector<Employee>& employees) {vector<Employee*> 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 C++17
或者 操作系統：win10 開發環境： VS2022 C++17
如無特殊說明，本算法用**C++**實現。