还是得看了别人的思路才做出来。
依然是动态规划。
对于动态规划我还是掌握不好,难一点就想不清楚,不能好好解决,加上递归我就更加完蛋了。。。
class Solution: def maximalSquare(self, matrix) -> int: #print(len(matrix)) if len(matrix)<1: return 0 if len(matrix)==1 and len(matrix[0])==1: return int(matrix[0][0]) elif len(matrix)<2 or len(matrix[0])<2: for i in range(len(matrix)): if '1' in matrix[i]: return 1 return 0 else: i=0 while i<len(matrix): if '1' not in matrix[i]: i+=1 else: break if i==len(matrix): return 0 m=0 for i in range(1,len(matrix)): for j in range(1,len(matrix[0])): if matrix[i][j]=='0': if len(matrix)==2 and len(matrix[0])==2: return max(int(matrix[i-1][j-1]),int(matrix[i-1][j]),int(matrix[i][j-1])) else: continue else: matrix[i][j]=min(int(matrix[i-1][j-1]),int(matrix[i-1][j]),int(matrix[i][j-1]))+1 m=max(m,int(matrix[i][j])) if m==0: return 1 else: return m**2
执行用时 :244 ms, 在所有 python3 提交中击败了81.88%的用户
内存消耗 :14.9 MB, 在所有 python3 提交中击败了5.32%的用户
——2019.10.16