i****h
发帖数: 321 | 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.
解释是：
This algorithm does the following:
1. Iterate through every (full) column from left 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 th |
|
s*********0
发帖数: 89 | 2 大家觉得呢？
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... 阅读全帖 |
|
l*****a
发帖数: 559 | 3 Copied the answer from careercup150. I can hardly understand the algorithm
which claimed to have complexity O^2.
Assumption: Square is of size NxN.
This algorithm does the following:
1. Iterate through every (full) column from left to right.
2. At each (full) column (call this currentColumn), 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.... 阅读全帖 |
|
w****x
发帖数: 2483 | 4 careercup上的一道题：
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 left to right.
2. At each (full) column (call this currentColumn), look at the subcolumns (
from biggest to smallest).
3. At each subcolumn, see if you can form a square with ... 阅读全帖 |
|
f****b
发帖数: 486 | 5 the problem is listed in the book from zhiyebei.
column by column scannning, then check the subcolumn for possible max square
, complexity O(n^2)
filled |
|
c********t
发帖数: 5706 | 6 不会吧，光第2步，求每个column的subColumn都已经不止O(N^2)了啊
that
(
the |
|
c********t
发帖数: 5706 | 7 我是觉得光扫一遍就n^2了，
找subcolumn 相当于找所有subset吧,是n^2 乘以column num = n^3,再每个验证square
，又是n 所以总的是 n^4
他是不是把matrix 元素总数算n啊（不是边长）那就是N^2 |
|
