题目
我们有 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。因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。
解答
要构成完美矩形，需要满足以下条件：
所有矩形的四个顶点中，只有完美矩形的四个顶点出现过奇数次，其余均是偶数次；
构成完美矩形的面积等于各个小矩形面积之和。
为了便于理解和展示，这里我们的代码都是用功能函数实现的，这样组织代码结构：
is_perfect：主函数，输入矩形列表，输出能否组成完美矩形的判断结果，其中包含以下步骤：
① get_all_vertexes_and_area函数：得到所有矩形的所有顶点列表和总面积；
② analize_vertexes函数：获得顶点列表中只出现过奇数次的顶点odd；
③ analize_odd_vertexes函数：包含矩形验证和面积计算两个功能，首先分析奇数次顶点，如果个数为4且每个顶点出现次数为1，并且可以组成矩形，那么返回这个矩形的面积，否则返回0；
④ 进行面积比对，如果完美矩形面积等于小矩形之和，那么则可以满足条件，返回True，否则返回False。
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)
如有疑问或建议，欢迎评论区留言~
