Description:
A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.
Given an grid
of integers, how many 3 x 3 "magic square" subgrids are there? (Each subgrid is contiguous).
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 <= grid[i][j] <= 15
思路:题目要求找出高维数组中的魔方数,暂时能做的方法就是从第二行开始依次遍历高维数组,以该点为中心判断是否符合魔方数规则,特别注意元素下标。魔方数规则如下(第三条容易不注意):
1.中间的数是 5
2.每行每列交叉 8 组数的和为 15
3.9 个数的和为 45 且积为 362880
(此条规则可排除特殊用例:[[5,5,5],[5,5,5],[5,5,5]])
我的 C++ 代码
class Solution {
public:
bool magic(vector<vector<int>>& g, int x, int y) {
int a = 0, b = 1;
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 3; j++) {
int c = g[i+x][j+y];
a += c;
b *= c;
}
}
return
a == 45 && b == 362880 &&
g[x][y] + g[x][y+1] + g[x][y+2] == 15 &&
g[x+1][y] + g[x+1][y+1] + g[x+1][y+2] == 15 &&
g[x+2][y] + g[x+2][y+1] + g[x+2][y+2] == 15 &&
g[x][y] + g[x+1][y] + g[x+2][y] == 15 &&
g[x][y+1] + g[x+1][y+1] + g[x+2][y+1] == 15 &&
g[x][y+2] + g[x+1][y+2] + g[x+2][y+2] == 15 &&
g[x][y] + g[x+1][y+1] + g[x+2][y+2] == 15 &&
g[x+2][y] + g[x+1][y+1] + g[x][y+2] == 15;
}
int numMagicSquaresInside(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int result = 0;
for(int i = 0; i + 2 < m; i++) {
for(int j = 0; j + 2 < n; j++) {
if(magic(grid, i, j)) result++;
}
}
return result;
}
};
运行时间:4ms
运行内存:9.2M
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于