h**6
发帖数: 4160 | 1 一个矩阵，所有元素都是0或者1，要在这个矩阵中寻找面积最大的
1)完全由1组成的矩形，正方形
2)四边由1组成的矩形，正方形
3)四个顶点是1的矩形，正方形
第一题我会，矩形和正方形都可以由动态规划求出。后面2, 3两题怎么求，有人有思路
吗？最低复杂度是多少呢？ | b******v
发帖数: 1493 | 2 re，这个系列的题感觉很难
我只会做第一题的正方形情形
【在 h**6 的大作中提到】
: 一个矩阵，所有元素都是0或者1，要在这个矩阵中寻找面积最大的
: 1)完全由1组成的矩形，正方形
: 2)四边由1组成的矩形，正方形
: 3)四个顶点是1的矩形，正方形
: 第一题我会，矩形和正方形都可以由动态规划求出。后面2, 3两题怎么求，有人有思路
: 吗？最低复杂度是多少呢？
| g*****t
发帖数: 42 | | b******v
发帖数: 1493 | 4 能否详细说说？
【在 g*****t 的大作中提到】
: 2，3都有O(n^2)解法。
| g*****t
发帖数: 42 | 5
不知道是不是最优
3最简单， 假设矩阵是n*m，从第一行开始， 按最大边长找， 如果左边两角为零， 左
边+1， 右边两角为零右边+1， 否则就是最大边长， 再从第二行往下找比最大边长大
的正方形。
2跟3类似， 生成两个特征矩阵， U(i,j) = Aik+...+Aij; (k
都为1） V(i,j) = Akj+...+Aij; (k
差可以算出是否符合条件，
1也一样， 生成特征矩阵， W(i,j) = 左上角是（0，0）右下角是（i,j)的矩阵中间的
所有值之和。 根据W可以算出3中正方形是否符合条件。
【在 b******v 的大作中提到】
: 能否详细说说？
| g*****u
发帖数: 298 | 6 能否用这个例子讲一下你的算法如何找出3的最大矩形
0 1 1 1
1 1 1 0
0 1 0 0
【在 g*****t 的大作中提到】
:
: 不知道是不是最优
: 3最简单， 假设矩阵是n*m，从第一行开始， 按最大边长找， 如果左边两角为零， 左
: 边+1， 右边两角为零右边+1， 否则就是最大边长， 再从第二行往下找比最大边长大
: 的正方形。
: 2跟3类似， 生成两个特征矩阵， U(i,j) = Aik+...+Aij; (k: 都为1） V(i,j) = Akj+...+Aij; (k: 差可以算出是否符合条件，
: 1也一样， 生成特征矩阵， W(i,j) = 左上角是（0，0）右下角是（i,j)的矩阵中间的
: 所有值之和。 根据W可以算出3中正方形是否符合条件。
| o****d
发帖数: 2835 | 7 请问第一题有O(n^2)解法吗
怎么做？ 谢谢
【在 b******v 的大作中提到】
: re，这个系列的题感觉很难
: 我只会做第一题的正方形情形
| b******v
发帖数: 1493 | 8 找最大全为1的正方形的情形：
依次扫描矩阵A的元素，生成矩阵B，
其中B(i,j)记录以A(i,j)为右下角最大的全为1的正方形的size
如果A(i,j) = 0, 则B(i,j) = 0
否则，如果A(i,j) = 1, 则让B(i,j) = 1+min{B(i-1,j), B(i,j-1), B(i-1,j-1)}
在扫描的同时用三个数分别记录最大的B(i,j)的值及其位置。
扫描完，就得到了想要的结果。时间复杂度O(m*n)。
其他的题不知道谁有好的方法？
【在 o****d 的大作中提到】
: 请问第一题有O(n^2)解法吗
: 怎么做？ 谢谢
| z*j
发帖数: 42 | 9 如果矩形，能否记录矩形的长和宽（ｘ，ｙ），然后再ｘ，ｙ 分别 1+min{B(i-1,j)
, B(i,j-1), B(i-1,j-1)}？ | s*****e
发帖数: 36 | 10 算法菜鸟，我的想法类似，但是
if A(i,j)=0, B(i,j)=0;
else
B(i,j)=B(i-1,j-1)+1 if A(i,k)=1, k: j-B(i-1,j-1)~j and
A(k,j)=1, k: i-B(i-1,j-1)~i
1 otherwise
这样的话，复杂度是不是 O(m*n*min(m,n))?
上面的min is nice，怎么想到用min呢?
j)
【在 z*j 的大作中提到】
: 如果矩形，能否记录矩形的长和宽（ｘ，ｙ），然后再ｘ，ｙ 分别 1+min{B(i-1,j)
: , B(i,j-1), B(i-1,j-1)}？
| z*j
发帖数: 42 | 11 I haven't proved it is correct yet, actually I think I am wrong and your
method is correct.
【在 s*****e 的大作中提到】
: 算法菜鸟，我的想法类似，但是
: if A(i,j)=0, B(i,j)=0;
: else
: B(i,j)=B(i-1,j-1)+1 if A(i,k)=1, k: j-B(i-1,j-1)~j and
: A(k,j)=1, k: i-B(i-1,j-1)~i
: 1 otherwise
: 这样的话，复杂度是不是 O(m*n*min(m,n))?
: 上面的min is nice，怎么想到用min呢?
:
: j)
| b********h
发帖数: 119 | 12 I think you are right. Basically, you are finding the intersection of three
rectangles. And the right and bottom borders of the intersection are covered
by B(i-1,j) and B(i,j-1). On the other hand, the recursion that only
considers B(i-1,j-1) would fail on the following test case:
11
00
【在 z*j 的大作中提到】
: I haven't proved it is correct yet, actually I think I am wrong and your
: method is correct.
| l*********y
发帖数: 142 | 13 还有牛人follow这个帖子吗？
到现在我只有1) 的正方形有最优解,楼上讨论的1)的矩形对吗?
110
010
111
111
右下角Entry (3,2) 的最大面积矩形是2*3 = 6. 怎么求出的?
2) 和 3)完全没懂楼上的讨论.
【在 h**6 的大作中提到】
: 一个矩阵，所有元素都是0或者1，要在这个矩阵中寻找面积最大的
: 1)完全由1组成的矩形，正方形
: 2)四边由1组成的矩形，正方形
: 3)四个顶点是1的矩形，正方形
: 第一题我会，矩形和正方形都可以由动态规划求出。后面2, 3两题怎么求，有人有思路
: 吗？最低复杂度是多少呢？
|
|
