LEETCODE算法:391:Perfect Rectangle

发表于 更新于 分类于 Waline： 阅读次数：

题目

Given an array rectangles where rectangles[i] = [xi, yi, ai, bi] represents an axis-aligned rectangle. The bottom-left point of the rectangle is (xi, yi) and the top-right point of it is (ai, bi).

Return true if all the rectangles together form an exact cover of a rectangular region.

Example 1:

img 
1
2
3
Input: rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
Output: true
Explanation: All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

img 
1
2
3
Input: rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
Output: false
Explanation: Because there is a gap between the two rectangular regions.

Example 3:

img 
1
2
3
Input: rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[3,2,4,4]]
Output: false
Explanation: Because there is a gap in the top center.

Example 4:

img 
1
2
3
Input: rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
Output: false
Explanation: Because two of the rectangles overlap with each other.

Constraints:

  • 1 <= rectangles.length <= 2 * 104
  • rectangles[i].length == 4
  • -105 <= xi, yi, ai, bi <= 105

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    typedef pair<int,int> Point;
public:
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        int xmin=rectangles[0][0];
        int ymin=rectangles[0][1];
        int xmax=rectangles[0][2];
        int ymax=rectangles[0][3];
        long area=(ymax-ymin)*(xmax-xmin);
        map<Point,int> num;
        num[{xmin,ymin}]=1;
        num[{xmax,ymax}]=1;
        num[{xmin, ymax}] = 1;
        num[{xmax, ymin}] = 1;
        for(int i =1;i<rectangles.size();i++){
            if (rectangles[i][0]<xmin) xmin=rectangles[i][0];
            if (rectangles[i][1]<ymin) ymin=rectangles[i][1];
            if (rectangles[i][2]>xmax) xmax=rectangles[i][2];
            if (rectangles[i][3]>ymax) ymax=rectangles[i][3];
            area+=(long)(rectangles[i][3]-rectangles[i][1])*(rectangles[i][2]-rectangles[i][0]);
            num[{rectangles[i][0],rectangles[i][1]}]+=1;
            num[{rectangles[i][2],rectangles[i][3]}]+=1;
            num[{rectangles[i][0],rectangles[i][3]}]+=1;
            num[{rectangles[i][2],rectangles[i][1]}]+=1;
        }
        if (area != (ymax-ymin)*(xmax-xmin)) return false;
        if(num[{xmin,ymin}]!=1 || num[{xmax,ymax}]!=1 || num[{xmin,ymax}]!=1 || num[{xmax,ymin}]!=1) return false;
        num.erase({xmin,ymin});
        num.erase({xmin,ymax});
        num.erase({xmax,ymin});
        num.erase({xmax,ymax});
        for (auto &t:num){
            if(t.second!=2 && t.second!=4) return false;
        }
        return true;
    }
};

注释

  1. 找规律：如果是完美矩形，那除了最终大矩形的四个点外，其余各点只能出现两次或四次
  2. 先判断大矩形面积是否和若干个小矩形面积相加相同，如果面积一样则判断各个点出现的次数，使用hash统计较为方便