2021-11-16[每日一题]391. 完美矩形__python3

给你一个数组 rectangles ,其中 rectangles[i] = [xi, yi, ai, bi]
表示一个坐标轴平行的矩形。这个矩形的左下顶点是 (xi, yi) ,右上顶点是 (ai, bi) 。
如果所有矩形一起精确覆盖了某个矩形区域,则返回 true ;否则,返回 false 。
https://leetcode-cn.com/problems/perfect-rectangle/

通俗易懂的解法:

class Solution:
    def isRectangleCover(self, rectangles):
        x1, x2, y1, y2 = [], [], [], []
        sum_area = 0
        count_dict = defaultdict(lambda: 0)
        for rec in rectangles:
            _x1, _x2, _y1, _y2 = [rec[0], rec[1]], [rec[2], rec[1]], [rec[2], rec[3]], [rec[0], rec[3]]
            for item in [_x1, _x2, _y1, _y2]:
            	# 统计词频
                count_dict[str(item)] += 1
            # 计算面积
            area = (rec[2]-rec[0]) * (rec[3] - rec[1])
            sum_area += area
            if not x1:
                x1, x2, y1, y2 = _x1, _x2, _y1, _y2
            else:
                # 选出拼出的图形的左上角,左下角,右上角,右下角四个坐标
                if x1[0] >= _x1[0] and x1[1] >= _x1[1]:
                    x1 = _x1
                if x2[0] <= _x2[0] and x2[1] >= _x2[1]:
                    x2 = _x2
                if y1[0] <= _y1[0] and y1[1] <= _y1[1]:
                    y1 = _y1
                if y2[0] >= _y2[0] and y2[1] <= _y2[1]:
                    y2 = _y2

        # 根据条件判断是否符合要求
        # 除四个坐标以外的坐标,均为2的倍数
        del count_dict[str(x1)], count_dict[str(x2)], count_dict[str(y1)], count_dict[str(y2)]
        for value in count_dict.values():
            if value % 2 is not 0:
                return False
        # 四个坐标位置,位置正确;实际面积和计算的面积相同
        if x1[1] == x2[1] and x1[0] == y2[0] and x2[0] == y1[0] and y1[1] == y2[1] and (x2[0] - x1[0]) * (y2[1] - x1[1]) == sum_area:
            return True
        else:
            return False

代码优化一下:

class Solution:
    def isRectangleCover(self, rectangles):
        area, minX, minY, maxX, maxY = 0, rectangles[0][0], rectangles[0][1], rectangles[0][2], rectangles[0][3]
        cnt = defaultdict(int)
        for rect in rectangles:
            x, y, a, b = rect[0], rect[1], rect[2], rect[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[(x, b)] += 1
            cnt[(a, y)] += 1
            cnt[(a, 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==0 for c in cnt.values())
上一篇:mysql分组取用户的前3条数据


下一篇:1017 Queueing at Bank (25 分)(坑点,思路分析)