狗家非常新鲜的现场表演（求大米）

感觉第二题像并查集。相交的圆合并成一组。对每个组，维护它能延伸到的左边界，右边界。如果某组的[左边界，右边界] 能包括马路，说明能block路

ZionHuang 发表于 2020-9-19 01:13
请问这个面经思路是啥呢 感觉要先建个坐标系 然后把这些圆圈全部给填到网格中 再用bfs扫一遍 看能不能走 ...

利用dfs或者union find做

1. def connect(p1, p2):
   
2.     return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2 <= (p1[2] + p2[2]) ** 2
   
3. 
   
4. def lobound(p):
   
5.     return p[1] - p[2]
   
6. 
   
7. def hibound(p):
   
8.     return p[1] + p[2]
   
9. 
   
10. # O(n * n)
    
11. def can_pass(pillars, lo, hi):
    
12.     from collections import defaultdict
    
13.     graph = defaultdict(set)
    
14.     for i in range(len(pillars)):
    
15.         if lobound(pillars[i]) <= lo and hibound(pillars[i]) >= hi:
    
16.             return False
    
17.         for j in range(i + 1, len(pillars)):
    
18.             if connect(pillars[i], pillars[j]):
    
19.                 graph[i].add(j)
    
20.                 graph[j].add(i)
    
21. 
    
22.     visit = set()
    
23. 
    
24. 
    
25.     def dfs(idx):
    
26.         stk = [(idx, lobound(pillars[idx]), hibound(pillars[idx]))]
    
27.         while stk:
    
28.             i, lb, hb = stk.pop()
    
29.             if i in visit:
    
30.                 continue
    
31.             visit.add(i)
    
32.             if lb <= lo and hb >= hi:
    
33.                 return False
    
34.             for nei in graph[i]:
    
35.                 if nei in visit:
    
36.                     continue
    
37.                 stk.append((nei, min(lb, lobound(pillars[nei])), max(hb, hibound(pillars[nei]))))
    
38.         return True
    
39. 
    
40.     return all(dfs(i) for i in range(len(pillars)) if i not in visit)
    

复制代码

[/i][/i][/i][/i][/i]

感谢分享！！！！！！！！

第一轮感觉是150变种 多了个 （） 所以需要 recursion？

如何面试好设计题？

请问lz第四题是怎么做的呢 线段树吗？

非常感谢分享！

楼主每轮都是45mins 吗