Given a grid where each entry is only 0 or 1, find the number of corner rectangles.

A corner rectangle is 4 distinct 1s on the grid that form an axis-aligned rectangle. Note that only the corners need to have the value 1. Also, all four 1s used must be distinct.

Example 1:

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: There is only one corner rectangle, with corners grid[1][2], grid[1][4], grid[3][2], grid[3][4].

Example 2:

Input: grid =

[[1, 1, 1],

 [1, 1, 1],

 [1, 1, 1]]

Output: 9

Explanation: There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.

Example 3:

Input: grid =

[[1, 1, 1, 1]]

Output: 0

Explanation: Rectangles must have four distinct corners.

Note:

The number of rows and columns of grid will each be in the range [1, 200].
Each grid[i][j] will be either 0 or 1.
The number of 1s in the grid will be at most 6000.

给了一个由0和1组成的二维数组，定义了一种边角矩形，其四个顶点均为1，求这个二维数组中有多少个不同的边角矩形。

不能一个一个的数，先固定2行，求每列与这2行相交是不是都是1 ，计算这样的列数，然后用公式：n*(n-1)/2，得出能组成的边角矩形，累加到结果中。

解法：枚举，枚举任意两行r1和r2，看这两行中存在多少列，满足在该列中第r1行和第r2行中对应的元素都是1。假设有counter列满足条件，那么这两行可以构成的的recangles的数量就是counter * (counter - 1) / 2。最后返回所有rectangles的数量即可。如果假设grid一共有m行n列，时间复杂度就是O(m^2n)，空间复杂度是O(1)。如果m远大于n的时候，还可以将时间复杂度优化到O(mn^2)。

Java:

class Solution {

    public int countCornerRectangles(int[][] grid) {

        int m = grid.length, n = grid[0].length;

        int ans = 0;

        for (int x = 0; x < m; x++) {

            for (int y = x + 1; y < m; y++) {

                int cnt = 0;

                for (int z = 0; z < n; z++) {

                    if (grid[x][z] == 1 && grid[y][z] == 1) {

                        cnt++;

                    }

                }

                ans += cnt * (cnt - 1) / 2;

            }

        }

        return ans;

    }

}

Python:

def countCornerRectangles(self, grid):

        """

        :type grid: List[List[int]]

        :rtype: int

        """

        n = len(grid)

        m = len(grid[0])

        res = 0

        for i in xrange(n):

            for j in xrange(i + 1, n):

                np = 0

                for k in xrange(m):

                    if grid[i][k] and grid[j][k]:

                        np += 1

                res += np * (np - 1) / 2

        return res

Python:

# Time:  O(n * m^2), n is the number of rows with 1s, m is the number of cols with 1s

# Space: O(n * m)

class Solution(object):

    def countCornerRectangles(self, grid):

        """

        :type grid: List[List[int]]

        :rtype: int

        """

        rows = [[c for c, val in enumerate(row) if val]

                for row in grid]

        result = 0

        for i in xrange(len(rows)):

            lookup = set(rows[i])

            for j in xrange(i):

                count = sum(1 for c in rows[j] if c in lookup)

                result += count*(count-1)/2

        return result

C++: 暴力，不好

class Solution {

public:

    int countCornerRectangles(vector<vector<int>>& grid) {

        int m = grid.size(), n = grid[0].size(), res = 0;

        for (int i = 0; i < m; ++i) {

            for (int j = 0; j < n; ++j) {

                if (grid[i][j] == 0) continue;

                for (int h = 1; h < m - i; ++h) {

                    if (grid[i + h][j] == 0) continue;

                    for (int w = 1; w < n - j; ++w) {

                        if (grid[i][j + w] == 1 && grid[i + h][j + w] == 1) ++res;

                    }

                }

            }

        }

        return res;

    }

};

C++:

// Time:  O(m^2 * n), m is the number of rows with 1s, n is the number of cols with 1s

// Space: O(m * n)

class Solution {

public:

    int countCornerRectangles(vector<vector<int>>& grid) {

        vector<vector<int>> rows;

        for (int i = 0; i < grid.size(); ++i) {

            vector<int> row;

            for (int j = 0; j < grid[i].size(); ++j) {

                if (grid[i][j]) {

                    row.emplace_back(j);

                }

            }

            if (!row.empty()) {

                rows.emplace_back(move(row));

            }

        }

        int result = 0;

        for (int i = 0; i < rows.size(); ++i) {

            unordered_set<int> lookup(rows[i].begin(), rows[i].end());

            for (int j = 0; j < i; ++j) {

                int count = 0;

                for (const auto& c : rows[j]) {

                    count += lookup.count(c);

                }

                result += count * (count - 1) / 2;

            }

        }

        return result;

    }

};

C++:

class Solution {

public:

    int countCornerRectangles(vector<vector<int>>& grid) {

        int ans = 0;

        for (int r1 = 0; r1 + 1 < grid.size(); ++r1) {

            for (int r2 = r1 + 1; r2 < grid.size(); ++r2) {

                int counter = 0;

                for (int c = 0; c < grid[0].size(); ++c) {

                    if (grid[r1][c] == 1 && grid[r2][c] == 1) {

                        ++counter;

                    }

                }

                ans += counter * (counter - 1) / 2;

            }

        }

        return ans;

    }

};

All LeetCode Questions List 题目汇总

巴特西

[LeetCode] 750. Number Of Corner Rectangles 边角矩形的数量

All LeetCode Questions List 题目汇总

最新文章

热门文章