从零开始算法之路 ---- 690. 员工的重要性

不念不忘少年蓝@ 2023-10-11 12:58 5阅读 0赞

**前言**:小白入门题解，算法大佬可以直接跳过此博客（大佬轻喷哈）  
**题源:** 力扣(LeetCode）[https://leetcode-cn.com/problems/employee-importance/][https_leetcode-cn.com_problems_employee-importance]  
**题目描述:**  
给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度 和 直系下属的id。

比如，员工1是员工2的领导，员工2是员工3的领导。他们相应的重要度为15, 10, 5。那么员工1的数据结构是\[1, 15, \[2\]\]，员工2的数据结构是\[2, 10, \[3\]\]，员工3的数据结构是\[3, 5, \[\]\]。注意虽然员工3也是员工1的一个下属，但是由于并不是直系下属，因此没有体现在员工1的数据结构中。

现在输入一个公司的所有员工信息，以及单个员工id，返回这个员工和他所有下属的重要度之和。  
**思路：** 首先找到要计算重要性员工 的id，id 进辅助队列并记录其重要性，然后该员工下属的 id 进队列，该员工的 id 出队列，之后再找到下属的 id 并记录重要性，重复上述步棸，直至无下属。  
**C++ 版代码：**

class Solution { 
    public:
        int getImportance(vector<Employee*> employees, int id) { 
        int sum = 0;            // 记录重要性变量
    	queue<int> number;      // 辅助队列
    	number.push(id);        // 员工 id 进队列
    	// 先找到需要求重要性员工的 id
    	for(int i = 0; i < employees.size(); i++){ 
    		if(id == employees[i]->id){ 
    
                //while(!number.empty()){ 
                //cout<<employees[i]->id<<" 的重要性为:"<<employees[i]->importance<<endl;
                sum += employees[i]->importance;    // 员工的重要性累加
                for(int j = 0; j < employees[i]->subordinates.size(); j++)
                    number.push(employees[i]->subordinates[j]);  // 员工 i 下属的 id 进队列
                if(!number.empty()){ 
                    number.pop();    // 如果队列不为空，队头（员工id）出队列
                }
                if(!number.empty()){ 
                    // 如果队列不为空，队头
                    id = number.front();
                    i = -1;  // 每一个员工号都从头开始查找
                }
    
    
    		}
    	}
        return sum;
        }
    };

**Java 版代码：**

class Solution { 
        public int getImportance(List<Employee> employees, int id) { 
            int sum = 0;          // 存储所求员工重要性变量
    		LinkedList<Integer> number = new LinkedList<Integer>();  // LinkedList 子类实现了 Queue（队列）接口，辅助队列变量
    		number.offer(id);     // 将目标 id 添加到队列结尾，这里用的是队列操作，不是链表
    		for(int i = 0; i < employees.size(); i++) { 
    			if(id == employees.get(i).id) { 
    				System.out.println(employees.get(i).importance);
    				sum += employees.get(i).importance;
    			
    				// 目标 id 下属的 id 进队列
    				if(employees.get(i).subordinates != null) { 
    					for(int j = 0; j < employees.get(i).subordinates.size(); j++) { 
    						number.offer(employees.get(i).subordinates.get(j));
    					}
    				}
    				
    				if(!number.isEmpty()) { 
    					number.poll();      // 找到并删除队头
    				}
    				if(!number.isEmpty()) { 
    					id = number.peek();  // 找到并但不删除队头
    					i = -1;              // 每一个 id 都从第一个员工寻找
    				}
    			}
    		}
    	      
    		return sum;    
        }
    }

[https_leetcode-cn.com_problems_employee-importance]: https://leetcode-cn.com/problems/employee-importance/