leetcode
leetcode 601 ~ 650
员工的重要性

员工的重要性

难度:

标签:

题目描述

代码结果

运行时间: 103 ms, 内存: 17.2 MB


/*
 * 题目思路:
 * 1. 定义一个 Employee 类,包含 id、重要度和下属 id 列表。
 * 2. 使用 HashMap 存储所有员工信息,以便快速查找员工。
 * 3. 使用 Stream 计算指定员工及其下属的重要度之和。
 */
 
import java.util.*;
import java.util.stream.*;
 
class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
}
 
public class Solution {
    private Map<Integer, Employee> employeeMap = new HashMap<>();
 
    public int getImportance(List<Employee> employees, int id) {
        employees.forEach(e -> employeeMap.put(e.id, e));
        return getTotalImportance(id);
    }
 
    private int getTotalImportance(int id) {
        Employee employee = employeeMap.get(id);
        return employee.importance + employee.subordinates.stream()
                .mapToInt(this::getTotalImportance)
                .sum();
    }
}

解释

方法:

本题解使用深度优先搜索(DFS)的方法,用哈希表 mp 存储员工 ID 到员工对象的映射,然后从给定的员工 ID 开始递归计算所有下属员工的重要度之和。在DFS过程中,对于每个员工,将其自身的重要度与所有直系下属的重要度相加,直到下属员工为空,然后回溯并返回总重要度。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在题解中,你提到使用哈希表来存储员工ID到员工对象的映射,这种方法在处理非连续或非整数ID时是否有特殊考虑或限制?
在Python中,哈希表(即字典)的键可以是任何不可变类型,包括整数、浮点数、字符串或元组,只要这些类型是不可变的且能够被哈希化。因此,无论ID是连续还是非连续,或是整数与非整数(如字符串),使用哈希表来存储员工ID到员工对象的映射都没有特殊的考虑或限制。这使得哈希表成为存储具有不同类型键值的灵活数据结构。
🦆
题解使用了深度优先搜索(DFS)进行数据遍历,这种方式在处理特别大的员工层级结构时是否会遇到栈溢出问题?如果会,如何避免?
是的,深度优先搜索(DFS)使用递归实现时,可能会在处理非常大的员工层级结构或非常深的递归深度时遭遇栈溢出问题,因为每一层递归调用都会消耗一定的栈空间。为避免这种情况,可以考虑使用迭代的方式实现DFS,借助显式栈来控制递归过程,或者改用广度优先搜索(BFS)来避免深层递归。另外,增加系统的栈大小也是一个可行的解决方案,但这并不总是最优的选择。
🦆
题解中的递归函数`dfs`在计算总重要度时直接累加了自身和所有直系下属的重要度,这在有循环引用(即员工间存在环形结构)的情况下是否会导致无限递归?
是的,如果员工的下属结构中存在环形引用,即一个员工直接或间接地成为自己的下属,则递归函数`dfs`会因为无限递归而导致栈溢出错误。为防止这种情况发生,可以在`dfs`函数中添加一个集合来跟踪已访问的员工ID。在每次递归调用前检查当前员工ID是否已在集合中,如果是,则跳过该员工,这样可以防止重复访问并避免环形递归。
🦆
在哈希表`mp`的使用中,如果输入的员工ID不存在于员工列表中,题解中的代码将如何处理?
题解中的代码并没有显式处理输入的员工ID不存在于员工列表中的情形。在这种情况下,尝试访问`mp[id]`将引发一个`KeyError`,因为该ID不在字典的键中。为了更健壮的错误处理,可以在访问哈希表之前加入检查,如果ID不存在于哈希表中,可以返回0或抛出一个更具体的异常,或者返回一个合理的错误信息,以更优雅地处理这种错误情况。

相关问题

嵌套列表加权和

嵌套列表加权和