XYZ 是一家拥有 CEO Bill 和员工等级制度的公司。员工可以有一份向他们报告的其他员工的列表,这些员工自己也可以有报告,等等。至少拥有一份报告的员工称为经理。 请实现 closestCommonManager 方法以找到距离两名员工最近的经理(即离 CEO 最远的经理)。您可能会假设所有员工最终都会向 CEO 汇报。
示例数据: 首席执行官比尔有 3 名员工向他汇报:{Dom、Samir、Michael}
Dom 有三个报告 { Peter, Bob, Porter}
Samir 没有报告 {}Michael 没有报告{}
Peter 有 2 个报告{Milton, Nina} Bob 没有报告{}
Porter 没有报告 {} Milton 没有报告{}
Nina 没有报告{}
调用示例: closestCommonManager(Milton, Nina) = 彼得
closestCommonManager(Nina, Porter) = Dom
closestCommonManager(Nina, Samir) = 比尔
closestCommonManager(Peter, Nina) = Peter
现在,为了解决这个问题,我采用了这种方法 - 但我还没有找到解决方案。 我尝试使用简单的 DFS 算法,但无法完成解决方案。
public static Employee closestCommonManager(Employee ceo, Employee firstEmployee, Employee secondEmployee)
{
var visited = new HashSet<Employee>();
bool firstFound = false, secondFound = false;
Stack<Employee> stack = new Stack<Employee>(); // DFS
stack.Push(ceo);
while (stack.Count != 0)
{
Employee current = stack.Pop();
IList<Employee> employeeList = current.getReports();
if (firstEmployee.getId() == current.getId())
{
firstFound = true;
}
else if (secondEmployee.getId() == current.getId())
{
secondFound = true;
}
if (firstFound && secondFound)
return current;
// Should i return previous one? how do i keep track of the
// node which i found first in hierarchy ???
Console.WriteLine(current.getName());
foreach (var employee in employeeList)
{
if (visited.Add(employee))
{
stack.Push(employee);
}
}
}
return null;
}
最佳答案
这看起来像是对 http://en.wikipedia.org/wiki/Lowest_common_ancestor 的请求.聪明的算法通常会对树进行一些预处理。一种简单的方法是标记树中的每个元素与根的距离。然后找到两个节点最近的共同祖先,首先从较低的节点向上移动一个指针,使它们都处于相同的深度,然后将两个指针一起向上移动,直到指针接触。如果您不进行预处理,则可以同时从两个节点向上移动,将您看到的所有节点添加到一个集合中,并检查何时将节点添加到遇到的已经存在的节点集合中。无论哪种情况,当您第一次遇到来自双方的节点时,该节点都是最低的共同祖先。
关于c# - 返回层次结构中的老板——尝试应用深度优先搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25072591/