LeetCode——391. 完美矩形（Java）

题目描述

题干：
给你一个数组 rectangles ，其中 rectangles[i] = [xi, yi, ai, bi] 表示一个坐标轴平行的矩形。
这个矩形的左下顶点是 (xi, yi) ，右上顶点是 (ai, bi) 。
如果所有矩形一起精确覆盖了某个矩形区域，则返回 true ；否则，返回 false 。

示例 1：
输入：rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
输出：true
解释：5 个矩形一起可以精确地覆盖一个矩形区域。 

示例 2：
输入：rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
输出：false
解释：两个矩形之间有间隔，无法覆盖成一个矩形。

示例 3：
输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[3,2,4,4]]
输出：false
解释：图形顶端留有空缺，无法覆盖成一个矩形。

示例 4：
输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
输出：false
解释：因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。

题解思路

判断给出矩阵是否可以组成完美矩阵，这里如果仅仅靠简单思路只判断面积

所有矩阵的面积和与最后矩阵组成的面积作比较，如果相等则可以组成

但是遇到 [[0,0,1,1],[0,1,3,2],[1,0,2,2]] 这个例子的时候就不会通过

所以我们需要继续发现限制条件，如果是完美矩阵，则每个矩阵的边都是会有重复的

这也就是扫描思路的解法，这里我们用简化的重复的点的思路来解答

和边一样，除了四个边界点，其他每个矩阵的顶点都会出现偶数次

所以我们这里采用Set集合统计每个顶点，最后Set中只会剩下四个顶点

正确代码

class isRectangleCoverSolution {
    Set set;

    /**
     * 1.面积之和必须等于最后组合的面积
     * 2.除了四个顶点其他所有顶点都为偶数个出现
     *
     * @param rectangles 顶点数组
     * @return 是否为完美矩阵
     */
    public boolean isRectangleCover(int[][] rectangles) {
        long area = 0;
        set = new HashSet<>();
        int minX = rectangles[0][0], minY = rectangles[0][1], maxX = rectangles[0][2], maxY = rectangles[0][3];

        for (int[] rectangle : rectangles) {
            int x = rectangle[0], y = rectangle[1], a = rectangle[2], b = rectangle[3];
            area += (long) (a - x) * (b - y); // 获取所有矩形面积的和

            // 获取边界值
            minX = Math.min(minX, x);
            minY = Math.min(minY, y);
            maxX = Math.max(maxX, a);
            maxY = Math.max(maxY, b);

            // 判断端点出现是否为偶数
            Point point1 = new Point(x, y);
            Point point2 = new Point(x, b);
            Point point3 = new Point(a, y);
            Point point4 = new Point(a, b);

            put(point1);
            put(point2);
            put(point3);
            put(point4);
        }

        if (area != ((long) (maxX - minX) * (maxY - minY))) return false;
        return set.size() == 4 && set.contains(new Point(minX, minY)) && set.contains(new Point(minX, maxY)) && set.contains(new Point(maxX, minY)) && set.contains(new Point(maxX, maxY));
    }

    private void put(Point point) {
        if (!set.add(point)) set.remove(point);
    }

    private class Point {
        int x;
        int y;

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

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

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Point) {
                Point point = (Point) obj;
                return this.x == point.x && this.y == point.y;
            }
            return false;
        }
    }
}

总结

虽然本题作为困难题，但是没有很难理解的地方，这里值得注意的是要重新写hashCode和equals方法

如果文章存在问题或者有更好的题解，欢迎在评论区斧正和评论，各自努力，最高处见