狗家店面，发面经攒人品顺便求大米

发面经赞人品吧。也不知道能不能过。 但是我尽力了。
我知道和大神是不能相比的。

狗家是不可能考leetcode原题的。但是觉得可以找到同类型的。
这次电面是一道图题。
题目如下：

解法是：哈希表构建图+dfs。




补充内容 (2019-5-27 15:43)

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

oms的index

补充内容 (2019-5-30 06:08):
再补充一点吧，炸弹爆炸范围就是一个圆形半径，不是沿x、y轴方向。就是计算两点间的距离。

楼主，你的题目看不懂啊，可以给个例子吗

我写了一个邻接表图+BFS的方案，大家看看有没有什么bug和提高

1. 
   
2.         boolean bomb(List<List<Integer>> bombs, int r, List<Integer> from, List<Integer> to) {
   
3. 
   
4.                 int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
   
5. 
   
6.                 // construct graph
   
7.                 HashMap<List<Integer>, List<List<Integer>>> adjList = new HashMap<>();
   
8.                 for (List<Integer> bomb : bombs) {
   
9. 
   
10.                         List<List<Integer>> edges = new LinkedList<>();
    
11.                         for (int i = 1; i <= r; i++) {
    
12.                                 for (int[] dir : dirs) {
    
13.                                         List<Integer> other = Arrays.asList(bomb.get(0) + i * dir[0], bomb.get(1) + i * dir[1]);
    
14.                                         if(adjList.containsKey(other)) {
    
15.                                                 edges.add(other);
    
16.                                                 adjList.get(other).add(bomb);
    
17.                                         }
    
18.                                 }
    
19.                         }
    
20.                 }
    
21.                        
    
22.                 HashSet<List<Integer>> bombed = new HashSet<>();
    
23.                 Queue<List<Integer>> queue = new LinkedList<List<Integer>>();
    
24.                 queue.offer(from);
    
25.                 while (queue.size() > 0) {
    
26.                
    
27.                         List<Integer> cur = queue.poll();
    
28.                         if(cur.equals(to)) {
    
29.                                 return true;
    
30.                         }
    
31.                         bombed.add(cur);
    
32.                        
    
33.                         List<List<Integer>> edges = adjList.get(cur);
    
34.                         for (List<Integer> other : edges) {
    
35.                                 if (!bombed.contains(other)) {
    
36.                                         queue.offer(other);
    
37.                                 }
    
38.                         }
    
39.                        
    
40.                 }
    
41.                 return false;
    
42.         }

复制代码

请问：题目的意思是不是boom.get(Start)这个位置的炸弹可以引爆下一个位置的炸弹（within range of d），直到引爆boom.get(end)位置的炸弹？谢谢！

zhiyazw 发表于 2019-5-29 18:14
我写了一个邻接表图+BFS的方案，大家看看有没有什么bug和提高
[mw_shl_code=java,true]
        boolean bomb(Li ...

请问你的这个代码是不是只能炸沿X或者Y方向距离为R范围内的点? 谢谢！

zorrowei 发表于 2019-5-29 20:32
请问你的这个代码是不是只能炸沿X或者Y方向距离为R范围内的点? 谢谢！

你说的对，没包含对角线，需要跟面试官确认这个case。
如果要包含对角线，可以增加一组directions = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}}, 在1<=i<r的范围内扫描

这题应该可以变成求图里两个点start，end是否可以连通
dfs能解
麻烦的是第一步，要每个点去查其他点是否在半径里，是的话构造edge，
有了所有的edge hashmap，dfs就简单了

zhiyazw 发表于 2019-5-29 20:53
你说的对，没包含对角线，需要跟面试官确认这个case。
如果要包含对角线，可以增加一组directions = {{- ...

其实如果查两个点是否在半径里，用x^2+y^2这么算，无所谓对角线斜线，都能支持

楼主你题目看不见了啊

不是求最短路，没必要bfs