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

class Solution:def numMagicSquaresInside(self, grid: List[List[int]]) -> int:rows = len(grid)columns = len(grid[0])count = 0for i in range(rows - 2):for j in range(columns - 2):if self.check(grid, i, j):count += 1return countdef 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 Falsefor i in range(x, x+3):for j in range(y, y+3):if grid[i][j] == 0 or grid[i][j] > 9:return Falsex1 = sum(grid[x][y:y+3])x2 = sum(grid[x+1][y:y+3])if x2 != x1:return Falsex3 = sum(grid[x+2][y:y+3])if x3 != x1:return Falsex4 = grid[x][y] + grid[x+1][y] + grid[x+2][y]if x4 != x1:return Falsex5 = grid[x][y+1] + grid[x+1][y+1] + grid[x+2][y+1]if x5 != x1:return Falsex6 = grid[x][y+2] + grid[x+1][y+2] + grid[x+2][y+2]if x6 != x1:return Falsex7 = grid[x][y] + grid[x+1][y+1] + grid[x+2][y+2]if x7 != x1:return Falsex8 = grid[x][y+2] + grid[x+1][y+1] + grid[x+2][y]if x8 != x1:return Falsereturn True

• Version 2

class Solution:def numMagicSquaresInside(self, grid: List[List[int]]) -> int:rows = len(grid)columns = len(grid[0])count = 0for i in range(rows - 2):for j in range(columns - 2):if self.check(grid, i, j):count += 1return countdef 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 Falsetemp[grid[i][j]] = 1temp = 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 Falsefor i in range(3):if temp != sum(grid[x+i][y:y+3]):return Falseif temp != grid[x][y+i] + grid[x+1][y+i] + grid[x+2][y+i]:return Falsereturn True

• Version 3

class Solution:def numMagicSquaresInside(self, grid: List[List[int]]) -> int:rows = len(grid)columns = len(grid[0])count = 0k = 3for i in range(rows-k+1):for j in range(columns-k+1):if self.check(grid, i, j, k):count += 1return countdef 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 Falsetemp[grid[i][j]] = 1main_diagonal = 0secondary_diagonal = 0for 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 Falsefor i in range(k):if main_diagonal != sum(grid[x+i][y:y+k]):return Falseif main_diagonal != sum([grid[x+j][y+i] for j in range(k)]):return Falsereturn True

Reference

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