发表于 2024.08.08

• 二维前缀和问题，由于子矩阵需要包含位置(0,0)，直接判断二维前缀0计数和1计数是否相等即可。

  class Solution:
      def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
          m, n = len(grid), len(grid[0])
          prev_x = [[0] * n for _ in range(m)]
          prev_y = [[0] * n for _ in range(m)]
          ans = 0
          for i in range(m):
              for j in range(n):
                  prev_x[i][j] = (
                         (prev_x[i - 1][j] if i > 0 else 0) +
                         (prev_x[i][j - 1] if j > 0 else 0) -
                         (prev_x[i - 1][j - 1] if i > 0 and j > 0 else 0)  # 务必剪掉重复计算的部分
                  ) + (grid[i][j] == 'X')
  
                  prev_y[i][j] = (
                         (prev_y[i - 1][j] if i > 0 else 0) +
                         (prev_y[i][j - 1] if j > 0 else 0) -
                         (prev_y[i - 1][j - 1] if i > 0 and j > 0 else 0)  # 务必剪掉重复计算的部分
                  ) + (grid[i][j] == 'Y')
                  
                  if prev_x[i][j] == prev_y[i][j] and prev_x[i][j] > 0:
                      ans += 1
          return ans

  类似题目：

  • LeetCode 1738 - 找出第K大的异或坐标值：二维前缀和+异或版本

  • LeetCode 1177 - 子数组异或查询

• LC 题目链接