直角三角形-LeetCode

3128. 直角三角形

🎯 问题描述

描述：
给你一个二维 boolean 矩阵 grid。
请你返回使用 grid 中的 3 个元素可以构建的直角三角形数目，且满足 3 个元素值都为 1。

注意：

• 如果 grid 中 3 个元素满足：一个元素与另一个元素在同一行，同时与第三个元素在同一列，那么这 3 个元素称为一个直角三角形。
• 这 3 个元素互相之间不需要相邻。
• 直角顶点是那个既在行上又在列上的交点元素。

说明：

• 这是一个矩阵统计结合组合数学的问题。

• 核心策略：

  • 直角三角形由三个点组成：直角顶点 (r, c)，同行点 (r, c2)，同列点 (r2, c)。
  • 我们可以枚举每一个值为 1 的格子作为直角顶点。
  • 对于每个直角顶点，它能形成的三角形数量 = (该行其他 1 的个数) × (该列其他 1 的个数)。

• 优化：为了避免重复计算每行每列的 1 的个数，我们可以先预处理统计出每一行和每一列的总和。

• 示例：

• 示例 1：

输入：grid = [[0,1,0],[0,1,1],[0,1,0]]
输出：2
解释：
- 只有 grid[1][1] (值为1) 可以作为直角顶点，因为它所在的行和列都有其他1。
- 行 1 的 1 的个数：2 (位置 (1,1), (1,2))。除去自己，还剩 1 个。
- 列 1 的 1 的个数：3 (位置 (0,1), (1,1), (2,1))。除去自己，还剩 2 个。
- 组合数：1 * 2 = 2。
- 另外两个 1 (0,1) 和 (2,1) 虽然在同列，但所在行没有其他 1，无法构成三角形。

💻 解题思路

思路1：预处理计数 + 乘法原理

核心逻辑

1. 预处理统计：
   • 创建两个数组 row_count 和 col_count。
   • 遍历整个矩阵，统计每一行有多少个 1，每一列有多少个 1。
2. 枚举直角顶点：
   • 再次遍历矩阵，对于每个 grid[i][j] == 1 的位置：
   • 假设它是直角顶点。
   • 它所在的第 i 行还有 row_count[i] - 1 个 1 可以作为三角形的第二个顶点。
   • 它所在的第 j 列还有 col_count[j] - 1 个 1 可以作为三角形的第三个顶点。
3. 计算组合：
   • 根据乘法原理，以 (i, j) 为直角顶点的三角形数量为 (row_count[i] - 1) * (col_count[j] - 1)。
   • 将所有结果累加。

代码实现

class Solution:
    def numberOfRightTriangles(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        
        # 1. 预处理：统计每行和每列中 1 的个数
        row_count = [0] * n
        col_count = [0] * m
        
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    row_count[i] += 1
                    col_count[j] += 1
        
        # 2. 枚举每个 1 作为直角顶点
        ans = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    # 3. 计算以 (i,j) 为直角顶点的三角形数量
                    # 同一行可选的其他 1 的个数
                    row_options = row_count[i] - 1
                    # 同一列可选的其他 1 的个数
                    col_options = col_count[j] - 1
                    
                    # 乘法原理
                    ans += row_options * col_options
                    
        return ans

📊 性能分析

• 时间复杂度：$O(N \times M)$
  • 其中 $N$ 是行数，$M$ 是列数。
  • 第一次遍历用于统计行列计数，耗时 $O(N \times M)$。
  • 第二次遍历用于枚举直角顶点并计算，耗时 $O(N \times M)$。
  • 总时间复杂度为 $O(N \times M)$。
• 空间复杂度：$O(N + M)$
  • 需要两个数组 row_count 和 col_count 分别存储行和列的计数。

思考

1. 为什么只需要考虑直角顶点？

   • 题目定义的直角三角形，其直角边平行于坐标轴。这意味着三个顶点中，有且仅有一个点既是“行连接点”又是“列连接点”，这个点就是直角顶点。
   • 另外两个点分别只贡献行方向或列方向的连接。
   • 因此，通过枚举直角顶点，我们可以不重不漏地覆盖所有可能的三角形。

2. 乘法原理的应用：

   • 对于固定的直角顶点 (i, j)，我们需要从第 i 行选一个点，从第 j 列选一个点。
   • 这两个选择是独立的。
   • 行方向有 row_count[i] - 1 种选择（减 1 排除自身）。
   • 列方向有 col_count[j] - 1 种选择。
   • 总方案数即为两者乘积。

3. 减 1 的原因：

   • row_count[i] 统计的是第 i 行所有 1 的总数，其中包含了 (i, j) 本身。
   • 我们要找的是另外两个顶点，所以必须排除直角顶点自己。

4. 边界情况：

   • 某行或某列只有一个 1：row_options 或 col_options 为 0，贡献为 0。
   • 矩阵全为 0：没有直角顶点，返回 0。
   • 矩阵全为 1：每个点都可以作为直角顶点，计算量最大。

5. 算法的正确性：

   • 每个合法的直角三角形都有唯一的直角顶点。
   • 我们的算法枚举了所有可能的直角顶点，并计算了以每个顶点为直角的所有三角形。
   • 因此，每个三角形被且仅被计算一次。