Leetcode 840. Magic Squares In Grid

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

1. Description

2. Solution

**解析：**根据三阶幻方的定义，一项项检查即可，满足条件 1。Version 1是针对3*3的，Version 2进行了一些修改，减少了代码量，Version 3是针对k*k的通用版本。

• Version 1

代码语言：javascript复制

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        columns = len(grid[0])
        count = 0
        for i in range(rows - 2):
            for j in range(columns - 2):
                if self.check(grid, i, j):
                    count  = 1
        return count


    def check(self, grid, x, y):
        temp = set(grid[x][y:y 3]   grid[x 1][y:y 3]   grid[x 2][y:y 3])
        if len(temp) != 9:
            return False
        for i in range(x, x 3):
            for j in range(y, y 3):
                if grid[i][j] == 0 or grid[i][j] > 9:
                    return False
        x1 = sum(grid[x][y:y 3])
        x2 = sum(grid[x 1][y:y 3])
        if x2 != x1:
            return False
        x3 = sum(grid[x 2][y:y 3])
        if x3 != x1:
            return False
        x4 = grid[x][y]   grid[x 1][y]   grid[x 2][y]
        if x4 != x1:
            return False
        x5 = grid[x][y 1]   grid[x 1][y 1]   grid[x 2][y 1]
        if x5 != x1:
            return False
        x6 = grid[x][y 2]   grid[x 1][y 2]   grid[x 2][y 2]
        if x6 != x1:
            return False
        x7 = grid[x][y]   grid[x 1][y 1]   grid[x 2][y 2]
        if x7 != x1:
            return False
        x8 = grid[x][y 2]   grid[x 1][y 1]   grid[x 2][y]
        if x8 != x1:
            return False
        return True

• Version 2

代码语言：javascript复制

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        columns = len(grid[0])
        count = 0
        for i in range(rows - 2):
            for j in range(columns - 2):
                if self.check(grid, i, j):
                    count  = 1
        return count


    def check(self, grid, x, y):
        temp = {i: 0 for i in range(1, 10)}
        for i in range(x, x 3):
            for j in range(y, y 3):
                if grid[i][j] not in temp or temp[grid[i][j]] == 1:
                    return False
                temp[grid[i][j]] = 1

        temp = grid[x][y]   grid[x 1][y 1]   grid[x 2][y 2]
        if temp != grid[x][y 2]   grid[x 1][y 1]   grid[x 2][y]:
            return False
        for i in range(3):
            if temp != sum(grid[x i][y:y 3]):
                return False
            if temp != grid[x][y i]   grid[x 1][y i]   grid[x 2][y i]:
                return False
        return True

• Version 3

代码语言：javascript复制

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        columns = len(grid[0])
        count = 0
        k = 3
        for i in range(rows-k 1):
            for j in range(columns-k 1):
                if self.check(grid, i, j, k):
                    count  = 1
        return count


    def check(self, grid, x, y, k):
        temp = {i: 0 for i in range(1, k*k 1)}
        for i in range(x, x k):
            for j in range(y, y k):
                if grid[i][j] not in temp or temp[grid[i][j]] == 1:
                    return False
                temp[grid[i][j]] = 1

        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):
            if main_diagonal != sum(grid[x i][y:y k]):
                return False
            if main_diagonal != sum([grid[x j][y i] for j in range(k)]):
                return False
        return True

Reference

1. https://leetcode.com/problems/magic-squares-in-grid/

sdn com version 博客

0 人点赞