问个Google面题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个Google面题

问个Google面题# JobHunting - 待字闺中

D*62013-06-06 07:06

1 楼

之前在版上看到的。
Given a matrix which contains black and white grids, use a method to find
out if the white grids are connected or not, if yes, return true.
这题是不是就是类似garbage collection mark and sweep. DFS就行了吧。还有什么
高级做法吗？

L*Q2013-06-06 07:06

2 楼

如果可以改动matrix的值，有一个简单办法。
Idea: 如果所有white的cell相连，那么从任何一个white cell开始，往四个方向扩展
，把遇到的white都改成black，那么最终所有cell都是black。
step 1：find any white cell as start point;
step 2: use a queue or stack to record white cells: get a cell, set it as
black, and then check the four directions. If a neighbor is white, put it in
queue/stack; Finish when queue/stack is empty
step 3: check the board again, return false if finding a white cell.
Complexity O(n^2). 如果两个white cell (i, j)和(i+1, j+1)算是相连，那step 2就
是check 8个方向

【在 D****6 的大作中提到】

: 之前在版上看到的。
: Given a matrix which contains black and white grids, use a method to find
: out if the white grids are connected or not, if yes, return true.
: 这题是不是就是类似garbage collection mark and sweep. DFS就行了吧。还有什么
: 高级做法吗？

c*e2013-06-06 07:06

3 楼

都连的条件是最多只有两个白点，它们的周围只有一个白点。遍历所有节点，每次检查
4个相连的点。
不知有没有更好的。

【在 D****6 的大作中提到】

D*62013-06-06 07:06

4 楼

想了想这题怎么都要走一遍。mark and sweep最容易了。

c*a2013-06-06 07:06

5 楼

不改原board也可以啊。
1. 从任一个白点开始，用你的queue走，走到走不动，看看总共搞过几个白点
2. check board，看一共有几个白点
看看1和2的白点数是不是一样。

in

【在 L***Q 的大作中提到】

: 如果可以改动matrix的值，有一个简单办法。
: Idea: 如果所有white的cell相连，那么从任何一个white cell开始，往四个方向扩展
: ，把遇到的white都改成black，那么最终所有cell都是black。
: step 1：find any white cell as start point;
: step 2: use a queue or stack to record white cells: get a cell, set it as
: black, and then check the four directions. If a neighbor is white, put it in
: queue/stack; Finish when queue/stack is empty
: step 3: check the board again, return false if finding a white cell.
: Complexity O(n^2). 如果两个white cell (i, j)和(i+1, j+1)算是相连，那step 2就
: 是check 8个方向