careerup 150的一道经典题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

careerup 150的一道经典题

careerup 150的一道经典题# JobHunting - 待字闺中

P*c2011-07-04 07:07

1 楼

20.11 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.
书上给的解法是 O(n^2)么？我怎么觉得是O(n^4）呢。有人可以解释下为啥是O(n^2)吗？
她的基本思路就是：
从第一列开始
－－第一行开始从最大的正方形开始找，如果不满足，那么size--, 直到size小于当前
的maxSize
－－第一行找完后从第二行开始, 一直到剩下的最大size小于当前的maxSize
第一列找完后开始第二列，找到剩下的列小于当前的maxiSize为止。
这个方法为什么是O(n^2)呢？

g*s2011-07-04 07:07

2 楼

DP保存状态。

吗？

【在 P**********c 的大作中提到】

: 20.11 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.
: 书上给的解法是 O(n^2)么？我怎么觉得是O(n^4）呢。有人可以解释下为啥是O(n^2)吗？
: 她的基本思路就是：
: 从第一列开始
: －－第一行开始从最大的正方形开始找，如果不满足，那么size--, 直到size小于当前
: 的maxSize
: －－第一行找完后从第二行开始, 一直到剩下的最大size小于当前的maxSize
: 第一列找完后开始第二列，找到剩下的列小于当前的maxiSize为止。

P*c2011-07-04 07:07

3 楼

书上这个解法用了DP保存状态吗？哪里体现出来的？

【在 g***s 的大作中提到】

: DP保存状态。
:
: 吗？

g*s2011-07-04 07:07

4 楼

没看过这本书。从你的转述来看，不像是O(n^2)。
这里早些时候有这题的讨论，还有这题的一些延伸。

【在 P**********c 的大作中提到】

: 书上这个解法用了DP保存状态吗？哪里体现出来的？

s*n2011-07-04 07:07

5 楼

因为是subsquare,所以还是一维的问题。

【在 P**********c 的大作中提到】

: 书上这个解法用了DP保存状态吗？哪里体现出来的？

g*y2011-07-04 07:07

6 楼

这是书上的答案，它把isSquare()当成O(1)的operation.
1 public static Subsquare findSquare(int[][] matrix){
2 assert(matrix.length > 0);
3 for (int row = 0; row < matrix.length; row++){
4 assert(matrix[row].length == matrix.length);
5 }
6
7 int N = matrix.length;
8
9 int currentMaxSize = 0;
10 Subsquare sq = null;
11 int col = 0;
12
13 // Iterate through each column from left to right
14 while (N - col > currentMaxSize) { // See step 4 above
15 for (int row = 0; row < matrix.length; row++){
16 // starting from the biggest
17 int size = N - Math.max(row, col);
18 while (size > currentMaxSize){
19 if (isSquare(matrix, row, col, size)){
20 currentMaxSize = size;
21 sq = new Subsquare(row, col, size);
22 break; // go to next (full) column
23 }
24 size--;
25 }
26 }
27 col++;
28 }
29 return sq;
30 }
31
32 private static boolean isSquare(int[][] matrix, int row, int col,
33 int size) {
34 // Check top and bottom border.
35 for (int j = 0; j < size; j++){
36 if (matrix[row][col+j] == 1) {
37 return false;
38 }
39 if (matrix[row+size-1][col+j] == 1){
40 return false;
41 }
42 }
43
44 // Check left and right border.
45 for (int i = 1; i < size - 1; i++){
46 if (matrix[row+i][col] == 1){
47 return false;
48 }
49 if (matrix[row+i][col+size-1] == 1){
50 return false;
51 }
52 }
53 return true;
54 }
55
56 public class Subsquare {
57 public int row, column, size;
58 public Subsquare(int r, int c, int sz) {
59 row = r;
60 column = c;
61 size = sz;
62 }
63 }

P*c2011-07-04 07:07

7 楼

就算isSquare是O(1), 是不是也应该是O(n^3)呢，对每一sub列worst case是要
比较O(n)个square的size吧。

【在 g**********y 的大作中提到】

: 这是书上的答案，它把isSquare()当成O(1)的operation.
: 1 public static Subsquare findSquare(int[][] matrix){
: 2 assert(matrix.length > 0);
: 3 for (int row = 0; row < matrix.length; row++){
: 4 assert(matrix[row].length == matrix.length);
: 5 }
: 6
: 7 int N = matrix.length;
: 8
: 9 int currentMaxSize = 0;

s*n2011-07-04 07:07

8 楼

当然不是，不用优化的话，两个for loop搞定了。

【在 P**********c 的大作中提到】

: 就算isSquare是O(1), 是不是也应该是O(n^3)呢，对每一sub列worst case是要
: 比较O(n)个square的size吧。

P*c2011-07-04 07:07

9 楼

假设给的矩阵只有一个1，其他的都是0，我觉得每次从最大的开始，size--都要减很多次啊，肯定不是O(1)啊。

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

: 当然不是，不用优化的话，两个for loop搞定了。

c*t2011-07-04 07:07

10 楼

我觉得你说的是对的。应该是O(n^3).
另外，可以按行iterate也行。careercup上的是按列搜索。

【在 P**********c 的大作中提到】

: 就算isSquare是O(1), 是不是也应该是O(n^3)呢，对每一sub列worst case是要
: 比较O(n)个square的size吧。

c*t2011-07-04 07:07

11 楼

may I ask a question? Is n the total cell counts or the edge length?
If it is the previous, isn't O(n^2) correct?

吗？

【在 P**********c 的大作中提到】

d*y2011-07-04 07:07

12 楼

这个解法算brutal force吧。
应该是O(n4)。
isSquare()不能当做O(1)。

【在 g**********y 的大作中提到】

P*c2011-07-04 07:07

13 楼

No. The book says the matrix is n*n.
Anyway, I think the book made a mistake in evaluating the time complexity.
Can someone provide a link to the dynamic programming solution? Is that one
O(n^2)?

【在 c********t 的大作中提到】

: may I ask a question? Is n the total cell counts or the edge length?
: If it is the previous, isn't O(n^2) correct?
:
: 吗？

w*p2011-07-04 07:07

14 楼

我能坐到n^3. 通过一个n^2的预处理，可以做到 issquare() 在循环里面 O(1).
举个例子。0是白，1是黑。
10011
01110
01010
01111
做两个矩阵：一个是对于每一个元素（i，j），同一行从它开始的最大连续1的个数。
同理，做一个矩阵，对于同列连续的1的个数。这两矩阵就n^2做到。
比如行的矩阵 xcell，
10021
03210
01010
04321
和列的矩阵 ycell
10041
03030
02020
01011
给定任意个点(x,y)，和size k，就可以判断这个square是不是都是黑边的。
比如 (2,2,3), 只要看4个值，xcell[2,2]>=k, ycell[2,2]>=k, xcell[2+k,2]>=k and
ycell[2,2+k]>=k, 这里的 k=3.因为成立，所以issquare 是成立的。
但是不管是dp还是非 dp，我都只能做到 n cube。

w*p2011-07-04 07:07

15 楼

SORRY, 是xcell[2+k-1,2]>=k 和 ycell[2,2+k-1]>=k