Leetcode 221. 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.Example:
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4
n3 method using 2d matrix presum
class Solution:
def maximalSquare(self, matrix: List]) -> int:
if matrix == None or len(matrix) == 0 or len(matrix) == 0:
return 0
sum_val = [) + 1)] for _ in range(len(matrix) + 1)]
for i in range(1, len(sum_val)):
for j in range(1, len(sum_val)):
sum_val = sum_val + sum_val - sum_val + int(matrix)
m = len(matrix)
n = len(matrix)
result = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
for size in range(1, min(m - i + 1, n - j + 1) + 1):
if sum_val - sum_val - sum_val + sum_val == (size) * (size):
result = max(result, (size) * (size))
return result
n2 method using dynamic programming
class Solution:
def maximalSquare(self, matrix: List]) -> int:
if matrix == None or len(matrix) == 0 or len(matrix) == 0:
return 0
size = [) + 1)] for _ in range(len(matrix) + 1)]
result = 0
for i in range(1, len(matrix) + 1):
for j in range(1, len(matrix) + 1):
if matrix == '1':
size = min(size, size, size) + 1
result = max(result, size)
return result * result
页:
[1]