当前位置：首页 > news >正文

Java Leetcode每日一题：DFS

news 来源：原创 2024/9/19 13:59:19

解法1：深度优先搜索（DFS）

深度优先搜索的做法非常直观。根据给定的员工编号找到员工，从该员工开始遍历，对于每个员工，将其重要性加到总和中，然后对该员工的每个直系下属继续遍历，直到所有下属遍历完毕，此时的总和即为给定的员工及其所有下属的重要性之和。

实现方面，由于给定的是员工编号，且每个员工的编号都不相同，因此可以使用哈希表存储每个员工编号和对应的员工，即可通过员工编号得到对应的员工。

package LeetcodeExercise120240826;import java.util.*;public class LeetcodeExercise1 {public static void main(String[] args) {// 需求：你有一个保存员工信息的数据结构，它包含了员工唯一的id，重要度和直系下属的id。// 给定一个员工数组employees，其中：// employees[i].id是第i个员工的ID。// employees[i].importance 是第i个员工的重要度。// employees[i].subordinates是第i名员工的直接下属的ID列表。// 给定一个整数id表示一个员工的ID，返回这个员工和他所有下属的重要度的总和。List<Integer> employee1List = new ArrayList<>();Collections.addAll(employee1List, 2,3);Employee employee1 = new Employee(1, 5, employee1List);List<Integer> employee2List = new ArrayList<>();Employee employee2 = new Employee(2, 3, employee2List);List<Integer> employee3List = new ArrayList<>();Employee employee3 = new Employee(3, 3, employee3List);List<Employee> employees = new ArrayList<>();Collections.addAll(employees, employee1, employee2, employee3);Solution solution = new Solution();int value = solution.getImportance(employees, 1);System.out.println(value);}
}class Solution {HashMap<Integer, Employee> hashMap = new HashMap<>();public int getImportance(List<Employee> employees, int id) {for (Employee employee : employees) {hashMap.put(employee.id, employee);}return dfs(id);}public int dfs(int id) {Employee employee = hashMap.get(id);// 通过员工id得到员工对象int total = employee.importance;for (int subordinate : employee.subordinates) {total += dfs(subordinate);}return total;}
}

Employee类

package LeetcodeExercise120240826;import java.util.List;public class Employee {public int id;public int importance;public List<Integer> subordinates;public Employee(int id, int importance, List<Integer> subordinates) {this.id = id;this.importance = importance;this.subordinates = subordinates;}public int getId() {return id;}public void setId(int id) {this.id = id;}public int getImportance() {return importance;}public void setImportance(int importance) {this.importance = importance;}public List<Integer> getSubordinates() {return subordinates;}public void setSubordinates(List<Integer> subordinates) {this.subordinates = subordinates;}
}