Google NY 全职 onsite 四轮

mileschen2008 发表于 2015-9-29 22:27
那P1, P2需要保证不能被水淹么？多谢啦。如果要保证的话，那么肯定不能超过min(p1, p2)吧。

万一第一列高度老高老高的话，水根本灌不进来，p1和p2的高度就反而无所谓了。。。

ChrisGates23 发表于 2015-9-29 22:36
请问lz第三轮，如果两个格子挨着，是不是相邻边就要从周长中去掉，同样如果走出了两排挨着的路线，相邻边都 ...

你楼上有人说了个更好的办法，走到死路加1即可。

这是猴哥吗？

gp89757 发表于 2015-9-28 15:09
感觉dfs遇到不能走的就周长加一比较好

嗯，是啊，感觉应该是这样的，不过好像还得加个限制条件，不能走且不是边缘就加一。

mileschen2008 发表于 2015-9-30 03:12
嗯，是啊，感觉应该是这样的，不过好像还得加个限制条件，不能走且不是边缘就加一。

这个思路之上，那么复杂度可以进一步优化吗？你觉得？

堕落的猴子 发表于 2015-9-30 04:26
这个思路之上，那么复杂度可以进一步优化吗？你觉得？

你在题目上写的复杂度是O（|包围这个cell的格子数|），我觉得好像应该是O(cell的个数)。

mileschen2008 发表于 2015-9-30 05:05
你在题目上写的复杂度是O（|包围这个cell的格子数|），我觉得好像应该是O(cell的个数)。

我的意思就是最后围起来的cell的总数，有没有更低的可能性呢。。。

堕落的猴子 发表于 2015-9-30 10:07
我的意思就是最后围起来的cell的总数，有没有更低的可能性呢。。。

那就不知道了，等待高人来解答，哈哈。个人感觉应该就是这个复杂度了, 我感觉至少需要知道里面有多少个等于这个 value的吧（而且与这点连通），这样就是O(cell个数)了。

mileschen2008 发表于 2015-9-30 10:20
那就不知道了，等待高人来解答，哈哈。个人感觉应该就是这个复杂度了, 我感觉至少需要知道里面有多少个等 ...

不过想了一次，如果这个会调用多次的话，那么可以做预处理，就是每个cell我们预先计算需要的周长。那么下次来调用的时候，O(1)返回。而且预处理只需要O(mn)就能做到，因为跟图找连通子图是一个概念，DFS或者BFS。DFS的复杂度是O(|E|)，这里边的数量是O(4mn)，所以还是O(mn).

mileschen2008 发表于 2015-9-30 10:27
不过想了一次，如果这个会调用多次的话，那么可以做预处理，就是每个cell我们预先计算需要的周长。那么下 ...

那么你觉得如何证明这个复杂度不可能低于O(|E|)呢。。。就和我面试里那样，感觉特别微妙。。。