当前位置：首页 > news >正文

leetcode3128. 直角三角形-medium

news 2025/6/3 0:38:55

1 题目：直角三角形

官方标定难度：中

给你一个二维 boolean 矩阵 grid 。

如果 grid 的 3 个元素的集合中，一个元素与另一个元素在同一行，并且与第三个元素在同一列，则该集合是一个直角三角形。3 个元素不必彼此相邻。

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

示例 1：

在这里插入图片描述

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

输出：2

解释：

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

示例 2：

在这里插入图片描述

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

输出：0

解释：

没有值为 1 的直角三角形。注意蓝色的那个没有组成直角三角形。

示例 3：

在这里插入图片描述

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

输出：2

解释：

有两个值为 1 的直角三角形。

提示：

1 <= grid.length <= 1000
1 <= grid[i].length <= 1000
0 <= grid[i][j] <= 1

2 solution

代码

class Solution {
public:long long numberOfRightTriangles(vector<vector<int>> &grid) {int m = grid.size(), n = grid[0].size();vector<int> row(m), col(n);long long s = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {row[i] += grid[i][j];col[j] += grid[i][j];}}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j]) {s += (row[i] - 1ll) * (col[j] - 1);   }}}return s;};
};