Medium

题目描述

给定一个二维字符矩阵 grid，其中 grid[i][j] 是 ‘X’、‘Y’ 或 ‘.’ 中的一个，返回满足以下条件的子矩阵数量：

  • 包含 grid[0][0]
  • ‘X’ 和 ‘Y’ 的频率相等
  • 至少包含一个 ‘X’

示例 1：

输入：grid = [["X","Y","."],["Y",".","."]]
输出：3

示例 2：

输入：grid = [["X","X"],["X","Y"]]
输出：0
解释：没有子矩阵具有相等的 'X' 和 'Y' 频率。

示例 3：

输入：grid = [[".","."],[".","."]]
输出：0
解释：没有子矩阵至少包含一个 'X'。

约束条件：

  • 1 <= grid.length, grid[i].length <= 1000
  • grid[i][j] 是 ‘X’、‘Y’ 或 ‘.’ 中的一个

提示：

  • 将 ‘X’ 替换为 1，‘Y’ 替换为 -1，’.’ 替换为 0
  • 需要找到多少个从 grid[0][0] 开始的子矩阵 grid[0..x][0..y] 的和为 0 且至少包含一个 ‘X’
  • 使用前缀和来计算子矩阵的和

解题思路

这是一个巧妙的前缀和问题。根据题目提示，我们可以将问题转化：

核心思路：

  1. 数值映射：将 ‘X’ 映射为 1，‘Y’ 映射为 -1，’.’ 映射为 0
  2. 问题转化：寻找从 grid[0][0] 开始的子矩阵，使得矩阵和为 0（即 X 和 Y 数量相等）且至少包含一个 X

算法步骤：

  1. 构建二维前缀和数组，同时记录 X 的数量
  2. 遍历所有可能的右下角位置 (i,j)
  3. 对每个位置，检查从 (0,0) 到 (i,j) 的子矩阵是否满足条件：
    • 前缀和为 0（X 和 Y 数量相等）
    • X 的数量大于 0（至少有一个 X）

优化要点：

  • 使用前缀和避免重复计算
  • 同时维护数值前缀和（用于判断 X、Y 是否相等）和 X 数量前缀和（用于判断是否有 X）

时间复杂度为 O(m×n)，空间复杂度为 O(m×n)，其中 m 和 n 分别为矩阵的行数和列数。

代码实现

class Solution {
public:
    int numberOfSubmatrices(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        // 前缀和数组：prefixSum[i][j] 表示从(0,0)到(i,j)的数值和
        // prefixX[i][j] 表示从(0,0)到(i,j)的X的数量
        vector<vector<int>> prefixSum(m + 1, vector<int>(n + 1, 0));
        vector<vector<int>> prefixX(m + 1, vector<int>(n + 1, 0));
        
        int result = 0;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int val = 0, xCount = 0;
                
                if (grid[i-1][j-1] == 'X') {
                    val = 1;
                    xCount = 1;
                } else if (grid[i-1][j-1] == 'Y') {
                    val = -1;
                }
                
                prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] 
                                - prefixSum[i-1][j-1] + val;
                prefixX[i][j] = prefixX[i-1][j] + prefixX[i][j-1] 
                              - prefixX[i-1][j-1] + xCount;
                
                // 检查从(0,0)到(i-1,j-1)的子矩阵
                if (prefixSum[i][j] == 0 && prefixX[i][j] > 0) {
                    result++;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # 前缀和数组
        prefix_sum = [[0] * (n + 1) for _ in range(m + 1)]
        prefix_x = [[0] * (n + 1) for _ in range(m + 1)]
        
        result = 0
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                val = 0
                x_count = 0
                
                if grid[i-1][j-1] == 'X':
                    val = 1
                    x_count = 1
                elif grid[i-1][j-1] == 'Y':
                    val = -1
                
                prefix_sum[i][j] = (prefix_sum[i-1][j] + prefix_sum[i][j-1] 
                                  - prefix_sum[i-1][j-1] + val)
                prefix_x[i][j] = (prefix_x[i-1][j] + prefix_x[i][j-1] 
                                - prefix_x[i-1][j-1] + x_count)
                
                # 检查从(0,0)到(i-1,j-1)的子矩阵
                if prefix_sum[i][j] == 0 and prefix_x[i][j] > 0:
                    result += 1
        
        return result

public class Solution {
    public int NumberOfSubmatrices(char[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        
        // 前缀和数组
        int[,] prefixSum = new int[m + 1, n + 1];
        int[,] prefixX = new int[m + 1, n + 1];
        
        int result = 0;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int val = 0, xCount = 0;
                
                if (grid[i-1][j-1] == 'X') {
                    val = 1;
                    xCount = 1;
                } else if (grid[i-1][j-1] == 'Y') {
                    val = -1;
                }
                
                prefixSum[i, j] = prefixSum[i-1, j] + prefixSum[i, j-1] 
                                - prefixSum[i-1, j-1] + val;
                prefixX[i, j] = prefixX[i-1, j] + prefixX[i, j-1] 
                              - prefixX[i-1, j-1] + xCount;
                
                // 检查从(0,0)到(i-1,j-1)的子矩阵
                if (prefixSum[i, j] == 0 && prefixX[i, j] > 0) {
                    result++;
                }
            }
        }
        
        return result;
    }
}

var numberOfSubmatrices = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    let count = 0;
    
    // Prefix sum arrays for X and Y counts
    const prefixX = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    const prefixY = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    
    // Build prefix sum arrays
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            prefixX[i][j] = prefixX[i-1][j] + prefixX[i][j-1] - prefixX[i-1][j-1];
            prefixY[i][j] = prefixY[i-1][j] + prefixY[i][j-1] - prefixY[i-1][j-1];
            
            if (grid[i-1][j-1] === 'X') {
                prefixX[i][j]++;
            } else if (grid[i-1][j-1] === 'Y') {
                prefixY[i][j]++;
            }
        }
    }
    
    // Check all submatrices starting from (0,0)
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            const xCount = prefixX[i][j];
            const yCount = prefixY[i][j];
            
            if (xCount > 0 && xCount === yCount) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m×n)需要遍历整个矩阵一次，每个位置的计算都是 O(1)
空间复杂度O(m×n)需要两个大小为 (m+1)×(n+1) 的前缀和数组

相关题目