uber电面

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

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

很简单的题，只怪交流不顺

就是BFS？

用bfs，把坐标和路径的tuple放入queue中

1. from collections import deque
   
2. 
   
3. def findShortestPath(board, start, end):
   
4.     visited = set()
   
5.     visited.add(start)
   
6.     queue = deque([])
   
7.     queue.append((start, [start]))
   
8.     while queue:
   
9.         cur, path = queue.popleft()
   
10.         cx, cy = cur
    
11.         if cur == end:
    
12.             return path
    
13.         for nx, ny in [(cx + 1, cy), (cx - 1, cy), (cx, cy + 1), (cx, cy - 1)]:
    
14.             if 0 <= nx < len(board) and 0 <= ny < len(board[0]) and board[nx][ny] == 'w' and (nx, ny) not in visited:
    
15.                 path.append((nx, ny))
    
16.                 queue.append(((nx, ny), list(path)))
    
17.                 visited.add((nx, ny))
    
18.     return []
    
19. 
    
20.    
    
21. 
    
22. if __name__ == '__main__':
    
23.     board = [['w', 'w', 'w', 'w'], ['b', 'w', 'w', 'b'], ['b', 'b', 'w', 'b'], ['w', 'w', 'w', 'b']]
    
24.     print findShortestPath(board, (0, 0), (3, 0))
    
25.    
    
26. # Output:
    
27. # [(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (3, 0)]

复制代码

如果是最短路径的话，好像你的程序没有这个功能哦。 只是路径而已！

taixingbi 发表于 2019-5-28 08:52
如果是最短路径的话，好像你的程序没有这个功能哦。 只是路径而已！

用bfs搜出来的就是最短路径吧

不过你每次把路径存起来时间和空间复杂度有点高，可以考虑用一个map记录每个点的上一个点