广度优先遍历----690. 员工的重要性

清疚 2022-11-19 01:14 143阅读 0赞

/** * 给定一个保存员工信息的数据结构，它包含了员工 唯一的 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, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1 * 输出：11 * 解释： * 员工 1 自身的重要度是 5 ，他有两个直系下属 2 和 3 ，而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5 + 3 + 3 = 11 。 * @param employees * @param id * @return */
        public static int getImportance(List<Employee> employees, int id) { 
    
            Queue<Employee> queue = new LinkedList<>();
            int weight = 0;
            for (Employee employee : employees) { 
                if(employee.id == id){ 
                    queue.offer(employee);
                }
            }
            while (!queue.isEmpty()){ 
                Employee poll = queue.poll();
                weight = weight + poll.importance;
                if(!poll.subordinates.isEmpty()){ 
    
                    for (Integer subordinate : poll.subordinates) { 
                        for (Employee employee : employees) { 
                            if(employee.id == subordinate){ 
                                queue.offer(employee);
                            }
                        }
                    }
                }
            }
        return weight;
        }
        public class Employee { 
    
        public int id;
        public int importance;
        public List<Integer> subordinates;
    
    }
    
        public static void main(String[] args) { 
    
            //[[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
            Employee employee1 = new Employee();
            employee1.id = 1;
            employee1.importance = 5;
            employee1.subordinates = Arrays.asList(2,3);
    
            Employee employee2 = new Employee();
            employee2.id = 2;
            employee2.importance = 3;
            employee2.subordinates = Arrays.asList();
    
            Employee employee3 = new Employee();
            employee3.id = 3;
            employee3.importance = 3;
            employee3.subordinates = Arrays.asList();
            List<Employee> employees = Arrays.asList(employee1, employee2, employee3);
            System.out.println(getImportance(employees, 1));
        }