给你一个数组 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
解释：因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。
提示：
1 <= rectangles.length <= 2 * 104
rectangles[i].length == 4
-105 <= xi, yi, ai, bi <= 105
from collections import Counter
class Solution:
def isRectangleCover(self, rectangles):
def get_basic_info(rectangle):
"""
获得矩形基本信息，包括四个顶点和矩形面积。输入矩形，返回四个顶点，
:param rectangle: 输入一个矩形
:return: 返回四个顶点，顺序：左下、右下、左上、右上
"""
x1, y1, x2, y2 = rectangle
area = (x2 - x1) * (y2 - y1)
return [(x1, y1), (x2, y1), (x1, y2), (x2, y2)], area
def get_all_vertexes_and_area(rectangles):
"""
取出所有矩形的所有顶点
:param rectangles: 输入所有矩形框
:return:
"""
all_vertexes, total_area = [], 0 # 结果列表和面积初始值
for rect in rectangles:
vertexes, area = get_basic_info(rect) # 获得每个矩形的顶点和面积
all_vertexes += vertexes # 加入到结果列表
total_area += area # 面积累加
return all_vertexes, total_area
def analize_vertexes(vertexes):
"""
分析顶点，类似游戏连连看，有重复顶点去掉这一对
:param vertexes:
:return:
"""
amount_dict = Counter(vertexes) # 统计每个顶点出现次数
even_vetexes, odd_vetexes = {}, {}
for key, value in amount_dict.items():
if value %2 == 0:
even_vetexes[key] = value # 统计出现次数为偶数的记录
else:
odd_vetexes[key] = value # 统计出现次数为奇数的记录
return even_vetexes, odd_vetexes # 返回偶数和奇数记录
def get_rectangle_area(vertexes):
"""
输入四个顶点，如果可以组成矩形，返回矩形的面积，否则返回0
:param vertexes:
:return:
"""
x_list = [vertex[0] for vertex in vertexes]
y_list = [vertex[1] for vertex in vertexes]
l, r, b, t = min(x_list), max(x_list), min(y_list), max(y_list)
if sorted([(l, b), (r, b), (l, t), (r, t)]) == sorted(vertexes):
return (r-l) * (t-b)
else:
return 0
def analize_odd_vertexes(vertex_records, area):
"""
对奇数个数的顶点和总面积进行判断
:param vertexes:
:param area:
:return:
"""
if len(vertex_records) == 4 and sum(vertex_records.values()) == 4:
vertexes = vertex_records.keys()
target_area = get_rectangle_area(vertexes)
if target_area == area:
return True
else:
return False
else:
return False
def is_perfect(rectangles):
vertexes, area = get_all_vertexes_and_area(rectangles)
even, odd = analize_vertexes(vertexes)
if analize_odd_vertexes(odd, area):
return True
else:
return False
return is_perfect(rectangles)
力扣https://leetcode-cn.com/problems/perfect-rectangle/solution/wan-mei-ju-xing-by-leetcode-solution-ty8q/
