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 either0
or1
. - The number of
1
s in the grid will be at most6000
.
找出每两个row之间的矩形个数。
O(m^2 * n)
可以优化的地方是把计算第一个row的时候把1额外开一个数组存好
class Solution { public int countCornerRectangles(int[][] grid) { int rt = 0; for (int i = 0; i < grid.length - 1; i++) { for (int j = i + 1; j < grid.length; j++) { int count = 0; for (int col = 0; col < grid[0].length; col++) { if (grid[i][col] == 1 && grid[j][col] == 1) count++; } if (count > 0) rt += count * (count - 1) / 2; } } return rt; } }另一种算法 ref: https://leetcode.com/problems/number-of-corner-rectangles/solution/
No comments:
Post a Comment