贡献一道面经,要求O(mn) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

贡献一道面经,要求O(mn)

贡献一道面经,要求O(mn)# JobHunting - 待字闺中

e*32015-09-10 07:09

1 楼

给一个矩阵,每个cell是1或者0. 要求把cell是1的相邻4个cell换成1.
follow up要求要求把cell是1的相邻4个方向,且和这个cell相差曼哈顿距离为K以内的
所有
cell置1. 时间复杂度要求O(MN).
举例:
k = 2,
00000 00100
00000 01110
00100 --> 11111
00000 01110
00000 00100

T*u2015-09-10 07:09

2 楼

in place ma?

e*32015-09-10 07:09

3 楼

只要求时间是MN,空间没要求

I*g2015-09-10 07:09

4 楼

先走一遍，把每个格子的邻居换成：如果原来是0，换成-1，如果是1 不变。
在走一遍，把-1 换成1.
O(5MN)

【在 e********3 的大作中提到】

: 给一个矩阵,每个cell是1或者0. 要求把cell是1的相邻4个cell换成1.
: follow up要求要求把cell是1的相邻4个方向,且和这个cell相差曼哈顿距离为K以内的
: 所有
: cell置1. 时间复杂度要求O(MN).
: 举例:
: k = 2,
: 00000 00100
: 00000 01110
: 00100 --> 11111
: 00000 01110

e*32015-09-10 07:09

5 楼

怎么得到5MN?K呢?怎么用到K

【在 I*******g 的大作中提到】

: 先走一遍，把每个格子的邻居换成：如果原来是0，换成-1，如果是1 不变。
: 在走一遍，把-1 换成1.
: O(5MN)

s*i2015-09-10 07:09

6 楼

你自己题没说清楚你那个followup也是换4个cell就可以了？我理解也是5MN就可以了

【在 e********3 的大作中提到】

: 怎么得到5MN?K呢?怎么用到K

c*t2015-09-10 07:09

7 楼

你们没有理解楼主。
楼主显然是笔误。
follow up肯定是把四个方向曼哈顿距离内的所有格子设置为1.
brutal force kmn.
但有mn 解法。

了

【在 s*******i 的大作中提到】

: 你自己题没说清楚你那个followup也是换4个cell就可以了？我理解也是5MN就可以了

e*32015-09-10 07:09

8 楼

了
举例:
k = 2,
00000 00100
00000 01110
00100 --> 11111
00000 01110
00000 00100

【在 s*******i 的大作中提到】

: 你自己题没说清楚你那个followup也是换4个cell就可以了？我理解也是5MN就可以了

h*e2015-09-10 07:09

9 楼

如果不要求空间的话多开个matrix 然后相当于 matrix 0, 1 区间 dfs么。
如果空间严格的话，可以自己在0， 1前面或者后面pigback 1位表示新的matrix的值。
然后dfs, 之后都dfs结束把原先位给抹掉就行了。

g*g2015-09-10 07:09

10 楼

Isn't brute force O(k^2*m*n)?

【在 c*******t 的大作中提到】

: 你们没有理解楼主。
: 楼主显然是笔误。
: follow up肯定是把四个方向曼哈顿距离内的所有格子设置为1.
: brutal force kmn.
: 但有mn 解法。
:
: 了

e*32015-09-10 07:09

11 楼

大牛是对的...我打漏了2个字:以内,已经补上了...求MN解法

【在 c*******t 的大作中提到】

: 你们没有理解楼主。
: 楼主显然是笔误。
: follow up肯定是把四个方向曼哈顿距离内的所有格子设置为1.
: brutal force kmn.
: 但有mn 解法。
:
: 了

c*t2015-09-10 07:09

12 楼

对，我搞错了。
O(mn)解法我还没想出来。

【在 g*******g 的大作中提到】

: Isn't brute force O(k^2*m*n)?

e*32015-09-10 07:09

13 楼

不是.K=1的时候是MN. 然后把之前得出的结果循环K次就是KMN

【在 g*******g 的大作中提到】

: Isn't brute force O(k^2*m*n)?

m*f2015-09-10 07:09

14 楼

没有看懂楼主的意思，感觉并查集是可能的方案
就像number of islands ii

e*32015-09-10 07:09

