Leetcode 1895. Largest Magic Square

Tyan

发布于 2021-07-08 15:54:08

34000

代码可运行

文章被收录于专栏：SnailTyanSnailTyan

运行总次数：0

代码可运行

文章作者：Tyan 博客：noahsnail.com | CSDN | 简书

1. Description

2. Solution

**解析：**根据幻方定义，分别检查主对角线、副对角线、各行、各列的和是否相等，按阶次从大到小依次检查，碰到满足条件的返回阶。

Version 1

class Solution:
    def largestMagicSquare(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        size = min(m, n)
        for k in range(size, 0, -1):
            for i in range(m-k+1):
                for j in range(n-k+1):
                    if self.check(grid, i, j, k):
                        return k


    def check(self, grid, x, y, k):
        main_diagonal = 0
        secondary_diagonal = 0
        for i in range(k):
            main_diagonal += grid[x+i][y+i]
            secondary_diagonal += grid[x+i][y+k-i-1]
        if main_diagonal != secondary_diagonal:
            return False

        for i in range(k):
            row = sum(grid[x+i][y:y+k])
            if row != main_diagonal:
                return False
            column = sum([grid[x+j][y+i] for j in range(k)])
            if column != main_diagonal:
                return False
        return True