Code & Fun

第50天。

恍恍惚惚,就50天了。

今天的题目是Maximal Square:

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:

1
2
3
4
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

让人很意外,这是一道动态规划的题目。

先说说我的非动态规划的解法:

大概的想法是,做一次遍历,每次遇到1,就向下拓展,如果扩展,扩展的方法是就是只需要看当前正方形的外围是否都是1,如果都是1,那么我们就可以继续向下扩展,这样就可以遍历出一个正方形,然后我们在对matrix进行遍历的时候还可以通过当前的最大面积来提早结束遍历:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def expend(self,matrix,i,j,ret):
"""
:type matrix: List[List[str]]
:type i: int
:type j: int
:type ret: int
:rtype ret
"""
if i >= len(matrix) or j >= len(matrix[0]):
return ret
for k in range(ret+1):
if matrix[i][j - k] == '0' or matrix[i-k][j] == '0':
return ret
return self.expend(matrix,i+1,j+1,ret+1)

def maximalSquare1(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
ret,i = 0,0
while i + ret < len(matrix):
j = 0
while j + ret < len(matrix[0]):
if matrix[i][j] == '1':
ret = max(ret,self.expend(matrix,i+1,j+1,1))
j += 1
i += 1
return ret*ret

挺暴力的方法,不知道是不是因为可以提前结束,所以这个方法也直接AC了。

然后是DP的解法。

在解决这个问题之前,我们先考虑如果求出以matrix[i][j]为右下角的正方形最大面积。

如果matrix[i][j] = '0',那么显然size[i][j] = 0
如果matrix[i][j] = '1',那么我们需要考虑其向上,向左,向左上的最大面积。

假设size[i-1][j-1] = 2,则我们至少可以知道:

1
2
3
4
5
[
[1,1,*]
[1,1,*]
[*,*,-]
]

如果size[i][j-1] = 2,我们至少知道:

1
2
3
4
5
[
[*,*,*]
[1,1,*]
[1,1,-]
]

如果size[i-1][j] = 2,我们至少知道:

1
2
3
4
5
[
[*,1,1]
[*,1,1]
[*,*,-]
]

从上面可以看出来,只有当size[i-1][j-1] == 2 and size[i][j-1] == 2 and size[i-1][j-1] == 2时,size[i][j] == 3,

则我们可以得出以下递推式:

size[i][j] = min(size[i-1][j-1],size[i][j-1],size[i-1][j])+1 if matrix[i][j] == '1'
size[i][j] = 0 if matrix[i][j] == '0'

然后我们还需要考虑一下边界条件,因为当i=0j=0时,上面的递推式是没有考虑到的,我们再加上:

size[i][j] = (matrix[i][j] == '1') where i == 0 or j == 0

然后我们就可以写出以下解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def maximalSquare(self,matrix):
if len(matrix) == 0:
return 0
dp1 = []
ret = 0
for i in range(len(matrix[0])):
t = int(matrix[0][i] == '1')
dp1.append(t)
ret = max(ret,t)
for i in range(1,len(matrix)):
dp2 = [ 0 for i in range(len(matrix[0])) ]
dp2[0] = int(matrix[i][0] == '1')
ret = max(dp2[0],ret)
for j in range(1,len(matrix[0])):
if matrix[i][j] == '1':
dp2[j] = min(min(dp1[j-1],dp1[j]),dp2[j-1]) + 1
ret = max(ret,dp2[j])
dp1 = dp2
return ret*ret

本文首发于Code & Fun