2025-02-25：统计 X 和 Y 频数相等的子矩阵数量。用go语言，给定一个二维字符矩阵 grid，元素可以是 ‘X‘、‘

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 main

import (

  "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 {

  letmut ans = 0;

  letn = grid.len();

  letm = grid[0].len();

  letmut col_cnt = vec![[0; 2]; m];

  forrowin grid {

      letmut s0 = 0;

      letmut s1 = 0;

      for (j, &c) in row.iter().enumerate() {

          if c != '.' {

              col_cnt[j][(c asu8 - b'X') asusize % 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

}

fnmain() {

  letgrid = vec![

      vec!['X', 'Y', '.'],

      vec!['Y', '.', '.'],

  ];

  letresult = number_of_submatrices(grid);

  println!("{}", result);

}

在这里插入图片描述Python完整代码如下：

# -*-coding:utf-8-*-

defnumber_of_submatrices(grid):

  ans = 0

  col_cnt = [[0, 0] for _ inrange(len(grid[0]))]

  for row in grid:

      s0, s1 = 0, 0

      for j, c inenumerate(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 > 0and s0 == s1:

              ans += 1

  return ans

defmain():

  grid = [['X', 'Y', '.'], ['Y', '.', '.']]

  result = number_of_submatrices(grid)

  print(result)

if __name__ == "__main__":

  main()

在这里插入图片描述引用链接