15 楼

可以具体点么?
应该不是DFS,BFS之类.个人感觉.错了勿喷

【在 m*f 的大作中提到】

: 没有看懂楼主的意思，感觉并查集是可能的方案
: 就像number of islands ii

m*f2015-09-10 07:09

16 楼

我没有看懂你的题意，不过并查集不是dfs/bfs

【在 e********3 的大作中提到】

:
: 可以具体点么?
: 应该不是DFS,BFS之类.个人感觉.错了勿喷

e*32015-09-10 07:09

17 楼

举了例子还没懂么??? 哪里不懂?

【在 m*f 的大作中提到】

: 我没有看懂你的题意，不过并查集不是dfs/bfs

m*f2015-09-10 07:09

18 楼

我看错了，不过答案给你找来了
http://www.jiuzhang.com/problem/30/

【在 e********3 的大作中提到】

:
: 举了例子还没懂么??? 哪里不懂?

e*32015-09-10 07:09

19 楼

不是这题,也不是这答案...这题我知道

【在 m*f 的大作中提到】

: 我看错了，不过答案给你找来了
: http://www.jiuzhang.com/problem/30/

h*e2015-09-10 07:09

20 楼

hi不知道你看懂我的解法没有我的是o(2mn) 时间复杂度不随着k变化，所以也就是O(
mn)了

【在 e********3 的大作中提到】

:
: 不是这题,也不是这答案...这题我知道

e*32015-09-10 07:09

21 楼

不太明白你的算法.
matrix 0, 1 区间 dfs? 意思就是loop through整个grid然后对没个cell做DFS?
DFS应该不行.因为你对每个cell做DFS的话时间复杂度是k^2. 最后会是MNK^2. 不知道
我有没有理解对你的算法.

【在 h*******e 的大作中提到】

: 如果不要求空间的话多开个matrix 然后相当于 matrix 0, 1 区间 dfs么。
: 如果空间严格的话，可以自己在0， 1前面或者后面pigback 1位表示新的matrix的值。
: 然后dfs, 之后都dfs结束把原先位给抹掉就行了。

c*w2015-09-10 07:09

22 楼

一个一个cell扫过去，碰到是1的就做k步bfs，bfs的时候遇到零就改成*，遇到*或1就
停止当前branch。
这样每个cell最多被4个bfs扫到。所以复杂度就是mn。
实际上跟区域涂色很相似。

【在 e********3 的大作中提到】

:
: 不太明白你的算法.
: matrix 0, 1 区间 dfs? 意思就是loop through整个grid然后对没个cell做DFS?
: DFS应该不行.因为你对每个cell做DFS的话时间复杂度是k^2. 最后会是MNK^2. 不知道
: 我有没有理解对你的算法.

h*e2015-09-10 07:09

23 楼

新matrix还有visited数组啊，visited check了就不访问了，每次旧数组遇到新的 1
产生的新曼哈顿区域一定是联通的如果没有edge的话（matrix 的 edge应该有可能切
断新曼哈顿区域），所以dfs如果碰到有新matrix里面有visited就不必再压入栈了，
做个菱形dfs之后大于edge的不显示就行了。所以所有点至多只经过一遍。

【在 e********3 的大作中提到】

l*32015-09-10 07:09

24 楼

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 1 0 0
k = 2
是不是有问题？
碰到 (2,2)位置的1以后，做bfs会直接遇到 (2,3)位置的1，然后就停了。这样就会少
涂。

【在 c******w 的大作中提到】

: 一个一个cell扫过去，碰到是1的就做k步bfs，bfs的时候遇到零就改成*，遇到*或1就
: 停止当前branch。
: 这样每个cell最多被4个bfs扫到。所以复杂度就是mn。
: 实际上跟区域涂色很相似。

e*32015-09-10 07:09

25 楼

问题就是停止branch的条件.不能遇到1或者*就停止吧.比如1左边位置是*,这时候不能
停止,因为*的左边和上边可能都需要染色.比如这样:
0000*00
000*1*0
0000*10
对于第三行的1,你bfs时往左走发现有个*,这时候按照染色算法就停止了.但是实际还是
要继续往左染色. 因为这个不是将包围面积染色,而是一定要染k^2个附近的cell.所以
对于每个cell按照这个算法一定要走遍k^2个cell.这样说对不

