http://bookshadow.com/weblog/2017/12/17/leetcode-number-of-corner-rectangles/
https://www.acwing.com/solution/LeetCode/content/213/
动态规划 O(n2∗m)O(n2∗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)
下面这种解法由热心网友edyyy提供，最大亮点是将解法二的beat 65%提高到了beat 97%，速度杠杠的，要飞起来了的节奏。在遍历前一行的时候，将所有为1的位置存入到了一个数组ones中，然后在遍历其他行时，直接检测ones数组中的那些位置是否为1，这样省去了检查一些之前行为0的步骤，提高了运行速度，但是也牺牲了一些空间，比如需要ones数组，算是个trade off吧
X.
https://www.jiuzhang.com/solution/number-of-corner-rectangles/
X.
http://www.cnblogs.com/grandyang/p/8433813.html
这道题给了我们一个由0和1组成的二维数组，这里定义了一种边角矩形，其四个顶点均为1，让我们求这个二维数组中有多少个不同的边角矩形。那么最简单直接的方法就是暴力破解啦，我们遍历所有的子矩形，并且检验其四个顶点是否为1即可。先确定左上顶点，每个顶点都可以当作左上顶点，所以需要两个for循环，然后我们直接跳过非1的左上顶点，接下来就是要确定右上顶点和左下顶点了，先用一个for循环确定左下顶点的位置，同理，如果左下顶点为0，直接跳过。再用一个for循环确定右上顶点的位置，如果右上顶点位置也确定了，那么此时四个顶点中确定了三个，右下顶点的位置也就确定了，此时如果右上和右下顶点均为1，则结果res自增1
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:
Example 2:
Example 3:
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.
我们来看一种优化了时间复杂度的方法，这种方法的原理是两行同时遍历，如果两行中相同列位置的值都为1，则计数器cnt自增1，那么最后就相当于有了(cnt - 1)个相邻的格子，问题就转化为了求cnt-1个相邻的格子能组成多少个矩形，就变成了初中数学问题了，共有cnt*(cnt-1)/2个
朴素解法是枚举左上角和右下角坐标，时间复杂度 O(m^2 * n^2)，会导致TLE
朴素解法是枚举左上角和右下角坐标，时间复杂度 O(m^2 * n^2)，会导致TLE
组合（Combination）时间复杂度 O(m^2 * n)
容易想到的是n*(n-1)/2这个计算公式，先固定2行，求每列与这2行相交是不是都是1 ，计算这样的列数
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还需要改变遍历方式做一点prune
counts[i][j] is used to keep track of the number of rows, found so far, in which column i and column j are 1.
Every time you find a new row that has i and j set to 1, counts will tell you how many rectangles you can form with this new row.
Every time you find a new row that has i and j set to 1, counts will tell you how many rectangles you can form with this new row.
def countCornerRectangles(self, grid):
res = 0
counts = [[0] * len(grid[rows]) for rows in range(len(grid))]
for row in range(0, len(grid)):
for j in range(1, len(grid[0])):
if grid[row][j] == 1:
for i in range(0, j):
if grid[row][i] == 1:
res += counts[i][j]
counts[i][j] += 1
return int(res)https://www.acwing.com/solution/LeetCode/content/213/
动态规划 O(n2∗m)O(n2∗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)
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;
}
X.下面这种解法由热心网友edyyy提供，最大亮点是将解法二的beat 65%提高到了beat 97%，速度杠杠的，要飞起来了的节奏。在遍历前一行的时候，将所有为1的位置存入到了一个数组ones中，然后在遍历其他行时，直接检测ones数组中的那些位置是否为1，这样省去了检查一些之前行为0的步骤，提高了运行速度，但是也牺牲了一些空间，比如需要ones数组，算是个trade off吧
int countCornerRectangles(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(), res = 0; for (int i = 0; i < m - 1; i++) { vector<int> ones; for (int k = 0; k < n; k++) if (grid[i][k]) ones.push_back(k); for (int j = i + 1; j < m; j++) { int cnt = 0; for (int l = 0; l < ones.size(); l++) { if (grid[j][ones[l]]) cnt++; } res += cnt * (cnt - 1) / 2; } } return res; }
https://www.jiuzhang.com/solution/number-of-corner-rectangles/
- 一个非常直观的想法是：每加入新的一行，会新加多少个矩形？
- 由此引出以下两种方法：
- 方法一：
- 对于新行的每对1（记为cur_row[i]和cur_row[j]），新加矩形个数，是之前行row[i]= row[j] = 1出现的次数！
- 所以逐行遍历网格，并维护一个统计表count（可用map实现，python中亦可用Counter或defaultdict实现），count记录了之前行的每一对row[i] = row[j] = 1的次数。
- 对于新行的每对1，例如cur_row[i]和cur_row[j]，最终结果加上count[i, j]，然后count[i, j]自增。
- 复杂度分析：
- 时间复杂度：O(R ∗ C ^ 2)，其中R是行数，C是列数。由于遍历每行当中都要寻找每对1，故每行遍历复杂度为C ^ 2。
- 空间复杂度：O（C ^ 2)。
- 方法二：
- 在方法一中每一行都要O(C ^ 2)时间去遍历，这个过程十分麻烦。
- 很容易想到，可以先将每一行的所有1的位置记录到列表当中，一共有R个这样的列表。然后行遍历过程中，直接对列表里的每一对元素进行统计表count的查询和自增即可。
- 这是一种很好的办法，但是如果这一行1很多，也即这一行很密集，那么这个列表会很长，遍历每一对元素复杂度仍然会逼近O(C ^ 2)。
- 针对这种密集的行（记该行为r），一种改进措施是不再遍历其列表中每一对元素，而是直接寻找表中每一行（如行a）有多少个1，它们在r行对应列上也是1。假设有f个，那么行a与行f所组成的矩形就有(f - 1) * f / 2个。我们可以用把行r的列表转换为集合Set，然后只需线性遍历每一行，计算出f及其产生的矩形数。
- 要注意如果如果行r和行a都是密集行，那么行a只有在行r的下方有效。否则会重复计算，也即遍历到行r计算了一次，遍历到行a又计算了一次。
- 那么到底一行超过多少个点算密集行，这里取的是N ^ 0.5，也即根号N，其中N为网格中1的个数。这样能保证最多只有N ^ 0.5个密集行，每一个密集行的复杂度为O(N)，故复杂度不超过N ^ 1.5。而对于稀疏行，因总点数不超过N，所以可证所有的稀疏行总共复杂度不超过N ^ 1.5（证明复杂，需用数学推导，这里略去）。
- 复杂度分析：
- 时间复杂度：由以上分析可得O(N ^ 1.5)。
- 空间复杂度：O(N + R + C ^ 2)。N是由于记录1的位置的列表，R是由于由R个列表，C ^ 2是由于统计表count
public int countCornerRectangles(int[][] grid) {
List<List<Integer>> rows = new ArrayList();
int N = 0;
for (int r = 0; r < grid.length; ++r) {
rows.add(new ArrayList());
for (int c = 0; c < grid[r].length; ++c)
if (grid[r][c] == 1) {
rows.get(r).add(c);
N++;
}
}
int sqrtN = (int) Math.sqrt(N);
int ans = 0;
Map<Integer, Integer> count = new HashMap();
for (int r = 0; r < grid.length; ++r) {
if (rows.get(r).size() >= sqrtN) {
Set<Integer> target = new HashSet(rows.get(r));
for (int r2 = 0; r2 < grid.length; ++r2) {
if (r2 <= r && rows.get(r2).size() >= sqrtN)
continue;
int found = 0;
for (int c2: rows.get(r2))
if (target.contains(c2))
found++;
ans += found * (found - 1) / 2;
}
} else {
for (int i1 = 0; i1 < rows.get(r).size(); ++i1) {
int c1 = rows.get(r).get(i1);
for (int i2 = i1 + 1; i2 < rows.get(r).size(); ++i2) {
int c2 = rows.get(r).get(i2);
int ct = count.getOrDefault(200*c1 + c2, 0);
ans += ct;
count.put(200*c1 + c2, ct + 1);
}
}
}
}
return ans;
}
}X.
http://www.cnblogs.com/grandyang/p/8433813.html
这道题给了我们一个由0和1组成的二维数组，这里定义了一种边角矩形，其四个顶点均为1，让我们求这个二维数组中有多少个不同的边角矩形。那么最简单直接的方法就是暴力破解啦，我们遍历所有的子矩形，并且检验其四个顶点是否为1即可。先确定左上顶点，每个顶点都可以当作左上顶点，所以需要两个for循环，然后我们直接跳过非1的左上顶点，接下来就是要确定右上顶点和左下顶点了，先用一个for循环确定左下顶点的位置，同理，如果左下顶点为0，直接跳过。再用一个for循环确定右上顶点的位置，如果右上顶点位置也确定了，那么此时四个顶点中确定了三个，右下顶点的位置也就确定了，此时如果右上和右下顶点均为1，则结果res自增1
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; }http://www.cnblogs.com/pk28/p/8051920.html
暴力枚举+轻微减枝
class Solution {
public:
int search(vector<vector<int>>& grid, int x, int y) {
int n = grid.size();
int m = grid[0].size();
int cnt = 0;
for (int i = 1; i < n - x; ++i) {
if(grid[x+i][y] == 0) continue;
for (int j = 1; j < m - y; ++j) {
int x1, y1;
x1 = x;
y1 = y + j;
if (grid[x1][y1] == 0) continue;
x1 = x + i;
y1 = y + j;
if (grid[x1][y1] == 0) continue;
x1 = x + i;
y1 = y;
if (grid[x1][y1] == 0) continue;
cnt++;
}
}
return cnt;
}
int countCornerRectangles(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
if (n == 1) return 0;
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 1) {
ans += search(grid, i, j);
}
}
}
return ans;
}
};