＜矩阵_前缀和＞LeetCode3212. 统计 X 和 Y 频数相等的子矩阵数量

LeetCode3212. 统计 X 和 Y 频数相等的子矩阵数量LeetCode3212我的解法AC了// 我的思路 :// 条件要求包含grid[0][0],意思是这个矩阵一定是以grid[0][0]为左上角的,只用确定它的右上角即可确定唯一矩阵// arr[i][j]的值以grid[0][0]为左上角,以grid[i][j]为右上角的矩阵中X和Y的数量// arr[i][j].first的值以grid[0][0]为左上角,以grid[i][j]为右上角的矩阵中X的数量// arr[i][j].second的值以grid[0][0]为左上角,以grid[i][j]为右上角的矩阵中Y的数量// 认真观察发现arr[i][j]的递推公式// arr[i][j].first(以grid[i-1][j]结束的矩阵的X数量)(以grid[i][j-1]结束的矩阵的X数量)-(矩阵重复计算的X数量-arr[i-1][j-1].first)(这个grid[i][j]是不是X);// arr[i][j].second(以grid[i-1][j]结束的矩阵的Y数量)(以grid[i][j-1]结束的矩阵的Y数量)-(矩阵重复计算的Y数量-arr[i-1][j-1].second)(这个grid[i][j]是不是Y);// (注意边界问题)classSolution{public:intnumberOfSubmatrices(vectorvectorchargrid){intcnt0;//统计符合条件的矩阵数量---返回值vectorvectorpairint,intarr(grid.size(),vectorpairint,int(grid[0].size(),{0,0}));//创建arr数组for(inti0;igrid.size();i){for(intj0;jgrid[0].size();j){arr[i][j].first(i-10?arr[i-1][j].first:0)(j-10?arr[i][j-1].first:0)-(i-10j-10?arr[i-1][j-1].first:0)(grid[i][j]X?1:0);arr[i][j].second(i-10?arr[i-1][j].second:0)(j-10?arr[i][j-1].second:0)-(i-10j-10?arr[i-1][j-1].second:0)(grid[i][j]Y?1:0);//三目运算符 哈哈哈if(arr[i][j].firstarr[i][j].secondarr[i][j].first0)cnt;//若满足(X数量Y数量X数量0)就计数}}returncnt;}};