头像

带翅膀的猫

时光荏苒,我们一直都在

《LeetCode刷题(Easy Rank):840. Magic Squares In Grid》

 1月前  •   LeetCode  •     •   15  •   0

Question:

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:

示例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

Solution:

JAVAclass Solution {
    public int numMagicSquaresInside(int[][] grid) {
        int count=0;
        for(int i=0;i<grid.length-2;i++){
            for(int j=0;j<grid[0].length-2;j++){
                if(grid[i][j]>9||grid[i][j+1]>9||grid[i][j+2]>9||grid[i+1][j]>9||grid[i+1][j+1]>9||grid[i+1][j+2]>9||grid[i+2][j]>9||grid[i+2][j+1]>9||grid[i+2][j+2]>9)
                    continue;//有没有比9大的数
                int sum = grid[i][j]+grid[i][j+1]+grid[i][j+2];//一行3个数之和
                if(grid[i][j]+grid[i+1][j+1]+grid[i+2][j+2]!=sum||grid[i][j+2]+grid[i+1][j+1]+grid[i+2][j]!=sum)
                    continue;//判断主对角线和反对角线之和是否等于sum
                if(grid[i+1][j]+grid[i+1][j+1]+grid[i+1][j+2]!=sum||grid[i+2][j]+grid[i+2][j+1]+grid[i+2][j+2]!=sum)
                    continue;//判断第2和第3行是否等于sum
                count++;
            }
        }
        return count;
    }
}

43816729解法:

思路Assume a magic square:
a1,a2,a3
a4,a5,a6
a7,a8,a9

a2 + a5 + a8 = 15
a4 + a5 + a6 = 15
a1 + a5 + a9 = 15
a3 + a5 + a7 = 15

Accumulate all, then we have:
sum(ai) + 3 * a5 = 60
3 * a5 = 15
a5 = 5

The center of magic square must be 5.

Another observation for other 8 numbers:
The even must be in the corner, and the odd must be on the edge.
And it must be in a order like “43816729” (clockwise or anticlockwise).

Pythondef numMagicSquaresInside(self, g):
        def isMagic(i, j):
            s = "".join(str(g[i + x / 3][j + x % 3]) for x in [0, 1, 2, 5, 8, 7, 6, 3])
            return g[i][j] % 2 == 0 and (s in "43816729" * 2 or s in "43816729"[::-1] * 2)
        return sum(isMagic(i, j) for i in range(len(g) - 2) for j in range(len(g[0]) - 2) if g[i + 1][j + 1] == 5)

 

 

上一篇:
下一篇:

 评论


 已有0条评论

    还没有任何评论,你来说两句吧!