A.每日一题——840. 矩阵中的幻方

题目链接：840. 矩阵中的幻方（中等）

算法原理：

解法：暴力枚举

0ms击败100.00%

时间复杂度O(mn)

幻方是由1~9组成的，总和为45，每一条线的和为45÷3=15，对于正中间的元素，有四条线经过，总和是15×4=60，但是正中间的元素重复算了四次，需要减去三次的，也就是说中心元素=（60-45）÷3=5，那么我们遍历时如果发现正中间元素不是5，就可以直接越过这次判断了

枚举每个幻方的左上角，如果正中间元素是5就继续判断

先要保证幻方中1~9这些数出现的次数必须是一次，有重复或者缺失都不能构成幻方

再依次判断三行、三列、主对角线、副对角线即可

Java代码：

class Solution { public int numMagicSquaresInside(int[][] nums) { int m=nums.length,n=nums[0].length; int ret=0; //枚举每个幻方的左上角 for(int i=0;i<m-2;i++){ for(int j=0;j<n-2;j++){ if(nums[i+1][j+1]!=5) continue; if(islegal(nums[i][j],nums[i][j+1],nums[i][j+2], nums[i+1][j],nums[i+1][j+1],nums[i+1][j+2], nums[i+2][j],nums[i+2][j+1],nums[i+2][j+2])) ret++; } } return ret; } public boolean islegal(int... val){ int[] count=new int[16]; for(int v:val) count[v]++; //幻方中1~9每个数必须只出现一次 for(int v=1;v<=9;v++) if(count[v]!=1) return false;//数字缺失或重复，必定不是幻方 return (val[0]+val[1]+val[2]==15&&//第一行 val[3]+val[4]+val[5]==15&&//第二行 val[6]+val[7]+val[8]==15&&//第三行 val[0]+val[3]+val[6]==15&&//第一列 val[1]+val[4]+val[7]==15&&//第二列 val[2]+val[5]+val[8]==15&&//第三列 val[0]+val[4]+val[8]==15&&//主对角线 val[2]+val[4]+val[6]==15);//副对角线 } }