题目描述：
LeetCode 750. Number Of Corner Rectangles
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
gridwill each be in the range[1, 200]. - Each
grid[i][j]will be either0or1. - The number of
1s in the grid will be at most6000.
题目大意：
求矩阵grid中所有四角为1的子矩阵的个数（四个角坐标必须互不相同）
解题思路：
朴素解法是枚举左上角和右下角坐标，时间复杂度 O(m^2 * n^2)，会导致TLE
组合（Combination）时间复杂度 O(m^2 * n)
枚举起始行x，终止行y：
遍历各列z，统计满足grid[x][z] == 1并且grid[y][z] == 1条件的列数，记为cnt
根据组合公式，C(cnt, 2) = cnt * (cnt - 1) / 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;
}
}
本文链接：http://bookshadow.com/weblog/2017/12/17/leetcode-number-of-corner-rectangles/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
