这两道题（CareerCup 150)的答案是不是有问题啊？# JobHunting - 待字闺中
s*0
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.
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.
