题目
给你一个数组 rectangles ，其中 rectangles[i] = [xi, yi, ai, bi] 表示一个坐标轴平行的矩形。这个矩形的左下顶点是 (xi, yi) ，右上顶点是 (ai, bi) 。
如果所有矩形一起精确覆盖了某个矩形区域，则返回 true ；否则，返回 false 。
示例 1：
输入：rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
输出：true
解释：5 个矩形一起可以精确地覆盖一个矩形区域。
示例 2：
输入：rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
输出：false
解释：两个矩形之间有间隔，无法覆盖成一个矩形。
示例 3：
输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
输出：false
解释：因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。
参数范围：
1 <= rectangles.length <= 2 * 104
rectangles[i].length == 4
-105 <= xi, yi, ai, bi <= 105
2023年6月版
class Solution { public: bool isRectangleCover(vector<vector>& rectangles) { int iMaxX = 0, iMaxY = 0; { vector rectMax = rectangles[0]; long long llTotalArea = 0; for (auto& v : rectangles) { if (v[0] > v[2]) { swap(v[0], v[2]); } if (v[1] > v[3]) { swap(v[1], v[3]); } MinSelf(&rectMax[0], v[0]); MinSelf(&rectMax[1], v[1]); MaxSelf(&rectMax[2], v[2]); MaxSelf(&rectMax[3], v[3]); long long llWidth = v[2] - v[0]; llTotalArea += llWidth * (v[3] - v[1]); } //总面积必须和小矩形面积之和相等 if (llTotalArea != (long long)(rectMax[2] - rectMax[0])*(rectMax[3] - rectMax[1])) { return false; } for (auto& v : rectangles) { v[0] -= rectMax[0]; v[1] -= rectMax[1]; v[2] -= rectMax[0]; v[3] -= rectMax[1]; } iMaxX = rectMax[2] - rectMax[0]; iMaxY = rectMax[3] - rectMax[1]; } std::map<std::pair<int, int>, int> mPointNums; for (auto& v : rectangles) { mPointNums[{v[0], v[1]}]++; mPointNums[{v[0], v[3]}]++; mPointNums[{v[2], v[1]}]++; mPointNums[{v[2], v[3]}]++; } std::set<std::pair<int, int>> setRang; setRang.insert(make_pair(0, 0)); setRang.insert(make_pair(0, iMaxY)); setRang.insert(make_pair(iMaxX, 0)); setRang.insert(make_pair(iMaxX, iMaxY)); for (const auto& it : mPointNums) { if (setRang.count(it.first)) { if (1 != it.second) { return false; } continue; } if ((2 != it.second) && (4 != it.second)) { return false; } } return true; } };
2023年8月版
class Solution { public: bool isRectangleCover(vector<vector>& rectangles) { vector vRange = rectangles.front(); std::unordered_map<long long, vector> mMaskNum; for (const auto& v : rectangles) { vRange[0] = min(vRange[0],v[0]); vRange[1] = min(vRange[1], v[1]); vRange[2] = max(vRange[2], v[2]); vRange[3] = max(vRange[3], v[3]); mMaskNum[Mask(v[0], v[1])].emplace_back(0);//左下 mMaskNum[Mask(v[0], v[3])].emplace_back(1);//左上 mMaskNum[Mask(v[2], v[1])].emplace_back(1);//右下 mMaskNum[Mask(v[2], v[3])].emplace_back(3);//右上 } vector vMaskRange; vMaskRange.emplace_back(Mask(vRange[0], vRange[1])); vMaskRange.emplace_back(Mask(vRange[0], vRange[3])); vMaskRange.emplace_back(Mask(vRange[2], vRange[1])); vMaskRange.emplace_back(Mask(vRange[2], vRange[3])); for (const auto mask : vMaskRange) { if (1 != mMaskNum[mask].size()) { return false; } mMaskNum.erase(mask); } for ( auto& it : mMaskNum) { auto& v = it.second; if ((2 != it.second.size())&& (4 != it.second.size())) { return false; } std::sort(it.second.begin(), it.second.end()); bool bVilid = (0 == v[0]) && (3 == v.back()); if (2 == it.second.size()) { if (v[0] == v[1]) { return false; } bVilid = (v[0]/2 == v[1]/2) || (v[0]%2 == v[1]%2); } if (!bVilid) { return false; } } return true; } long long Mask(int x, int y) { x += 100 * 1000; y += 100 * 1000; return (long long)x * 1000 * 1000 + y; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 洒家想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 墨家名称的来源：有所得以墨记之。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
