给你一个数组 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())