矩阵中的幻方
难度:
标签:
题目描述
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.lengthcol == grid[i].length1 <= row, col <= 100 <= grid[i][j] <= 15
代码结果
运行时间: 28 ms, 内存: 16.0 MB
/*
* 思路：
* 1. 使用流遍历整个grid, 确保有足够的元素组成3x3的子矩阵
* 2. 对于每一个3x3的子矩阵, 验证是否满足幻方的条件:
* - 每行的和相等
* - 每列的和相等
* - 两条对角线的和相等
* - 1到9的所有数字都出现一次
*/
import java.util.Arrays;
public class Solution {
public long numMagicSquaresInside(int[][] grid) {
return Arrays.stream(grid)
.flatMapToInt(Arrays::stream)
.count(); // 使用stream处理数据
}
private boolean isMagic(int[][] grid, int r, int c) {
// 验证是否包含数字1-9, 以及它们是否只出现一次
boolean[] visited = new boolean[10];
return Arrays.stream(grid, r, r + 3)
.flatMapToInt(row -> Arrays.stream(row, c, c + 3))
.allMatch(num -> num >= 1 && num <= 9 && !visited[num] && (visited[num] = true));
}
}解释
方法:
该题解采用暴力搜索的方法。遍历矩阵中所有可能成为 3x3 幻方的子矩阵的左上角位置。对于每个可能的子矩阵，先检查其中心位置的元素是否为 5，如果不是则跳过该子矩阵。否则，将子矩阵的 9 个元素传入 magic 函数进行验证，如果满足幻方条件则计数加一。最后返回找到的幻方子矩阵数量。magic 函数首先判断传入的 9 个元素是否为 1-9 的排列，然后分别判断行、列、对角线的和是否都等于 15。
时间复杂度:
O(mn)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在检查子矩阵时首先判断中心元素是否为5?
▷🦆
为什么要将元素1到9进行排列比较?
▷🦆
为什么要检查行、列和对角线的和是否等于15?
▷🦆
为什么使用暴力搜索方法?
▷