h**6 发帖数: 4160 | 1 一个矩阵,所有元素都是0或者1,要在这个矩阵中寻找面积最大的
1)完全由1组成的矩形,正方形
2)四边由1组成的矩形,正方形
3)四个顶点是1的矩形,正方形
第一题我会,矩形和正方形都可以由动态规划求出。后面2, 3两题怎么求,有人有思路
吗?最低复杂度是多少呢? | b******v 发帖数: 1493 | 2 re,这个系列的题感觉很难
我只会做第一题的正方形情形
【在 h**6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一个矩阵,所有元素都是0或者1,要在这个矩阵中寻找面积最大的 : 1)完全由1组成的矩形,正方形 : 2)四边由1组成的矩形,正方形 : 3)四个顶点是1的矩形,正方形 : 第一题我会,矩形和正方形都可以由动态规划求出。后面2, 3两题怎么求,有人有思路 : 吗?最低复杂度是多少呢?
| g*****t 发帖数: 42 | | b******v 发帖数: 1493 | 4 能否详细说说?
【在 g*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能否详细说说?
| g*****u 发帖数: 298 | 6 能否用这个例子讲一下你的算法如何找出3的最大矩形
0 1 1 1
1 1 1 0
0 1 0 0
【在 g*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 不知道是不是最优 : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请问第一题有O(n^2)解法吗 : 怎么做? 谢谢
| z*j 发帖数: 42 | 9 如果矩形,能否记录矩形的长和宽(x,y),然后再x,y 分别 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果矩形,能否记录矩形的长和宽(x,y),然后再x,y 分别 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 算法菜鸟,我的想法类似,但是 : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一个矩阵,所有元素都是0或者1,要在这个矩阵中寻找面积最大的 : 1)完全由1组成的矩形,正方形 : 2)四边由1组成的矩形,正方形 : 3)四个顶点是1的矩形,正方形 : 第一题我会,矩形和正方形都可以由动态规划求出。后面2, 3两题怎么求,有人有思路 : 吗?最低复杂度是多少呢?
|
|