技术

leetcode 750.角矩阵的数量

image.png

解题思路

  1. 就是分析两两行之前能构成多少个矩阵，显然就是看两行有多少相同列位置的1（grid[i][j] == grid[z][j] == 1）,然后排列组合的公式(a * (a - 1)) / 2;
  2. 1个for循环是遍历所有行，一个for循环是当前行之前的行（要挨个比较与之前的每行麻），一个for循环是列宽度，看两行有多个相同位置的1
  3. 把所有结果相加

复杂度分析

  • 时间复杂度： O(n^3)，认为行列都是n
  • 空间复杂度： O(1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define LEN 100
int countCornerRectangles(int** grid, int gridSize, int* gridColSize){
    //int row[LEN] = {0};
    int res = 0;
    for (int i = 0; i < gridSize; i ++) {
        for (int z = 0; z < i; z++) {
            int temp = 0;       
            for (int j = 0; j < *gridColSize; j++) {
                if (grid[i][j] == 1 &&  grid[z][j]  == 1) {
                    temp += 1;
                }                
            }
            res += (temp * (temp -1)) / 2;
        }
    }
    return res;
}