参数 ted eth pad summary 应该 logs win
- 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]]
- Return true.All 5 rectangles together form an exact cover of a rectangular region.
- 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.
- 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.
- 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.
这个题我甚至不知道该怎么总结。
难就难在从这个题抽象出一种解法,看了别人的答案和思路 = = 然而没有归类总结到某种类型,这题相当于背了个题。。。
简单的说,除了最外面的 4 个点,所有的点都会 2 次 2 次的出现,如果有覆盖,覆盖进去的点就不是成对出现了。
最外面 4 个点围的面积等于所有小矩形面积的和。
就用这 2 个判断就行了。
判断成对的点用的 SET,单次出现添加,第二次出现删除。。这样最后应该都删掉,SET 里只剩下 4 个最外面的点。
剩下的就是判断最外点,不停地更新。。
Consider how the corners of all rectangles appear in the large rectangle if there's a perfect rectangular cover.
Rule1: The local shape of the corner has to follow one of the three following patterns
For each point being a corner of any rectangle, it should appear even times except the 4 corners of the large rectangle. So we can put those points into a hash map and remove them if they appear one more time.
At the end, we should only get 4 points.
Rule2: the large rectangle area should be equal to the sum of small rectangles
- public class Solution {
- public boolean isRectangleCover(int[][] rectangles) {
- if (rectangles == null || rectangles.length == 0 || rectangles[0].length == 0) return false;
- int subrecAreaSum = 0; //sum of subrectangle's area
- int x1 = Integer.MAX_VALUE; //large rectangle bottom left x-axis
- int y1 = Integer.MAX_VALUE; //large rectangle bottom left y-axis
- int x2 = Integer.MIN_VALUE; //large rectangle top right x-axis
- int y2 = Integer.MIN_VALUE; //large rectangle top right y-axis
- HashSet < String > set = new HashSet < String > (); // store points
- for (int[] rec: rectangles) {
- //check if it has large rectangle's 4 points
- x1 = Math.min(x1, rec[0]);
- y1 = Math.min(y1, rec[1]);
- x2 = Math.max(x2, rec[2]);
- y2 = Math.max(y2, rec[3]);
- //calculate sum of subrectangles
- subrecAreaSum += (rec[2] - rec[0]) * (rec[3] - rec[1]);
- //store this rectangle's 4 points into hashSet
- String p1 = Integer.toString(rec[0]) + "" + Integer.toString(rec[1]);
- String p2 = Integer.toString(rec[0]) + "" + Integer.toString(rec[3]);
- String p3 = Integer.toString(rec[2]) + "" + Integer.toString(rec[1]);
- String p4 = Integer.toString(rec[2]) + "" + Integer.toString(rec[3]);
- if (!set.add(p1)) set.remove(p1);
- if (!set.add(p2)) set.remove(p2);
- if (!set.add(p3)) set.remove(p3);
- if (!set.add(p4)) set.remove(p4);
- }
- if (set.size() != 4 || !set.contains(x1 + "" + y1) || !set.contains(x1 + "" + y2) || !set.contains(x2 + "" + y1) || !set.contains(x2 + "" + y2)) return false;
- return subrecAreaSum == (x2 - x1) * (y2 - y1);
- }
- }
- 存为字符串 //store this rectangle's 4 points into hashSet
- String p1 = Integer.toString(rec[0]) + "" + Integer.toString(rec[1]);
|
如果此 set 中尚未包含指定元素,则添加指定元素。 |
391. Perfect Rectangle
来源: http://www.bubuko.com/infodetail-2163971.html