Medium
Related Topics: Array / Hash Table / Math / Matrix
LeetCode Source

解題想法

整體來說透過尋訪整個 grid，從 i = 0, j = 0 到 i = m-2, j = n-2

其中 m 是 grid row 長度，n 是 column 的長度

接著在 isMagic() 的函示判斷是否為 magic square

首先是 3*3 的格子內有無數字 1 到 9

接著是每 3 個格子相加是否為 15

注意包括斜對邊也是

最後在雙層 loop 內加總 magic square 個數即是答案

Complexity

Time Complexity: O(rows * cols)
Space Complexity: O(1)

Python

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        def isMagic(i, j):
            s = [grid[x][y] for x in range(i, i+3) for y in range(j, j+3)]
            
            if sorted(s) != list(range(1, 10)):
                return False

            return (s[0] + s[1] + s[2] == 15 and
                    s[3] + s[4] + s[5] == 15 and
                    s[6] + s[7] + s[8] == 15 and
                    s[0] + s[3] + s[6] == 15 and
                    s[1] + s[4] + s[7] == 15 and
                    s[2] + s[5] + s[8] == 15 and
                    s[0] + s[4] + s[8] == 15 and
                    s[2] + s[4] + s[6] == 15)
        
        m, n = len(grid), len(grid[0])
        res = 0

        for i in range(m - 2):
            for j in range(n - 2):
                if isMagic(i, j):
                    res += 1

        return res

C++

class Solution {
public:
    int numMagicSquaresInside(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int res = 0;

        for (int i = 0; i < m - 2; ++i) {
            for (int j = 0; j < n - 2; ++j) {
                if (isMagic(grid, i, j)) {
                    res += 1;
                }
            }
        }
        
        return res;
    }

    bool isMagic(vector<vector<int>>& grid, int i, int j) {
        vector<int> s;
        for (int x = i; x < i + 3; ++x) {
            for (int y = j; y < j + 3; ++y) {
                s.push_back(grid[x][y]);
            }
        }
        
        sort(s.begin(), s.end());
        if (s != vector<int>{1, 2, 3, 4, 5, 6, 7, 8, 9}) {
            return false;
        }
        
        return (grid[i][j] + grid[i][j+1] + grid[i][j+2] == 15 &&
                grid[i+1][j] + grid[i+1][j+1] + grid[i+1][j+2] == 15 &&
                grid[i+2][j] + grid[i+2][j+1] + grid[i+2][j+2] == 15 &&
                grid[i][j] + grid[i+1][j] + grid[i+2][j] == 15 &&
                grid[i][j+1] + grid[i+1][j+1] + grid[i+2][j+1] == 15 &&
                grid[i][j+2] + grid[i+1][j+2] + grid[i+2][j+2] == 15 &&
                grid[i][j] + grid[i+1][j+1] + grid[i+2][j+2] == 15 &&
                grid[i][j+2] + grid[i+1][j+1] + grid[i+2][j] == 15);
    }
};