Medium

题目描述

一个 3 x 3 的幻方是一个 3 x 3 的网格，其中填入了 1 到 9 的不同数字，使得每一行、每一列以及两条对角线的和都相等。

给你一个 row x col 的整数网格，返回其中有多少个 3 x 3 的幻方子网格。

注意：虽然幻方只能包含 1 到 9 的数字，但 grid 可能包含最大为 15 的数字。

示例 1：

输入：grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]]
输出：1
解释：
以下子网格是一个 3 x 3 幻方：
4 3 8
9 5 1  
2 7 6

而这个不是：
3 8 4
5 1 9
7 6 2

总共只有一个幻方在给定的网格中。

示例 2：

输入：grid = [[8]]
输出：0

提示：

  • row == grid.length
  • col == grid[i].length
  • 1 <= row, col <= 10
  • 0 <= grid[i][j] <= 15

解题思路

解题思路

要判断一个 3×3 的子网格是否为幻方，需要满足以下条件：

  1. 包含且仅包含数字 1-9，每个数字恰好出现一次
  2. 每行、每列、两条对角线的和都相等（必须等于 15）

算法步骤：

  1. 遍历所有可能的 3×3 子网格的左上角位置 (i, j)
  2. 对于每个子网格，检查是否为有效幻方：
    • 使用集合或数组检查是否包含 1-9 且无重复
    • 验证所有行、列、对角线的和是否都等于 15
  3. 统计满足条件的幻方数量

优化技巧：

  • 由于幻方的和固定为 15，可以先检查中心元素是否为 5（3×3 幻方中心必须是 5）
  • 可以只检查部分和，如果某一行/列不等于 15，直接跳过

时间复杂度：O(m×n)，其中 m 和 n 是网格的行数和列数 空间复杂度：O(1)

代码实现

class Solution {
public:
    int numMagicSquaresInside(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        int count = 0;
        
        for (int i = 0; i <= rows - 3; i++) {
            for (int j = 0; j <= cols - 3; j++) {
                if (isMagicSquare(grid, i, j)) {
                    count++;
                }
            }
        }
        
        return count;
    }
    
private:
    bool isMagicSquare(vector<vector<int>>& grid, int row, int col) {
        // 检查是否包含1-9且无重复
        vector<bool> used(10, false);
        for (int i = row; i < row + 3; i++) {
            for (int j = col; j < col + 3; j++) {
                int num = grid[i][j];
                if (num < 1 || num > 9 || used[num]) {
                    return false;
                }
                used[num] = true;
            }
        }
        
        // 检查所有行、列、对角线的和是否等于15
        int target = 15;
        
        // 检查行
        for (int i = row; i < row + 3; i++) {
            if (grid[i][col] + grid[i][col + 1] + grid[i][col + 2] != target) {
                return false;
            }
        }
        
        // 检查列
        for (int j = col; j < col + 3; j++) {
            if (grid[row][j] + grid[row + 1][j] + grid[row + 2][j] != target) {
                return false;
            }
        }
        
        // 检查对角线
        if (grid[row][col] + grid[row + 1][col + 1] + grid[row + 2][col + 2] != target) {
            return false;
        }
        if (grid[row][col + 2] + grid[row + 1][col + 1] + grid[row + 2][col] != target) {
            return false;
        }
        
        return true;
    }
};

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        def is_magic_square(row, col):
            # 检查是否包含1-9且无重复
            nums = []
            for i in range(row, row + 3):
                for j in range(col, col + 3):
                    nums.append(grid[i][j])
            
            if sorted(nums) != list(range(1, 10)):
                return False
            
            # 检查所有行、列、对角线的和是否等于15
            target = 15
            
            # 检查行
            for i in range(row, row + 3):
                if sum(grid[i][col:col + 3]) != target:
                    return False
            
            # 检查列
            for j in range(col, col + 3):
                if grid[row][j] + grid[row + 1][j] + grid[row + 2][j] != target:
                    return False
            
            # 检查对角线
            if grid[row][col] + grid[row + 1][col + 1] + grid[row + 2][col + 2] != target:
                return False
            if grid[row][col + 2] + grid[row + 1][col + 1] + grid[row + 2][col] != target:
                return False
            
            return True
        
        rows, cols = len(grid), len(grid[0])
        count = 0
        
        for i in range(rows - 2):
            for j in range(cols - 2):
                if is_magic_square(i, j):
                    count += 1
        
        return count