【在 c******w 的大作中提到】

e*32015-09-10 07:09

26 楼

看我上面回复.最重要就是停止条件.不能因为visit过就停止,因为我们要的是所有K^2
个cell,而不是某个包围区域.

【在 h*******e 的大作中提到】

: 新matrix还有visited数组啊，visited check了就不访问了，每次旧数组遇到新的 1
: 产生的新曼哈顿区域一定是联通的如果没有edge的话（matrix 的 edge应该有可能切
: 断新曼哈顿区域），所以dfs如果碰到有新matrix里面有visited就不必再压入栈了，
: 做个菱形dfs之后大于edge的不显示就行了。所以所有点至多只经过一遍。

h*e2015-09-10 07:09

27 楼

是做 O(M*n) 个 dfs 但正是因为有了新matrix 的 visited数组的存在总共访问才降
到了 Om*n 新matrix 基本每点都只访问一次。

2

【在 e********3 的大作中提到】

:
: 看我上面回复.最重要就是停止条件.不能因为visit过就停止,因为我们要的是所有K^2
: 个cell,而不是某个包围区域.

l*32015-09-10 07:09

28 楼

我认为应该这么做：
考虑这么一个类似的问题：
m x n 的0 ， 1矩阵，要求：
对于每个 "1", 把以这个 “1” 为左上角，以其位置 + (k,k) 为右下角的正方形内所
有点涂色。要求复杂度 O(m x n)
再说具体一点，我们考虑一个新的问题，这时候对于每个 “1” , 假设位置在 (i,j),
不是要求涂曼哈顿距离了，而是要求涂满 (i,j) 为左上角和 (i+k, j+k) 为右下
角的正方形。
这个问题有什么好处呢？且看如下图形（对应 k = 3 的情形)：
3 2 1
2 2 1
1 1 1
如果我们把原先矩阵里面的每个 “1” 都换成 k，然后用 “从左上角开始，以矩形圈
的方式往外扩散（具体参见上图中 "1" 的位置对应的圈）” 的loop顺序对当前点右
方和下方最
邻近的三个点进行值的update就行了。在当前的 (i,j)位置时，需要update (i+1,j) (
i,j+1) 和 (i+1,j+1) 的值， update方法就是，如果新的点的值小于 "(i,j)位置的值
-1" 时，那么就把他update成 "(i,j)位置的值 - 1"。这样处理完之后，所有正整数
的地方都是要着色的地方，复杂度是 O(m x n)，不需要额外的空间。
以上算法的关键是，根据涂色要求的本身需要设计一个合理的遍历方式，使得可以不重
复的回头看已经涂过的地方。因为这个类似的变种题更容易观察出这种遍历方式，所以
作为引子先说一下。
这时候考虑原题，就简单了。我们用类似的算法，标记规则是这样的 (假设 k = 3)
0 0 1 0 0
0 1 2 1 0
1 2 3 2 1
0 1 2 1 0
0 0 1 0 0
然后遍历方式是什么呢？是这样的：
从任意一个标记为 k 的点开始（先预处理矩阵，把所有 “1” 改成 k），以圈状的
方式向矩阵外围遍历（参见上图 “1” 构成的菱形圈），然后每次update 该点周围上
下左右的四个位置。

e*32015-09-10 07:09

29 楼

好吧,看来我误解你的意思了.
你的edge指的是啥?
"碰到有新matrix里面有visited就不必再压入栈". 不明白你这个是怎么保证染遍K^2个
cell的?

【在 h*******e 的大作中提到】

h*e2015-09-10 07:09

30 楼

我又想了一下dfs起始位置应该是菱形的一个尖尖，也就是之前check过的点产生的菱形
touch不到的位置，因为每次dfs的区域菱形的边和正方形的matrix的边有时候难免
有切割，这个切割先不要管，先做dfs这个新产生的曼哈顿区域一定是联通的。dfs
check一般check两个一个是 rowI colI 是否越界，再一个是此点是否访问过，越
界在现在的情况下暂时不要管，这样能保证dfs出来的区域是联通的，否则如果被edge
切割无法保证连通性的话，dfs就很难继续了。之后不要显示越界matrix之外的点就好
了。

