840. Magic Squares In Grid Python题解

标签: python

A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.

Given an grid of integers, how many 3 x 3 "magic square" subgrids are there?  (Each subgrid is contiguous).

 

Example 1:

Input: [[4,3,8,4],
        [9,5,1,9],
        [2,7,6,2]]
Output: 1
Explanation: 
The following subgrid is a 3 x 3 magic square:
438
951
276

while this one is not:
384
519
762

In total, there is only one magic square inside the given grid.

Note:

  1. 1 <= grid.length <= 10
  2. 1 <= grid[0].length <= 10
  3. 0 <= grid[i][j] <= 15

这道题还是比较坑的,首先需要了解幻方结构,不然按朴素的匹配基本是炸了,踩了好几个坑,现在提供一种比较高效(相对)简洁的python解法,三阶幻方一共有8种,且每一种中心都是5所以按照一个方向一个起点顺时针转换为一个长度为8的字符串,可以减少后续比较和保持代码的优雅

class Solution:
    def numMagicSquaresInside(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        res,n=0,len(grid)
        isMag=['16729438','18349276','34927618','38167294','72943816','76183492','92761834','94381672']
        for i in range(1,n-1):
            for j in range(1,n-1):
                if grid[i][j]==5:
                    tmp=''.join(map(str,[grid[i-1][j],grid[i-1][j+1],grid[i][j+1],grid[i+1][j+1],grid[i+1][j],\
                                         grid[i+1][j-1],grid[i][j-1],grid[i-1][j-1]]))
                    res+=1 if tmp in isMag else 0
        return res

对于isMag数组,也可以使用set结构提高效率,但是差别不大,最后附上时间图

原文链接:加载失败,请重新获取