当前位置: 首页> 文旅> 文化 > 力扣每日一题 直角三角形

力扣每日一题 直角三角形

时间:2025/7/13 18:52:03来源:https://blog.csdn.net/weixin_74141526/article/details/140881321 浏览次数:0次

题目

中等  数学

给你一个二维 boolean 矩阵 grid 。

请你返回使用 grid 中的 3 个元素可以构建的 直角三角形 数目,且满足 3 个元素值  为 1 。

注意:

  • 如果 grid 中 3 个元素满足:一个元素与另一个元素在 同一行,同时与第三个元素在 同一列 ,那么这 3 个元素称为一个 直角三角形 。这 3 个元素互相之间不需要相邻。

示例 1:

010
011
010

输入:grid = [[0,1,0],[0,1,1],[0,1,0]]

输出:2

解释:

有 2 个直角三角形。

示例 2:

1000
0101
1000

输入:grid = [[1,0,0,0],[0,1,0,1],[1,0,0,0]]

输出:0

解释:

没有直角三角形。

示例 3:

101
100
100

输入:grid = [[1,0,1],[1,0,0],[1,0,0]]

输出:2

解释:

有两个直角三角形。

思路

根据题意,我们遍历这个二维数组,遇到为1的就计算它这行和这一列还有多少个1然后个数相乘就是可以组合出来的直角的数量,刚开始我的思路有点问题,我想的是计算当前遍历到的1的右边有多少1和下边有多少1,它们的数量相乘,可是它的上边和左边的1也是可以和后面的1组合出直角的,所以应该直接用当前行和当前列的1的数量-1再相乘即可。

解题过程

为了简化计算,我们可以预先设置两个数组计算出每一行和每一列的1的个数,然后挨个遍历数组,如果当前为1则结果加上(当前行的1的数量-1)*(当前列的1的数量-1),这样遍历一遍即可

复杂度

  • 时间复杂度: O(n^2)
  • 空间复杂度: O(n)

代码如下:

class Solution {
public:long long numberOfRightTriangles(vector<vector<int>>& grid) {int n=grid.size(),m=grid[0].size();vector<int> col(m),row(n);//分别存储每一行和每一列的1的个数for(int i=0;i<grid.size();i++){for(int j=0;j<grid[i].size();j++){col[j]+=grid[i][j];row[i]+=grid[i][j];}}long long res=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1){res+=(row[i]-1)*(col[j]-1);}}}return res;}
};

关键字:力扣每日一题 直角三角形

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: