力扣刷题之3128.直角三角形
题干描述
给你一个二维 boolean 矩阵 grid 。
请你返回使用 grid 中的 3 个元素可以构建的 直角三角形 数目，且满足 3 个元素值 都 为 1 。
注意：
- 如果
grid中 3 个元素满足：一个元素与另一个元素在 同一行，同时与第三个元素在 同一列 ，那么这 3 个元素称为一个 直角三角形 。这 3 个元素互相之间不需要相邻。
示例 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 个直角三角形。
示例 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
解释：
没有直角三角形。
示例 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
解释：
有两个直角三角形。
题干描述
问题理解
我们需要在一个二维布尔矩阵grid中统计由1组成的直角三角形的数量。一个直角三角形由三个元素组成，要求：
- 一个元素与另一个元素在同一行。
- 这个元素还需要与第三个元素在同一列。
这些组成三角形的元素之间不需要相邻。
解题思路
为了解决这个问题，我们需要系统地检查矩阵中的每一个位置，看它是否能作为直角三角形直角顶点。具体步骤如下：
1.统计行和列中i的数量
- 对于矩阵中的内个单元格，计算它所在的行和列中1的数量。的数量。这有助于我们确定可以形成三角形的水平和垂直线。
2.计算直角三角形的数量
对于每一个位置（i，j）的1，我们计算它所在的行和列中1的数量。
如果grid[i][j]为1，则可以通过在同行中选择另一个1和在同列中选择另一个1来形成三角形。
这种情况下的三角形数量为（row_count - 1）*（col_count - 1），其中row_count是第i行中的1的数量，col_count 是第 j 列中的 1 的数量，减去当前的 1 是为了避免重复计算当前位置。
代码详解
#include <stdio.h>
#include <stdlib.h>
#include <string.h>//计算矩阵中的直角三角形数量
long long numberOfRightTriangles(int** grid, int gridSize, int* gridColSize) {int n = gridSize, m = gridColSize[0];int* col = (int*)malloc(m * sizeof(int));//动态分配内存用于计算计数数组memset(col, 0, m * sizeof(int));//将数组col中的所有数组初始化为0//计算每列中1的数量for (int i = 0; i < n; i++){for (int j = 0; j < m; j++) {col[j] += grid[i][j];}}long long res = 0;//用于存储直角三角形的数量for (int i = 0; i < n; i++){int row = 0;//计算当前行中1的数量for (int j = 0; j < m; j++){row += grid[i][j];}//对于当前行中的每个1，计算能够构成的直角三角形数量for (int j = 0; j < m; j++){if (grid[i][j] == 1) {//如果grid[i][j]为1，则可能构成三角形的个数为(row - 1) * (col[j] - 1)res += (long long)(row - 1) * (col[j] - 1);}}}free(col);//释放动态分配的内存return res;}
int main() {// 测试用例1int grid1Data[][3] = {{0, 1, 0},{0, 1, 1},{0, 1, 0}};int gridSize1 = 3;int gridColSize1 = 3;int** grid1 = (int**)malloc(gridSize1 * sizeof(int*));for (int i = 0; i < gridSize1; i++) {grid1[i] = (int*)malloc(gridColSize1 * sizeof(int));memcpy(grid1[i], grid1Data[i], gridColSize1 * sizeof(int));}int gridColSizes1[] = { gridColSize1, gridColSize1, gridColSize1 };printf("Output: %lld\n", numberOfRightTriangles(grid1, gridSize1, gridColSizes1));for (int i = 0; i < gridSize1; i++) {free(grid1[i]);}free(grid1);// 测试用例2int grid2Data[][4] = {{1, 0, 0, 0},{0, 1, 0, 1},{1, 0, 0, 0}};int gridSize2 = 3;int gridColSize2 = 4;int** grid2 = (int**)malloc(gridSize2 * sizeof(int*));for (int i = 0; i < gridSize2; i++) {grid2[i] = (int*)malloc(gridColSize2 * sizeof(int));memcpy(grid2[i], grid2Data[i], gridColSize2 * sizeof(int));}int gridColSizes2[] = { gridColSize2, gridColSize2, gridColSize2 };printf("Output: %lld\n", numberOfRightTriangles(grid2, gridSize2, gridColSizes2));for (int i = 0; i < gridSize2; i++) {free(grid2[i]);}free(grid2);// 测试用例3int grid3Data[][3] = {{1, 0, 1},{1, 0, 0},{1, 0, 0},{1, 0, 1},{1, 0, 0},{1, 0, 0}};int gridSize3 = 6;int gridColSize3 = 3;int** grid3 = (int**)malloc(gridSize3 * sizeof(int*));for (int i = 0; i < gridSize3; i++) {grid3[i] = (int*)malloc(gridColSize3 * sizeof(int));memcpy(grid3[i], grid3Data[i], gridColSize3 * sizeof(int));}int gridColSizes3[] = { gridColSize3, gridColSize3, gridColSize3, gridColSize3, gridColSize3, gridColSize3 };printf("Output: %lld\n", numberOfRightTriangles(grid3, gridSize3, gridColSizes3));for (int i = 0; i < gridSize3; i++) {free(grid3[i]);}free(grid3);return 0;
}