Youtube/Google 11/23电面

ssross 发表于 2015-12-3 03:01
自己也写了个。就是对每个‘*’进行BFS！最后把distance累加起来。

这代码的时间复杂度是O(n^4)?

bobzhang2004 发表于 2015-12-3 03:48
这代码的时间复杂度是O(n^4)?

没有这么大。他只从target开始bfs。每个bfs是O(n^2)所以其实总的就是O(k * n^2)，k是target的数量！

ssross 发表于 2015-12-3 03:52
没有这么大。他只从target开始bfs。每个bfs是O(n^2)所以其实总的就是O(k * n^2)，k是target的数量！

但是你的sumDistance(dis, curDis, matrix);，是在两重for循环中，感觉如果要做到O(k * n^2)，得用hashset来保存是否访问过，因为Arrays.fill也是在三重循环中

bobzhang2004 发表于 2015-12-2 23:46
写了下代码，有个问题是当计算从*到其他地方的位置时，可以经过'*'的吗？还是需要绕开？代码为可以经过的情 ...

不可以，要绕开*