刷爆力扣之矩阵中的幻方

刷爆力扣之矩阵中的幻方

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 的幻方子矩阵。
1
2
3
4
5
6
7
8

示例 2:

输出: grid = [[8]]
输入: 0
1
2

提示:

• 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& tmpVec) {
	for (int targetIndex = 0; targetIndex < 8; targetIndex += 2) { //遍历临时数组
		if (tmpVec[0] == targetVec[targetIndex]) { //输入的数组首位元素和 8 6 2 4 逐个比较
			//从目标数组中取出正向镜像两个解比较是否其一
            return tmpVec == std::vector(targetVec.begin() + targetIndex, targetVec.begin() + targetIndex + 8) || tmpVec == std::vector(targetVec.rbegin() + 7 - targetIndex, targetVec.rbegin() + 15 - targetIndex);
		}
	}
	return false;
}

//初始化目标数组
std::vector targetVec = { 8, 1, 6, 7, 2, 9, 4, 3, 8, 1, 6, 7, 2, 9, 4, 3 };

int numMagicSquaresInside(std::vector>& grid) {
	//初始化矩阵 x 轴, y 轴对应偏移
	std::vector> 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 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;  //返回结果
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

3.2 🚀 细节解析

看完 👀👀👀 全注释版的代码实现后，相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃

那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析，直接开干，走起来 👇👇👇👇

targetIndex += 2 
1

输入的数组（tmpVec）首位元素和 8 6 2 4 逐个比较，因此索引移动两位 🐳🐳🐳

tmpVec == std::vector(targetVec.begin() + i , targetVec.begin() + i + 8);
1

旋转逻辑 ：找到目标位置后，从当前位置至当前位置移动八位（正向）

tmpVec == std::vector(targetVec.rbegin() + 7 - i, targetVec.rbegin() + 15 - i);
1

镜像逻辑 ：找到目标位置后，从反向迭代 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 ]
1
2
3

四 🏠 心路历程

为方便各位看官大大了解博主真实刷题过程，我把当时状态纯纯真实还原，记录在心路历程这一小节，不感兴趣的小伙伴可以直接跳过哈

博主在第一阶段提取 🚀 关键信息没有问题，在第二阶段 🚀 思路整理没有问题

代码实现时使用了暴力解（官网题解同暴力，旋转法确实难想），简洁性差 😭😭😭 ，代码如下 👇👇👇👇

int numMagicSquaresInside(vector>& 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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

五 🏠 结语

身处于这个浮躁的社会，却有耐心看到这里，你一定是个很厉害的人吧 👍👍👍

如果各位看官大大觉得文章有帮助的话，别忘了点赞 + 关注哦，你们的鼓励就是我最大的动力

博主还会不断更新更优质的内容，加油吧！技术人！ 💪💪💪