class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="1">

解法二： 找规律

时间复杂度： O(N^2)；  空间复杂度： O(N).

其实通过上面的两个限定条件就可以很明确的确定出 0~9 中满足的方阵。 同时因为幻方是对称结构，所以当一个幻方结构确定后，对它进行对称或者旋转同样满足，总共有这八种。

自然是不可能逐个判断是不是这八个之一，大家仔细观察，相信很容易找出这八个解的共同点，首先中间的元素都是五，角上元素都是偶数，中点都是奇数。同一行的解可以通过旋转得到，第一行镜像，可以得到第二行。也就是说，三阶幻方本质只有一种解，其余都是旋转镜像的体现。
我们可以依据这一点，写出优雅简洁的代码。

1. 遍历中间的部分，只有是五的时候，才判断以他为中心的三阶方阵是否是幻方。
2. 五已经比对过了，只需要比对其他八个元素，由于解的旋转不变特性，这里将八个元素按顺序存放，方便后面比较，顺序如下图。
3. 解的编码，如何表示旋转镜像，参考旋转数组这题的思想，将前面部分的放在后面就达到了旋转的效果。镜像只需要反向迭代就好了。

4.第二步输入的数组首位元素和8 6 2 4逐个比较决定可能的解，从编码的数组中取出正向镜像两个解比较是否其一，就可确定是否是幻方。

（方法参考资料，感觉确实这个方法也行，但思维稍麻烦了，并且没有进行特别好的优化的地方）非暴力，努力写出优雅的代码，双百 - 矩阵中的幻方 - 力扣（LeetCode） (leetcode-cn.com)）

 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="1"> class="hljs-ln-code"> class="hljs-ln-line">class Solution {
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="2"> class="hljs-ln-code"> class="hljs-ln-line">public:
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="3"> class="hljs-ln-code"> class="hljs-ln-line">    vector<int> m={8,1,6,7,2,9,4,3,8,1,6,7,2,9,4,3};
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="4"> class="hljs-ln-code"> class="hljs-ln-line">    int numMagicSquaresInside(vectorint>>& grid) {
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="5"> class="hljs-ln-code"> class="hljs-ln-line">        int di[8]={-1,-1,-1,0,1,1,1,0};
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="6"> class="hljs-ln-code"> class="hljs-ln-line">        int dj[8]={-1,0,1,1,1,0,-1,-1};
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="7"> class="hljs-ln-code"> class="hljs-ln-line">        int count=0;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="8"> class="hljs-ln-code"> class="hljs-ln-line">        for(int i=1;isize()-1;i++)
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="9"> class="hljs-ln-code"> class="hljs-ln-line">            for(int j=1;j0].size()-1;j++)
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="10"> class="hljs-ln-code"> class="hljs-ln-line">                if(grid[i][j]==5){
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="11"> class="hljs-ln-code"> class="hljs-ln-line">                    vector<int> around;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="12"> class="hljs-ln-code"> class="hljs-ln-line">                    for(int k=0;k<8;k++)
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="13"> class="hljs-ln-code"> class="hljs-ln-line">                        around.push_back(grid[i+di[k]][j+dj[k]]);
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="14"> class="hljs-ln-code"> class="hljs-ln-line">                    count+=IsMagic(around);
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="15"> class="hljs-ln-code"> class="hljs-ln-line">                }
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="16"> class="hljs-ln-code"> class="hljs-ln-line">        return count;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="17"> class="hljs-ln-code"> class="hljs-ln-line">    }
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="18"> class="hljs-ln-code"> class="hljs-ln-line">    bool IsMagic(vector<int>& v){
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="19"> class="hljs-ln-code"> class="hljs-ln-line">        for(int i=0;i<8;i+=2)
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="20"> class="hljs-ln-code"> class="hljs-ln-line">            if(m[i]==v[0])
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="21"> class="hljs-ln-code"> class="hljs-ln-line">            return v==vector<int>(m.begin()+i,m.begin()+i+8)
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="22"> class="hljs-ln-code"> class="hljs-ln-line">            ||v==vector<int>(m.rbegin()+7-i,m.rbegin()+15-i);
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="23"> class="hljs-ln-code"> class="hljs-ln-line">        return false;//奇数元素
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="24"> class="hljs-ln-code"> class="hljs-ln-line">    }
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="25"> class="hljs-ln-code"> class="hljs-ln-line">}; class="hide-preCode-box"> class="hljs-button signin" data-title="登录后复制" data-report-click="{"spm":"1001.2101.3001.4334"}" onclick="hljs.signin(event)">

 上一篇： 从B站 (哔哩哔哩) 泄露的源码里发现了B站视频推荐的秘密

下一篇： 400+条实用C/C++框架、库、工具整理 ，你能想到的都在这里了

如果有什么要补充的，欢迎下方👇评论区留言~

1份赞许 = 100分的认可，如果感觉还不错，点个赞👍 支持一下吧 ~

不定期分享 有趣、有料、有营养内容，欢迎 订阅关注 🤝 我的博客 ，期待在这与你相遇 ~

发表评论

登录后才能发表评论和回复 注册

/ 登录

提交评论

评论记录：

未查询到任何数据！

回复评论：

×

关闭 提交评论