t******i
发帖数: 32 | 1 n*n 矩阵, 元素包括0 和1
求size(面积)最大的全1子矩阵.
想不出来,求教大家. | w****l
发帖数: 88 | 2 什么时候的题啊？今天问你的么？（解法改天上来....） | a***9
发帖数: 364 | 3 divide and conqure?
【在 t******i 的大作中提到】
: n*n 矩阵, 元素包括0 和1
: 求size(面积)最大的全1子矩阵.
: 想不出来,求教大家.
| t******i
发帖数: 32 | 4 今天面的, 感觉挂了...
【在 t******i 的大作中提到】
: n*n 矩阵, 元素包括0 和1
: 求size(面积)最大的全1子矩阵.
: 想不出来,求教大家.
| g*******y
发帖数: 1930 | 5 comfort，遇到刁难你的了，这个题目属于面试题里面最高的难度级别 | a***9
发帖数: 364 | 6 布个道吧 只能想到用分治，分4块再围着中间十字架找，大概是O(n^2),估计错的
【在 g*******y 的大作中提到】
: comfort，遇到刁难你的了，这个题目属于面试题里面最高的难度级别
| I**********s
发帖数: 441 | 7 如果是正方形子矩阵, 答案见http://geeksforgeeks.org/?p=6257
属于DP, 时空复杂度都是O(n*n).
如果可以是长宽不等的子矩阵, 需要进一步考虑. | i**********e
发帖数: 1145 | | h**6
发帖数: 4160 | 9 我的解法是这样的，需要五个辅助矩阵: H, L, Lx, R, Rx, 大小都为n*m，与原矩阵X
相等。
H中记录当前点向上连续1的个数，或者称为当前最高一字柱的高度。
L中记录当前点向左连续1的个数。
Lx中记录当前最高一字柱向左最远延伸到的位置。
R中记录当前点向右连续1的个数。
Rx中记录当前最高一字柱向右最远延伸到的位置。
最后再遍历一遍，求出每个点对应当前最高一字柱向左右延拓的面积，最大值就是最大
矩形面积。
S = H(Rx-Lx+1)
优化方法：
第一次遍历可以求出H, L, Lx
第二次遍历可以求出R, Rx, S
每个矩阵只需要保留当前行和上一行，复杂度是O(2m)*5 = O(10m) | r**********1
发帖数: 292 | | | | r**********1
发帖数: 292 | 11 不错啊。
【在 I**********s 的大作中提到】
: 如果是正方形子矩阵, 答案见http://geeksforgeeks.org/?p=6257
: 属于DP, 时空复杂度都是O(n*n).
: 如果可以是长宽不等的子矩阵, 需要进一步考虑.
| b******n
发帖数: 823 | 12 辅助matrix A，原始matrix R
A[i][j]存 R[1][j]+...+R[i][j],即该column从0到i为止的和
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*********应为R[k][j]+...+R[i][j]，k-i是连续的1****
然后扫描每个row，row上的值实际构成一个histogram，求该histogram内最大的rectangle，O(N)
总体O（MN）
不知对不。。。 | l********k
发帖数: 613 | 13 这个是不对的，R[1][j]+...+R[i][j]，加起来的和不代表连续的1啊，当中会有0。
rectangle
【在 b******n 的大作中提到】
: 辅助matrix A，原始matrix R
: A[i][j]存 R[1][j]+...+R[i][j],即该column从0到i为止的和
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: *********应为R[k][j]+...+R[i][j]，k-i是连续的1****
: 然后扫描每个row，row上的值实际构成一个histogram，求该histogram内最大的rectangle，O(N)
: 总体O（MN）
: 不知对不。。。
| b******n
发帖数: 823 | 14 恩，改成R[k][j]+...+R[i][j]，k-i是连续的1
【在 l********k 的大作中提到】
: 这个是不对的，R[1][j]+...+R[i][j]，加起来的和不代表连续的1啊，当中会有0。
:
: rectangle
| c***p
发帖数: 221 | 15 这个题是 largest rectangle under a histogram 的延伸。作为面试题是有点过分了。
【在 g*******y 的大作中提到】
: comfort，遇到刁难你的了，这个题目属于面试题里面最高的难度级别
| j**l
发帖数: 2911 | 16 开始没看到，原来子矩阵是方的，这个难度降低了不少阿。
不过就是这样也不是一下子想到
0 1 1 0 1
1 1 0 1 0
0 1 0 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0
方的话那个算法找到
1 1
1 1
不方的话应该是
1 1 1 1
1 1 1 1
那个算法无能为力
【在 I**********s 的大作中提到】
: 如果是正方形子矩阵, 答案见http://geeksforgeeks.org/?p=6257
: 属于DP, 时空复杂度都是O(n*n).
: 如果可以是长宽不等的子矩阵, 需要进一步考虑.
| j**l
发帖数: 2911 | 17 就和哥德巴赫猜想或者费马大定理一样，题目描述很简单，可是找到解法很难 | c****l
发帖数: 1280 | | l******l
发帖数: 497 | 19 能不能产生一个新的矩阵，然后矩阵的每个元素是数组。数组的第一个元素计算同一行
向左有多少个连续的1，第二个元素计算同一列向上有有多少个连续的1。
产生矩阵之后，每个数组取积。
非cs专业，所以瞎猜的，轻拍 | s*****e
发帖数: 36 | 20 Is my idea right? (Not CS major, welcome to make some comments)
Use a matrix A[i,j] to remember the size of all-1 matrix whose right-end
corner is (i,j) in the given matrix B.
if B[i,j]=0, A[i,j]=0
else
if A[i-1,j],A[i,j-1], A[i-1,j-1] are all >0
A[i,j]=A[i-1,j]+A[i,j-1]-A[i-1,j-1]+1
else
if A[i-1,j-1]==0 && (A[i-1,j]>0 || A[i,j-1]>0)
A[i,j]=max(A[i-1,j],A[i,j-1])+1
else
if A[i-1,j-1]==0 && A[i-1,j]=0 && A[i,j-1]=0
A[i,j]=1
else
【在 t******i 的大作中提到】
: n*n 矩阵, 元素包括0 和1
: 求size(面积)最大的全1子矩阵.
: 想不出来,求教大家.
| | | s*****e
发帖数: 36 | 21 Found erros in my previous solution. It seems I should remember the sizes
for three directions: horizontal, vertical, and rectangular and then
establish the recursive relation. The above is not right.
【在 s*****e 的大作中提到】
: Is my idea right? (Not CS major, welcome to make some comments)
: Use a matrix A[i,j] to remember the size of all-1 matrix whose right-end
: corner is (i,j) in the given matrix B.
: if B[i,j]=0, A[i,j]=0
: else
: if A[i-1,j],A[i,j-1], A[i-1,j-1] are all >0
: A[i,j]=A[i-1,j]+A[i,j-1]-A[i-1,j-1]+1
: else
: if A[i-1,j-1]==0 && (A[i-1,j]>0 || A[i,j-1]>0)
: A[i,j]=max(A[i-1,j],A[i,j-1])+1
| p********7
发帖数: 549 | 22 我觉得这个办法很好，histogram做一次O（N）每行都做O（M＊N）
【在 b******n 的大作中提到】
: 恩，改成R[k][j]+...+R[i][j]，k-i是连续的1
| y****n
发帖数: 579 | 23 赞
【在 p********7 的大作中提到】
: 我觉得这个办法很好，histogram做一次O（N）每行都做O（M＊N）
| s****a
发帖数: 528 | 24 没有看那些网站，自己想出来的
用另外一个矩阵B表示原矩阵A，元素值B(i,j)是原矩阵位置到左上角子矩阵的1的数目。
那么判断A(i0,j0)->A(i1,j1) 是不是全一子矩阵就可以从 B(i1,j1)+B(i0,j0)-B(i1,
j0)-B(i0,j1)
得知 O(1)
From now on, we can do dynamic programming:
assume we found the maximum sub matrix for A(1,1) -> A(i,j),
we save the maximum submatrix which has the right-bottom corner at A(i,j_k),
and A(i_k,j), and maximum submatrix without limitation
go to A(i,j+1), A(i+1,j) | p********7
发帖数: 549 | 25 老题目了，就是用求histogram最大面积的方法做。 | i*******t
发帖数: 79 | 26 面试给多长时间啊？
【在 t******i 的大作中提到】
: n*n 矩阵, 元素包括0 和1
: 求size(面积)最大的全1子矩阵.
: 想不出来,求教大家.
| c***z
发帖数: 6348 | 27 方阵的话用Dynamic Programming
/**************************************************************
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 Programming. Assume we are going
【在 t******i 的大作中提到】
: n*n 矩阵, 元素包括0 和1
: 求size(面积)最大的全1子矩阵.
: 想不出来,求教大家.
| c***z
发帖数: 6348 | 28 我最后做出来了，也被默拒了。MSFT
不过是第二天做出来的。。。
总之就是再无消息。 | c***z
发帖数: 6348 | 29
非方阵的我也做出来了，可是还是没有用。从此以后我就没有信心了。。。
/**************************************************************
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 the 2x5 submatrix (row 0~4, col 2~3)
1000010
0000100
001010
【在 I**********s 的大作中提到】
: 如果是正方形子矩阵, 答案见http://geeksforgeeks.org/?p=6257
: 属于DP, 时空复杂度都是O(n*n).
: 如果可以是长宽不等的子矩阵, 需要进一步考虑.
|
|