【在 e********3 的大作中提到】

:
: 好吧,看来我误解你的意思了.
: 你的edge指的是啥?
: "碰到有新matrix里面有visited就不必再压入栈". 不明白你这个是怎么保证染遍K^2个
: cell的?

b*e2015-09-10 07:09

31 楼

灰常简单：
从所有1所在的位置开始做parallel BFS。具体的讲就是：
// assume input matrix is A
for each (i,j) {
if (A[i,j] == 1) {
M[i,j] = 0;
Q.enque((i, j));
} else {
M[i,j] = null;
}
}
while (Q.notEmpty()) {
(i, j) = Q.deque();
if (M[i+1,j] is null) {
Q.enque(i+1,j);
M[i+1,j] = M[i,j] + 1;
}
if (M[i-1,j] is null) {
Q.enque(i-1,j);
M[i-1,j] = M[i,j] + 1;
}
if (M[i,j+1] is null) {
Q.enque(i,j+1);
M[i,j+1] = M[i,j] + 1;
}
if (M[i,j-1] is null) {
Q.enque(i,j-1);
M[i,j-1] = M[i,j] + 1;
}
}
for each (i, j) {
if (M[i,j] <= k) {
A[i,j] = 1
}
}

【在 e********3 的大作中提到】

C*72015-09-10 07:09

32 楼

我觉得他的意思是遇到（2，3）的1就不加入队列了，队列里的其他元素继续bfs。这样
应该没什么问题

【在 l*3 的大作中提到】

: 0 0 0 0 0 0
: 0 0 0 0 0 0
: 0 0 1 1 0 0
: k = 2
: 是不是有问题？
: 碰到 (2,2)位置的1以后，做bfs会直接遇到 (2,3)位置的1，然后就停了。这样就会少
: 涂。

e*32015-09-10 07:09

33 楼

不加入的话那那个1怎么办?

【在 C*7 的大作中提到】

: 我觉得他的意思是遇到（2，3）的1就不加入队列了，队列里的其他元素继续bfs。这样
: 应该没什么问题

e*32015-09-10 07:09

34 楼

没明白...假设矩阵就只有1个1,你的算法好像是染遍了整个矩阵?

【在 b***e 的大作中提到】

: 灰常简单：
: 从所有1所在的位置开始做parallel BFS。具体的讲就是：
: // assume input matrix is A
: for each (i,j) {
: if (A[i,j] == 1) {
: M[i,j] = 0;
: Q.enque((i, j));
: } else {
: M[i,j] = null;
: }

e*32015-09-10 07:09

35 楼

edge
想不通啊...T T略抽象...

【在 h*******e 的大作中提到】

: 我又想了一下dfs起始位置应该是菱形的一个尖尖，也就是之前check过的点产生的菱形
: touch不到的位置，因为每次dfs的区域菱形的边和正方形的matrix的边有时候难免
: 有切割，这个切割先不要管，先做dfs这个新产生的曼哈顿区域一定是联通的。dfs
: check一般check两个一个是 rowI colI 是否越界，再一个是此点是否访问过，越
: 界在现在的情况下暂时不要管，这样能保证dfs出来的区域是联通的，否则如果被edge
: 切割无法保证连通性的话，dfs就很难继续了。之后不要显示越界matrix之外的点就好
: 了。

b*e2015-09-10 07:09

36 楼

打回去再读。M是一个辅助矩阵，A是原始输入。M就是要都染上，里面的数字是到1岛的
最短距离。

【在 e********3 的大作中提到】

:
: edge
: 想不通啊...T T略抽象...

C*72015-09-10 07:09

37 楼

不是最外层要每个点扫一遍吗，扫到那个1的时候会以它为起点bfs。这个不加入指的是
bfs内循环遇到的时候，不放入队列。大概的样子：
for（i，j）｛
if（found 1）｛
bfs
｝
｝

【在 e********3 的大作中提到】

:
: edge
: 想不通啊...T T略抽象...

e*32015-09-10 07:09

38 楼

懂了.你的算法应该是对的.

【在 b***e 的大作中提到】

: 打回去再读。M是一个辅助矩阵，A是原始输入。M就是要都染上，里面的数字是到1岛的
: 最短距离。

f*y2015-09-10 07:09

39 楼

这个算法强。 M[i,j] 要是初始化为INT_MAX 更清楚些
M[i,j] = null;

【在 b***e 的大作中提到】

: 打回去再读。M是一个辅助矩阵，A是原始输入。M就是要都染上，里面的数字是到1岛的
: 最短距离。

e*32015-09-10 07:09

40 楼

大牛们都太NB了...我回去面壁...

b*b2015-09-10 07:09

41 楼

This solution is great, thanks for provide this!

),

