2024-12-06：直角三角形。用go语言，给定一个二维布尔矩阵 grid，要求找出在该矩阵中以数值为 1 的元素构成的集合中

福大大架构师每日一题

发布于 2024-12-09 14:25:07

2900

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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 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{
letn= grid.len();
letm= grid[0].len();
letmut col=vec![0; m];

// Calculate the sum of 1s in each column
foriin0..n {
forjin0..m {
            col[j]+= grid[i][j];
}
}

letmut res=0;

// Calculate the sum of 1s in each row and the number of right triangles
foriin0..n {
letrow:i32= grid[i].iter().sum();
forjin0..m {
if grid[i][j]==1{
                res +=(row -1)asi64*(col[j]-1)asi64;
}
}
}

    res
}

fnmain(){
letgrid=vec![
vec![0,1,0],
vec![0,1,1],
vec![0,1,0],
];
println!("{}",number_of_right_triangles(&grid));
}