如何判定完美矩形 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：如何判定完美矩形

评论礼仪 见这里，违者直接拉黑。

[lcfgrn]

这个题没做过类似题还真想不到

[wangpeiming110]

也就是说，当某一个点同时是 2 个或者 4 个小矩形的顶点时，该点最终不是顶点；

但如果2个矩形完全重合，那么这4个顶点全部同时是2个矩形的定点呢

[deepbreath373]

Java版

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        int X1 = Integer.MAX_VALUE, Y1 = Integer.MAX_VALUE, X2 = Integer.MIN_VALUE, Y2 = Integer.MIN_VALUE;
        Set<String> points = new HashSet<>();
        int actual_area = 0;
        for(int[] item : rectangles){
            int x1 = item[0], y1 = item[1], x2 = item[2], y2 = item[3];
            X1 = Math.min(X1, x1);Y1 = Math.min(Y1, y1);
            X2 = Math.max(X2, x2);Y2 = Math.max(Y2, y2);
            actual_area += (x2-x1)*(y2-y1);
            int[] p1 = new int[]{x1,y1};int[] p2 = new int[]{x1,y2};
            int[] p3 = new int[]{x2,y1};int[] p4 = new int[]{x2,y2};
            for(int[] p : new int[][]{p1,p2,p3,p4}){
                String s = p[0] + "," + p[1];
                if(points.contains(s)){
                    points.remove(s);
                }else{
                    points.add(s);
                }
            }
        }
        int expected_area = (X2-X1)*(Y2-Y1);
        if(actual_area != expected_area){
            return false;
        }
        if(points.size() != 4) return false;
        String s1 = X1 + "," + Y1;
        String s2 = X1 + "," + Y2;
        String s3 = X2 + "," + Y1;
        String s4 = X2 + "," + Y2;
        if(!points.contains(s1)) return false;
        if(!points.contains(s2)) return false;
        if(!points.contains(s3)) return false;
        if(!points.contains(s4)) return false;
        return true;
    }
}

[zhongweiLeex]

@labuladong 东哥，这一题的题解在 插件中的思路没有更新，插件中的思路代码没有判断最后的 理想顶点情况

[labuladong]

@zhongweiLeex 感谢指出，已修正~

[deepbreath373]

check in

[freezer2046]

重复举行给的贴图好像标错了？rectangles=[[0,0,3,1],[0,0,3,1],[0,3,3,4]]

[labuladong]

感谢指出，已修复~

[RW2918]

@labuladong 重复矩形应该是[[0,0,3,1],[0,0,3,1],[0,2,3,3]]吧，这样两个area算出来一样，所以才要四个if来判断？

[mefengl]

最后需要取验证「留下的四个角」是不是「之前遍历得到的四个角」，这一步通过验证Area也可以，因为这步验证是为了防止「完全重叠」的情况，这种情况下，二者面积一定不相等，即：

Area(「留下的四个角」） =? Area（「之前遍历得到的四个角」）

又，之前已经得到 Area（「所有小矩形」）= Area（「之前遍历得到的四个角」）。

到这里应该很明显了，直接验证Area(「留下的四个角」）=? Area（「所有小矩形」）就可以了。

这也是英文高赞的做法：https://leetcode.com/problems/perfect-rectangle/discuss/1229993

[ChillZoe]

C++版（菜鸟作品，大佬见笑）

class Solution {
public:
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        tuple<int,int> point;
        set<tuple<int,int>> point_set;
        vector<tuple<int,int>> angle;
        int X_min=INT_MAX,Y_min=INT_MAX,A_max=INT_MIN,B_max=INT_MIN;
        long split_area=0;
        for (auto & square : rectangles){
            X_min=min(square[0],X_min);
            Y_min=min(square[1],Y_min);
            A_max=max(square[2],A_max);
            B_max=max(square[3],B_max);
            long square_size=((long)square[3]-(long)square[1])*((long)square[2]-(long)square[0]);
            split_area+=square_size;
            angle={{square[0],square[1]},{square[0],square[3]},{square[2],square[1]},{square[2],square[3]}};
            // if(point_set.count({square[0],square[1]}))
            for (auto& item :angle ){
                if(point_set.count(item))point_set.erase(item);
                else point_set.emplace(item);
            }
        }
        if(((long)A_max-(long)X_min)*((long)B_max-(long)Y_min)!=split_area||point_set.size()!=4) return false;
        angle={{X_min,Y_min},{X_min,B_max},{A_max,Y_min},{A_max,B_max}};
        for (auto& item :angle ){
            if(point_set.count(item)) continue;
            else return false;
        }
        return true;
    }
};

[GoingMyWay]

C++

class Solution {
public:
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        int X1 = INT_MAX, Y1 = INT_MAX;
        int X2 = INT_MIN, Y2 = INT_MIN;
        using point = pair<int, int>;
        set<point> points;
        long recAreas = 0;
        for (auto & rec: rectangles) {
            int x1 = rec[0], y1 = rec[1];
            int x2 = rec[2], y2 = rec[3];
            X1 = min(x1, X1), Y1 = min(y1, Y1);
            X2 = max(x2, X2), Y2 = max(y2, Y2);
            recAreas += ((long)x2 - (long)x1) * ((long)y2 - (long)y1);
            
            for (point & p: vector<point>({{x1, y1}, {x1, y2}, {x2, y1}, {x2, y2}})) {
                if (points.find(p) != points.end()) {
                    points.erase(p);
                } else {
                    points.emplace(p);
                }
            }
        }

        if(points.size() != 4) return false;

        if (points.find({X1, Y1}) == points.end()) return false;
        if (points.find({X1, Y2}) == points.end()) return false;
        if (points.find({X2, Y1}) == points.end()) return false;
        if (points.find({X2, Y2}) == points.end()) return false;

        if (((long)X2 - (long)X1) * ((long)Y2 - (long)Y1) != recAreas) {
            return false;
        }

        return true;
    }
};

