力扣每日一题2021-11-16完美矩形

• 391.完美矩形
• • 题目描述
  • 思路
  • • 哈希
    • • Python实现
      • Java实现

完美矩形

根据题目要求的精确覆盖，可知：

• 矩形区域内不能出现空缺；
• 矩形区域内不能有相交区域。
  根据这两个条件，我们可以通过如下方法进行求解。
  判定空缺区域可以使用矩形区域面积等于所有矩形面积之和来判定，而相交区域的判定需要维护一个统计量来判断。
  后者可以通过统计每个矩形顶点出现的次数，同一个位置最多存在四个顶点，在满足该条件的前提下，如果矩形区域中有相交区域，则要么是矩形区域四角的顶点出现不止一次，要么导致非四角的顶点存在出现一次或三次的顶点。
  因此，要满足精确覆盖，除了满足矩形区域面积等于所有矩形面积之和，还要满足矩形区域四角的顶点只出现一次，且其余顶点的出现次数只能是2次或4次。
  在具体实现时，可以遍历矩形数组，计算矩形区域的四个顶点的位置，以及矩形面积之和，并用哈希表统计每个矩形顶点出现的次数。遍历完成后，检查矩形区域的面积是否等于所有矩形的面积之和，以及每个顶点的出现次数是否满足上述要求。

class Solution:
    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
        area, minX, minY, maxX, maxY = 0, rectangles[0][0], rectangles[0][1], rectangles[0][2], rectangles[0][3]
        cnt = defaultdict(int)
        for r in rectangles:
            x, y, a, b = r[0], r[1], r[2], r[3]
            area += (a-x)*(b-y)
            minX = min(minX, x)
            minY = min(minY, y)
            maxX = max(maxX, a)
            maxY = max(maxY, b)
            
            cnt[(x, y)] += 1
            cnt[(a, b)] += 1
            cnt[(a, y)] += 1
            cnt[(x, b)] += 1
            
        if area != (maxX-minX) * (maxY-minY) or cnt[(minX, minY)] != 1 or cnt[(minX, maxY)] != 1 or cnt[(maxX, minY)] != 1 or cnt[(maxX, maxY)] != 1:
            return False
        del cnt[(minX, minY)], cnt[(minX, maxY)], cnt[(maxX, minY)], cnt[(maxX, maxY)]
        return all(c == 2 or c == 4 for c in cnt.values())

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        long area = 0;
        int minX = rectangles[0][0], minY = rectangles[0][1], maxX = rectangles[0][2], maxY = rectangles[0][3];
        Map cnt = new HashMap();
        for (int[] rect : rectangles) {
            int x = rect[0], y = rect[1], a = rect[2], b = rect[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);

            cnt.put(point1, cnt.getOrDefault(point1, 0) + 1);
            cnt.put(point2, cnt.getOrDefault(point2, 0) + 1);
            cnt.put(point3, cnt.getOrDefault(point3, 0) + 1);
            cnt.put(point4, cnt.getOrDefault(point4, 0) + 1);
        }

        Point pointMinMin = new Point(minX, minY);
        Point pointMinMax = new Point(minX, maxY);
        Point pointMaxMin = new Point(maxX, minY);
        Point pointMaxMax = new Point(maxX, maxY);
        if (area != (long) (maxX - minX) * (maxY - minY) || cnt.getOrDefault(pointMinMin, 0) != 1 || cnt.getOrDefault(pointMinMax, 0) != 1 || cnt.getOrDefault(pointMaxMin, 0) != 1 || cnt.getOrDefault(pointMaxMax, 0) != 1) {
            return false;
        }

        cnt.remove(pointMinMin);
        cnt.remove(pointMinMax);
        cnt.remove(pointMaxMin);
        cnt.remove(pointMaxMax);

        for (Map.Entry entry : cnt.entrySet()) {
            int value = entry.getValue();
            if (value != 2 && value != 4) {
                return false;
            }
        }
        return true;
    }
}

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 point2 = (Point) obj;
            return this.x == point2.x && this.y == point2.y;
        }
        return false;
    }
}