- Leetcode 3212. Count Submatrices With Equal Frequency of X and Y
- 1. 解题思路
- 2. 代码实现
- 题目链接:3212. Count Submatrices With Equal Frequency of X and Y
1. 解题思路
这一题我的思路就是一个二维累计数组的实现,具体来说,我们事先算出关于x和y的两个二维累积矩阵,然后遍历一下每一个位置,看看他们作为矩形右下角的位置时,对应的矩形内x和y的个数是否相同且不为0。
2. 代码实现
给出python代码实现如下:
class Solution:
def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
n, m = len(grid), len(grid[0])
def count(ch):
cnt = [[0 for _ in range(m)] for _ in range(n)]
cnt[0][0] = 0 if grid[0][0] != ch else 1
for j in range(1, m):
cnt[0][j] = cnt[0][j-1] if grid[0][j] != ch else cnt[0][j-1]+1
for i in range(1, n):
cnt[i][0] = cnt[i-1][0] if grid[i][0] != ch else cnt[i-1][0]+1
for j in range(1, m):
cnt[i][j] = cnt[i-1][j] + cnt[i][j-1] - cnt[i-1][j-1]
if grid[i][j] == ch:
cnt[i][j] += 1
return cnt
cntx = count("X")
cnty = count("Y")
ans = 0
for i in range(n):
for j in range(m):
if cntx[i][j] == cnty[i][j] and cntx[i][j] > 0:
ans += 1
return ans
提交代码评测得到:耗时3560ms,占用内存108.8MB。