{"id":458,"date":"2017-09-28T22:17:25","date_gmt":"2017-09-29T05:17:25","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=458"},"modified":"2018-04-19T08:41:35","modified_gmt":"2018-04-19T15:41:35","slug":"leetcode-690-employee-importance","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-690-employee-importance\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 690. Employee Importance"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 690. Employee Importance - \u5237\u9898\u627e\u5de5\u4f5c EP75\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/kK9TBtQBmCg?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p><a href=\"https:\/\/leetcode.com\/problems\/employee-importance\/description\/\">https:\/\/leetcode.com\/problems\/employee-importance\/description\/<\/a><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>ou are given a data structure of employee information, which includes the employee&#8217;s\u00a0<b>unique id<\/b>, his\u00a0<b>importance value<\/b>\u00a0and his\u00a0<b>direct<\/b>\u00a0subordinates&#8217; id.<\/p>\n<p>For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is\u00a0<b>not direct<\/b>.<\/p>\n<p>Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all his subordinates.<\/p>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"\">Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1\r\nOutput: 11\r\nExplanation:\r\nEmployee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3. They both have importance value 3. \r\nSo the total importance value of employee 1 is 5 + 3 + 3 = 11.\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<ol>\n<li>One employee has at most one\u00a0<b>direct<\/b>\u00a0leader and may have several subordinates.<\/li>\n<li>The maximum number of employees won&#8217;t exceed 2000.<\/li>\n<\/ol>\n<p><strong>Idea:<\/strong><\/p>\n<p>BFS \/ DFS<\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/690-ep75.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-466\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/690-ep75.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/690-ep75.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/690-ep75-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/690-ep75-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/690-ep75-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p><strong>Time complexity: O(n)<\/strong><\/p>\n<p><strong>Space complexity: O(n)<\/strong><\/p>\n<p><strong>Solution:<\/strong><\/p>\n<p>C++ \/ BFS<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 13 ms\r\nclass Solution {\r\npublic:\r\n    int getImportance(vector&lt;Employee*&gt; employees, int id) {\r\n        unordered_map&lt;int, Employee*&gt; es;        \r\n        for (auto e : employees)\r\n            es.emplace(e-&gt;id, e);                \r\n        \r\n        queue&lt;int&gt; q;\r\n        q.push(id);\r\n        int sum = 0;\r\n        while (!q.empty()) {\r\n            int eid = q.front(); q.pop();\r\n            auto e = es[eid];\r\n            sum += e-&gt;importance;\r\n            for (auto rid : e-&gt;subordinates)\r\n                q.push(rid);\r\n        }\r\n        return sum;\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p>C++ \/ DFS<\/p>\n<pre class=\"lang:c++ decode:true \">class Solution {\r\npublic:\r\n    int getImportance(vector&lt;Employee*&gt; employees, int id) {\r\n        unordered_map&lt;int, Employee*&gt; es;\r\n        for (auto e : employees)\r\n            es.emplace(e-&gt;id, e);\r\n        return dfs(id, es);\r\n    }\r\nprivate:\r\n    int dfs(int id, const unordered_map&lt;int, Employee*&gt;&amp; es) {\r\n        const auto e = es.at(id);\r\n        int sum = e-&gt;importance;\r\n        for (int rid : e-&gt;subordinates)\r\n            sum += dfs(rid, es);\r\n        return sum;\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/leetcode.com\/problems\/employee-importance\/description\/ Problem: ou are given a data structure of employee information, which includes the employee&#8217;s\u00a0unique id, his\u00a0importance value\u00a0and his\u00a0direct\u00a0subordinates&#8217; id. For example, employee 1 is&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[34,33,114],"class_list":["post-458","post","type-post","status-publish","format-standard","hentry","category-searching","tag-bfs","tag-dfs","tag-hash","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/458","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=458"}],"version-history":[{"count":10,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/458\/revisions"}],"predecessor-version":[{"id":2717,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/458\/revisions\/2717"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=458"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=458"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=458"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}