JZX轻语：简
LeetCode 3212 - 统计 X 和 Y 频数相等的子矩阵数量
发表于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类似题目：