直角三角形。用go语言，给定一个二维布尔矩阵 grid，要求找出在该矩阵中以数值为 1 的元素构成的集合中，有多少个直角三角形。直角三角形的定义是其中的三个元素分别在同一行、同一列。
输入：grid = [[0,1,0],[0,1,1],[0,1,0]]。
输出：2。
解释：
有 2 个值为 1 的直角三角形。注意蓝色的那个 没有 组成直角三角形，因为 3 个元素在同一列。
大体步骤如下：
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 main
import (
"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));
}
