Skip to content

Latest commit

 

History

History
332 lines (279 loc) · 25 KB

README.md

File metadata and controls

332 lines (279 loc) · 25 KB
Raw
comments difficulty edit_url rating source tags
true
中等
1540
第 129 场双周赛 Q2
数组
哈希表
数学
组合数学
计数

3128. 直角三角形

English Version

题目描述

给你一个二维 boolean 矩阵 grid 。

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

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

 

示例 1：

0 1 0
0 1 1
0 1 0
0 1 0
0 1 1
0 1 0

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

输出：2

解释：

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

示例 2：

1 0 0 0
0 1 0 1
1 0 0 0

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

输出：0

解释：

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

示例 3：

1 0 1
1 0 0
1 0 0
1 0 1
1 0 0
1 0 0

输入：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

解法

方法一：计数 + 枚举

我们可以先统计每一行和每一列的 $1$ 的个数，记录在数组 $rows$ 和 $cols$ 中。

然后我们枚举每一个 $1$，假设当前 $1$ 在第 $i$ 行第 $j$ 列，那么以当前 $1$ 为直角三角形的直角点，另外两个直角点分别在第 $i$ 行和第 $j$ 列，那么直角三角形的个数就是 $(rows[i] - 1) \times (cols[j] - 1)$，累加到答案中即可。

时间复杂度 $O(m \times n)$，空间复杂度 $O(m + n)$。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

Python3

class Solution:
    def numberOfRightTriangles(self, grid: List[List[int]]) -> int:
        rows = [0] * len(grid)
        cols = [0] * len(grid[0])
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                rows[i] += x
                cols[j] += x
        ans = 0
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x:
                    ans += (rows[i] - 1) * (cols[j] - 1)
        return ans

Java

class Solution {
    public long numberOfRightTriangles(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] rows = new int[m];
        int[] cols = new int[n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                rows[i] += grid[i][j];
                cols[j] += grid[i][j];
            }
        }
        long ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    ans += (rows[i] - 1) * (cols[j] - 1);
                }
            }
        }
        return ans;
    }
}

C++

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

Go

func numberOfRightTriangles(grid [][]int) (ans int64) {
	m, n := len(grid), len(grid[0])
	rows := make([]int, m)
	cols := make([]int, n)
	for i, row := range grid {
		for j, x := range row {
			rows[i] += x
			cols[j] += x
		}
	}
	for i, row := range grid {
		for j, x := range row {
			if x == 1 {
				ans += int64((rows[i] - 1) * (cols[j] - 1))
			}
		}
	}
	return
}

TypeScript

function numberOfRightTriangles(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    const rows: number[] = Array(m).fill(0);
    const cols: number[] = Array(n).fill(0);
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            rows[i] += grid[i][j];
            cols[j] += grid[i][j];
        }
    }
    let ans = 0;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (grid[i][j] === 1) {
                ans += (rows[i] - 1) * (cols[j] - 1);
            }
        }
    }
    return ans;
}