b********e 发帖数: 693 | 1 Given a NxN matrix with 0s and 1s. Now whenever you encounter a 0 make the
corresponding row and column elements 0.
Flip 1 to 0 and 0 remains as they are.
for example
1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
results in
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0
my solution is define a function remove1(x1,y1,x2,y2)
(x1,y1) is the matrix start point, and (x2,y2) is the end point
if(i,j) == 1, we need remove all 1 from i row and j column
so we divide into four small matrix
resrucive |
t****a 发帖数: 1212 | 2 I don't think you are right.
when you dive in some small matrix, find a 0, and start removing 1, you
might miss the 1 in another small matrix |
b********e 发帖数: 693 | 3 you are the man:)
do you have any solution?
【在 t****a 的大作中提到】 : I don't think you are right. : when you dive in some small matrix, find a 0, and start removing 1, you : might miss the 1 in another small matrix
|
s****a 发帖数: 50 | 4 How about use 2 arrays row[] and col[](all initialized 1) to record whether
each row and column should contain 1? Just scan the matrix to and set row[i
] = 0 and col[j] = 0 when matrix[i][j] = 0. Then set each matrix[i][j] = row
[i]*col[j].
Complexity is O(n^2).
【在 b********e 的大作中提到】 : you are the man:) : do you have any solution?
|
l******c 发帖数: 2555 | 5 this is a MSFT onsite question(I was asked), no extra space allowed
I don't know which tech company first asked this question, seems they copy the questions each other.
【在 b********e 的大作中提到】 : Given a NxN matrix with 0s and 1s. Now whenever you encounter a 0 make the : corresponding row and column elements 0. : Flip 1 to 0 and 0 remains as they are. : for example : 1 0 1 1 0 : 0 1 1 1 0 : 1 1 1 1 1 : 1 0 1 1 1 : 1 1 1 1 1 : results in
|
t*****j 发帖数: 1105 | 6 把matrix第一行和第一栏作为临时存储空间
对于每一row, 加到第一row(或者&&也行)。该函数变成
4 3 5 5 3
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
同理 对于第一列,则函数变成
20 3 5 5 3
3 1 1 1 0
5 1 1 1 1
4 0 1 1 1
5 1 1 1 1
扫描第一行及第一列(除A1,1以外),若不足n,则改行全部改0,否则改1.
20 0 1 1 0
3 0 1 1 0
5 0 1 1 0
4 0 1 1 0
5 0 1 1 0
把matrix第一行和第一栏作为临时存储空间
对于每一row, 加到第一row(或者&&也行)。该函数变成
4 3 5 5 3
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
同理 对于第一列,则函数变成
20 3 5 5 3
3 1 1 1 0
5 1 1 1 1
4 0 1 1 1
5 1 1 1 1
扫描第一行及第一列(除A1,1以外),若不足n,则该行全部改0,否则改此累计数字改
为1。
20 0 1 1 0
0 0 0 0 0
1 0
【在 b********e 的大作中提到】 : Given a NxN matrix with 0s and 1s. Now whenever you encounter a 0 make the : corresponding row and column elements 0. : Flip 1 to 0 and 0 remains as they are. : for example : 1 0 1 1 0 : 0 1 1 1 0 : 1 1 1 1 1 : 1 0 1 1 1 : 1 1 1 1 1 : results in
|
h**k 发帖数: 3368 | 7 对于A1,1 若第一行或者第一列其他数字有0,则第一行第一列全改为0.
你怎么做到这个的?既然你已经用第一行和第一列存了临时的和,原来的数据已经不在
了啊
【在 t*****j 的大作中提到】 : 把matrix第一行和第一栏作为临时存储空间 : 对于每一row, 加到第一row(或者&&也行)。该函数变成 : 4 3 5 5 3 : 0 1 1 1 0 : 1 1 1 1 1 : 1 0 1 1 1 : 1 1 1 1 1 : 同理 对于第一列,则函数变成 : 20 3 5 5 3 : 3 1 1 1 0
|
t*****j 发帖数: 1105 | 8 扫描第一行及第一列(除A1,1以外),若不足n,则该行全部改0,否则改此累计数字改
为1。
这句话是把非A11的累计数字位都改了。
【在 h**k 的大作中提到】 : 对于A1,1 若第一行或者第一列其他数字有0,则第一行第一列全改为0. : 你怎么做到这个的?既然你已经用第一行和第一列存了临时的和,原来的数据已经不在 : 了啊
|
b*****n 发帖数: 221 | |
l******c 发帖数: 2555 | 10 CareerCup 没有给出正确答案
【在 b*****n 的大作中提到】 : CareerCup上的原题?
|
|
|
a**********k 发帖数: 1953 | 11 I would use bit AND (&) operation (cumulatively).
time: O(n^2), space O(1). |
b******y 发帖数: 126 | 12 1,按行扫描,如果遇到0,将该行所有1改成2,换到下一行
2,按列扫描,如果遇到0,将该列所有1改成2,换到下一列
3,扫描整个矩阵a[i][j]/=2;
time:O(mn), space 0 |
t*****j 发帖数: 1105 | 13 and 和 累加 其实一样,都行。
【在 a**********k 的大作中提到】 : I would use bit AND (&) operation (cumulatively). : time: O(n^2), space O(1).
|
s***e 发帖数: 793 | 14 this is not space 0
because, if each element in the matrix is stored in a bit. how would this
work?
【在 b******y 的大作中提到】 : 1,按行扫描,如果遇到0,将该行所有1改成2,换到下一行 : 2,按列扫描,如果遇到0,将该列所有1改成2,换到下一列 : 3,扫描整个矩阵a[i][j]/=2; : time:O(mn), space 0
|
s***e 发帖数: 793 | 15 you are assuming the element in the matrix is an integer instead of a
boolean, which is a strong assumption
【在 t*****j 的大作中提到】 : 把matrix第一行和第一栏作为临时存储空间 : 对于每一row, 加到第一row(或者&&也行)。该函数变成 : 4 3 5 5 3 : 0 1 1 1 0 : 1 1 1 1 1 : 1 0 1 1 1 : 1 1 1 1 1 : 同理 对于第一列,则函数变成 : 20 3 5 5 3 : 3 1 1 1 0
|