rust 解法, 执行用时: 20 ms, 内存消耗: 2.6 MB, 提交时间: 2023-10-21 19:28:59

impl Solution {
    pub fn count_corner_rectangles(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid[0].len();
        let mut ans = 0;
        let mut dp = vec![vec![0;n];n];

        for row in &grid {
            for left in 0..n-1 {
                if row[left] == 1 {
                    for right in left+1..n {
                        if row[right] == 1 {
                            ans += dp[left][right];
                            dp[left][right] += 1;
                        }
                    }
                }
            }
        }

        ans
    }
}

golang 解法, 执行用时: 100 ms, 内存消耗: 6.8 MB, 提交时间: 2023-10-21 19:28:41

func countCornerRectangles(grid [][]int) int {
    n,m:=len(grid),len(grid[0])
    if n<1 ||m<1{
        return 0
    }
    ans:=0
    for i:=0;i<n;i++{
        for k:=i+1;k<n;k++{
            cnt:=0
            for j:=0;j<m;j++{
                if grid[i][j]==1 && grid[k][j]==1{
                    cnt++
                    ans+=cnt-1
                }
            }
        }
    }
    return ans
}

python3 解法, 执行用时: 552 ms, 内存消耗: 17.7 MB, 提交时间: 2023-10-21 19:27:49

class Solution:
    def countCornerRectangles(self, g: List[List[int]]) -> int:
        n, dp = 0, [[0 for i in range(200)] for i in range(200)]
        for i in range(len(g)):
            for j in range(len(g[i])):
                if g[i][j]:
                    for k in range(j + 1, len(g[i])):
                        if g[i][k]:
                            n += dp[j][k]
                            dp[j][k] += 1

        return n
        
    
    def countCornerRectangles2(self, grid: List[List[int]]) -> int:
        count = collections.Counter()
        ans = 0
        for row in grid:
            for c1, v1 in enumerate(row):
                if v1:
                    for c2 in xrange(c1+1, len(row)):
                        if row[c2]:
                            ans += count[c1, c2]
                            count[c1, c2] += 1
        return ans


        
    def countCornerRectangles3(self, g: List[List[int]]) -> int:
        idxv = [[] for i in range(len(g))]
        map = [[0 for i in range(200)] for i in range(200)]
        
        for i in range(len(g)):
            for j in range(len(g[i])):
                if g[i][j]:
                    idxv[i].append(j)
                    map[i][j] = 1
        n = 0
        for i in range(len(g)):
            for j in range(i + 1, len(g)):
                t = 0
                for k in range(len(idxv[i])):
                    if map[j][idxv[i][k]]:
                        t += 1
                n += t * (t - 1) >> 1

        return n

cpp 解法, 执行用时: 96 ms, 内存消耗: 26.7 MB, 提交时间: 2023-10-21 19:26:11

class Solution {
public:
    // dp[j][k] 表示矩阵从第1行开始到当前正在处理的行，j点和k点两个点都为1的行的个数，比如下面的矩阵；
    int countCornerRectangles(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]) {
                    for (int k = j + 1; k < n; k++) {
                        if (grid[i][k]) {
                            ans += dp[j][k];
                            dp[j][k]++;
                        }
                    }
                }
            }
        }
        return ans;
    }
    
    // dp2
    int countCornerRectangles2(vector<vector<int>>& g) {
        int dp[200][200]{}, n = 0;
        for (int i = 0; i < g.size(); i++) {
            for (int j = 0; j < g[i].size(); j++) {
                if (g[i][j]) {
                    for (int k = j + 1; k < g[i].size(); k++) {
                        if (g[i][k]) {
                            n += dp[j][k];
                            dp[j][k]++;
                        }
                    }
                }
            }
        }
        return n;
    }

    int countCornerRectangles3(vector<vector<int>>& g) {
        vector<vector<int>> idxv(g.size(), vector<int>{});
        bool map[200][200]{};
        for (int i = 0; i < g.size(); i++) {
            for (int j = 0; j < g[i].size(); j++) {
                if (g[i][j]) {
                    idxv[i].push_back(j);
                    map[i][j] = true;
                }
            }
        }
        int n = 0;
        for (int i = 0; i < g.size(); i++) {
            for (int j = i + 1; j < g.size(); j++) {
                int t = 0;
                for (int k = 0; k < idxv[i].size(); k++) {
                    if (map[j][idxv[i][k]]) t++;
                }
                n += t * (t - 1) >> 1;
            }
        }
        return n;
    }
};

java 解法, 执行用时: 56 ms, 内存消耗: 52.7 MB, 提交时间: 2023-10-21 19:23:37

class Solution {
    public int countCornerRectangles(int[][] grid) {
        int res = 0;
        int row = grid.length, col = grid[0].length;
        if (row == 1) return res;
        //固定两条边
        for (int r1 = 0; r1 < row; r1++) {
            for (int r2 = r1 + 1; r2 < row; r2++) {
                int count = 0;//记录满足的列数
                for (int j = 0; j < col; j++) {
                    if (grid[r1][j] == 1 && grid[r2][j] == 1)
                        count++;
                }
                //记录此次遍历的长方形个数
                res += count * (count - 1) / 2;
            }
        }
        return res;
    }

    public int countCornerRectangles2(int[][] grid) {
        Map<Integer, Integer> count = new HashMap();
        int ans = 0;
        for (int[] row: grid) {
            for (int c1 = 0; c1 < row.length; ++c1) if (row[c1] == 1) {
                for (int c2 = c1+1; c2 < row.length; ++c2) if (row[c2] == 1) {
                    int pos = c1 * 200 + c2;
                    int c = count.getOrDefault(pos, 0);
                    ans += c;
                    count.put(pos, c+1);
                }
            }
        }
        return ans;
    }

    public int countCornerRectangles3(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;
    }
}