2024-12-06：直角三角形。用go语言，给定一个二维布尔矩阵 grid，要求找出在该矩阵中以数值为 1 的元素构成的集合中，有多少个直角三角形。直角三角形的定义是其中的三个元素分别在同一行、同一列。

输入：grid = [[0,1,0],[0,1,1],[0,1,0]]。

输出：2。

解释：

有 2 个值为 1 的直角三角形。注意蓝色的那个 没有 组成直角三角形，因为 3 个元素在同一列。

答案2024-12-06：

chatgpt[1]

题目来自leetcode3128。

大体步骤如下：

1.获取输入二维布尔矩阵 grid 的行数和列数，并创建一个在列数的整数切片 col 用于记录每列中值为 1 的元素数量。

2.遍历整个矩阵，更新 col 中每一列中值为 1 的元素的数量。

3.初始化一个变量 res 用于记录直角三角形的数量。

4.遍历每一行：

• 统计当前行中值为 1 的元素数量并存储在 row 中。• 遍历当前行的每个元素，并根据行和列上的值为 1 的元素计算可以构成的直角三角形数量并累加到 res 中。

5.返回最终的直角三角形数量 res.

总的时间复杂度：

• 对整个矩阵的遍历为 O(nm)，其中 n 为行数，m 为列数。 总的时间复杂度为 O(nm)。

总的额外空间复杂度：

• 除了存储结果、函数参数和局部变量之外，额外使用了一个长度为列数的整数切片 col 用于记录每一列中值为 1 的元素的数量，因此额外空间复杂度为 O(m)。Go完整代码如下：package mainimport ( "fmt")func numberOfRightTriangles(grid [][]int) int64 { n := len(grid) m := len(grid[0]) col := make([]int, m) for i := 0; i < n; i++ { for j := 0; j < m; j++ { col[j] += grid[i][j] } } var res int64 for i := 0; i < n; i++ { row := 0 for j := 0; j < m; j++ { row += grid[i][j] } for j := 0; j < m; j++ { if grid[i][j] == 1 { res += int64(row-1) * int64(col[j]-1) } } } return res}func main() { grid := [][]int{{0, 1, 0}, {0, 1, 1}, {0, 1, 0}} fmt.Println(numberOfRightTriangles(grid))}

Rust完整代码如下：fn number_of_right_triangles(grid: &Vec<Vec<i32>>) -> i64 { let n = grid.len(); let m = grid[0].len(); let mut col = vec![0; m]; // Calculate the sum of 1s in each column for i in 0..n { for j in 0..m { col[j] += grid[i][j]; } } let mut res = 0; // Calculate the sum of 1s in each row and the number of right triangles for i in 0..n { let row: i32 = grid[i].iter().sum(); for j in 0..m { if grid[i][j] == 1 { res += (row - 1) as i64 * (col[j] - 1) as i64; } } } res}fn main() { let grid = vec![ vec![0, 1, 0], vec![0, 1, 1], vec![0, 1, 0], ]; println!("{}", number_of_right_triangles(&grid));}

引用链接

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