LN : leetcode 690 Employee Importance
lc 690 Employee Importance
You are given a data structure of employee information, which includes the employee's unique id, his importance value and his direct subordinates' id.
For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct.
Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all his subordinates.
Example 1:
Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
Output: 11
Note:
- One employee has at most one direct leader and may have several
subordinates. - The maximum number of employees won't exceed 2000.
BFS Accepted##
很经典的可以用BFS算法快速解决的问题。唯一需要注意的是push进队列的应该为id-1,而不是id,因为它是vector的下标。
/*
// Employee info
class Employee {
public:
// It's the unique ID of each node.
// unique id of this employee
int id;
// the importance value of this employee
int importance;
// the id of direct subordinates
vector<int> subordinates;
};
*/
class Solution {
public:
int getImportance(vector<Employee*> employees, int id) {
if (!employees.size()) return 0;
int total_value = 0;
queue<int> q;
q.push(id-1);
while (!q.empty()) {
auto employee = employees[q.front()];
q.pop();
total_value += employee->importance;
for (auto i : employee->subordinates) q.push(i-1);
}
return total_value;
}
};
最新文章
- 终端mysql Operation not permitted错误解决方案
- 一步步学习javascript基础篇(7):BOM和DOM
- Linux学习笔记(17) Shell编程之基础
- 如何查看编译安装的lnmp环境各自的配置参数
- 基于Enterprise Library的Winform开发框架实现支持国产达梦数据库的扩展操作
- a标签有小手状和无小手状css属性
- JSP基本语法小结
- css体验优化之图片容器设置宽高比
- 人人都是 DBA(XI)I/O 信息收集脚本汇编
- hdu 4568 Hunter(spfa预处理 + 状压dp)
- iOS已发布应用中对异常信息捕获和处理
- swift3.0 coredata 的使用
- DEDE更改版权信息
- Linux随笔
- 每个程序员都应该学习使用Python或Ruby
- 在IOS应用中从竖屏模式强制转换为横屏模式
- 微服务架构的基础框架选择:Spring Cloud还是Dubbo?
- 莫烦theano学习自修第四天【激励函数】
- linux下执行sh脚本,提示Command not found解决办法
- Git学习笔记05-撤销修改