google面經

Shortest Manhattan distance betwee

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

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

0, 0 ]
[ 0, y, 0, 0 ]

时间O(m*n)最优，把所有的x放进queue里，然后bfs找到第一个y。

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

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

假设x = 0, y = 1. 只要把所有的0存入queue， 然后层遍历，每一层结果增加1， 遇到的第一个1就返回结果。

1. // 0 means x, 1 means y
   
2. int shortestDist(vector<vector<int>> & grid) {
   
3.     int m = grid.size(), n = grid[0].size(), res = 0;
   
4.     queue<pair<int, int>> q;
   
5.    
   
6.     for (int i = 0; i < m; ++i) {
   
7.         for (int j = 0; j < n; ++j) {
   
8.             if (grid[i][j] == 0) {
   
9.                 q.push({i, j});
   
10.             }
    
11.         }
    
12.     }
    
13.     while (!q.empty()) {
    
14.         int len = q.size();
    
15.         
    
16.         for (int i = 0; i < len; ++i) {
    
17.             auto r = q.front().first, c = q.front().second;
    
18.             q.pop();
    
19.             if (grid[r][c] == 1) return res;
    
20. 
    
21.             for (auto dir : dirs) {
    
22.                 int x = r + dir[0], y = c + dir[1];
    
23.                 if (x < 0 || x >= m ||  y < 0 || y >= n) continue;
    
24. 
    
25.                 q.push({x, y});
    
26.             }
    
27.         }
    
28.         ++res;
    
29.     }
    
30.     return -1;
    
31. }

复制代码

如果用dp 记住左， 左上，上方最近的x, y 就是O(M *N ) ，是否还有更好的解法？

不可能有更优的吧 你总得把整个输入扫一遍

 同意楼上，时间上应该最优了吧，更优可能要看空间复杂度？

双向BFS也得遍历O(mn)

o(m * n)的solution 是什么样的？哪位大神能给个提示？

johnnywsd 发表于 2021-1-19 13:15
o(m * n)的solution 是什么样的？哪位大神能给个提示？

[i][/i]

johnnywsd 发表于 2021-1-19 13:15
o(m * n)的solution 是什么样的？哪位大神能给个提示？

求大米