classSolution: deflargest1BorderedSquare(self, grid: List[List[int]]) -> int: matrix_heng = copy.deepcopy(grid) matrix_su = copy.deepcopy(grid) ans = 0 iflen(grid) == 1: if1in grid[0]: return1 else:return0 for ind, i inenumerate(grid): for index inrange(len(i)): # 每一行相加 if index >= 1: matrix_heng[ind][index] += matrix_heng[ind][index-1] # 每一列相加 if ind >= 1: matrix_su[ind][index] += matrix_su[ind-1][index] print(matrix_heng, matrix_su) for i inrange(len(grid)): for j inrange(len(grid[i])): minus = min(matrix_heng[i][j], matrix_su[i][j]) try: if grid[i-minus+1][j-minus+1] == 1and i >= minus-1and j >= minus-1: ans = max(ans, minus ** 2) except: pass return ans
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution: deflargest1BorderedSquare(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) rs = [list(accumulate(row, initial=0)) for row in grid] # 每行的前缀和 cs = [list(accumulate(col, initial=0)) for col inzip(*grid)] # 每列的前缀和 for d inrange(min(m, n), 0, -1): # 从大到小枚举正方形边长 d for i inrange(m - d + 1): for j inrange(n - d + 1): # 枚举正方形左上角坐标 (i,j) # 上 左 下 右 四条边 1 的个数均为 d if rs[i][j + d] - rs[i][j] == d and \ cs[j][i + d] - cs[j][i] == d and \ rs[i + d - 1][j + d] - rs[i + d - 1][j] == d and \ cs[j + d - 1][i + d] - cs[j + d - 1][i] == d: return d * d return0