狗2轮实习面经

lzx801 发表于 2018-12-16 00:05
额，请问第一轮第二题的BFS可以麻烦详细说一下吗？
如果是单纯的bfs的话，貌似是需要对于矩阵中的每一个1 ...

可以一开始就把所有的1的位置都加到同一个queue中，然后做level-order遍历。当第一次找到2时的遍历过的level数即为1和2之间可能的最短距离。

John1993 发表于 2018-12-15 23:36
想了一下才发现第一题的第二问原来是自行车...

但是因为只要求最短距离，不需要求所有1和2配对的最短距离，所以lz的bfs貌似就够了？自行车的原始解法反而更复杂了

第一题第一问有two pointer one pass的解法么？

第一题

1.         private int shotestDistance(int[] array) {
   
2.                 int i = -1;
   
3.                 int j = -1;
   
4.                 int ans = Integer.MAX_VALUE;
   
5.                 for (int n = 0; n < array.length; n++) {
   
6.                         if (array[n] == 1) {
   
7.                                 i = n;
   
8.                                 if (j != -1) {
   
9.                                         ans = Math.min(ans,        Math.abs(i - j));
   
10.                                 }
    
11.                         }
    
12.                         if (array[n] == 2) {
    
13.                                 j = n;
    
14.                                 if (i != -1) {
    
15.                                         ans = Math.min(ans,        Math.abs(i - j));
    
16.                                 }
    
17.                         }
    
18.                        
    
19.                 }
    
20.                 return ans;

复制代码

感谢楼主帮助！已加米
第二题可不可以细讲下具体怎么实现union find，想了很久没想出来555
有些疑问：
1 这辆车是否需要考虑有宽度？
2. 每个bomb的作用范围是一个圆形，怎么判断是否和其他bomb互联？
3

关键39 发表于 2018-12-26 19:55
感谢楼主帮助！已加米
第二题可不可以细讲下具体怎么实现union find，想了很久没想出来555
有些疑问：

判断两雷达是否直接相连的标准是看二者中心的距离是否<=二者探测范围之和。车应该不需要考虑宽度，否则难度过大了。

我想可以这样：先找到所有与上沿相交的雷达A，从每一个这样的雷达开始做dfs/bfs。如果从某个A能够搜索到一个和下沿相交的雷达B，那此时路就会被A到B之间的所有雷达覆盖的区域切断，那此时小车一定无法通过。

stellari 发表于 2018-12-27 03:24
判断两雷达是否直接相连的标准是看二者中心的距离是否

感谢大佬的回复！！
还有一个疑问，就是每个地雷在做dfs的时候，是遍历其余所有的地雷，计算圆心距离吗？感觉这个挺慢的