题目
思路一 哈希表
精确覆盖需要满足【面积相等】和【边缘点出现一次,其余点出现2或4次】的条件。
pair表示点,哈希表存储点的数目,area存储矩形面积,四个int型数据存储最小/最大的x/y坐标。
在循环中,需要计算面积,更新边缘点极值,增加点的数目。
最后根据条件来判断面积、点出现的次数。
代码一
typedef pair<int,int> Point;
class Solution {
public:
bool isRectangleCover(vector<vector<int>>& rectangles) {
long area=0;
int minX=rectangles[0][0],minY=rectangles[0][1],maxX=rectangles[0][2],maxY=rectangles[0][3];
map<Point,int> cnt;
for(auto &rect:rectangles){
int x=rect[0],y=rect[1],a=rect[2],b=rect[3];
area+=(long)(a-x)*(b-y);
minX=min(minX,x);
minY=min(minY,y);
maxX=max(maxX,a);
maxY=max(maxY,b);
Point point1({x,y});
Point point2({x,b});
Point point3({a,y});
Point point4({a,b});
cnt[point1]++;
cnt[point2]++;
cnt[point3]++;
cnt[point4]++;
}
Point pointMinMin({minX,minY});
Point pointMinMax({minX,maxY});
Point pointMaxMin({maxX,minY});
Point pointMaxMax({maxX,maxY});
if(area!=(long long)(maxX-minX)*(maxY-minY)||!cnt.count(pointMinMin)||!cnt.count(pointMinMax)||!cnt.count(pointMaxMin)||!cnt.count(pointMaxMax))
return false;
cnt.erase(pointMinMin);
cnt.erase(pointMinMax);
cnt.erase(pointMaxMin);
cnt.erase(pointMaxMax);
for(auto &entry:cnt){
int value=entry.second;
if(value!=2&&value!=4)
return false;
}
return true;
}
};