Letcode 221 최대 정사각형
제목: 0과 1로 구성된 2차원 행렬에서 1만 포함된 최대 정사각형을 찾아 그 면적을 되돌려줍니다.
예:
입력:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
: 4
분석:
class Solution:
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if matrix == []: return 0
M, N = len(matrix), len(matrix[0])
dp = [[0 for _ in range(N)]for _ in range(M)]
Max = 0
for i in range(N): # dp
dp[0][i] = int(matrix[0][i])
Max = max(dp[0][i], Max)
for i in range(M): # dp
dp[i][0] = int(matrix[i][0])
Max = max(dp[i][0], Max)
for i in range(1, M):
for j in range(1, N):
if matrix[i][j] == '0': continue
dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
Max = max(dp[i][j], Max)
return Max**2
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
