[LeetCode] 221. Maximal Square _ Medium Tag: Dynamic Program

发布时间：2020-12-14 03:20:56 所属栏目：大数据来源：网络整理

导读：Given a 2D binary matrix filled with 0‘s and 1‘s,find the largest square containing only 1‘s and return its area. Example: Input: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0Output: 4 思路是DP,3种做法,通用的T: O(m*n),S: O(m*n) 和只针对部分情况

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

Example:

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4


思路是DP,3种做法,通用的T: O(m*n),S: O(m*n)  和只针对部分情况可以use 滚动数组来reduce space成为O(n).
A[i][j] = min(A[i-1][j-1],left[i][j-1],up[i-1][j]) + 1 为边长  i,j > 0

滚动数组

A[i][j] = min(A[i-1][j-1],A[i][j-1],A[i-1][j]) + 1 为边长  i,j > 0

A[i][j] = min(A[i%2-1][j-1],A[i%2][j-1],A[i%2-1][j]) + 1 为边长  i,j > 0



1. Constraints
1) size >=[0*0]
2) element will be "1" or "0"  # note it will be integer or string

2. Ideas

DP     T: O(m*n)   S: O(n)  optimal
1) edge case,empty,m == 1 or n == 1
2) left,up,ans,init
3)

A[i][j] = min(A[i-1][j-1],up[i-1][j]) + 1
4) return res*res

3. codes

1) use left,and ans   T: O(m*n)    S: O(m*n)

 1 class Solution:
 2     def maxSquare(self,matrix):
 3         if not matrix: return 0
 4         m,n = len(matrix),len(matrix[0])
 5         left,res = [[0]*n for _ in range(m)],[[0]*n for _ in range(m)],[[0]*n for _ in range(m)],0
 6         for i in range(m):
 7             for j in range(n):
 8                 if matrix[i][j] == "1":
 9                     res = 1   # edge case when m == 1 or n == 1
10                     if j == 0:
11                         left[i][j] = ans[i][j] = 1
12                     if i == 0:
13                         up[i][j] = ans[i][j] = 1
14                     if i >0 and j > 0:
15                         left[i][j] = left[i][j-1] + 1
16                         up[i][j] = up[i-1][j] + 1
17         for i in range(1,m):
18             for j in range(1,n):
19                 if matrix[i][j] == "1":
20                     ans[i][j] = min(ans[i-1][j-1],up[i-1][j])+1
21                     res = max(res,ans[i][j])
22         return res*res

3.2) skip left and up,just use ans array

 1 class Solution:
 2     def maxSquare(self,len(matrix[0])
 5         ans,temp,res = [[0]*n for _ in range(m)],0
 6         for i in range(m):
 7             for j in range(n):
 8                 if matrix[i][j] == "1":
 9                     temp = 1
10                     ans[i][0] = int(matrix[i][0])
11                     ans[0][j] = int(matrix[0][j])
12                     if i > 0 and j >0 :
13                         ans[i][j] = min(ans[i-1][j-1],ans[i][j-1],ans[i-1][j]) + 1
14                         res = max(res,ans[i][j])
15         
16         return max(res,temp )**2

3.3) 滚动数组,? ?T: O(m*n),? ? S: O(n)

 1 class Solution:
 2     def maxSquare(self,res = [[0]*n for _ in range(2)],0
 6         for j in range(n):  # note initialize when using rolling array
 7             if matrix[0][j] == "1":
 8                 temp = 1
 9                 ans[0][j] = int(matrix[0][j])
10         for i in range(1,m):
11             for j in range(n):
12                 if j == 0:  # initialize
13                     ans[i%2][0] = int(matrix[i][0])
14                 if matrix[i][j] == "1":
15                     temp = 1  
16                     if i > 0 and j >0 :
17                         ans[i%2][j] = min(ans[i%2-1][j-1],ans[i%2][j-1],ans[i%2-1][j]) + 1
18                         res = max(res,ans[i%2][j])
19                 else:   # very important for initialize 
20                     ans[i%2][j] = 0
21         return max(res,temp )**2

4. Test cases

1) edge case

2)?

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!