leetcode——221. 最大正方形

还是得看了别人的思路才做出来。

依然是动态规划。

对于动态规划我还是掌握不好，难一点就想不清楚，不能好好解决，加上递归我就更加完蛋了。。。

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