深度优先搜索的解题详细介绍, 点击
给定一个保存员工信息的数据结构, 它包含了员工唯一的 id, 重要度 和 直系下属的 id.
比如, 员工 1 是员工 2 的领导, 员工 2 是员工 3 的领导. 他们相应的重要度为 15, 10, 5. 那么员工 1 的数据结构是[1, 15, [2]], 员工 2 的数据结构是[2, 10, [3]], 员工 3 的数据结构是[3, 5, []]. 注意虽然员工 3 也是员工 1 的一个下属, 但是由于并不是直系下属, 因此没有体现在员工 1 的数据结构中.
现在输入一个公司的所有员工信息, 以及单个员工 id, 返回这个员工和他所有下属的重要度之和.
示例 1:
输入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
输出: 11
解释:
员工 1 自身的重要度是 5, 他有两个直系下属 2 和 3, 而且 2 和 3 的重要度均为 3. 因此员工 1 的总重要度是 5 + 3 + 3 = 11.
注意:
一个员工最多有一个直系领导, 但是可以有多个直系下属
员工数量不超过 2000.
一直搜索它的下属节点并叠加 importance 值即可.
- /*
- // Employee info
- class Employee {
- // It's the unique id of each node;
- // unique id of this employee
- public int id;
- // the importance value of this employee
- public int importance;
- // the id of direct subordinates
- public List<Integer> subordinates;
- };
- */
- class Solution {
- public int getImportance(List<Employee> employees, int id) {
- Employee person = null;
- for(Employee e:employees){
- if(e.id==id){
- person = e;
- break;
- }
- }
- List<Integer> sub_list = person.subordinates;
- int sum = 0;
- for(int i=0;i<sub_list.size();i++){
- sum += getImportance(employees,sub_list.get(i));
- }
- return person.importance + sum;
- }
- }
来源: http://www.bubuko.com/infodetail-3157341.html