问个老题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个老题

问个老题# JobHunting - 待字闺中

l*n2012-10-14 07:10

1 楼

Give a square matrix with n x n cells. Each cell is either filled with a
black pixel or a white pixel. Design an algorithm to find the maximum
subsquare such that all four borders are filled with black pixels;
Note: it is not the same as the wellknown question for the max sub-matrix
with all filled 0/1.... so the DP equation does not apply here..
Any good approach better than brute force?

p*22012-10-14 07:10

2 楼

你老怎么也上来做题了？夫人吗。

p*22012-10-14 07:10

3 楼

你说的bruteforce是什么复杂度？ N^3?

l*a2012-10-14 07:10

4 楼

牛人不都是拿着18W的offer然后准备找25W的？

【在 p*****2 的大作中提到】

: 你老怎么也上来做题了？夫人吗。

l*a2012-10-14 07:10

5 楼

brute force应该是N4

【在 p*****2 的大作中提到】

: 你说的bruteforce是什么复杂度？ N^3?

l*n2012-10-14 07:10

6 楼

二爷您还在这坐镇呢：） yes, this is LD
N^3 is the minimum I can think , with some auxiliary space. The most naive
brute force is actually N^4..
等待二爷高招

p*22012-10-14 07:10

7 楼

感觉N^3是不是就行了？

【在 l*****n 的大作中提到】

: 二爷您还在这坐镇呢：） yes, this is LD
: N^3 is the minimum I can think , with some auxiliary space. The most naive
: brute force is actually N^4..
: 等待二爷高招

l*a2012-10-14 07:10

8 楼

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. If N - currentColumn <= currentMaxSize, then break completely. We've
found the largest square possible. Why? At each column, we're trying to
create a square with that column as the left side. The largest such square
we could possibly create is N - currentColumn. Thus, if N-currentColumn <=
currentMaxSize, then we have no need to proceed.
Time complexity: O(N^2).