Perfect Rectangle 391
Question
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)).
Example 1:
rectangles = [
[1,1,3,3],
[3,1,4,2],
[3,2,4,4],
[1,3,2,4],
[2,3,3,4]
]
Example 2:
rectangles = [
[1,1,2,3],
[1,3,2,4],
[3,1,4,2],
[3,2,4,4]
]
Example 3:
rectangles = [
[1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[3,2,4,4]
]
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.
Return false. Because there is a gap in the top center.
Return false. Because there is a gap between the two rectangular regions.
Return true. All 5 rectangles together form an exact cover of a rectangular region.
Solution
这道题一开始没有想出解法，参考了别人的答案之后，解法如下。
观察矩形的顶点，发现所有顶点只可能属于以下3种：
观察每个顶点可以发现，每个绿点其实都是两个顶点的重合，每个红点都是四个顶点的重合，而每个蓝点只有一个顶点，有了这条性质，我们直接用一个set，对于遍历到的任意一个矩形的4个顶点，如果set中已经存在了，则删去这个点，如果没有就加上，这样如果是perfect rectangle，最后会把绿点和红点都滤去，剩下的都是蓝点，我们只要看此时set中剩下的顶点的个数是否为四个同时是否为矩形的左下，左上，右下，右上顶点，再加上检测每个矩形面积累加和要等于最后的大矩形的面积即可。
每个顶点都将其坐标转化为字符串的形式，这样便于比较。
代码如下：
public class Solution {
public boolean isRectangleCover(int[][] rectangles) {
if (rectangles == null || rectangles.length == 0 || rectangles[0].length == 0) {
return false;
}
int minX = Integer.MAX_VALUE;
int minY = Integer.MAX_VALUE;
int maxX = Integer.MIN_VALUE;
int maxY = Integer.MIN_VALUE;
int total = 0;
HashSet<String> set = new HashSet<String>();
for (int i = 0; i < rectangles.length; i++) {
int[] rect = rectangles[i];
minX = Math.min(minX, rect[0]);
minY = Math.min(minY, rect[1]);
maxX = Math.max(maxX, rect[2]);
maxY = Math.max(maxY, rect[3]);
total += (rect[2] - rect[0]) * (rect[3] - rect[1]);
String s1 = rect[0] + "_" + rect[1];
String s2 = rect[0] + "_" + rect[3];
String s3 = rect[2] + "_" + rect[1];
String s4 = rect[2] + "_" + rect[3];
if (set.contains(s1)) {
set.remove(s1);
} else {
set.add(s1);
}
if (set.contains(s2)) {
set.remove(s2);
} else {
set.add(s2);
}
if (set.contains(s3)) {
set.remove(s3);
} else {
set.add(s3);
}
if (set.contains(s4)) {
set.remove(s4);
} else {
set.add(s4);
}
}
String t1 = minX + "_" + minY;
String t2 = minX + "_" + maxY;
String t3 = maxX + "_" + minY;
String t4 = maxX + "_" + maxY;
if (!set.contains(t1) || !set.contains(t2) || !set.contains(t3) || !set.contains(t4) || set.size() != 4) {
return false;
}
return total == (maxX - minX) * (maxY - minY);
}
}