LeetCode算法题-Magic Squares In Gri

这是悦乐书的第326次更新，第349篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第196题（顺位题号是840）。3 x 3魔方是一个3 x 3网格，填充了从1到9的不同数字，这样每行，每列和两个对角线都具有相同的总和。

给定一个整数网格，求有多少个3 x 3“魔方”子网格？ （每个子网格都是连续的）。例如：


输入：[[4,3,8,4]，[9,5,1,9]，[2,7,6,2]]

输出：1

说明：

以下子网格是一个3 x 3魔方：

4 3 8

9 5 1

2 7 6

而这一个不是：

3 8 4

5 1 9

7 6 2

所以，给定网格中只有一个魔方。


注意：

• 1 <= grid.length <= 10

• 1 <= grid [0] .length <= 10

• 0 <= grid [i] [j] <= 15

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 解题

题目的意思很明确，需要我们从给定的二维数组中找出符合题意的3x3魔方，而一个合格的3x3魔方需要满足以下条件：

（1）每行、每列、两条对角线上的元素之和相等。

（2）每个元素的取值范围为：[1,9]。

（3）魔方中的任意元素不能出现重复值，即为1到9的随机排列。

因此，解题思路就是将截取出一个子数组，分别取出9个元素，判断是否满足上述三个条件即可。在判断是否有重复值出现时，使用了异或位运算，因为两个相同的数进行异或运算的结果是0，同时使用异或运算也判断了元素的取值范围，一举两得。

public int numMagicSquaresInside(int[][] grid) {
    int row = grid.length, col = grid[0].length;
    if (row < 2 || col < 2) {
        return 0;
    }
    int count = 0;
    for (int i=0; i<row-2; i++) {
        for (int j=0; j<col-2; j++) {
            int n = grid[i][j], n2 = grid[i][j+1], n3 = grid[i][j+2];
            int n4 = grid[i+1][j], n5 = grid[i+1][j+1], n6 = grid[i+1][j+2];
            int n7 = grid[i+2][j], n8 = grid[i+2][j+1], n9 = grid[i+2][j+2];
            // 1 <= grid[i][j] <= 9，且不能出现重复值
            if ((n^n2^n3^n4^n5^n6^n7^n8^n9) != (1^2^3^4^5^6^7^8^9)) {
                continue;
            }
            // 三行三列外加两对角线，判断和
            int sum = n+n2+n3;
            int sum2 = n4+n5+n6;
            int sum3 = n7+n8+n9;
            int sum4 = n+n4+n7;
            int sum5 = n2+n5+n8;
            int sum6 = n3+n6+n9;
            int sum7 = n+n5+n9;
            int sum8 = n3+n5+n7;
            if (sum == sum2 && sum2 == sum3 && sum3 == sum4
                && sum4 == sum5 && sum5 == sum6 && sum6 == sum7
               && sum7 == sum8) {
                count++;
            }
        }            
    }
    return count;
}

03 小结

算法专题目前已日更超过五个月，算法题文章196+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！