n*******s
发帖数: 482 | 1 you are given a M x N matrix with 0's and 1's
find the matrix with largest number of 1,
1. find the largest square matrix with 1's
2. Find the largest rectangular matrix with 1's
没想到很有效的办法。大家见集思广益~ | b*********n
发帖数: 1258 | 2 where do u see this?
【在 n*******s 的大作中提到】
: you are given a M x N matrix with 0's and 1's
: find the matrix with largest number of 1,
: 1. find the largest square matrix with 1's
: 2. Find the largest rectangular matrix with 1's
: 没想到很有效的办法。大家见集思广益~
| h*********i
发帖数: 116 | | h*********i
发帖数: 116 | 4 我好像写过这道题的code。
【在 n*******s 的大作中提到】
: you are given a M x N matrix with 0's and 1's
: find the matrix with largest number of 1,
: 1. find the largest square matrix with 1's
: 2. Find the largest rectangular matrix with 1's
: 没想到很有效的办法。大家见集思广益~
| n*******s
发帖数: 482 | 5 careercup::amazon
我笨，感觉是DP,不过没建出递归模型。 | q******u
发帖数: 46 | 6 1有O(MN)的算法，关键就是用integral image只要O(1)就能check一个square or recta
ngle是不是满的。
具体做法令B(x0,y0)=sum_{x<=x0,y<=y0}A(x,y), A(x,y)=0/1。这样B(x0,y0)+B(x1,y1
)-B(x0,y1)-B(x1,y0)就是(x0,y0,x1,y1)中1的个数。
问题1就沿对角线y-x=k扫描，用DP可以在linear时间内解决。其中用到上面的trick去c
heck。
【在 n*******s 的大作中提到】
: you are given a M x N matrix with 0's and 1's
: find the matrix with largest number of 1,
: 1. find the largest square matrix with 1's
: 2. Find the largest rectangular matrix with 1's
: 没想到很有效的办法。大家见集思广益~
| s*********l
发帖数: 103 | 7 http://www.spellscroll.com/questionfull/275/
【在 n*******s 的大作中提到】
: you are given a M x N matrix with 0's and 1's
: find the matrix with largest number of 1,
: 1. find the largest square matrix with 1's
: 2. Find the largest rectangular matrix with 1's
: 没想到很有效的办法。大家见集思广益~
|
|
