s*********0
发帖数: 89 | 1 大家觉得呢？
Imagine you have a square matrix, where each cell is filled with either
black or
white. Design an algorithm to find the maximum subsquare such that all four
borders are filled with black pixels.
Assumption: Square is of size NxN.
This algorithm does the following:
1. Iterate through every (full) column from let to right.
2. At each (full) column, look at the subcolumns (from biggest to smallest).
3. At each subcolumn, see if you can form a square with the subcolumn as the
left side. If
so, update currentMaxSize and go to the next (full) column.
4. If N - col <= currentMaxSize, then break completely. We’ve found the
largest square
possible.
。。。
Time complexity: O(N^2)
不觉得可以是O(N^2). 光是step 2就要N^2了。加上step 1的循环，就是N^3了。而且
step 3要用O（1）需要pre-processing. | j******8
发帖数: 191 | 2 too simple, sometimes too naive.
four
smallest).
the
【在 s*********0 的大作中提到】
: 大家觉得呢？
: Imagine you have a square matrix, where each cell is filled with either
: black or
: white. Design an algorithm to find the maximum subsquare such that all four
: borders are filled with black pixels.
: Assumption: Square is of size NxN.
: This algorithm does the following:
: 1. Iterate through every (full) column from let to right.
: 2. At each (full) column, look at the subcolumns (from biggest to smallest).
: 3. At each subcolumn, see if you can form a square with the subcolumn as the
|
|
