骨骼电面1题

既然只有一条path，就是说没有环，那我感觉可以理解成一个k叉树.

amgfan 发表于 2020-6-13 16:24
你这不是 greedy 吧 ...

面试官，自己说greedy。我做的，是吧，所有的点亮的可能都算一遍。找到最小值。

beef1218 发表于 2020-6-14 04:44
既然只有一条path，就是说没有环，那我感觉可以理解成一个k叉树.

谢谢。对。欢迎给个code 解法。学习下。

jtzgz 发表于 2020-6-14 04:54
谢谢。对。欢迎给个code 解法。学习下。

https://paste.ubuntu.com/p/k2488KfHrh/  这是 dp 的解法。

每次找到出度最多的房间 选择点亮后 已经被点亮的点要从图中删除 继续选择出度最多的房间 直到点被删完

难道不是House Robber III换个壳吗？任意两node之间只有一条path。

EmanekaT 发表于 2020-6-16 15:45
难道不是House Robber III换个壳吗？任意两node之间只有一条path。

那个是求max money，这个是min的node。

fangdanzai 发表于 2020-6-15 17:04
每次找到出度最多的房间 选择点亮后 已经被点亮的点要从图中删除 继续选择出度最多的房间 直到点被删完

我也是如此做的。后来发现不对。面试官说不对。

按照K tree做的，不知道对不对。 狗的连电面都这么难！@！

1. 
   
2. def minLights(edges):
   
3.     # exactly one path betteween any two rooms (means no cycle, one graph)
   
4.     neighbors = defaultdict(list)
   
5.     for i, j in edges:
   
6.         neighbors[i].append(j)
   
7.         neighbors[j].append(i)
   
8. 
   
9.     root = None
   
10.     for i, v in neighbors.items():
    
11.         if len(v) == 1:
    
12.             root = i
    
13.             break
    
14.     print(root, neighbors)
    
15.     def dfs(cur, last):
    
16.         # [State 0] Strict subtree: All the nodes below this node are covered, but not this node.
    
17.         # [State 1] Normal subtree: All the nodes below and including this node are covered, but there is no camera here.
    
18.         # [State 2] Placed camera: All the nodes below and including this node are covered, and there is a camera here (which may cover nodes above this node).
    
19.         
    
20.         dp_next = []
    
21.         for n in neighbors[cur]:
    
22.             if n == last:
    
23.                 continue
    
24.             dp_next.append(dfs(n, cur))
    
25. 
    
26.         # leaf node
    
27.         if not dp_next:
    
28.             print(cur)
    
29.             return [0, float('inf'), 1]
    
30. 
    
31.         dp0 = sum(dp_next[i][1] for i in range(len(dp_next)))
    
32. 
    
33.         dp1 = float('inf')
    
34.         if len(dp_next) == 1:
    
35.             dp1 = dp_next[0][2]
    
36.         else:
    
37.             total = 0
    
38.             for i in range(len(dp_next)):
    
39.                 total += min(dp_next[i][1:])
    
40.             for i in range(len(dp_next)):
    
41.                 dp1 = min(dp1, dp_next[i][2] + total - min(dp_next[i][1:]))
    
42. 
    
43.         dp2 = 1 + sum(min(dp_next[i]) for i in range(len(dp_next)))
    
44.         print(cur, dp0, dp1, dp2)
    
45.         return dp0, dp1, dp2
    
46. 
    
47.     return min(dfs(root, None)[1:])

复制代码

ninjax 发表于 2020-7-20 04:58
按照K tree做的，不知道对不对。 狗的连电面都这么难！@！
[mw_shl_code=python,true]
def minLights(edg ...

也没有。我backtracking 做出来了，也让过了呢。