2025-02-25：统计 X 和 Y 频数相等的子矩阵数量。用go语言，给定一个二维字符矩阵 grid，元素可以是 'X'、'Y' 或 '.'。请计算满足以下条件的子矩阵的数量：

1.包含矩阵的左上角元素 grid[0][0]。

2.在所选子矩阵中，'X' 和 'Y' 的数量相等。

3.至少包含一个 'X'。

1 <= grid.length, grid[i].length <= 1000。

grid[i][j] 可能是 'X'、'Y' 或 '.'。

输入： grid = [["X","Y","."],["Y",".","."]]。

输出： 3。

答案2025-02-25：

chatgpt[1]

题目来自leetcode3212。

大体步骤如下：

1.创建函数 numberOfSubmatrices，该函数接受一个二维字符矩阵 grid 作为参数，并返回符合条件的子矩阵数量。

2.创建一个长度与 grid[0] 相同的二维数组 colCnt，用于存储每列中 'X' 和 'Y' 的出现次数。

3.遍历 grid 中的每一行：

3.1.初始化 s0 和 s1 分别表示当前列中 'X' 和 'Y' 的出现次数的总和。

3.2.遍历当前行中的每个字符：

3.2.1.如果字符不为 '.'，更新当前列对应的 'X' 或 'Y' 的出现次数。

3.2.2.更新当前列中 'X' 和 'Y' 的总和。

3.2.3.如果 s0 大于 0 且 s0 等于 s1，则增加符合条件的子矩阵数量。

4.返回子矩阵的数量 ans。

总的时间复杂度：

• 遍历二维字符矩阵需要 O(rows * columns) 的时间复杂度，即 O(n*m)，其中 n 和 m 分别为矩阵的行数和列数。

总的额外空间复杂度：

• 需要额外存储列中 'X' 和 'Y' 出现次数的二维数组 colCnt，其空间复杂度为 O(columns) 或者 O(m)，其中 m 为列数。

因此，总的时间复杂度为 O(n*m)，总的额外空间复杂度为 O(m)。

Go完整代码如下：package mainimport ( "fmt")func numberOfSubmatrices(grid [][]byte) (ans int) { colCnt := make([][2]int, len(grid[0])) for _, row := range grid { s0, s1 := 0, 0 for j, c := range row { if c != '.' { colCnt[j][c&1]++ } s0 += colCnt[j][0] s1 += colCnt[j][1] if s0 > 0 && s0 == s1 { ans++ } } } return}func main() { grid := [][]byte{{'X','Y','.'},{'Y','.','.'}} result := numberOfSubmatrices(grid) fmt.Println(result)}

在这里插入图片描述

Rust完整代码如下：

fn number_of_submatrices(grid: Vec<Vec<char>>) -> i32 { let mut ans = 0; let n = grid.len(); let m = grid[0].len(); let mut col_cnt = vec![[0; 2]; m]; for row in grid { let mut s0 = 0; let mut s1 = 0; for (j, &c) in row.iter().enumerate() { if c != '.' { col_cnt[j][(c as u8 - b'X') as usize % 2] += 1; // 'X' and 'Y' maps to 0 and 1 respectively } s0 += col_cnt[j][0]; s1 += col_cnt[j][1]; if s0 > 0 && s0 == s1 { ans += 1; } } } ans}fn main() { let grid = vec![ vec!['X', 'Y', '.'], vec!['Y', '.', '.'], ]; let result = number_of_submatrices(grid); println!("{}", result);}

在这里插入图片描述

Python完整代码如下：

# -*-coding:utf-8-*-def number_of_submatrices(grid): ans = 0 col_cnt = [[0, 0] for _ in range(len(grid[0]))] for row in grid: s0, s1 = 0, 0 for j, c in enumerate(row): if c != '.': col_cnt[j][ord(c) - ord('X')] += 1 # 'X' 和 'Y' 映射到 0 和 1 s0 += col_cnt[j][0] s1 += col_cnt[j][1] if s0 > 0 and s0 == s1: ans += 1 return ansdef main(): grid = [['X', 'Y', '.'], ['Y', '.', '.']] result = number_of_submatrices(grid) print(result)if __name__ == "__main__": main()

在这里插入图片描述

引用链接

[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP