刷爆力扣之矩阵中的幻方
HELLO,各位看官大大好,我是阿呆 🙈🙈🙈
今天阿呆继续记录下力扣刷题过程,收录在专栏算法中 😜😜😜
该专栏按照不同类别标签进行刷题,每个标签又分为 Easy、Medium、Hard 三个等级 👊👊👊
本部分所有题目均来自于LeetCode 网,并于每道题目下标明具体力扣网原题链接 🏃🏃🏃
OK,兄弟们,废话不多直接上题,冲冲冲 🌞🌞🌞
一 🏠 题目描述
840. 矩阵中的幻方
3 x 3
的幻方是一个填充有 从 1
到 9
的不同数字的 3 x 3
矩阵,其中每行,每列以及两条对角线上的各数之和都相等。
给定一个由整数组成的row x col
的 grid
,其中有多少个 3 × 3
的 “幻方” 子矩阵?(每个子矩阵都是连续的)。
示例 1:
输入: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]
输出: 1
解释:
下面的子矩阵是一个 3 x 3 的幻方:
而这一个不是:
总的来说,在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。
示例 2:
输出: grid = [[8]]
输入: 0
提示:
row == grid.length
col == grid[i].length
1 <= row, col <= 10
0 <= grid[i][j] <= 15
二 🏠破题思路
2.1 🚀 关键信息
解决问题第一步,当然先提取题目字面上的关键信息 😎😎😎
3 x 3
幻方是一个 从 1
到 9
不同数字的 3 x 3
矩阵,每行每列及两条对角线上各数之和都相等。给一个矩阵,求其中有多少个 3 × 3
幻方子矩阵
从题干易知,3 × 3
幻方必须是 1
到 9
不同数字( 第一遍解错以为大于 9
也可,审题一定要细致 😭😭😭 )
对 3 × 3
幻方而言,其中心元素必为 5
,因此在遍历输入矩阵时只需遍历中心元素即可,故循环条件是 [ 1 , len - 1 )
提取完题目中的关键信息后,直接进入第二阶段,思路整理 😃😃😃
2.2 🚀 思路整理
暴力法:分别检查每 3x3
网格
对于每个网格,所有数字必不同,且在 1 到 9 之间,且每一个行,列,对角线的和必须相同 🌷🌷🌷
小细节:
① 在遍历输入矩阵时只需遍历中心元素即可
② 在判决数字必不同,且在 1 到 9 之间时,只需最值处于
[ 1 , 9 ]
即可
旋转法:三阶幻方解是固定的,有以下八种
八个解共同点,首先中间元素为五,角上元素都是偶数,中点都是奇数。同一行的解可以通过旋转得到,第一行镜像,可以得到第二行。也就是说,三阶幻方本质只有一种解,其余都是旋转镜像的体现
实现逻辑
1、依据上述,只有中心元素为五时,才判断以它是否为幻方
2、此时只需对比其余八个元素,由于解的旋转不变特性,将八个元素按顺序存放,方便后面比较,顺序如下图
3、如何旋转镜像,参考这道 189. 轮转数组 的思想,将前面部分放到后面即达到了旋转效果,镜像只需反向迭代即可
4、第二步输入的数组首位元素和 8 6 2 4 逐个比较,从目标数组中取出正向镜像两个解比较是否其一,即可确定是否为幻方 🐌🐌🐌
注:旋转法出处 ,有部分删减
整理完解题思路后,直接进入第三阶段,代码实现 😃😃😃
三 🏠 代码详解
3.1 🚀 代码实现
按照我们刚才的破题思路,直接代码走起来 👇👇👇👇
bool isMagic(std::vector<int>& tmpVec) {
for (int targetIndex = 0; targetIndex < 8; targetIndex += 2) { //遍历临时数组
if (tmpVec[0] == targetVec[targetIndex]) { //输入的数组首位元素和 8 6 2 4 逐个比较
//从目标数组中取出正向镜像两个解比较是否其一
return tmpVec == std::vector<int>(targetVec.begin() + targetIndex, targetVec.begin() + targetIndex + 8) || tmpVec == std::vector<int>(targetVec.rbegin() + 7 - targetIndex, targetVec.rbegin() + 15 - targetIndex);
}
}
return false;
}
//初始化目标数组
std::vector<int> targetVec = { 8, 1, 6, 7, 2, 9, 4, 3, 8, 1, 6, 7, 2, 9, 4, 3 };
int numMagicSquaresInside(std::vector<std::vector<int>>& grid) {
//初始化矩阵 x 轴, y 轴对应偏移
std::vector<std::pair<int, int>> offsetVals = { { -1, -1 }, { -1, 0 },
{ -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 } };
//初始化返回值, 行列长度
int count = 0, rows = grid.size() - 1, columns = grid[0].size() - 1;
//初始化临时数组
std::vector<int> tmpVec(8);
for (int i = 1; i < rows; ++i) { //遍历行
for (int j = 1; j < columns; ++j) { //遍历列
if (grid[i][j] == 5) { //若中心元素为 5
for (int index = 0; index < 8; ++index) {
tmpVec[index] = grid[i + offsetVals[index].first][j + offsetVals[index].second]; //将以i,j为中心的八个元素置于 tmpVec
}
count += isMagic(tmpVec); //并判断其是否为幻方
}
}
}
return count; //返回结果
}
3.2 🚀 细节解析
看完 👀👀👀 全注释版的代码实现后,相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃
那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析,直接开干,走起来 👇👇👇👇
targetIndex += 2
输入的数组(tmpVec)
首位元素和 8 6 2 4
逐个比较,因此索引移动两位 🐳🐳🐳
tmpVec == std::vector<int>(targetVec.begin() + i , targetVec.begin() + i + 8);
旋转逻辑 :找到目标位置后,从当前位置至当前位置移动八位(正向)
tmpVec == std::vector<int>(targetVec.rbegin() + 7 - i, targetVec.rbegin() + 15 - i);
镜像逻辑 :找到目标位置后,从反向迭代 7 - i
至反向迭代 15 - i
(反向) 🌼🌼🌼
//例如找到第一个2,对镜像而言, 它是 [ 2, 7, 6, 1, 8, 3, 4, 9 ]
//即是反向迭代的 3, 4, 9, 2 这段距离 7 - 4 = 3 (targetVec.rbegin() + 7 - i)
[ 8, 1, 6, 7, 2, 9, 4, 3, 8, 1, 6, 7, 2, 9, 4, 3 ]
四 🏠 心路历程
为方便各位看官大大了解博主真实刷题过程,我把当时状态纯纯真实还原,记录在心路历程这一小节,不感兴趣的小伙伴可以直接跳过哈
博主在第一阶段提取 🚀 关键信息没有问题,在第二阶段 🚀 思路整理没有问题
代码实现时使用了暴力解(官网题解同暴力,旋转法确实难想),简洁性差 😭😭😭 ,代码如下 👇👇👇👇
int numMagicSquaresInside(vector<vector<int>>& grid) {
int count = 0;
int width = grid.size(), high = grid[0].size();
for (int i = 1; i < width - 1; ++i) { //遍历二维输入的宽
for (int j = 1; j < high - 1; ++j) {
if (grid[i][j] != 5) continue;
if (grid[i-1][j] == grid[i][j]) continue; //各个数值不相同
//横向加和
if (grid[i-1][j-1] + grid[i][j-1] + grid[i+1][j-1] != 15) continue;
if (grid[i-1][j] + grid[i][j] + grid[i + 1][j] != 15) continue;
if (grid[i-1][j+1] + grid[i][j+1] + grid[i+1][j+1] != 15) continue;
//竖向加和
if (grid[i-1][j-1] + grid[i-1][j] + grid[i-1][j+1] != 15) continue;
if (grid[i][j-1] + grid[i][j] + grid[i][j+1] != 15) continue;
if (grid[i+1][j-1] + grid[i+1][j] + grid[i+1][j+1] != 15) continue;
//对角加和
if (grid[i-1][j-1] + grid[i][j] + grid[i+1][j+1] != 15) continue;
if (grid[i-1][j+1] + grid[i][j] + grid[i+1][j-1] != 15) continue;
//求最大值和最小值 legalScope
int mem_max = std::max({grid[i-1][j-1], grid[i][j-1], grid[i+1][j-1],
grid[i-1][j], grid[i][j], grid[i+1][j],
grid[i-1][j+1], grid[i][j+1], grid[i+1][j+1]});
int mem_min = std::min({grid[i-1][j-1], grid[i][j-1], grid[i+1][j-1],
grid[i-1][j], grid[i][j], grid[i+1][j],
grid[i-1][j+1], grid[i][j+1], grid[i+1][j+1]});
if (mem_max <= 9 && mem_min >= 1) ++count;
}
}
return count;
}
五 🏠 结语
身处于这个浮躁的社会,却有耐心看到这里,你一定是个很厉害的人吧 👍👍👍
如果各位看官大大觉得文章有帮助的话,别忘了点赞 + 关注哦,你们的鼓励就是我最大的动力
博主还会不断更新更优质的内容,加油吧!技术人! 💪💪💪