题目描述

一个二维数组grid只包含0,1，找到grid中的矩形个数。在矩形中4个不同的1表示一个四边形的四个角。只需要求与x轴和y轴平行的矩形，不考虑旋转的情况。

样例

Input: grid = 
[[1, 0, 0, 1, 0],
 [0, 0, 1, 0, 1],
 [0, 0, 0, 1, 0],
 [1, 0, 1, 0, 1]]
Output: 1

Explanation: 例子中只有一个矩形，由 grid[1][2], grid[1][4], grid[3][2], grid[3][4] 组成.

Input: grid = 
[[1, 1, 1],
 [1, 1, 1],
 [1, 1, 1]]
Output: 9
Explanation: 例子中有4个2x2矩形, 四个2x3和3x2矩形, 一个3x3矩形.

Input: grid = 
[[1, 1, 1, 1]]
Output: 0
Explanation: 矩形的四个角必须是不同的1组成.

算法1

动态规划 $O(n^2*m)$

定义n为行数，m为列数，建立一个二维数组dp[n][n]。对于每一列遍历，dp[i][k]表示前m列中，第i行为1且第k行为1的个数。

当前遍历第j列时，如果grid[i][j]==1&&grid[k][j]==1，则以grid[i][j] grid[k][j]为右上角和右下角的的矩形个数为dp[i][k]
第j列遍历结束后，更新dp[i][k] += grid[i][j]&grid[k][j]

时间复杂度分析：每一列的遍历中，对行遍历了n*n次，时间复杂度O(n^2*m)，空间复杂度O(n*n)

Java 代码

class Solution {
    public int countCornerRectangles(int[][] grid) {
        int n=grid.length;
        if(n<=1) return 0;
        int m=grid[0].length;
        if(m<=1) return 0;

        int[][] dp = new int[n][n];

        for(int i=0; i<n; i++)
            for(int i1=0; i1<n; i1++)
                dp[i][i1] = grid[i][0]&grid[i1][0];

        int ans=0;
        for(int j=1; j<m; j++) {
            for(int i=0; i<n; i++) {
                for(int i1=0; i1<i; i1++){
                    if(grid[i1][j]!=1||grid[i][j]!=1) continue;
                    ans+=dp[i][i1];
                }
            }
            for(int i=0; i<n; i++) {
                for(int i1=0; i1<n; i1++)
                    dp[i1][i] += grid[i][j]&grid[i1][j];
            }
        }
        return ans;
    }
}