【在 l*3 的大作中提到】

: 我认为应该这么做：
: 考虑这么一个类似的问题：
: m x n 的0 ， 1矩阵，要求：
: 对于每个 "1", 把以这个 “1” 为左上角，以其位置 + (k,k) 为右下角的正方形内所
: 有点涂色。要求复杂度 O(m x n)
: 再说具体一点，我们考虑一个新的问题，这时候对于每个 “1” , 假设位置在 (i,j),
: 不是要求涂曼哈顿距离了，而是要求涂满 (i,j) 为左上角和 (i+k, j+k) 为右下
: 角的正方形。
: 这个问题有什么好处呢？且看如下图形（对应 k = 3 的情形)：
: 3 2 1

s*t2015-09-10 07:09

42 楼

觉得这道题就是普通的BFS，只是在加入每个相邻的点时，加上 distance，如果
distance+1 = k 就不在继续：
dfs(vector>& mat, int x, int y, int k)
{
queue> que;
que.push({x, y);
queue distance;
distance.push(0);
int dis = 0;
while (!que.empty()) {
int x = que.top().first();
int y = que.top().second();
que.pop();
mat[x][y] = '#';
int dis = distance.top();
distance.pop();
if (dis+1 == k) continue;
vector> adjs = {{1,0}, {-1,0}, {0, 1}, {0, -1}};
for (int i=0; iint new_x = x + adjs[i].first;
int new_y = y + adsj[i].second;

if (new_x < 0 || new_x > max.size() || new_y <0 || new_y >max[0].
size() || max[x][y] == '#') continue;
que.push({new_x, new_y});
distance.push(dis+1);
}
}
}
不知对不对

w*k2015-09-10 07:09

43 楼

曼哈顿半径为k的圆是个固定的模版, 拿它去处理每个点就行了,没必要dfs or bfs.

l*s2015-09-10 07:09

44 楼

private static void updateBoard(int[,] board, int k){
int m = board.GetLength(0), n = board.GetLength(1);
Queue queue = new Queue();
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(board[i, j] == 1) queue.Enqueue(new int[]{i, j});
while(k-- > 0 && queue.Count != 0){
int count = queue.Count;
while(count-- > 0){
int[] xy = queue.Dequeue();
for(int x = xy[0] - 1; x <= xy[0] + 1; x++)
for(int y = xy[1] - 1; y <= xy[1] + 1; y++){
if(x < 0 || y < 0 || x == m || y == n) continue;
if(Math.Abs(x + y - xy[0] - xy[1]) != 1) continue;
if(board[x, y] == 1) continue;
board[x, y] = 1; queue.Enqueue(new int[]{x, y});
}
}
}
}

b*m2015-09-10 07:09

45 楼

这个是不对的，比如：
* *
*****
*******
***&*&***
*******
*****
* *
&: 原来的1位置， *：新被标记为数字的
当你标记左边那个&的区域后，右边那个&的四面都是not null，因此会漏掉本来右边那
个&的区域。

【在 b***e 的大作中提到】

a*r2015-09-10 07:09

46 楼

If M(I,j) == k break;

m*k2015-09-10 07:09

47 楼

he used queue, not stack,
what you said won't happen.
use this simple example:
A=[1 0 0 1]
M=[0 null null 0]
then
M=[0 1 null 0]
then
M=[0 1 1 0]

【在 b*****m 的大作中提到】

: 这个是不对的，比如：
: * *
: *****
: *******
: ***&*&***
: *******
: *****
: * *
: &: 原来的1位置， *：新被标记为数字的
: 当你标记左边那个&的区域后，右边那个&的四面都是not null，因此会漏掉本来右边那