# LWC 63: 750. Number Of Corner Rectangles

## LWC 63: 750. Number Of Corner Rectangles

Problem:

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 grid1[2], grid1[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.

Java版本：

```    public int countCornerRectangles(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int ret = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int np = 0;
for (int k = 0; k < m; ++k) {
if (grid[i][k] == 1 && grid[j][k] == 1) {
np ++;
}
}
ret += np * (np - 1) / 2;
}
}
return ret;
}```

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  ```

0 条评论

## 相关文章

822

2008

### JavaScript基础学习--13字符串、查找高亮显示

Demos：   https://github.com/jiangheyan/JavaScriptBase 一、字符串      1、str.length; ...

2066

3696

### python 入门知识拾遗

Python 3最重要的新特性大概要算是对文本和二进制数据作了更为清晰的区分。文本总是Unicode，由str类型表示，二进制数据则由bytes类型表示。Pyt...

894

### leetcode-17-电话号码的字母组合

vector<string> letterCombinations(string digits)

813

31011

732

### 让你一看就明白什么是聚合-java版本_源码下载

=================================================

1893

37410