Magic Squares In Grid
给一个2d数组, 找到其中的3×3的2d数组, row, col,diagonal都是一个数, 并且从1-9组成. 这个题限制很多, 我开始直接做的,后来发现答案有一个很巧妙的. 通过观察可以得知, 5肯定在中间, 四个角肯定是偶数, 其他位置是奇数, 然而奇数能组成题意的矩阵的, 只有
1 2 3 |
438 951 276 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution { public int numMagicSquaresInside(int[][] grid) { int res = 0; for (int i = 1; i < grid.length - 1; i++) { for (int j = 1; j < grid[0].length - 1; j++) { if (grid[i][j] == 5) { res += isMagic(i, j, grid) ? 1 : 0; } } } return res; } public boolean isMagic(int i, int j, int[][] grid) { String s = "" + grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] + grid[i][j + 1] + grid[i + 1][j + 1] + grid[i + 1][j] + grid[i + 1][j - 1] + grid[i][j - 1]; return "4381672943816729".contains(s) || "9276183492761834".contains(s); } } |