Leetcode - Perfect Rectangle

My code:

import java.util.HashMap;
import java.util.Iterator;

public class Solution {
    HashMap<String, Integer> map;
    public boolean isRectangleCover(int[][] rectangles) {
        if (rectangles == null || rectangles.length == 0 || rectangles[0].length == 0) {
            return false;
        }
        
        int l_x = Integer.MAX_VALUE;
        int l_y = Integer.MAX_VALUE;
        int r_x = Integer.MIN_VALUE;
        int r_y = Integer.MIN_VALUE;
        
        map = new HashMap<String, Integer>();
        int sum = 0;
        
        for (int i = 0; i < rectangles.length; i++) {
            l_x = Math.min(l_x, rectangles[i][0]);
            l_y = Math.min(l_y, rectangles[i][1]);
            r_x = Math.max(r_x, rectangles[i][2]);
            r_y = Math.max(r_y, rectangles[i][3]);
            sum += (rectangles[i][2] - rectangles[i][0]) * (rectangles[i][3] - rectangles[i][1]);
            
            if (overlap(rectangles[i][0] + " " + rectangles[i][1], 1)) {
                return false;
            }
            if (overlap(rectangles[i][2] + " " + rectangles[i][1], 2)) {
                return false;
            }
            if (overlap(rectangles[i][2] + " " + rectangles[i][3], 4)) {
                return false;
            }
            if (overlap(rectangles[i][0] + " " + rectangles[i][3], 8)) {
                return false;
            }
        }
        
        int counter = 0;
        for (Iterator<Integer> iter = map.values().iterator(); iter.hasNext();) {
            int temp = iter.next();
            if (temp == 1 || temp == 2 || temp == 4 || temp == 8) {
                counter++;
            }
            else if (temp == 0 || temp == 14 || temp == 7) {
                return false;
            }
        }
        
        return counter == 4 && (r_x - l_x) * (r_y - l_y) == sum;
    }
    
    private boolean overlap(String s, int type) {
        int temp = 0;
        if (map.containsKey(s)) {
            temp = map.get(s);
        }
        if ((temp & type) != 0) {
            return true;
        }
        temp |= type;
        map.put(s, temp);
        return false;
    }
}

reference：
比较好的解释：
https://discuss.leetcode.com/topic/55923/o-n-solution-by-counting-corners-with-detailed-explaination
比较简单的实现：
https://discuss.leetcode.com/topic/55997/short-java-solution-with-explanation-updated/5

听说有人谷歌电面面到这个题目的变形了，而且题意是口述，对方是阿三。还迟到了10分钟，生下30分钟说明题意，再口述 codepad 链接，再说思路，再写代码。。真的太恐怖了。。。

我是直接看的答案。感觉很巧妙，要真的做出这样一道题目，45分钟，真的够吗？？？

首先需要观察，总结。
发现一共就三类点。
1 . 最边界上的四个点。他们只可能出现一次。
2 . 两个矩形的交界点，他们只可能重复出现两次，在矩形的不同位置
3 . 四个矩形的交界点，他们只可能重复出现四次。在矩形的不同位置
4 . 每个点，在矩形的同一位置(左下，右下，左上，右上)，只可能出现一次。

然后构造一个 HashMap, 对每个点已经出现的次数，已经出现的类型，进行保存。

比如对于点 (1,2)
key: "1 2"
value: Integer
其中我们只用这个Integer 的前四位
0X0001 left down 1
0X0010 right down 2
0X0100 right top 4
0X1000 left top 8

如果这个点是第一次出现，且出现在左下角 1
那么：
"1 2" -> 0X0001

下次再次出现，出现在右下角 2
0X0010 & 0X0001 == 0
没问题。
更新这个 bit map
0X0010 | 0X0001 = 0X0011

"1 2" -> 0X0011

下次再次出现，仍然在右下角 2，
于是 0X0011 & 0X0010 != 0,
overlap
返回false

当遍历完所有点后，检查所有点的 bitmap 即，value
不可能出现 0X1110 0X0111 0X0000, 如果出现，就return false
记录下， 0X0001 0X0010 0X0100 0X1000 的次数。
他们只可能等于4，因为只有四个点，从头到尾只出现一次，且在不同的位置。

同时，要保证，所有sub rectangular 的面积之和等于最外面四个点画出来的矩形的面积之和。

Anyway, Good luck, Richardo! -- 09/23/2016

Leetcode - Perfect Rectangle

推荐阅读更多精彩内容