LeetCode 750. 角矩形的数量

Categories:

题目描述
思路分析
1. 解法一：枚举行对 + 计数（推荐）
2. 解法二：动态规划（列对计数优化）
相似题目

题目描述

✅ 750. 角矩形的数量

思路分析

解法一：枚举行对 + 计数（推荐）

核心思路：

两个角矩形的四个角由”两行”和”两列”共同确定

枚举任意两行 r1、r2，统计这两行中同时为 1 的列数 common

对于 common 个公共列，任选两列即可构成一个角矩形，贡献 C(common, 2) = common * (common - 1) / 2

遍历所有行对，累加贡献即为答案

复杂度分析：

时间复杂度：O(m² * n)，其中 m 表示行数，n 表示列数

空间复杂度：O(1)，仅使用常数额外空间

class Solution {
  public int countCornerRectangles(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    int ans = 0;

    // 枚举两行
    for (int r1 = 0; r1 < m; r1++) {
      for (int r2 = r1 + 1; r2 < m; r2++) {
        int common = 0;

        // 统计两行中同时为 1 的列数
        for (int c = 0; c < n; c++) {
          if (grid[r1][c] == 1 && grid[r2][c] == 1) {
            common++;
          }
        }

        // C(common, 2) 种选法
        ans += common * (common - 1) / 2;
      }
    }

    return ans;
  }
}

func countCornerRectangles(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    ans := 0

    // 枚举两行
    for r1 := 0; r1 < m; r1++ {
        for r2 := r1 + 1; r2 < m; r2++ {
            common := 0

            // 统计两行同时为 1 的列数
            for c := 0; c < n; c++ {
                if grid[r1][c] == 1 && grid[r2][c] == 1 {
                    common++
                }
            }

            // C(common, 2)
            ans += common * (common - 1) / 2
        }
    }

    return ans
}

解法二：动态规划（列对计数优化）

核心思路：

用哈希表 cnt[c1][c2] 记录每对列 (c1, c2) 在已处理行中同时为 1 的次数

遍历每一行，对行内所有 1 的列对 (c1, c2) 查询 cnt 后累加答案，再将 cnt[c1][c2]++

适合行数远大于列数的情况

复杂度分析：

时间复杂度：O(m * k²)，其中 k 为每行中 1 的平均个数，最坏 O(m * n²)

空间复杂度：O(n²)，哈希表存储列对计数

class Solution {
  public int countCornerRectangles(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    int ans = 0;

    // cnt[c1][c2] 表示列对 (c1, c2) 在已处理行中同时为 1 的次数
    int[][] cnt = new int[n][n];

    for (int r = 0; r < m; r++) {
      // 收集当前行中所有为 1 的列
      List<Integer> ones = new ArrayList<>();
      for (int c = 0; c < n; c++) {
        if (grid[r][c] == 1) {
          ones.add(c);
        }
      }

      // 枚举当前行中所有列对
      for (int i = 0; i < ones.size(); i++) {
        for (int j = i + 1; j < ones.size(); j++) {
          int c1 = ones.get(i);
          int c2 = ones.get(j);
          ans += cnt[c1][c2];
          cnt[c1][c2]++;
        }
      }
    }

    return ans;
  }
}

func countCornerRectangles(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    ans := 0

    // cnt[c1][c2] 记录列对同时为 1 的行数
    cnt := make([][]int, n)
    for i := range cnt {
        cnt[i] = make([]int, n)
    }

    for r := 0; r < m; r++ {
        // 收集当前行为 1 的列索引
        ones := []int{}
        for c := 0; c < n; c++ {
            if grid[r][c] == 1 {
                ones = append(ones, c)
            }
        }

        // 枚举列对，累加答案后更新计数
        for i := 0; i < len(ones); i++ {
            for j := i + 1; j < len(ones); j++ {
                c1, c2 := ones[i], ones[j]
                ans += cnt[c1][c2]
                cnt[c1][c2]++
            }
        }
    }

    return ans
}

相似题目

题目	难度	考察点
1074. 元素和为目标值的子矩阵数量	困难	前缀和 + 哈希
304. 二维区域和检索 - 矩阵不可变	中等	二维前缀和
363. 矩形区域不超过 K 的最大数值和	困难	前缀和 + 枚举
221. 最大正方形	中等	动态规划
85. 最大矩形	困难	单调栈
1277. 统计全为 1 的正方形子矩阵	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/44055865