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 | x****r 发帖数: 99 | 2 同问,,,这题我看他的解也很迷茫,感觉那个电子书里面有的复杂度是乱说的,比如
matrix里面找
max sub-matrix sum那题他的优化只做了一半只能到N^5,还有N^4和N^3的解法都没说
four
smallest).
the
【在 i****h 的大作中提到】 : 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
| h**6 发帖数: 4160 | 3 这题应该有N^3的解法,楼主所列的方法,恐怕是N^4的 |
|