谷狗电面背靠背（求大米！！！）

刚面完就来给大家汇报了。求大米！
楼主对bfs理解得太肤浅真是怕什么来什么，第一面就考了Manhattan Distance; 第二面容易多了，然而我第一面悲惨地没写出来，只写出个bfs的框架。感觉应当是凉凉。

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

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

和Google擦肩而过，心情很凄凉。

第一题为啥是BFS呢？如果没看错意思的化，感觉是把坐标加起来放到一个数组里面，然后排序再二分查找。

第二题有啥时间负载度的要求吗？

写了个第一题大家说的BFS的解法，但现在只能return 最短距离，而且觉得代码有点长。 请教大家怎么return最短距离的X，Y的坐标值， 谢谢！

1. def manhattanXYDist(grid):
   
2.         if not grid or not grid[0]:
   
3.                 return
   
4.         rows = len(grid)
   
5.         cols = len(grid[0])
   
6.         qX = []
   
7.         qY = []
   
8.         count = 0
   
9.         deltaX = [0,0,-1,1]
   
10.         deltaY = [-1,1,0,0]
    
11.         for i in range(rows):
    
12.                 for j in range(cols):
    
13.                         if grid[i][j] == 'X':
    
14.                                 qX.append(i)
    
15.                                 qY.append(j)
    
16. 
    
17.         while qX and qY:
    
18.                 tempX = qX
    
19.                 tempY = qY
    
20.                 qX = []
    
21.                 qY = []
    
22.                 count += 1
    
23.                 while tempX and tempY:
    
24.                         curX = tempX.pop(0)
    
25.                         curY = tempY.pop(0)
    
26.                         for i in range(4):
    
27.                                 nbX = curX + deltaX[i]
    
28.                                 nbY = curY + deltaY[i]
    
29. 
    
30.                                 if 0 <= nbX < rows and 0<=nbY < cols:
    
31.                                         if grid[nbX][nbY] == '0':
    
32.                                                 grid[nbX][nbY] = count
    
33.                                         if grid[nbX][nbY] == 'Y':
    
34.                                                 return count
    
35.                                         qX.append(nbX)
    
36.                                         qY.append(nbY)
    
37.         return -1
    
38. 
    
39. grid = [['X','0','X','0'],       
    
40.                 ['0','0','0','0'],
    
41.                 ['0','0','0','Y']]
    
42. 
    
43. print(manhattanXYDist(grid))

复制代码

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

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

第一题对每个x做bfs吗

请问楼主第一题是要求一定要bfs做？感觉用backtracking也可以？
然后同问第二题有时间要求吗？最暴利就n^2, 最快就kmp, 不过感觉店面应该不会让写kmp吧

pengdu 发表于 2019-2-7 09:02
第一题为啥是BFS呢？如果没看错意思的化，感觉是把坐标加起来放到一个数组里面，然后排序再二分查找。

第 ...

我没太看懂你第一题把坐标放进数组的做法。
第二题没有要求时间复杂度，应该是怎么做都行。

ziwei1992 发表于 2019-2-7 12:16
请问楼主第一题是要求一定要bfs做？感觉用backtracking也可以？
然后同问第二题有时间要求吗？最暴利就n^2 ...

不一定啊，bfs是我的第一反应。backtrack怎么做？第二题我暴力循环的，考官没说不行

pandami 发表于 2019-2-7 08:34
第一题对每个x做bfs吗

我是这么想的，最后没做出来。楼下有个老哥说可以用backtrack

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

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

第二题不太明白，LZ能讲一下他让你做什么吗

ziwei1992 发表于 2019-2-7 12:44
我想的其实就是dfs，从每一个y出发，然后到另一个y结束，如果距离小于全局变量的距离的话，更新这个最小 ...

你说的做法难道不是bfs吗？0.0