2019/1/7 狗家店面

三哥面试，口音不重。上来问了最近有什么challenge的job，就把自己准备好的BQ答了一遍，没什么反馈，直接进入题目：

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

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

讲了下brute force的解法，和时间复杂度。

Followup问如何优化？想了好久之后被提示可以考虑如果是一维数组怎么办？我按照思路尝试把矩阵理解为按照横向和纵向的两个数组，在两个数组中找到距离最近的一对X，Y，计算着两组点的曼哈顿距离，取最小返回。对方没有确认。

后来他说时间比较紧，让我代码brute force，很快完成，然后让我问他问题。我就问了技术债、process等问题。时间到就结束了。

非常感谢地里宝贵的信息，希望能帮助大家。顺求过，也请大牛贡献更优解

是求距离最短的x和y吗？输出距离？
曼哈顿距离 可不可以把x和y的坐标分别加起来做两个数组 然后binary search

1. package Graph.UG;
   
2. 
   
3. import java.util.*;
   
4. 
   
5. public class FindShortestDistance {
   
6. 
   
7.     private char X = 'X';
   
8.     private char Y = 'Y';
   
9. 
   
10.     private int [] xCoordinate = {-1, 1, 0, 0};
    
11.     private int [] yCoordinate = {0, 0, -1, 1};
    
12. 
    
13.     public int shortestDistance(char [][] matrix) {
    
14. 
    
15.         int n = matrix.length;
    
16.         int m = matrix[0].length;
    
17. 
    
18.         int [][] output = new int[n][m];
    
19.         boolean [][] visited = new boolean[n][m];
    
20. 
    
21.         Queue<int []> queue = new LinkedList<>();
    
22.         for (int i = 0; i < n; i ++) {
    
23.             for (int j = 0; j < m; j ++) {
    
24.                 if (matrix[i][j] == X) {
    
25.                     queue.offer(new int [] {i, j});
    
26.                     visited[i][j] = true;
    
27.                 }
    
28.             }
    
29.         }
    
30. 
    
31.         int distance = 0;
    
32. 
    
33.         while (!queue.isEmpty()) {
    
34.             int size = queue.size();
    
35. 
    
36.             for (int i = 0; i < size; i ++) {
    
37.                 int [] currentPosition = queue.remove();
    
38.                 if (matrix[currentPosition[0]][currentPosition[1]] == Y) {
    
39.                     return distance;
    
40.                 }
    
41. 
    
42.                 for (int k = 0; k < 4; k ++) {
    
43.                     int newX = currentPosition[0] + xCoordinate[k];
    
44.                     int newY = currentPosition[1] + yCoordinate[k];
    
45. 
    
46.                     if (isValid(matrix, newX, newY) && visited[newX][newY] == false) {
    
47.                         queue.offer(new int[] {newX, newY});
    
48.                         visited[newX][newY] = true;
    
49.                     }
    
50.                 }
    
51.             }
    
52.             distance ++;
    
53.         }
    
54. 
    
55.         return distance;
    
56.     }
    
57. 
    
58.     private boolean isValid(char [][] matrix, int x, int y) {
    
59.         int n = matrix.length;
    
60.         int m = matrix[0].length;
    
61. 
    
62.         return (x >= 0 && x < n && y >= 0 && y < m);
    
63.     }
    
64. 
    
65.     public static void main(String [] args) {
    
66.         char[][] maze = {{'X','O','O','O'} ,{'X','O','O','O'} ,{'O','O','O','Y'}};
    
67. 
    
68.         FindShortestDistance t = new FindShortestDistance();
    
69.         System.out.println(t.shortestDistance(maze));
    
70.     }
    
71. }
    

复制代码

我之前在另一个帖子的回答是错的，在这里纠正一下吧。

方法就是BFS，时空复杂度是O(n*m)

窍门是最开始把所有的X放进queue，并且distance = 0，搜到第一个Y就退出。

run two BFS for 'X' and 'Y' at the same time. The first (X,Y) pair meets each other is the answer.

补充内容 (2019-2-13 04:17):
run one BFS is sufficient.

如果点非常多，直接BFS我觉得效率更高。
比较稀疏或者按照面试官的意思：可以把每个X 和 O的坐标xy相加，然后分别排序，两个数组然后two pointers即可。我觉得倒不用binary search

BFS, 最近面亚麻问了类似的题目

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

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

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

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

这个是经典的bfs找最短路径吧，从所有的x或者o开始遍历都行。时间复杂度是o（mn），没法进一步优化了吧。面试官的优化只是指采用双向bfs缩短搜寻时间么？

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

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