天猫与京东的网站建设管理,如何做一个购物网站,小程序直播开发,自己做免费手机网站题干描述
给你一个二维 boolean 矩阵 grid 。
请你返回使用 grid 中的 3 个元素可以构建的 直角三角形 数目#xff0c;且满足 3 个元素值 都 为 1 。
注意#xff1a;
如果 grid 中 3 个元素满足#xff1a;一个元素与另一个元素在 同一行#xff0c;同时与第三个元素…题干描述
给你一个二维 boolean 矩阵 grid 。
请你返回使用 grid 中的 3 个元素可以构建的 直角三角形 数目且满足 3 个元素值 都 为 1 。
注意
如果 grid 中 3 个元素满足一个元素与另一个元素在 同一行同时与第三个元素在 同一列 那么这 3 个元素称为一个 直角三角形 。这 3 个元素互相之间不需要相邻。 示例 1
010011010
010011010
输入grid [[0,1,0],[0,1,1],[0,1,0]]
输出2
解释
有 2 个直角三角形。
示例 2
100001011000
输入grid [[1,0,0,0],[0,1,0,1],[1,0,0,0]]
输出0
解释
没有直角三角形。
示例 3
101100100
101100100
输入grid [[1,0,1],[1,0,0],[1,0,0]]
输出2
解释
有两个直角三角形。
题干描述
问题理解 我们需要在一个二维布尔矩阵grid中统计由1组成的直角三角形的数量。一个直角三角形由三个元素组成要求
一个元素与另一个元素在同一行。这个元素还需要与第三个元素在同一列。 这些组成三角形的元素之间不需要相邻。
解题思路 为了解决这个问题我们需要系统地检查矩阵中的每一个位置看它是否能作为直角三角形直角顶点。具体步骤如下
1.统计行和列中i的数量
对于矩阵中的内个单元格计算它所在的行和列中1的数量。的数量。这有助于我们确定可以形成三角形的水平和垂直线。
2.计算直角三角形的数量
对于每一个位置ij的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;
}
