391 Perfect Rectangle

Leetcode

Given an array rectangles where rectangles[i] = [xi, yi, ai, bi] represents an axis-aligned rectangle. The bottom-left point of the rectangle is (xi, yi) and the top-right point of it is (ai, bi).

Return true if all the rectangles together form an exact cover of a rectangular region.

Example 1:

Input: rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
Output: true
Explanation: All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

Input: rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
Output: false
Explanation: Because there is a gap between the two rectangular regions.

Example 3:

Input: rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
Output: false
Explanation: Because two of the rectangles overlap with each other.

找到上下左右边界，求出大矩形的面积，并求所有小矩形的面积，如果不相等，则无法拼成。统计所有矩形的顶点所在的点。如果出现次数为 1 ，只能是大矩形的顶点，次数为 2 ，不能是大矩形定点，次数为 4 ，不能在大矩形边上。如果面积没有问题，满足这些条件即可拼成大矩形。

class Solution {
    int minX, minY, maxX, maxY;
    long area;
    public boolean isRectangleCover(int[][] rectangles) {
        HashMap<Dot,Integer> map=new HashMap<>();
        edgeAndArea(rectangles);
        if(area!=(maxX-minX)*(maxY-minY))
            return false;
        int t;
        for(int [] ret: rectangles){

            Dot[] dots=new Dot[]{new Dot(ret[0],ret[1]),
                    new Dot(ret[0],ret[3]),
                    new Dot(ret[2],ret[1]),
                    new Dot(ret[2],ret[3])
            };
            for(Dot dot:dots){
                if(map.containsKey(dot)){
                    t=map.get(dot);
                    if(t>4)
                        return false;
                    map.put(dot,t+1);
                } else {
                    map.put(dot,1);
                }
            }


        }
        for(Map.Entry<Dot,Integer> set:map.entrySet()){
            int val=set.getValue();
            Dot d=set.getKey();
            if(val==1 && (d.x==minX || d.x==maxX) && (d.y==minY || d.y==maxY)) continue;
            else if(val==2 && ((d.x!=minX && d.x!=maxX) || (d.y!=minY && d.y!=maxY))) continue;
            else if(val==4 && (d.x!=minX && d.y!=minY && d.x!=maxX && d.y!=maxY)) continue;
            else return false;
        }
        return true;

    }

    private void edgeAndArea(int[][] rectangles){
        area=0L;
        minX=Integer.MAX_VALUE;
        minY=Integer.MAX_VALUE;
        maxX=Integer.MIN_VALUE;
        maxY=Integer.MIN_VALUE;
        for(int[] arr: rectangles){
            if(arr[0]<minX) minX=arr[0];
            if(arr[1]<minY) minY=arr[1];
            if(arr[2]>maxX) maxX=arr[2];
            if(arr[3]>maxY) maxY=arr[3];
            area+=(arr[3]-arr[1])*(arr[2]-arr[0]);
        }
    }

    private static class Dot{
        int x;
        int y;
        public Dot(int x, int y){
            this.x=x; this.y=y;
        }
        @Override
        public boolean equals(Object d2){
            if(!(d2 instanceof Dot)) return false;
            Dot d=(Dot)d2;
            if(x==d.x && y==d.y) return true;
            return false;
        }
        @Override
        public int hashCode(){
            return x*7+y;
        }
        public String toString(){
            return "x:"+x+" y:"+y;
        }
    }
}

方法二：

定义一个 boolean 数组，统计是否被覆盖。这种方法数据量大会内存不够。。。

class Solution {
    int minX, minY, maxX, maxY;
    public boolean isRectangleCover(int[][] rectangles) {
        if(rectangles==null || rectangles.length==0) return false;
        edge(rectangles);
        boolean[][] map=new boolean[maxX-minX][maxY-minY];
        for(int[] ret:rectangles){
            if(!fill(map, ret)) return false;
        }
        for(int i=0;i<map.length;++i){
            for(int j=0;j<map[0].length;++j){
                if(!map[i][j]) return false;
            }
        }
        return true;
        
    }
    
    private void edge(int[][] rectangles){
        minX=Integer.MAX_VALUE;
        minY=Integer.MAX_VALUE;
        maxX=Integer.MIN_VALUE;
        maxY=Integer.MIN_VALUE;
        for(int[] arr: rectangles){
            if(arr[0]<minX) minX=arr[0];
            if(arr[1]<minY) minY=arr[1];
            if(arr[2]>maxX) maxX=arr[2];
            if(arr[3]>maxY) maxY=arr[3];
        }
    }
    
    boolean fill(boolean[][] map, int[] ret){
        int x,y;
        for(int i=ret[0];i<ret[2];++i){
            for(int j=ret[1];j<ret[3];++j){
                x=i-minX;
                y=j-minY;
                if(map[x][y]) return false;
                map[x][y]=true;
            }
        }
        return true;
    }
}