当前位置：首页 > news >正文

【数据结构-二维前缀和】【列维护优化】力扣3212. 统计 X 和 Y 频数相等的子矩阵数量

news 2025/5/23 12:48:07

给你一个二维字符矩阵 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’ 或 ‘.’.

二位前缀和

class Solution {
public:int numberOfSubmatrices(vector<vector<char>>& grid) {int m = grid.size(), n = grid[0].size();int ans = 0;vector<vector<array<int,2>>> sum(m+1, vector<array<int,2>>(n+1));for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){sum[i+1][j+1][1] = sum[i+1][j][1] + sum[i][j+1][1] - sum[i][j][1];sum[i+1][j+1][0] = sum[i+1][j][0] + sum[i][j+1][0] - sum[i][j][0];if(grid[i][j] != '.'){sum[i+1][j+1][grid[i][j] & 1]++;}if(sum[i+1][j+1][0] && sum[i+1][j+1][0] == sum[i+1][j+1][1]){ans++;}}}return ans;}
};

时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度：O(mn)。

还是二位前缀和，这道题 x 的 ASCII 码值是 120。y 的 ASCII 码值是 121。X的二进制表示: 01111000，Y的二进制表示: 01111001。所以可以根据ascii码的二进制最低为来储存X和Y的数据。

题解中

sum[i+1][j+1][1] = sum[i+1][j][1] + sum[i][j+1][1] - sum[i][j][1];

细心的人就会发现怎么没有加上grid[i][j]所储存的值。实际上在下面代码中，当网格元素不等于’.'的时候，就是加上了grid[i][j]所储存的值，在这里表示为sum[i+1][j+1][grid[i][j] & 1]++;，最后判断X是否不为0，并比较前缀和中X和Y的数量是否相等。

优化：维护列字符元素

class Solution {
public:int numberOfSubmatrices(vector<vector<char>>& grid) {int m = grid.size(), n = grid[0].size();int ans = 0;vector<array<int, 2>> col_sum(n);for(int i = 0; i < m; i++){int s1 = 0, s2 = 0;for(int j = 0; j < n; j++){if(grid[i][j] != '.'){col_sum[j][grid[i][j] & 1]++;}s1 += col_sum[j][0];s2 += col_sum[j][1];if(s1 && s1 == s2){ans++;}}} return ans;}
};