840--矩阵中的幻方(找规律)

题目

3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。

给定一个由整数组成的 grid,其中有多少个 3 × 3 的 “幻方” 子矩阵?(每个子矩阵都是连续的)。

规律

网格的总和是 45,因为网格必须是 1 到 9 不同的数字。
每一列和行加起来必须是 15,乘以 3 则是网格的总和。
对角线的和也必须是 15,题目中说了对角线与列,行的和相同。
将四条穿过中心的线的 12 个值相加(即一行一列两条对角线),这四条线加起来等于 60;而整个网格加起来为 45。则中心等于 (60-45)/3 = 5(60−45)/3=5。

题解

`class Solution {
public int numMagicSquaresInside(int[][] grid) {
int R = grid.length, C = grid[0].length;
int ans = 0;
for (int r = 0; r < R-2; ++r)
for (int c = 0; c < C-2; ++c) {
if (grid[r+1][c+1] != 5) continue; // optional skip
if (magic(grid[r][c], grid[r][c+1], grid[r][c+2],
grid[r+1][c], grid[r+1][c+1], grid[r+1][c+2],
grid[r+2][c], grid[r+2][c+1], grid[r+2][c+2]))
ans++;
}
return ans;
}
public boolean magic(int... vals) {
int[] count = new int[16];
for (int v: vals) count[v]++;
for (int v = 1; v <= 9; ++v)
if (count[v] != 1)
return false;
return (vals[0] + vals[1] + vals[2] == 15 &&
vals[3] + vals[4] + vals[5] == 15 &&
vals[6] + vals[7] + vals[8] == 15 &&
vals[0] + vals[3] + vals[6] == 15 &&
vals[1] + vals[4] + vals[7] == 15 &&
vals[2] + vals[5] + vals[8] == 15 &&
vals[0] + vals[4] + vals[8] == 15 &&
vals[2] + vals[4] + vals[6] == 15);
}
}

上一篇:45.贪心算法


下一篇:62. 不同路径