力扣-391. 完美矩形-Python题解

我们有 N 个与坐标轴对齐的矩形, 其中 N > 0, 判断它们是否能精确地覆盖一个矩形区域。

每个矩形用左下角的点和右上角的点的坐标来表示。例如， 一个单位正方形可以表示为 [1,1,2,2]。 ( 左下角的点的坐标为 (1, 1) 以及右上角的点的坐标为 (2, 2) )。

示例 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。因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。

class Solution:
    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
        '''
        更新矩形的四个边界，边界形成的矩形面积和所有矩形面积和相等，是完美平铺的
        必要条件，同时还需要保证没有重叠，判断有没有重叠的方法比较巧妙，不断将新增矩形的
        四个顶点加入集合，如果同一个顶点出现偶数次，就抵消掉，最后剩余的顶点数如果是4个
        且就是矩形边界组成的4个顶点，那就没有重叠
        '''
        # 首先定义一个矩形区域的边界
        # bound0:矩阵左下角的x值
        # bound1:矩阵左小角的y值
        # bound2:矩阵右上角的x值
        # bound3:矩阵右上角的y值
        # import sys
        max_val = sys.maxsize
        min_val = -sys.maxsize -1
        bound = [max_val, max_val, min_val, min_val]

        # 小矩形的面积和
        sum_rectangles_areas = 0
        # pos_set:记录矩阵坐标的集合,如果左下角、右下角的坐标出现过，则直接清除，最后应该只剩下大矩形的4个边
        pos_set = set()
        # 从传入的参数中获取每一个小矩形的左下角的x,y值，右下角的x,y值
        for x1, y1, x2, y2 in rectangles:
            # 从bound0,x1,x2中获取最小值赋值给bound0
            bound[0] = min(bound[0], x1, x2)
            # 从bound1，y1,y2中获取最小的y值赋值给bound1
            bound[1] = min(bound[1], y1, y2)
            # 从bound2,x1,x2中获取最大的x值赋值给bound2
            bound[2] = max(bound[2], x1, x2)
            # 从bound[3],y1,y2中获取最大的y值赋值给bound[3]
            bound[3] = max(bound[3], y1, y2)
            sum_rectangles_areas += (x2 - x1) * (y2 - y1)
            
            self.pos_set_handle((x1,y1), pos_set)
            self.pos_set_handle((x1,y2), pos_set)
            self.pos_set_handle((x2,y1), pos_set)
            self.pos_set_handle((x2,y2), pos_set)
        if len(pos_set) != 4:
            return False
        # 最后大矩形的4个顶点在pos_set集合中且大矩形面积是各个小矩形面积之和
        elif (bound[0],bound[1]) in pos_set and (bound[0],bound[3]) in pos_set and                    (bound[2], bound[1]) in pos_set and (bound[2],bound[3]) in pos_set and sum_rectangles_areas == (bound[2] - bound[0]) * (bound[3] - bound[1]):
            return True
        return False
            
        
    def pos_set_handle(self, pos, pos_set:set):
        if pos in pos_set:
            pos_set.remove(pos)
        else:
            pos_set.add(pos)