当前位置: 首页> 教育> 大学 > 广东人才招聘网_建盏公司最新消息_网络广告宣传平台_宁波seo优化定制

广东人才招聘网_建盏公司最新消息_网络广告宣传平台_宁波seo优化定制

时间:2025/7/11 15:17:51来源:https://blog.csdn.net/Pisasama/article/details/142827098 浏览次数:0次
广东人才招聘网_建盏公司最新消息_网络广告宣传平台_宁波seo优化定制

力扣3128. 直角三角形

题目解析及思路

题目要求找到矩阵中的直角三角形,不必相邻

套路:三个点**枚举(中间)**直角顶点更容易计算

对于(i,j)的直角顶点,构成直角三角形有多少个?

设第 i 行有 rowSum 个 1,第 j 列有 colSum 个 1。根据乘法原理,直角顶点为 (i,j) 的「直角三角形」有

(rowSum−1)⋅(colSum−1)

那么也就是说我们要求出rowSum和colSum,再通过乘法原理计算答案即可

实现见代码

代码

class Solution {
public:long long numberOfRightTriangles(vector<vector<int>>& grid) {//n为列数int n = grid[0].size();//提前-1vector<int> col_sum(n,-1);for(auto &row : grid)//遍历每一列 再对应列+=row[j]for(int j=0;j<n;j++)col_sum[j] += row[j];long long ans = 0;for(auto &row : grid){//reduce求和,同样提前-1int row_sum = reduce(row.begin(), row.end()) - 1;for(int j=0;j<n;j++)//枚举当前点作为直角顶点if(row[j] == 1)ans += row_sum * col_sum[j];}return ans;}
};
关键字:广东人才招聘网_建盏公司最新消息_网络广告宣传平台_宁波seo优化定制

版权声明:

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

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

责任编辑: