题目描述:
LeetCode 391. Perfect Rectangle
Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.
Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).
![](https://leetcode.com/static/images/problemset/rectangle_perfect.gif)
Example 1:
rectangles = [ [1,1,3,3], [3,1,4,2], [3,2,4,4], [1,3,2,4], [2,3,3,4] ] Return true. All 5 rectangles together form an exact cover of a rectangular region.
![](https://leetcode.com/static/images/problemset/rectangle_separated.gif)
Example 2:
rectangles = [ [1,1,2,3], [1,3,2,4], [3,1,4,2], [3,2,4,4] ] Return false. Because there is a gap between the two rectangular regions.
![](https://leetcode.com/static/images/problemset/rectangle_hole.gif)
Example 3:
rectangles = [ [1,1,3,3], [3,1,4,2], [1,3,2,4], [3,2,4,4] ] Return false. Because there is a gap in the top center.
![](https://leetcode.com/static/images/problemset/rectangle_intersect.gif)
Example 4:
rectangles = [ [1,1,3,3], [3,1,4,2], [1,3,2,4], [2,2,4,4] ] Return false. Because two of the rectangles overlap with each other.
题目大意:
给定N个与坐标轴对齐的矩形(其中N > 0),判断它们是否恰好围成一个矩形区域。
每一个矩形通过左下角和右上角的坐标表示。例如,一个单位正方形用[1,1,2,2]表示。(左下角坐标(1, 1),右上角坐标(2, 2)).
测试用例如题目描述。
解题思路:
解法I “顶点检查法”:
参考LeetCode Discuss,链接地址:
https://discuss.leetcode.com/topic/55923/o-n-solution-by-counting-corners-with-detailed-explaination
利用points记录各个顶点被矩形的覆盖情况
记矩形的左下、右下、右上、左上顶点为A、B、C、D,则有:
左下顶点A的坐标为(l, b) 右下顶点B的坐标为(r, b) 右上顶点C的坐标为(r, t) 左上顶点D的坐标为(l, t)
如下图所示:
G D |-----|-----| C | | | H |-----I-----| F | | | A |-----|-----| B E
将左下A、右下B、右上C、左上D分别标号为1、2、4、8(这样标号便于位运算),则有:
points[A] |= 1 points[B] |= 2 points[C] |= 4 points[D] |= 8 points[E] = points[A] | points[B] = 3 (左下顶点、右下顶点的并) points[F] = points[B] | points[C] = 6 (右下顶点、右上顶点的并) points[G] = points[C] | points[D] = 12 (右上顶点、左上顶点的并) points[H] = points[A] | points[D] = 9 (左下顶点、左上顶点的并) points[I] = points[A] | points[B] | points[C] | points[D] = 15(四个顶点的并)
Python代码:
class Solution(object):
def isRectangleCover(self, rectangles):
"""
:type rectangles: List[List[int]]
:rtype: bool
"""
left = min(x[0] for x in rectangles)
bottom = min(x[1] for x in rectangles)
right = max(x[2] for x in rectangles)
top = max(x[3] for x in rectangles)
points = collections.defaultdict(int)
for l, b, r, t in rectangles:
A, B, C, D = (l, b), (r, b), (r, t), (l, t)
for p, q in zip((A, B, C, D), (1, 2, 4, 8)):
if points[p] & q: return False
points[p] |= q
for px, py in points:
if left < px < right or bottom < py < top:
if points[(px, py)] not in (3, 6, 9, 12, 15):
return False
return True
解法II 扫描线法
参阅LeetCode Discuss:https://discuss.leetcode.com/topic/55944/o-n-log-n-sweep-line-solution
本文链接:http://bookshadow.com/weblog/2016/08/28/leetcode-perfect-rectangle/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。
我想知道这道题这样的思路是怎么想出来的。。。自己做的时候这道题真是毫无头绪
第一个解法还是会报错。。。
我用了一个非常笨的解法 等于是先去检查四条边 然后检查内部没有overlap 然后再检查面积
感谢提醒!解法I无法通过[[0,0,1,1],[0,0,1,1],[1,1,2,2],[1,1,2,2]],已经修改!