c***z
发帖数: 6348 | 1 Q1. Describe one of your projects.
Q2. Why the copy constructor pass by reference not by value?
I said I know the general difference between passing by reference (globe
copy) and value (local copy), but I don't know if it applies here.
He told me that if I pass by value and the value is an object of another
class, then there will be an infinite loop.
(I bombed this one I think.)
Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
I started with the naive approach (go along | s*********t
发帖数: 1663 | 2 第二个完全不懂。。
and
【在 c***z 的大作中提到】
: Q1. Describe one of your projects.
: Q2. Why the copy constructor pass by reference not by value?
: I said I know the general difference between passing by reference (globe
: copy) and value (local copy), but I don't know if it applies here.
: He told me that if I pass by value and the value is an object of another
: class, then there will be an infinite loop.
: (I bombed this one I think.)
: Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
: I started with the naive approach (go along
| p******y
发帖数: 708 | 3 thank you for sharing
what kind of position you are applying? SDE? | c***z
发帖数: 6348 | 4 SDE.
For objects, I always pass by reference without knowing or thinking why... | m****u
发帖数: 3915 | 5 第二题的意思是pass by value会调用 copy constructor吧
submatrix?
and
【在 c***z 的大作中提到】
: Q1. Describe one of your projects.
: Q2. Why the copy constructor pass by reference not by value?
: I said I know the general difference between passing by reference (globe
: copy) and value (local copy), but I don't know if it applies here.
: He told me that if I pass by value and the value is an object of another
: class, then there will be an infinite loop.
: (I bombed this one I think.)
: Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
: I started with the naive approach (go along
| c*******d
发帖数: 255 | 6 第三题有没有什么好的解法？
and
it
【在 c***z 的大作中提到】
: Q1. Describe one of your projects.
: Q2. Why the copy constructor pass by reference not by value?
: I said I know the general difference between passing by reference (globe
: copy) and value (local copy), but I don't know if it applies here.
: He told me that if I pass by value and the value is an object of another
: class, then there will be an infinite loop.
: (I bombed this one I think.)
: Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
: I started with the naive approach (go along
| H*M
发帖数: 1268 | 7 这两ID不错，connectedGraph hehe
【在 c*******d 的大作中提到】
: 第三题有没有什么好的解法？
:
: and
: it
| c******f
发帖数: 2144 | | c*******d
发帖数: 255 | 9 多谢
【在 H*M 的大作中提到】
: 这两ID不错，connectedGraph hehe
| r**u
发帖数: 1567 | 10 构造一个nxn matrix B，对每一行，B［i,j]是从左面起到这个元素连续0元素的个数。
e.g.,
1 0 0 0 1 --> 0 1 2 3 0
1 1 0 0 1 --> 0 0 1 2 0
0 0 0 0 1 --> 1 2 3 4 0
...
然后对每一列用最大柱状图的算法。
【在 c*******d 的大作中提到】
: 第三题有没有什么好的解法？
:
: and
: it
| | | c******f
发帖数: 2144 | | c*******d
发帖数: 255 | 12 多谢提示，不过我还是不太明白
什么是最大柱状图的算法？
【在 r**u 的大作中提到】
: 构造一个nxn matrix B，对每一行，B［i,j]是从左面起到这个元素连续0元素的个数。
: e.g.,
: 1 0 0 0 1 --> 0 1 2 3 0
: 1 1 0 0 1 --> 0 0 1 2 0
: 0 0 0 0 1 --> 1 2 3 4 0
: ...
: 然后对每一列用最大柱状图的算法。
| l******o
发帖数: 144 | 13 同求解释。简单的动态规划可以做到O(MN*min(M,N))的复杂度，希望能有一个O(MN)的
算法。
多谢提示，不过我还是不太明白
什么是最大柱状图的算法？
【在 c*******d 的大作中提到】
: 多谢提示，不过我还是不太明白
: 什么是最大柱状图的算法？
| c*******d
发帖数: 255 | 14 动态规划怎么做？
【在 l******o 的大作中提到】
: 同求解释。简单的动态规划可以做到O(MN*min(M,N))的复杂度，希望能有一个O(MN)的
: 算法。
:
: 多谢提示，不过我还是不太明白
: 什么是最大柱状图的算法？
| b******n
发帖数: 823 | 15 linear scan应该可以把，
用O(m*n) extra space,
每个点记录原matrix中以该点为右下角的sub matrix的大小，
然后scan，(x, y)只用check (x-1, y-1), (x-1, y), (x,y-1)
复杂度O(NM) | S******n
发帖数: 1009 | 16 简单的DP就可以做到O(MN), 这个是square
柱状图是用于求rectangle的情形
【在 l******o 的大作中提到】
: 同求解释。简单的动态规划可以做到O(MN*min(M,N))的复杂度，希望能有一个O(MN)的
: 算法。
:
: 多谢提示，不过我还是不太明白
: 什么是最大柱状图的算法？
| l******o
发帖数: 144 | 17 这个具体怎么做？右下角为(x,y)的最大sub matrix同(x-1, y-1), (x-1, y), (x,y-1)
有可能完全没有关系。比如
1111101
1111101
1111101
1111101
1111000
0000000
1111000
右下角那个是3x3，(x-1, y), (x,y-1)都是1x7或7x1的那个, (x-1, y-1)是1x6或6x1那
个. 所以不能直接通过(x-1, y-1), (x-1, y), (x,y-1)的结果得到(x,y)的结果.
linear scan应该可以把，
用O(m*n) extra space,
每个点记录原matrix中以该点为右下角的sub matrix的大小，
然后scan，(x, y)只用check (x-1, y-1), (x-1, y), (x,y-1)
【在 b******n 的大作中提到】
: linear scan应该可以把，
: 用O(m*n) extra space,
: 每个点记录原matrix中以该点为右下角的sub matrix的大小，
: 然后scan，(x, y)只用check (x-1, y-1), (x-1, y), (x,y-1)
: 复杂度O(NM)
| b******n
发帖数: 823 | 18 (x,y)存的是以自身为右下角的square submatrix的size，
你的例子里面(x-1, y), (x,y-1)，(x-1, y-1)都是2
就是DP
1)
【在 l******o 的大作中提到】
: 这个具体怎么做？右下角为(x,y)的最大sub matrix同(x-1, y-1), (x-1, y), (x,y-1)
: 有可能完全没有关系。比如
: 1111101
: 1111101
: 1111101
: 1111101
: 1111000
: 0000000
: 1111000
: 右下角那个是3x3，(x-1, y), (x,y-1)都是1x7或7x1的那个, (x-1, y-1)是1x6或6x1那
| l******o
发帖数: 144 | 19 哦, 没看清题目, 原来要求的是方阵啊, 那就简单多了. 确实可以做到O(MN)
假如, 如果不要求是方阵, 不知道有没有O(MN)的算法?
(x,y)存的是以自身为右下角的square submatrix的size，
你的例子里面(x-1, y), (x,y-1)，(x-1, y-1)都是2
就是DP
1)
【在 b******n 的大作中提到】
: (x,y)存的是以自身为右下角的square submatrix的size，
: 你的例子里面(x-1, y), (x,y-1)，(x-1, y-1)都是2
: 就是DP
:
: 1)
| c***z
发帖数: 6348 | 20 What I finally arrive at before timed out was this:
if there is a 1 on a line or row, change that line or row to all 1;
for each blocks of 0s, min{height, width} is the dimension of the submatrix.
two passes on the matrix, O(MN). | | | c*******d
发帖数: 255 | 21 对，是方阵的我知道怎么做了，
如果是求面积最大子长方形，有没有O(MN)的算法？
【在 l******o 的大作中提到】
: 哦, 没看清题目, 原来要求的是方阵啊, 那就简单多了. 确实可以做到O(MN)
: 假如, 如果不要求是方阵, 不知道有没有O(MN)的算法?
:
: (x,y)存的是以自身为右下角的square submatrix的size，
: 你的例子里面(x-1, y), (x,y-1)，(x-1, y-1)都是2
: 就是DP
: 1)
| h*******x
发帖数: 12808 | 22 Q2这个问题不错，还真容易没有考虑到。
Q3有更好的办法吗？
and
it
【在 c***z 的大作中提到】
: Q1. Describe one of your projects.
: Q2. Why the copy constructor pass by reference not by value?
: I said I know the general difference between passing by reference (globe
: copy) and value (local copy), but I don't know if it applies here.
: He told me that if I pass by value and the value is an object of another
: class, then there will be an infinite loop.
: (I bombed this one I think.)
: Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
: I started with the naive approach (go along
| c*******d
发帖数: 255 | 23 0001
0001
0001
这样就全变成1了吧？
submatrix.
【在 c***z 的大作中提到】
: What I finally arrive at before timed out was this:
: if there is a 1 on a line or row, change that line or row to all 1;
: for each blocks of 0s, min{height, width} is the dimension of the submatrix.
: two passes on the matrix, O(MN).
| s********y
发帖数: 3811 | 24 steve ballmer. s****[email protected]
and
【在 c***z 的大作中提到】
: Q1. Describe one of your projects.
: Q2. Why the copy constructor pass by reference not by value?
: I said I know the general difference between passing by reference (globe
: copy) and value (local copy), but I don't know if it applies here.
: He told me that if I pass by value and the value is an object of another
: class, then there will be an infinite loop.
: (I bombed this one I think.)
: Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
: I started with the naive approach (go along
| c**********a
发帖数: 199 | 25 竟然不全是算法，感觉比较nice啊
and
【在 c***z 的大作中提到】
: Q1. Describe one of your projects.
: Q2. Why the copy constructor pass by reference not by value?
: I said I know the general difference between passing by reference (globe
: copy) and value (local copy), but I don't know if it applies here.
: He told me that if I pass by value and the value is an object of another
: class, then there will be an infinite loop.
: (I bombed this one I think.)
: Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
: I started with the naive approach (go along
| c***z
发帖数: 6348 | 26 You are right, I was wrong.
Need to study more DP...
【在 c*******d 的大作中提到】
: 0001
: 0001
: 0001
: 这样就全变成1了吧？
:
: submatrix.
| c***z
发帖数: 6348 | 27 I finally made it. Anyone care to check it up? :)
/**************************************************************
Maximum all-0 square submatrix problem -- Compiled under VC++ 2008.
Problem Description:
Given MxN binary matrix M, find the maximum all 0 square submatrix (
denoted by MASS) of it.
Example:
0000100
1100100
0000011 <= an answer is the 3x3 submatrix (row 2~4, col 0~2)
0000010
0000100
0010100
Algorithm Description:
The key idea is Dynamic Programm | c***z
发帖数: 6348 | 28 co-ask, I am really curious...
thanks!
【在 c*******d 的大作中提到】
: 对，是方阵的我知道怎么做了，
: 如果是求面积最大子长方形，有没有O(MN)的算法？
| c***z
发帖数: 6348 | 29 It seems that it is better to store total # of 1's.
My idea is first fix column i and column j, try to find the max all 0
rectangular between them.
For that purpose, we need one pass on the rows, keeping track of the longest
rectangular ending at row k (LREK). This is a variant of the max sum
subarray problem.
If row k has an 1, then LREK=0; otherwise add 1 to the previous LREK.
To fast calculate if row k has an 1 or not, it is better to store the total
# of 1's and just do a subtraction.
O(M^2N
【在 r**u 的大作中提到】
: 构造一个nxn matrix B，对每一行，B［i,j]是从左面起到这个元素连续0元素的个数。
: e.g.,
: 1 0 0 0 1 --> 0 1 2 3 0
: 1 1 0 0 1 --> 0 0 1 2 0
: 0 0 0 0 1 --> 1 2 3 4 0
: ...
: 然后对每一列用最大柱状图的算法。
| c***z
发帖数: 6348 | 30 I worked out the rectangular algorithm. I feel that I like these problems,
but... I am too slow I think...
/**************************************************************
Maximum All-0 Submatrix Problem (not necessarily square submatrix)
-- compiled under VC++ 2008
Problem Description:
Given MxN binary matrix R, find the maximum all 0 submatrix (not
necessarily square submatrix, denoted by MAS) of it.
Example:
0000100
1100100
0000011 <= an answer is |
|