[zichengl]

Java 版本，cleaner code

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        int X1 = Integer.MAX_VALUE, Y1 = Integer.MAX_VALUE, X2 = Integer.MIN_VALUE, Y2 = Integer.MIN_VALUE;
        Set<Point> points = new HashSet<>();
        int sumArea = 0;
        for (int[] rec : rectangles) {
            int x1 = rec[0], y1 = rec[1], x2 = rec[2], y2 = rec[3];
            X1 = Math.min(X1, x1); 
            Y1 = Math.min(Y1, y1);
            X2 = Math.max(X2, x2); 
            Y2 = Math.max(Y2, y2);
            sumArea += (x2 - x1) * (y2 - y1);
            Point p1 = new Point(x1, y1);
            Point p2 = new Point(x1, y2);
            Point p3 = new Point(x2, y1);
            Point p4 = new Point(x2, y2);
            for (Point p : new Point[]{p1, p2, p3, p4}) {
                if (points.contains(p)) {
                    points.remove(p);
                } else {
                    points.add(p);
                }
            }
        }
        // System.out.println(points);
        int perfectArea = (X2 - X1) * (Y2 - Y1);
        if (perfectArea != sumArea) {
            return false;
        }
        if (points.size() != 4) return false;
        Point P1 = new Point(X1, Y1);
        Point P2 = new Point(X1, Y2);
        Point P3 = new Point(X2, Y1);
        Point P4 = new Point(X2, Y2);
        if (!points.contains(P1)) return false;
        if (!points.contains(P2)) return false;
        if (!points.contains(P3)) return false;
        if (!points.contains(P4)) return false;
        return true;
    }
}

class Point {
    int x;
    int y; 
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object obj) {
        if(this == obj)
            return true;
        
        if(obj == null || obj.getClass() != this.getClass())
            return false;
        
        Point p = (Point) obj;

        StringBuilder sb1 = new StringBuilder();
        sb1.append(p.x);
        sb1.append(",");
        sb1.append(p.y);
        StringBuilder sb2 = new StringBuilder();
        sb2.append(this.x);
        sb2.append(",");
        sb2.append(this.y);
        return sb1.toString().equals(sb2.toString());
    }

    @Override
    public int hashCode() {
        return x + y;
    }
}

[zichengl]

Java 版本，cleaner code

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        int X1 = Integer.MAX_VALUE, Y1 = Integer.MAX_VALUE, X2 = Integer.MIN_VALUE, Y2 = Integer.MIN_VALUE;
        Set<Point> points = new HashSet<>();
        int sumArea = 0;
        for (int[] rec : rectangles) {
            int x1 = rec[0], y1 = rec[1], x2 = rec[2], y2 = rec[3];
            X1 = Math.min(X1, x1); 
            Y1 = Math.min(Y1, y1);
            X2 = Math.max(X2, x2); 
            Y2 = Math.max(Y2, y2);
            sumArea += (x2 - x1) * (y2 - y1);
            Point p1 = new Point(x1, y1);
            Point p2 = new Point(x1, y2);
            Point p3 = new Point(x2, y1);
            Point p4 = new Point(x2, y2);
            for (Point p : new Point[]{p1, p2, p3, p4}) {
                if (points.contains(p)) {
                    points.remove(p);
                } else {
                    points.add(p);
                }
            }
        }
        // System.out.println(points);
        int perfectArea = (X2 - X1) * (Y2 - Y1);
        if (perfectArea != sumArea) {
            return false;
        }
        if (points.size() != 4) return false;
        Point P1 = new Point(X1, Y1);
        Point P2 = new Point(X1, Y2);
        Point P3 = new Point(X2, Y1);
        Point P4 = new Point(X2, Y2);
        if (!points.contains(P1)) return false;
        if (!points.contains(P2)) return false;
        if (!points.contains(P3)) return false;
        if (!points.contains(P4)) return false;
        return true;
    }
}

class Point {
    int x;
    int y; 
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object obj) {
        if(this == obj)
            return true;
        
        if(obj == null || obj.getClass() != this.getClass())
            return false;
        
        Point p = (Point) obj;

        StringBuilder sb1 = new StringBuilder();
        sb1.append(p.x);
        sb1.append(",");
        sb1.append(p.y);
        StringBuilder sb2 = new StringBuilder();
        sb2.append(this.x);
        sb2.append(",");
        sb2.append(this.y);
        return sb1.toString().equals(sb2.toString());
    }

    @Override
    public int hashCode() {
        return x + y;
    }
}