请教一道著名CS面试题：最大黑边正方形# JobHunting - 待字闺中
b*a
1 楼
N×N矩阵，每个CELL或黑或白，要求找出最大正方形，边全部是黑的
感觉是Dynamic Programming, 但正方形似乎与矩形完全不同，请教正确答案，谢谢！
感觉是Dynamic Programming, 但正方形似乎与矩形完全不同，请教正确答案，谢谢！
g*s
2 楼
a(x,y) 表示到(x,y)的最长水平黑边 O(n*n)
b(x,y) 表示到(x,y)的最长竖直黑边 O(n*n)
c(x,y) 表示(x,y)为右上角的最大黑色正方形的边长。
c(x,y) = min ( a(x,y), b(x,y), c(x-1,y-1)+1) O(n*n)
所以，空间和时间复杂度都是O(n×n)
【在 b*******a 的大作中提到】
: N×N矩阵，每个CELL或黑或白，要求找出最大正方形，边全部是黑的
: 感觉是Dynamic Programming, 但正方形似乎与矩形完全不同，请教正确答案，谢谢！
b(x,y) 表示到(x,y)的最长竖直黑边 O(n*n)
c(x,y) 表示(x,y)为右上角的最大黑色正方形的边长。
c(x,y) = min ( a(x,y), b(x,y), c(x-1,y-1)+1) O(n*n)
所以，空间和时间复杂度都是O(n×n)
【在 b*******a 的大作中提到】
: N×N矩阵，每个CELL或黑或白，要求找出最大正方形，边全部是黑的
: 感觉是Dynamic Programming, 但正方形似乎与矩形完全不同，请教正确答案，谢谢！
g*s
3 楼
如果是黑边白芯呢？
【在 g***s 的大作中提到】
: a(x,y) 表示到(x,y)的最长水平黑边 O(n*n)
: b(x,y) 表示到(x,y)的最长竖直黑边 O(n*n)
: c(x,y) 表示(x,y)为右上角的最大黑色正方形的边长。
: c(x,y) = min ( a(x,y), b(x,y), c(x-1,y-1)+1) O(n*n)
: 所以，空间和时间复杂度都是O(n×n)
【在 g***s 的大作中提到】
: a(x,y) 表示到(x,y)的最长水平黑边 O(n*n)
: b(x,y) 表示到(x,y)的最长竖直黑边 O(n*n)
: c(x,y) 表示(x,y)为右上角的最大黑色正方形的边长。
: c(x,y) = min ( a(x,y), b(x,y), c(x-1,y-1)+1) O(n*n)
: 所以，空间和时间复杂度都是O(n×n)
b*n
4 楼
怎么看着是 O(n^3)
谢！
【在 g***s 的大作中提到】
: a(x,y) 表示到(x,y)的最长水平黑边 O(n*n)
: b(x,y) 表示到(x,y)的最长竖直黑边 O(n*n)
: c(x,y) 表示(x,y)为右上角的最大黑色正方形的边长。
: c(x,y) = min ( a(x,y), b(x,y), c(x-1,y-1)+1) O(n*n)
: 所以，空间和时间复杂度都是O(n×n)
谢！
【在 g***s 的大作中提到】
: a(x,y) 表示到(x,y)的最长水平黑边 O(n*n)
: b(x,y) 表示到(x,y)的最长竖直黑边 O(n*n)
: c(x,y) 表示(x,y)为右上角的最大黑色正方形的边长。
: c(x,y) = min ( a(x,y), b(x,y), c(x-1,y-1)+1) O(n*n)
: 所以，空间和时间复杂度都是O(n×n)
j*x
5 楼
公式是错的
这个貌似只适用于求“全部是黑色”的正方形
【在 g***s 的大作中提到】
: a(x,y) 表示到(x,y)的最长水平黑边 O(n*n)
: b(x,y) 表示到(x,y)的最长竖直黑边 O(n*n)
: c(x,y) 表示(x,y)为右上角的最大黑色正方形的边长。
: c(x,y) = min ( a(x,y), b(x,y), c(x-1,y-1)+1) O(n*n)
: 所以，空间和时间复杂度都是O(n×n)
这个貌似只适用于求“全部是黑色”的正方形
【在 g***s 的大作中提到】
: a(x,y) 表示到(x,y)的最长水平黑边 O(n*n)
: b(x,y) 表示到(x,y)的最长竖直黑边 O(n*n)
: c(x,y) 表示(x,y)为右上角的最大黑色正方形的边长。
: c(x,y) = min ( a(x,y), b(x,y), c(x-1,y-1)+1) O(n*n)
: 所以，空间和时间复杂度都是O(n×n)
g*s
6 楼
Sorry, my mistake. Didn't read the question carefully.
So, we need to change a little:
c(x,y) = max t,
0 <=t <= min ( a[x,y], b[x,y] ]
b(x-t+1,y) >= t && a(x, y-t+1) >= t
this step needs O(n). So total time is O(n^3) and space is O(n^2).
【在 g*********s 的大作中提到】
: 如果是黑边白芯呢？
So, we need to change a little:
c(x,y) = max t,
0 <=t <= min ( a[x,y], b[x,y] ]
b(x-t+1,y) >= t && a(x, y-t+1) >= t
this step needs O(n). So total time is O(n^3) and space is O(n^2).
【在 g*********s 的大作中提到】
: 如果是黑边白芯呢？
l*y
7 楼
Could you please elaborate the solution?
Thanks a lot!
【在 g***s 的大作中提到】
: Sorry, my mistake. Didn't read the question carefully.
: So, we need to change a little:
: c(x,y) = max t,
: 0 <=t <= min ( a[x,y], b[x,y] ]
: b(x-t+1,y) >= t && a(x, y-t+1) >= t
: this step needs O(n). So total time is O(n^3) and space is O(n^2).
Thanks a lot!
【在 g***s 的大作中提到】
: Sorry, my mistake. Didn't read the question carefully.
: So, we need to change a little:
: c(x,y) = max t,
: 0 <=t <= min ( a[x,y], b[x,y] ]
: b(x-t+1,y) >= t && a(x, y-t+1) >= t
: this step needs O(n). So total time is O(n^3) and space is O(n^2).
c*0
8 楼
My solution:
我们首先第一次循环 一列一列的 找到每一列的所有的连续黑边 每一个黑边用一个坐
标 (x,y)和垂直长度 l 表示
之后一行一行的循环 找到每一行所有连续的黑边 每个黑边用(x,y)加水平长度l表示
之后对每个竖向的黑边 check 存不存在对应的一个竖向的黑边和两个水平的黑边，这
个check应该是很快的 O(1)或者O(lgn) 取决于怎么存连续黑边
这样是不是O(n^2)的复杂度？
我们首先第一次循环 一列一列的 找到每一列的所有的连续黑边 每一个黑边用一个坐
标 (x,y)和垂直长度 l 表示
之后一行一行的循环 找到每一行所有连续的黑边 每个黑边用(x,y)加水平长度l表示
之后对每个竖向的黑边 check 存不存在对应的一个竖向的黑边和两个水平的黑边，这
个check应该是很快的 O(1)或者O(lgn) 取决于怎么存连续黑边
这样是不是O(n^2)的复杂度？
g*s
9 楼
0 <=t <= a[x,y] 这个保证上边是黑的
0 <=t <= b[x,y] 这个保证右边是黑的
b(x-t+1,y) >= t 这个保证左边是黑的
a(x, y-t+1)>= t 这个保证下边是黑的
W W B B B B
W B B B W B
W W B W W B
B B B B B B
W W W W W B
W W W W W W
give a sample,
c(6,6) = 4
a(6,6) = 4
b(6,6) = 5
b(3,6) = 4 >=4
a(6,3) = 6 >=4
【在 l*********y 的大作中提到】
: Could you please elaborate the solution?
: Thanks a lot!
0 <=t <= b[x,y] 这个保证右边是黑的
b(x-t+1,y) >= t 这个保证左边是黑的
a(x, y-t+1)>= t 这个保证下边是黑的
W W B B B B
W B B B W B
W W B W W B
B B B B B B
W W W W W B
W W W W W W
give a sample,
c(6,6) = 4
a(6,6) = 4
b(6,6) = 5
b(3,6) = 4 >=4
a(6,3) = 6 >=4
【在 l*********y 的大作中提到】
: Could you please elaborate the solution?
: Thanks a lot!
g*s
10 楼
~~~this is not easy to get in O(1) or O(lgn).
sample: all (1,y) = B, all (2, even number) = B
now, there are O(n) 水平边.
B
BB
B
BB
B
BB
B
BB
B
【在 c********0 的大作中提到】
: My solution:
: 我们首先第一次循环 一列一列的 找到每一列的所有的连续黑边 每一个黑边用一个坐
: 标 (x,y)和垂直长度 l 表示
: 之后一行一行的循环 找到每一行所有连续的黑边 每个黑边用(x,y)加水平长度l表示
: 之后对每个竖向的黑边 check 存不存在对应的一个竖向的黑边和两个水平的黑边，这
: 个check应该是很快的 O(1)或者O(lgn) 取决于怎么存连续黑边
: 这样是不是O(n^2)的复杂度？
g*k
11 楼
这些个变量都是什么？
神马叫做 到(x,y)的最长黑边？
即便是求黑方块，这也是错的。
【在 g***s 的大作中提到】
: a(x,y) 表示到(x,y)的最长水平黑边 O(n*n)
: b(x,y) 表示到(x,y)的最长竖直黑边 O(n*n)
: c(x,y) 表示(x,y)为右上角的最大黑色正方形的边长。
: c(x,y) = min ( a(x,y), b(x,y), c(x-1,y-1)+1) O(n*n)
: 所以，空间和时间复杂度都是O(n×n)
神马叫做 到(x,y)的最长黑边？
即便是求黑方块，这也是错的。
【在 g***s 的大作中提到】
: a(x,y) 表示到(x,y)的最长水平黑边 O(n*n)
: b(x,y) 表示到(x,y)的最长竖直黑边 O(n*n)
: c(x,y) 表示(x,y)为右上角的最大黑色正方形的边长。
: c(x,y) = min ( a(x,y), b(x,y), c(x-1,y-1)+1) O(n*n)
: 所以，空间和时间复杂度都是O(n×n)
g*s
12 楼
你没看懂得话怎么看出是错的？
【在 g*****k 的大作中提到】
: 这些个变量都是什么？
: 神马叫做 到(x,y)的最长黑边？
: 即便是求黑方块，这也是错的。
【在 g*****k 的大作中提到】
: 这些个变量都是什么？
: 神马叫做 到(x,y)的最长黑边？
: 即便是求黑方块，这也是错的。
r*h
13 楼
very nice
【在 g***s 的大作中提到】
: 0 <=t <= a[x,y] 这个保证上边是黑的
: 0 <=t <= b[x,y] 这个保证右边是黑的
: b(x-t+1,y) >= t 这个保证左边是黑的
: a(x, y-t+1)>= t 这个保证下边是黑的
: W W B B B B
: W B B B W B
: W W B W W B
: B B B B B B
: W W W W W B
: W W W W W W
【在 g***s 的大作中提到】
: 0 <=t <= a[x,y] 这个保证上边是黑的
: 0 <=t <= b[x,y] 这个保证右边是黑的
: b(x-t+1,y) >= t 这个保证左边是黑的
: a(x, y-t+1)>= t 这个保证下边是黑的
: W W B B B B
: W B B B W B
: W W B W W B
: B B B B B B
: W W W W W B
: W W W W W W
U*R
14 楼
I like this solution!
【在 g***s 的大作中提到】
: 0 <=t <= a[x,y] 这个保证上边是黑的
: 0 <=t <= b[x,y] 这个保证右边是黑的
: b(x-t+1,y) >= t 这个保证左边是黑的
: a(x, y-t+1)>= t 这个保证下边是黑的
: W W B B B B
: W B B B W B
: W W B W W B
: B B B B B B
: W W W W W B
: W W W W W W
【在 g***s 的大作中提到】
: 0 <=t <= a[x,y] 这个保证上边是黑的
: 0 <=t <= b[x,y] 这个保证右边是黑的
: b(x-t+1,y) >= t 这个保证左边是黑的
: a(x, y-t+1)>= t 这个保证下边是黑的
: W W B B B B
: W B B B W B
: W W B W W B
: B B B B B B
: W W W W W B
: W W W W W W
b*a
15 楼
Thanks! This solution looks right.
【在 g***s 的大作中提到】
: a(x,y) 表示到(x,y)的最长水平黑边 O(n*n)
: b(x,y) 表示到(x,y)的最长竖直黑边 O(n*n)
: c(x,y) 表示(x,y)为右上角的最大黑色正方形的边长。
: c(x,y) = min ( a(x,y), b(x,y), c(x-1,y-1)+1) O(n*n)
: 所以，空间和时间复杂度都是O(n×n)
【在 g***s 的大作中提到】
: a(x,y) 表示到(x,y)的最长水平黑边 O(n*n)
: b(x,y) 表示到(x,y)的最长竖直黑边 O(n*n)
: c(x,y) 表示(x,y)为右上角的最大黑色正方形的边长。
: c(x,y) = min ( a(x,y), b(x,y), c(x-1,y-1)+1) O(n*n)
: 所以，空间和时间复杂度都是O(n×n)
e*e
16 楼
如果这题目变变，变成长方形，黑边就可以了。。
求最大（周长最大比如）咋办？
求最大（周长最大比如）咋办？
相关阅读
二维数组问题bloomberg的phone interview邮件内容是空的山人现场完求不累死F家电面Linux 的困惑。paypal phoenix opening (urgent)是准备充分重要还是赶时间重要请教Offer选择: IBM vs. Cisco真诚地请教各位GG或者JJ一个问题！求二叉树最大路径和的变体题准备动手找工作了，现在那些渠道比较有效？能不能用OPT先工作，然后quit 当前的program申请OPT用的白底相片哪里可以照呢？Chciago地区有哪些猎头公司啊？去epic面试的一点问题烧香拜佛求bless 下周三个onsite请问毕业以前可以转成H1B签证吗？ebay的面试谁有经验啊? new grad software engineer请教Google onsite 问题onsite可以要求几个月之后再去么？