## Thursday, May 17, 2018

### 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 `1`s in the grid will be at most `6000`.

```枚举起始行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. 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 (1200) GeeksforGeeks (1127) Review (893) Algorithm (795) LeetCode - Review (649) to-do (639) Dynamic Programming (329) Classic Algorithm (323) Classic Interview (288) Google Interview (245) Tree (145) POJ (140) Difficult Algorithm (131) LeetCode - Phone (127) EPI (125) Bit Algorithms (121) Different Solutions (120) Lintcode (112) Math (109) Smart Algorithm (109) HackerRank (89) Binary Search (84) Binary Tree (82) Greedy Algorithm (80) Graph Algorithm (76) DFS (73) Stack (68) Interview Corner (61) List (58) BFS (57) Codility (54) ComProGuide (52) LeetCode Hard (52) Trie (49) Interval (46) USACO (46) ACM-ICPC (41) Segment Tree (41) Union-Find (41) Data Structure (40) Knapsack (40) Matrix (40) Jobdu (39) Backtracking (38) String Algorithm (38) TopCoder (38) Codeforces (36) Must Known (36) Sort (35) Sliding Window (34) Array (33) prismoskills (33) Priority Queue (32) HDU (31) Google Code Jam (30) LeetCode - DP (30) Permutation (30) Puzzles (30) Array O(N) (29) Company-Airbnb (29) Company-Zenefits (28) Graph (28) Palindrome (28) to-do-must (28) Random (27) Queue (26) GeeksQuiz (25) Logic Thinking (25) Pre-Sort (25) Time Complexity (25) hihocoder (25) Company-Facebook (23) High Frequency (23) Two Pointers (23) Algorithm Game (22) Bisection Method (22) Hash (22) DFS + Review (21) Follow Up (21) Brain Teaser (20) CareerCup (20) Merge Sort (20) O(N) (20) Ordered Stack (20) Topological Sort (19) UVA (19) Company-Uber (17) Game Theory (17) Probabilities (17) Codercareer (16) Heap (16) Iterator (16) Shortest Path (16) String Search (16) Tree Traversal (16) itint5 (16) Difficult (15) BST (14) DP - Tree (14) KMP (14) LeetCode - DFS (14) Number (14) Number Theory (14) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Euclidean GCD (13) Majority (13) Reverse Thinking (13) mitbbs (13) Bisection (12) Combination (12) Modify Tree (12) Proof (12) Reconstruct Tree (12) TreeMap (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Graph DFS (11) LCA (11) Miscs (11) O(1) Space (11) Prefix Sum (11) Princeton (11) Rolling Hash (11) X Sum (11) 挑战程序设计竞赛 (11) Bucket Sort (10) Coin Change (10) DFS+Cache (10) DP - Bit Masking (10) DP - Digit (10) DP - Interval (10) HackerRank Easy (10) MinMax (10) SPOJ (10) Simulation (10) Theory (10) Tutorialhorizon (10) Mathblog (9) Max-Min Flow (9) Quick Sort (9) Stock (9) Use XOR (9) Book Notes (8) Bottom-Up (8) DFS+BFS (8) Linked List (8) Prime (8) Suffix Tree (8) Tech-Queries (8) TreeSet (8) 穷竭搜索 (8) Expression (7) Game Nim (7) Graph BFS (7) Hackerearth (7) Inversion (7) Quick Select (7) Radix Sort (7) Tree DP (7) n00tc0d3r (7) 蓝桥杯 (7) DFS+DP (6) Dijkstra (6) Dutch Flag (6) How To (6) Manacher (6) One Pass (6) Pruning (6) Rabin-Karp (6) Sampling (6) Schedule (6) Stream (6) Suffix Array (6) Sweep Line (6) Threaded (6) Xpost (6) reddit (6) AI (5) Big Data (5) Brute Force (5) Code Kata (5) Coding (5) Convex Hull (5) Crazyforcode (5) Cycle (5) Find Rule (5) Flood fill (5) Graph Cycle (5) Immutability (5) Java (5) Maze (5) Pre-Sum (5) Quadtrees (5) Quora (5) Subarray Sum (5) Sudoku (5) Word Search (5) jiuzhang (5) 单调栈 (5) 1point3acres (4) Abbreviation (4) Anagram (4) Anagrams (4) Chess Game (4) Dequeue (4) Distributed (4) Histogram (4) MST (4) N Queens (4) Probability (4) Programcreek (4) Subset Sum (4) Subsets (4) Symbol Table (4) Triangle (4) Water Jug (4) algnotes (4) fgdsb (4) to-do-2 (4) 最大化最小值 (4) 树形DP (4) A Star (3) B Tree (3) Coins (3) Dedup (3) Dropbox (3) Easy (3) Github (3) GoLang (3) Joseph (3) Jump Game (3) K (3) LogN (3) Minesweeper (3) NP Hard (3) O(N) Hard (3) Parser (3) Rectangle (3) Scala (3) SegmentFault (3) Shuffle (3) Skyline (3) Subtree (3) TSP (3) Trie + DFS (3) Word Ladder (3) bookkeeping (3) codebytes (3) Array Merge (2) BOJ (2) Bellman Ford (2) Bit Counting (2) Bit Mask (2) Bloom Filter (2) Clock (2) Codesays (2) DP - DFS (2) DP - Trie (2) DP-3D Table (2) DP-Classical (2) DP-i-k-j (2) Factor (2) GoHired (2) Graham Scan (2) Hard (2) Huffman Tree (2) Invariant (2) Islands (2) Lucene-Solr (2) Matrix Power (2) Median (2) Parentheses (2) Peak (2) Programming (2) Robot (2) Rosettacode (2) Search (2) SimHash (2) Sparse Table (2) Summary (2) TV (2) Tile (2) Tree Sum (2) Word Break (2) Word Graph (2) Word Trie (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) ? (1) Akka (1) BACK (1) BFS Hard (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Big Integer (1) Big Number (1) Binary (1) Bipartite (1) BitMap (1) BitMap index (1) BitSet (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Chinese (1) Clean Code (1) Cloest (1) Clone (1) Code Quality (1) Company-Epic (1) Company-Yelp (1) Concise (1) Concurrency (1) Custom Sort (1) DFS-Matrix (1) DI (1) DP-Difficult (1) DP-Graph (1) DP-MaxMin (1) DP-树形 (1) Database (1) Diagonal (1) Domino (1) Dr Dobb's (1) Duplicate (1) FST (1) Fraction (1) Funny (1) Game (1) Generation (1) GeoHash (1) Google APAC (1) Gray Code (1) HOJ (1) Hanoi (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Interview (1) Isomorphic (1) JDK8 (1) Knight (1) Kruskal (1) Kth Element (1) LeetCode -P (1) Linkedin (1) Local MinMax (1) Matrix BFS (1) Matrix Graph (1) Matrix+DP (1) MinHash (1) MinMax Heap (1) Monto Carlo (1) Multiple DFS (1) Next Element (1) Optimal Play (1) PAT (1) Parenthesis (1) Partition (1) Path Finding (1) Persistent (1) Power Set (1) PreProcess (1) Python (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Region (1) Resources (1) Revi (1) Robin (1) Selection (1) Similarity (1) Square (1) String DP (1) SubMatrix (1) Subsequence (1) Test (1) Test Cases (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tree Rotate (1) Trie vs Hash (1) Triplet (1) Two Stacks (1) Two-End-BFS (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) ZOJ (1) ZigZag (1) codevs (1) cos126 (1) javabeat (1) jum (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)