LeetCode 750 - Number Of Corner Rectangles


http://bookshadow.com/weblog/2017/12/17/leetcode-number-of-corner-rectangles/
Given a grid where each entry is only 0 or 1, find the number of corner rectangles.
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:
  1. The number of rows and columns of grid will each be in the range [1, 200].
  2. Each grid[i][j] will be either 0 or 1.
  3. The number of 1s in the grid will be at most 6000.
我们来看一种优化了时间复杂度的方法,这种方法的原理是两行同时遍历,如果两行中相同列位置的值都为1,则计数器cnt自增1,那么最后就相当于有了(cnt - 1)个相邻的格子,问题就转化为了求cnt-1个相邻的格子能组成多少个矩形,就变成了初中数学问题了,共有cnt*(cnt-1)/2个

朴素解法是枚举左上角和右下角坐标,时间复杂度 O(m^2 * n^2),会导致TLE
组合(Combination)时间复杂度 O(m^2 * n)
容易想到的是n*(n-1)/2这个计算公式,先固定2行,求每列与这2行相交是不是都是1 ,计算这样的列数
枚举起始行x,终止行y:

    遍历各列z,统计满足grid[x][z] == 1并且grid[y][z] == 1条件的列数,记为cnt

    根据组合公式,C(cnt, 2) = cnt * (cnt - 1) / 2,累加至答案。
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.
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)
X.
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;
    }

X.
https://www.jiuzhang.com/solution/number-of-corner-rectangles/
  1. 一个非常直观的想法是:每加入新的一行,会新加多少个矩形?
  2. 由此引出以下两种方法:
  3. 方法一:
    1. 对于新行的每对1(记为cur_row[i]和cur_row[j]),新加矩形个数,是之前行row[i]= row[j] = 1出现的次数!
    2. 所以逐行遍历网格,并维护一个统计表count(可用map实现,python中亦可用Counter或defaultdict实现),count记录了之前行的每一对row[i] = row[j] = 1的次数。
    3. 对于新行的每对1,例如cur_row[i]和cur_row[j],最终结果加上count[i, j],然后count[i, j]自增。
    4. 复杂度分析:
      1. 时间复杂度:O(R ∗ C ^ 2),其中R是行数,C是列数。由于遍历每行当中都要寻找每对1,故每行遍历复杂度为C ^ 2。
      2. 空间复杂度:O(C ^ 2)。
  4. 方法二:
    1. 在方法一中每一行都要O(C ^ 2)时间去遍历,这个过程十分麻烦。
    2. 很容易想到,可以先将每一行的所有1的位置记录到列表当中,一共有R个这样的列表。然后行遍历过程中,直接对列表里的每一对元素进行统计表count的查询和自增即可。
    3. 这是一种很好的办法,但是如果这一行1很多,也即这一行很密集,那么这个列表会很长,遍历每一对元素复杂度仍然会逼近O(C ^ 2)。
    4. 针对这种密集的行(记该行为r),一种改进措施是不再遍历其列表中每一对元素,而是直接寻找表中每一行(如行a)有多少个1,它们在r行对应列上也是1。假设有f个,那么行a与行f所组成的矩形就有(f - 1) * f / 2个。我们可以用把行r的列表转换为集合Set,然后只需线性遍历每一行,计算出f及其产生的矩形数。
    5. 要注意如果如果行r和行a都是密集行,那么行a只有在行r的下方有效。否则会重复计算,也即遍历到行r计算了一次,遍历到行a又计算了一次。
    6. 那么到底一行超过多少个点算密集行,这里取的是N ^ 0.5,也即根号N,其中N为网格中1的个数。这样能保证最多只有N ^ 0.5个密集行,每一个密集行的复杂度为O(N),故复杂度不超过N ^ 1.5。而对于稀疏行,因总点数不超过N,所以可证所有的稀疏行总共复杂度不超过N ^ 1.5(证明复杂,需用数学推导,这里略去)。
    7. 复杂度分析:
      1. 时间复杂度:由以上分析可得O(N ^ 1.5)。
      2. 空间复杂度: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;
        }
    };

    Labels

    LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

    Popular Posts