求两道google onsite题目的详细解答~跪谢！！

跪求大神，给一些比较详细的解答。
第一道题是：
求party中最大level的和
给一个Employee class
class Employee {
       int level;
       List<Employee> directReports; // 直接的汇报关系
}
该方法要求得到所有能参加party的人的level之和的最大值。参加party的唯一限制条件是如果邀请了一个人的direct report，则这个人不能参加party（同理， 邀请了一个人，那么这个人的direct report也不能参加party）。我卡在了如果这个关系图里面是有环的话，我不知道怎么解决？

第二题就是经典的扫地机器人，我是完全不会做：
要求全部扫完房间，一开始不知道机器人在哪里，不知道一共有多少个cell，比企鹅也不知道机器人一开始朝向哪里（这个可以假设，从任何一个方向开始，感觉dfs结果都是一样的）

Given a robot cleaner in a room modeled as a grid. Each cell in the grid can be empty or blocked. The robot cleaner can move forward, turn left or turn right. When it tries to move into a blocked cell, its bumper sensor detects the obstacle and it stays on the current cell.

. 鍥磋?鎴戜滑@1point 3 acres

The control API:

.鐣欏?璁哄潧-涓

不知道说的对不对，

首先我们用connected component labelling 的方法把相互有关联的人都放到同一个组里，同时记录每个人被report的次数，当然你挨个search也行。

因为有level，我们可以做个假设：同级之间不互相report，如果你发现互相report或者还能向下级report的话就比较麻烦了，你要在每个级更新的时候找环，基本和暴力枚举没啥区别了。

下面我们设计一个DP记录：
从级别最低（如果同级可以互相report还能向下级report的话就用report次数最少）的人开始，记录3个东西，1.该人被邀请的话最大得分 2.该人不被邀请的最大得分 3.当前层最大得分的时候（所有人）不能被邀请的次数（这可能是个vector哦,如果能向下report，gg，基本等于记录所有情况吧。。。）
下一层把 被report数+1 的人挨个加进来，更新所有人状态，祈求不要出现得分一样的情况，否则你要把多个相同最高分的情况下每个人不能被邀请的次数都maintain住，根据此人不能被邀请次数是否为0,更新一次总和。

其实我感觉只是弱一点的暴力枚举。



补充内容 (2018-4-13 09:38):
感觉从级别最高的人开始往下dp比较好，记录下一层每个人不能被邀请的次数，恩

前两天写的扫地机器人，求大神斧正

1. '''
   
2. ## this API is already defined for you
   
3. class Robot(object):
   
4.     def clean():
   
5.         ## clean the current location.
   
6.     def turnleft(k):
   
7.         ## turn left k*90 degrees.
   
8.     def turnright(k):
   
9.         ## turn right k*90 degrees.
   
10.     def move():
    
11.         ## move forward for 1 position and return True, return False if that’s not possible.
    
12. '''
    
13. 
    
14. class Solution(object):
    
15.     def __init__(self):
    
16.         self.direction = 0
    
17. 
    
18.     def cleanRoom(self, robot):
    
19.         ## robot: Robot
    
20.         self.dfs(robot, set(), None, (0, 0))
    
21. 
    
22.     def dfs(self, robot, visited, prev, curr):
    
23.         robot.clean()
    
24.         directions_tried = set()
    
25.         while len(directions_tried) < 4:   ## try all 4 directions
    
26.             while self.direction in directions_tried:
    
27.                 robot.turnleft(1)   ## everytime you turn, update self.direction
    
28.                 self.direction = (self.direction + 1) % 4
    
29. 
    
30.             directions_tried.add(self.direction)
    
31.             if self.direction == 0:
    
32.                 new_pos = (curr[0] + 1, curr[1])
    
33.             elif self.direction == 1:
    
34.                 new_pos = (curr[0], curr[1] + 1)
    
35.             elif self.direction == 2:
    
36.                 new_pos = (curr[0] - 1, curr[1])
    
37.             else:
    
38.                 new_pos = (curr[0], curr[1] - 1)
    
39. 
    
40.             if new_pos not in visited:
    
41.                 visited.add(new_pos)
    
42.                 if robot.move():
    
43.                     self.dfs(robot, visited, curr, new_pos)
    
44. 
    
45.         if prev is not None:
    
46.             tmp_diff = (prev[0] - curr[0], prev[1] - curr[1])
    
47.             if tmp_diff == (1, 0):
    
48.                 while self.direction != 2:
    
49.                     robot.turnleft(1)
    
50.                     self.direction = (self.direction + 1) % 4
    
51. 
    
52.                 robot.move()
    
53.             elif tmp_diff == (0, 1):
    
54.                 while self.direction != 3:
    
55.                     robot.turnleft(1)
    
56.                     self.direction = (self.direction + 1) % 4
    
57. 
    
58.                 robot.move()
    
59.             elif tmp_diff == (-1, 0):
    
60.                 while self.direction != 0:
    
61.                     robot.turnleft(1)
    
62.                     self.direction = (self.direction + 1) % 4
    
63. 
    
64.                 robot.move()
    
65.             else:
    
66.                 while self.direction != 1:
    
67.                     robot.turnleft(1)
    
68.                     self.direction = (self.direction + 1) % 4
    
69. 
    
70.                 robot.move()

复制代码

第一题不可能有环吧？ 上下级关系是不是应该都是树形关系我感觉，好像有环不太符合常识？还是面试官提到了可能有环？

会有环，举个例子，a是b的上司，b是c的上司，但是a也是c的直接上司

sth830 发表于 2018-4-7 05:10
会有环，举个例子，a是b的上司，b是c的上司，但是a也是c的直接上司

当成有向图来处理就没有环了吧

zec 发表于 2018-4-7 05:44
当成有向图来处理就没有环了吧

请问怎么做呢？

机器人，使用random方向，记录visited，eventually visited all cells.

sth830 发表于 2018-4-7 05:54
请问怎么做呢？

提供一个思路，用hashmap建树，然后用dp做

bambloo 发表于 2018-4-7 06:57
提供一个思路，用hashmap建树，然后用dp做

能不能大概写一下代码？我还是不理解，我试过了用dfs + dp来做，但是一旦图里有环就做不了

sth830 发表于 2018-4-7 06:59
能不能大概写一下代码？我还是不理解，我试过了用dfs + dp来做，但是一旦图里有环就做不了

你的问题就是用了无向图，用hashmap可以建有向图（其实二维数组也可以，不过需要输入都是数字），代码有空写吧，我觉得跟微软某年的预科生笔试题有点像，场景是酒会，然后是直属上司来了只能喝自己酒量的一半什么的，求最大酒量