public class Solution {
    public int NumMagicSquaresInside(int[][] grid) {
        int rows = grid.Length, cols = grid[0].Length;
        int count = 0;
        
        for (int i = 0; i <= rows - 3; i++) {
            for (int j = 0; j <= cols - 3; j++) {
                if (IsMagicSquare(grid, i, j)) {
                    count++;
                }
            }
        }
        
        return count;
    }
    
    private bool IsMagicSquare(int[][] grid, int row, int col) {
        // 检查是否包含1-9且无重复
        bool[] used = new bool[10];
        for (int i = row; i < row + 3; i++) {
            for (int j = col; j < col + 3; j++) {
                int num = grid[i][j];
                if (num < 1 || num > 9 || used[num]) {
                    return false;
                }
                used[num] = true;
            }
        }
        
        // 检查所有行、列、对角线的和是否等于15
        int target = 15;
        
        // 检查行
        for (int i = row; i < row + 3; i++) {
            if (grid[i][col] + grid[i][col + 1] + grid[i][col + 2] != target) {
                return false;
            }
        }
        
        // 检查列
        for (int j = col; j < col + 3; j++) {
            if (grid[row][j] + grid[row + 1][j] + grid[row + 2][j] != target) {
                return false;
            }
        }
        
        // 检查对角线
        if (grid[row][col] + grid[row + 1][col + 1] + grid[row + 2][col + 2] != target) {
            return false;
        }
        if (grid[row][col + 2] + grid[row + 1][col + 1] + grid[row + 2][col] != target) {
            return false;
        }
        
        return true;
    }
}

var numMagicSquaresInside = function(grid) {
    const isMagicSquare = (row, col) => {
        // 检查是否包含1-9且无重复
        const nums = [];
        for (let i = row; i < row + 3; i++) {
            for (let j = col; j < col + 3; j++) {
                nums.push(grid[i][j]);
            }
        }
        
        nums.sort((a, b) => a - b);
        for (let i = 0; i < 9; i++) {
            if (nums[i] !== i + 1) {
                return false;
            }
        }
        
        // 检查所有行、列、对角线的和是否等于15
        const target = 15;
        
        // 检查行
        for (let i = row; i < row + 3; i++) {
            if (grid[i][col] + grid[i][col + 1] + grid[i][col + 2] !== target) {
                return false;
            }
        }
        
        // 检查列
        for (let j = col; j < col + 3; j++) {
            if (grid[row][j] + grid[row + 1][j] + grid[row + 2][j] !== target) {
                return false;
            }
        }
        
        // 检查对角线
        if (grid[row][col] + grid[row + 1][col + 1] + grid[row + 2][col + 2] !== target) {
            return false;
        }
        if (grid[row][col + 2] + grid[row + 1][col + 1] + grid[row + 2][col] !== target) {
            return false;
        }
        
        return true;
    };
    
    const rows = grid.length, cols = grid[0].length;
    let count = 0;
    
    for (let i = 0; i <= rows - 3; i++) {
        for (let j = 0; j <= cols - 3; j++) {
            if (isMagicSquare(i, j)) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m × n)，其中 m 和 n 分别是网格的行数和列数。对于每个可能的 3×3 子网格，验证是否为幻方需要常数时间
空间复杂度O(1)，只使用了常数额外空间来存储临时变量和标记数组

相关题目