840. Magic Squares In Grid
题目
一个魔法方块是一个3x3的矩阵,矩阵内的每个值是1-9的不重复数字,并且其每行,每列和对角线的和都相等。
给一个整数矩阵,找出这个矩阵中有多少个上面说的魔法方快。(每一个子矩阵都是连续的)。
Example 1:
Input: [[4,3,8,4],
[9,5,1,9],
[2,7,6,2]]
Output: 1
Explanation:
The following subgrid is a 3 x 3 magic square:
438
951
276
while this one is not:
384
519
762
In total, there is only one magic square inside the given grid.
Note:
- 1 <= grid.length <= 10
- 1 <= grid[0].length <= 10
- 0 <= gridi <= 15
思路
由于我们需要判断3x3的矩阵是否1-9的唯一值,我们只能通过遍历来搞定,因此,目前我暂时还没有找到一个更好的办法,n^2的时间复杂度是没办法避免的了。
通过对3x3矩阵的描述来看,其实我们可以知道有这么几个特征:
- 矩阵的值是1-9不重复的
- 为了行列对角线都是相等,中间的那个值必须要为5
因此,我们可以在判断一个矩阵是不是的时候通过这两个条件加速一下,避免不必要的判断。代码如下:
func numMagicSquaresInside(grid [][]int) int {
if len(grid) < 3 || len(grid[0]) < 3 {
return 0
}
rowLength := len(grid[0])
columnLength := len(grid)
find := 0
for column := 0; column+2 < columnLength; column++ {
for row := 0; row+2 < rowLength; row++ {
// 找到起点
if isMagicSquare(grid, column, row) {
find++
}
}
}
return find
}
// 暴力破解查找
func isMagicSquare(grid [][]int, column, row int) bool {
// 中间不为5肯定不是
if grid[column+1][row+1] != 5 {
return false
}
num := make([]int, 9, 9)
for i := column; i < 3+column; i++ {
for j := row; j < 3+row; j++ {
// 数字必须为1-9,且只能出现一次
if grid[i][j] > 9 || grid[i][j] < 1 {
return false
}
num[grid[i][j]-1]++
if num[grid[i][j]-1] > 1 {
return false
}
if j == row {
// 右
if 15 != grid[i][j]+grid[i][j+1]+grid[i][j+2] {
return false
}
// 右上
if i == 2+column {
if 15 != grid[i][j]+grid[i-1][j+1]+grid[i-2][j+2] {
return false
}
}
}
// 下
if i == column {
if 15 != grid[i][j]+grid[i+1][j]+grid[i+2][j] {
return false
}
// 右下
if j == row {
if 15 != grid[i][j]+grid[i+1][j+1]+grid[i+2][j+2] {
return false
}
}
}
}
}
return true
}
完整代码见:https://github.com/scofieldpeng/leetcode/blob/master/numMagicSquaresInside/numMagicSquaresInside.go