如何判定完美矩形
数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 391. Perfect Rectangle | 391. 完美矩形 | 🔴 |
———–
今天讲一道非常有意思，而且比较有难度的题目。
我们知道一个矩形有四个顶点，但是只要两个顶点的坐标就可以确定一个矩形了（比如左下角和右上角两个顶点坐标）。
今天来看看力扣第 391 题「
完美矩形」，题目会给我们输入一个数组 rectangles，里面装着若干四元组 (x1,y1,x2,y2)，每个四元组就是记录一个矩形的左下角和右上角坐标。
也就是说，输入的 rectangles 数组实际上就是很多小矩形，题目要求我们输出一个布尔值，判断这些小矩形能否构成一个「完美矩形」。函数签名如下：
// 注意：java 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
public boolean isRectangleCover(int[][] rectangles) {
// 注意：cpp 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
bool isRectangleCover(vector<vector<int>>& rectangles)
def isRectangleCover(rectangles: List[List[int]]) -> bool
// 注意：go 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
func isRectangleCover(rectangles [][]int) bool {
// 注意：javascript 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
function isRectangleCover(rectangles) {
// function body here
}
所谓「完美矩形」，就是说 rectangles 中的小矩形拼成图形必须是一个大矩形，且大矩形中不能有重叠和空缺。
比如说题目给我们举了几个例子：
这个题目难度是 Hard，如果没有做过类似的题目，还真做不出来。
常规的思路，起码要把最终形成的图形表示出来吧，而且你要有方法去判断两个矩形是否有重叠，是否有空隙，虽然可以做到，不过感觉异常复杂。
其实，想判断最终形成的图形是否是完美矩形，需要从「面积」和「顶点」两个角度来处理。
先说说什么叫从「面积」的角度。
rectangles 数组中每个元素都是一个四元组 (x1, y1, x2, y2)，表示一个小矩形的左下角顶点坐标和右上角顶点坐标。
那么假设这些小矩形最终形成了一个「完美矩形」，你会不会求这个完美矩形的左下角顶点坐标 (X1, Y1) 和右上角顶点的坐标 (X2, Y2)？
这个很简单吧，左下角顶点 (X1, Y1) 就是 rectangles 中所有小矩形中最靠左下角的那个小矩形的左下角顶点；右上角顶点 (X2, Y2) 就是所有小矩形中最靠右上角的那个小矩形的右上角顶点。
注意我们用小写字母表示小矩形的坐标，大写字母表示最终形成的完美矩形的坐标，可以这样写代码：
// 注意：java 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
// 左下角顶点，初始化为正无穷，以便记录最小值
double X1 = Double.POSITIVE_INFINITY;
double Y1 = Double.POSITIVE_INFINITY;
// 右上角顶点，初始化为负无穷，以便记录最大值
double X2 = Double.NEGATIVE_INFINITY;
double Y2 = Double.NEGATIVE_INFINITY;
for (int i = 0; i < rectangles.length; i++) {
double x1 = rectangles[i][0];
double y1 = rectangles[i][1];
double x2 = rectangles[i][2];
double y2 = rectangles[i][3];
// 取小矩形左下角顶点的最小值
X1 = Math.min(X1, x1);
Y1 = Math.min(Y1, y1);
// 取小矩形右上角顶点的最大值
X2 = Math.max(X2, x2);
Y2 = Math.max(Y2, y2);
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
// 左下角顶点，初始化为正无穷，以便记录最小值
int X1 = std::numeric_limits<int>::max(), Y1 = std::numeric_limits<int>::max();
// 右上角顶点，初始化为负无穷，以便记录最大值
int X2 = std::numeric_limits<int>::min(), Y2 = std::numeric_limits<int>::min();
for (auto rect : rectangles) {
// 取小矩形左下角顶点的最小值
X1 = std::min(X1, rect[0]);
Y1 = std::min(Y1, rect[1]);
// 取小矩形右上角顶点的最大值
X2 = std::max(X2, rect[2]);
Y2 = std::max(Y2, rect[3]);
}
# 左下角顶点，初始化为正无穷，以便记录最小值
X1, Y1 = float('inf'), float('inf')
# 右上角顶点，初始化为负无穷，以便记录最大值
X2, Y2 = -float('inf'), -float('inf')
for x1, y1, x2, y2 in rectangles:
# 取小矩形左下角顶点的最小值
X1, Y1 = min(X1, x1), min(Y1, y1)
# 取小矩形右上角顶点的最大值
X2, Y2 = max(X2, x2), max(Y2, y2)
// 注意：go 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
// 计算小矩形区域的边界坐标，返回四个最可能成为边界的坐标值
func bounds(rects [][]int) (float64, float64, float64, float64) {
x1, y1, x2, y2 := math.Inf(1), math.Inf(1), math.Inf(-1), math.Inf(-1)
for _, rect := range rects {
x1, y1 = math.Min(float64(x1), float64(rect[0])), math.Min(float64(y1), float64(rect[1]))
x2, y2 = math.Max(float64(x2), float64(rect[2])), math.Max(float64(y2), float64(rect[3]))
}
return x1, y1, x2, y2
}
// 计算覆盖所有小矩形的最小大矩形
func minRectangle(rects [][]int) int {
x1, y1, x2, y2 := bounds(rects)
return int(math.Ceil((x2-x1)*(y2-y1)))
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
// 初始化为正无穷，以便记录最小值
var X1 = Infinity, Y1 = Infinity;
// 初始化为负无穷，以便记录最大值
var X2 = -Infinity, Y2 = -Infinity;
// 遍历所有矩形
for (var i = 0; i < rectangles.length; i++) {
// 取出当前矩形的左下角和右上角坐标
var x1 = rectangles[i][0];
var y1 = rectangles[i][1];
var x2 = rectangles[i][2];
var y2 = rectangles[i][3];
// 取小矩形左下角顶点的最小值
X1 = Math.min(X1, x1);
Y1 = Math.min(Y1, y1);
// 取小矩形右上角顶点的最大值
X2 = Math.max(X2, x2);
Y2 = Math.max(Y2, y2);
}
这样就能求出完美矩形的左下角顶点坐标 (X1, Y1) 和右上角顶点的坐标 (X2, Y2) 了。
计算出的 X1,Y1,X2,Y2 坐标是完美矩形的「理论坐标」，如果所有小矩形的面积之和不等于这个完美矩形的理论面积，那么说明最终形成的图形肯定存在空缺或者重叠，肯定不是完美矩形。
代码可以进一步：
// 注意：java 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
public boolean isRectangleCover(int[][] rectangles) {
int X1 = Integer.MAX_VALUE, Y1 = Integer.MAX_VALUE;
int X2 = Integer.MIN_VALUE, Y2 = Integer.MIN_VALUE;
// 记录所有小矩形的面积之和
int actual_area = 0;
for (int[] rectangle : rectangles) {
int x1 = rectangle[0], y1 = rectangle[1], x2 = rectangle[2], y2 = rectangle[3];
// 计算完美矩形的理论坐标
X1 = Math.min(X1, x1);
Y1 = Math.min(Y1, y1);
X2 = Math.max(X2, x2);
Y2 = Math.max(Y2, y2);
// 累加所有小矩形的面积
actual_area += (x2 - x1) * (y2 - y1);
}
// 计算完美矩形的理论面积
int expected_area = (X2 - X1) * (Y2 - Y1);
// 面积应该相同
return actual_area == expected_area;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
// 判断是否为完美矩形
bool isRectangleCover(vector<vector<int>>& rectangles) {
// 初始化完美矩形的理论坐标，X1, Y1 分别为正无穷，X2, Y2 分别为负无穷
int X1 = INT_MAX, Y1 = INT_MAX;
int X2 = INT_MIN, Y2 = INT_MIN;
int actual_area = 0; // 记录所有小矩形的面积之和
// 遍历所有小矩形
for (auto& rectangle : rectangles) {
int x1 = rectangle[0], y1 = rectangle[1];
int x2 = rectangle[2], y2 = rectangle[3];
// 计算完美矩形的理论坐标
X1 = min(X1, x1);
Y1 = min(Y1, y1);
X2 = max(X2, x2);
Y2 = max(Y2, y2);
// 累加所有小矩形的面积
actual_area += (x2 - x1) * (y2 - y1);
}
// 计算完美矩形的理论面积
int expected_area = (X2 - X1) * (Y2 - Y1);
// 面积应该相同
if (actual_area != expected_area) {
return false; // 如果面积不相同，返回 false
}
return true; // 否则返回 true
}
def isRectangleCover(rectangles: List[List[int]]) -> bool:
X1, Y1 = float('inf'), float('inf')
X2, Y2 = -float('inf'), -float('inf')
# 记录所有小矩形的面积之和
actual_area = 0
for x1, y1, x2, y2 in rectangles:
# 计算完美矩形的理论坐标
X1, Y1 = min(X1, x1), min(Y1, y1)
X2, Y2 = max(X2, x2), max(Y2, y2)
# 累加所有小矩形的面积
actual_area += (x2 - x1) * (y2 - y1)
# 计算完美矩形的理论面积
expected_area = (X2 - X1) * (Y2 - Y1)
# 面积应该相同
if actual_area != expected_area:
return False
return True
// 注意：go 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
func isRectangleCover(rectangles [][]int) bool {
// 初始化完美矩形的理论坐标
X1, Y1 := math.MaxInt64, math.MaxInt64
X2, Y2 := math.MinInt64, math.MinInt64
// 记录所有小矩形的面积之和
actualArea := 0
for _, rectangle := range rectangles {
x1, y1, x2, y2 := rectangle[0], rectangle[1], rectangle[2], rectangle[3]
// 计算完美矩形的理论坐标
X1, Y1 = min(X1, x1), min(Y1, y1)
X2, Y2 = max(X2, x2), max(Y2, y2)
// 累加所有小矩形的面积
actualArea += (x2 - x1) * (y2 - y1)
}
// 计算完美矩形的理论面积
expectedArea := (X2 - X1) * (Y2 - Y1)
// 面积应该相同
if actualArea != expectedArea {
return false
}
return true
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
/**
* @param {number[][]} rectangles
* @return {boolean}
*/
function isRectangleCover(rectangles) {
var X1 = Infinity,
Y1 = Infinity;
var X2 = -Infinity,
Y2 = -Infinity;
var actual_area = 0;
// 遍历所有矩形并记录必要信息
for (var i = 0; i < rectangles.length; i++) {
var rect = rectangles[i];
var x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
// 计算完美矩形的理论坐标
X1 = Math.min(X1, x1);
Y1 = Math.min(Y1, y1);
X2 = Math.max(X2, x2);
Y2 = Math.max(Y2, y2);
// 累加所有小矩形的面积
actual_area += (x2 - x1) * (y2 - y1);
}
// 计算完美矩形的理论面积
var expected_area = (X2 - X1) * (Y2 - Y1);
// 面积应该相同
if(actual_area != expected_area){
return false;
}
return true;
}
这样，「面积」这个维度就完成了，思路其实不难，无非就是假设最终形成的图形是个完美矩形，然后比较面积是否相等，如果不相等的话说明最终形成的图形一定存在空缺或者重叠部分，不是完美矩形。
但是反过来说，如果面积相同，是否可以证明最终形成的图形是完美矩形，一定不存在空缺或者重叠？
肯定是不行的，举个很简单的例子，你假想一个完美矩形，然后我在它中间挖掉一个小矩形，把这个小矩形向下平移一个单位。这样小矩形的面积之和没变，但是原来的完美矩形中就空缺了一部分，也重叠了一部分，已经不是完美矩形了。
综上，即便面积相同，并不能完全保证不存在空缺或者重叠，所以我们需要从「顶点」的维度来辅助判断。
记得小学的时候有一道智力题，给你一个矩形，切一刀，剩下的图形有几个顶点？答案是，如果沿着对角线切，就剩 3 个顶点；如果横着或者竖着切，剩 4 个顶点；如果只切掉一个小角，那么会出现 5 个顶点。
回到这道题，我们接下来的分析也有那么一点智力题的味道。
显然，完美矩形一定只有四个顶点。矩形嘛，按理说应该有四个顶点，如果存在空缺或者重叠的话，肯定不是四个顶点，比如说题目的这两个例子就有不止 4 个顶点：
我也不知道应该用「顶点」还是「角」来形容，好像都不太准确，本文统一用「顶点」来形容，大家理解就好~
rectangles 中的小矩形最终形成的图形有几个顶点，就能判断最终的图形是不是一个完美矩形了。
那么顶点是如何形成的呢？我们倒是一眼就可以看出来顶点在哪里，问题是如何让计算机，让算法知道某一个点是不是顶点呢？这也是本题的难点所在。
看下图的四种情况：
图中画红点的地方，什么时候是顶点，什么时候不是顶点？显然，情况一和情况三的时候是顶点，而情况二和情况四的时候不是顶点。
也就是说，当某一个点同时是 2 个或者 4 个小矩形的顶点时，该点最终不是顶点；当某一个点同时是 1 个或者 3 个小矩形的顶点时，该点最终是一个顶点。
注意，2 和 4 都是偶数，1 和 3 都是奇数，我们想计算最终形成的图形中有几个顶点，也就是要筛选出那些出现了奇数次的顶点，可以这样写代码：
// 注意：java 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
/**
* 计算小矩形是否能拼成完美矩形
* @param rectangles 小矩形
* @return boolean
*/
public boolean isRectangleCover(int[][] rectangles) {
// 定义完美矩形的左下角和右上角的坐标
int X1 = Integer.MAX_VALUE, Y1 = Integer.MAX_VALUE;
int X2 = Integer.MIN_VALUE, Y2 = Integer.MIN_VALUE;
// 定义小矩形的面积之和
int actual_area = 0;
// 定义哈希集合，记录最终图形的顶点坐标
Set<String> points = new HashSet<>();
for (int[] rectangle: rectangles) {
int x1 = rectangle[0], y1 = rectangle[1], x2 = rectangle[2], y2 = rectangle[3];
// 更新完美矩形的左下角和右上角的坐标
X1 = Math.min(X1, x1);
Y1 = Math.min(Y1, y1);
X2 = Math.max(X2, x2);
Y2 = Math.max(Y2, y2);
// 计算小矩形的面积并加入到面积之和中
actual_area += (x2 - x1) * (y2 - y1);
// 计算小矩形的每个点的坐标
String p1 = x1 + "," + y1, // 左下角坐标
p2 = x1 + "," + y2, // 左上角坐标
p3 = x2 + "," + y1, // 右下角坐标
p4 = x2 + "," + y2; // 右上角坐标
// 遍历小矩形的每个点，如果存在在集合中，就删除；
// 如果不存在在集合中，就添加；
// 在集合中剩下的点都是出现奇数次的点
for (String p: Arrays.asList(p1, p2, p3, p4)) {
if (points.contains(p)) points.remove(p);
else points.add(p);
}
}
// 计算理论上完美矩形的面积
int expected_area = (X2 - X1) * (Y2 - Y1);
if (actual_area != expected_area) return false; // 如果小矩形面积之和不等于完美矩形的面积，则不能拼成完美矩形
// 如果顶点数量不为4或者顶点中不包含完美矩形的四个角，则不能拼成完美矩形
if (points.size() != 4 || !points.contains(X1 + "," + Y1) || !points.contains(X1 + "," + Y2) || !points.contains(X2 + "," + Y1) || !points.contains(X2 + "," + Y2)) return false;
return true;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
// 给定一个矩形列表，判断这些矩形是否合法（不重叠，且其总面积恰好等于他们覆盖的面积和），并返回结果。
bool isRectangleCover(vector<vector<int>>& rectangles) {
int X1 = INT_MAX, Y1 = INT_MAX;
int X2 = INT_MIN, Y2 = INT_MIN;
int actual_area = 0;
set<pair<int, int>> points;
for(auto& rec : rectangles) {
int x1 = rec[0], y1 = rec[1], x2 = rec[2], y2 = rec[3];
// 记录这些矩形中确定的大矩形四个角的坐标
X1 = min(X1, x1); Y1 = min(Y1, y1);
X2 = max(X2, x2); Y2 = max(Y2, y2);
// 计算这些矩形的面积和，并同时记录所有矩形小矩形子对象的四个顶点，以及确保小矩形顶点恰好被覆盖一次
actual_area += (x2 - x1) * (y2 - y1);
// 重组原小矩形的四个顶点的坐标
auto p1 = make_pair(x1, y1), p2 = make_pair(x1, y2);
auto p3 = make_pair(x2, y1), p4 = make_pair(x2, y2);
// 对于每个点，如果存在集合中，删除它；
// 如果不存在集合中，添加它；
// 在集合中剩下的点都是出现奇数次的点
for(auto p : {p1, p2, p3, p4}) {
if(points.count(p)) points.erase(p);
else points.insert(p);
}
}
// 计算最终连续的大矩形的面积
int expected_area = (X2 - X1) * (Y2 - Y1);
if(actual_area != expected_area) {
return false;
}
// 线面积为矩形的面积，四个顶点都必须存在且仅被计算出现奇数次
return points.size() == 4 &&
points.count(make_pair(X1, Y1)) &&
points.count(make_pair(X1, Y2)) &&
points.count(make_pair(X2, Y1)) &&
points.count(make_pair(X2, Y2));
}
def isRectangleCover(rectangles: List[List[int]]) -> bool:
X1, Y1 = float('inf'), float('inf')
X2, Y2 = -float('inf'), -float('inf')
actual_area = 0
# 哈希集合，记录最终图形的顶点
points = set()
for x1, y1, x2, y2 in rectangles:
X1, Y1 = min(X1, x1), min(Y1, y1)
X2, Y2 = max(X2, x2), max(Y2, y2)
actual_area += (x2 - x1) * (y2 - y1)
# 先算出小矩形每个点的坐标
p1, p2 = (x1, y1), (x1, y2)
p3, p4 = (x2, y1), (x2, y2)
# 对于每个点，如果存在集合中，删除它；
# 如果不存在集合中，添加它；
# 在集合中剩下的点都是出现奇数次的点
for p in [p1, p2, p3, p4]:
if p in points: points.remove(p)
else: points.add(p)
expected_area = (X2 - X1) * (Y2 - Y1)
if actual_area != expected_area:
return False
return True
// 注意：go 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
func isRectangleCover(rectangles [][]int) bool {
X1, Y1 := math.MaxInt64, math.MaxInt64
X2, Y2 := math.MinInt64, math.MinInt64
actualArea := 0
// 哈希集合，记录最终图形的顶点
points := make(map[[2]int]bool)
for _, rectangle := range rectangles {
x1, y1, x2, y2 := rectangle[0], rectangle[1], rectangle[2], rectangle[3]
X1, Y1 = min(X1, x1), min(Y1, y1)
X2, Y2 = max(X2, x2), max(Y2, y2)
actualArea += (x2 - x1) * (y2 - y1)
// 先算出小矩形每个点的坐标
p1, p2 := [2]int{x1, y1}, [2]int{x1, y2}
p3, p4 := [2]int{x2, y1}, [2]int{x2, y2}
// 对于每个点，如果存在集合中，删除它；
// 如果不存在集合中，添加它；
// 在集合中剩下的点都是出现奇数次的点
for _, p := range []([2]int){p1, p2, p3, p4} {
if _, ok := points[p]; ok {
delete(points, p)
} else {
points[p] = true
}
}
}
expectedArea := (X2 - X1) * (Y2 - Y1)
if actualArea != expectedArea {
return false
}
return len(points) == 4 &&
points[[2]int{X1, Y1}] &&
points[[2]int{X1, Y2}] &&
points[[2]int{X2, Y1}] &&
points[[2]int{X2, Y2}]
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
// 使用 var 关键字声明函数
var isRectangleCover = function(rectangles) {
// 初始化顶点边界，由于是矩形，X1 和 Y1 取最大值，X2 和 Y2 取最小值，这样才是最终的矩形边界
let X1 = Infinity, Y1 = Infinity;
let X2 = -Infinity, Y2 = -Infinity;
// 实际面积，遍历每个矩形时累加每个矩形的面积
let actual_area = 0;
// 哈希集合，记录最终图形的所有点坐标
const points = new Set();
for (const [x1, y1, x2, y2] of rectangles) {
// 更新顶点边界
X1 = Math.min(X1, x1);
Y1 = Math.min(Y1, y1);
X2 = Math.max(X2, x2);
Y2 = Math.max(Y2, y2);
// 累加实际面积
actual_area += (x2 - x1) * (y2 - y1);
// 将矩形每个顶点坐标通过数组存储
const p1 = [x1, y1], p2 = [x1, y2], p3 = [x2, y1], p4 = [x2, y2];
// 对每个顶点进行判断，如果是已确认的点，则剔除；否则加入
for (const p of [p1, p2, p3, p4]) {
if (points.has(p)) {
points.delete(p);
} else {
points.add(p);
}
}
}
// 期望面积，即边界宽度和高度的乘积
const expected_area = (X2 - X1) * (Y2 - Y1);
// 如果实际面积与期望面积不等，则不符合条件
if (actual_area !== expected_area) return false;
return true;
};
这段代码中，我们用一个 points 集合记录 rectangles 中小矩形组成的最终图形的顶点坐标，关键逻辑在于如何向 points 中添加坐标：
如果某一个顶点 p 存在于集合 points 中，则将它删除；如果不存在于集合 points 中，则将它插入。
这个简单的逻辑，让 points 集合最终只会留下那些出现了 1 次或者 3 次的顶点，那些出现了 2 次或者 4 次的顶点都被消掉了。
那么首先想到，points 集合中最后应该只有 4 个顶点对吧，如果 len(points) != 4 说明最终构成的图形肯定不是完美矩形。
但是如果 len(points) == 4 是否能说明最终构成的图形肯定是完美矩形呢？也不行，因为题目并没有说 rectangles 中的小矩形不存在重复，比如下面这种情况：
下面两个矩形重复了，按照我们的算法逻辑，它们的顶点都被消掉了，最终是剩下了四个顶点；再看面积，完美矩形的理论坐标是图中红色的点，计算出的理论面积和实际面积也相同。但是显然这种情况不是题目要求完美矩形。
所以不仅要保证 len(points) == 4，而且要保证 points 中最终剩下的点坐标就是完美矩形的四个理论坐标，直接看代码吧：
// 注意：java 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
public boolean isRectangleCover(int[][] rectangles) {
int X1 = Integer.MAX_VALUE, Y1 = Integer.MAX_VALUE;
int X2 = Integer.MIN_VALUE, Y2 = Integer.MIN_VALUE;
HashSet<String> points = new HashSet<>();
int actual_area = 0;
for (int[] rectangle : rectangles) {
// 计算完美矩形的理论顶点坐标
X1 = Math.min(X1, rectangle[0]);
Y1 = Math.min(Y1, rectangle[1]);
X2 = Math.max(X2, rectangle[2]);
Y2 = Math.max(Y2, rectangle[3]);
// 累加小矩形的面积
actual_area += (rectangle[2] - rectangle[0]) * (rectangle[3] - rectangle[1]);
// 记录最终形成的图形中的顶点
String p1 = rectangle[0] + "," + rectangle[1];
String p2 = rectangle[0] + "," + rectangle[3];
String p3 = rectangle[2] + "," + rectangle[1];
String p4 = rectangle[2] + "," + rectangle[3];
for (String p : new String[]{p1, p2, p3, p4}) {
if (points.contains(p)) {
points.remove(p);
} else {
points.add(p);
}
}
}
// 判断面积是否相同
int expected_area = (X2 - X1) * (Y2 - Y1);
if (actual_area != expected_area) {
return false;
}
// 判断最终留下的顶点个数是否为 4
if (points.size() != 4) {
return false;
}
// 判断留下的 4 个顶点是否是完美矩形的顶点
String[] ps = new String[]{X1 + "," + Y1, X1 + "," + Y2, X2 + "," + Y1, X2 + "," + Y2};
for (String p : ps) {
if (!points.contains(p)) {
return false;
}
}
// 面积和顶点都对应，说明矩形符合题意
return true;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
bool isRectangleCover(vector<vector<int>>& rectangles) {
int X1 = INT_MAX, Y1 = INT_MAX;
int X2 = INT_MIN, Y2 = INT_MIN;
set<pair<int, int>> points;
int actual_area = 0;
for (auto& r : rectangles) {
int x1 = r[0], y1 = r[1], x2 = r[2], y2 = r[3];
// 计算完美矩形的理论顶点坐标
X1 = min(X1, x1);
Y1 = min(Y1, y1);
X2 = max(X2, x2);
Y2 = max(Y2, y2);
// 累加小矩形的面积
actual_area += (x2 - x1) * (y2 - y1);
// 记录最终形成的图形中的顶点
pair<int, int> p1(x1, y1), p2(x1, y2);
pair<int, int> p3(x2, y1), p4(x2, y2);
for (auto p : {p1, p2, p3, p4}) {
if (points.count(p)) {
points.erase(p);
} else {
points.insert(p);
}
}
}
// 判断面积是否相同
int expected_area = (X2 - X1) * (Y2 - Y1);
if (actual_area != expected_area) {
return false;
}
// 判断最终留下的顶点个数是否为 4
if (points.size() != 4) {
return false;
}
// 判断留下的 4 个顶点是否是完美矩形的顶点
if (!points.count(make_pair(X1, Y1))) {
return false;
}
if (!points.count(make_pair(X1, Y2))) {
return false;
}
if (!points.count(make_pair(X2, Y1))) {
return false;
}
if (!points.count(make_pair(X2, Y2))) {
return false;
}
// 面积和顶点都对应，说明矩形符合题意
return true;
}
def isRectangleCover(rectangles: List[List[int]]) -> bool:
X1, Y1 = float('inf'), float('inf')
X2, Y2 = -float('inf'), -float('inf')
points = set()
actual_area = 0
for x1, y1, x2, y2 in rectangles:
# 计算完美矩形的理论顶点坐标
X1, Y1 = min(X1, x1), min(Y1, y1)
X2, Y2 = max(X2, x2), max(Y2, y2)
# 累加小矩形的面积
actual_area += (x2 - x1) * (y2 - y1)
# 记录最终形成的图形中的顶点
p1, p2 = (x1, y1), (x1, y2)
p3, p4 = (x2, y1), (x2, y2)
for p in [p1, p2, p3, p4]:
if p in points: points.remove(p)
else: points.add(p)
# 判断面积是否相同
expected_area = (X2 - X1) * (Y2 - Y1)
if actual_area != expected_area:
return False
# 判断最终留下的顶点个数是否为 4
if len(points) != 4: return False
# 判断留下的 4 个顶点是否是完美矩形的顶点
if (X1, Y1) not in points: return False
if (X1, Y2) not in points: return False
if (X2, Y1) not in points: return False
if (X2, Y2) not in points: return False
# 面积和顶点都对应，说明矩形符合题意
return True
// 注意：go 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
func isRectangleCover(rectangles [][]int) bool {
var (
X1, Y1 int = math.MaxInt32, math.MaxInt32
X2, Y2 int = -math.MaxInt32, -math.MaxInt32
points = make(map[[2]int]bool)
actualArea int
)
for _, rect := range rectangles {
x1, y1, x2, y2 := rect[0], rect[1], rect[2], rect[3]
// 统计最大完美矩形的理论顶点坐标
X1, Y1 = min(X1, x1), min(Y1, y1)
X2, Y2 = max(X2, x2), max(Y2, y2)
// 累加每个小矩形的面积，并记录最终形成的图形中的顶点
actualArea += (x2 - x1) * (y2 - y1)
p1, p2 := [2]int{x1, y1}, [2]int{x1, y2}
p3, p4 := [2]int{x2, y1}, [2]int{x2, y2}
for _, p := range [...] [2]int{p1, p2, p3, p4} {
if _, ok := points[p]; ok {
delete(points, p)
} else {
points[p] = true
}
}
}
// 判断面积是否相同
expectedArea := (X2 - X1) * (Y2 - Y1)
if actualArea != expectedArea {
return false
}
// 判断最终留下的顶点个数是否为 4
if len(points) != 4 {
return false
}
// 判断留下的 4 个顶点是否是完美矩形的顶点
// 使用 delete() 和 map 类型，可以方便进行 lookup 操作
// 而 [] 是无法直接进行 lookup 操作的
if _, ok := points[[2]int{X1, Y1}]; !ok {
return false
}
if _, ok := points[[2]int{X1, Y2}]; !ok {
return false
}
if _, ok := points[[2]int{X2, Y1}]; !ok {
return false
}
if _, ok := points[[2]int{X2, Y2}]; !ok {
return false
}
// 面积和顶点都对应，说明矩形符合题意
return true
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 python 代码对比查看。
function isRectangleCover(rectangles) {
let X1 = Infinity, Y1 = Infinity;
let X2 = -Infinity, Y2 = -Infinity;
const points = new Set();
let actual_area = 0;
for (let i = 0; i < rectangles.length; i++) {
const [x1, y1, x2, y2] = rectangles[i];
// 计算完美矩形的理论顶点坐标
X1 = Math.min(X1, x1);
Y1 = Math.min(Y1, y1);
X2 = Math.max(X2, x2);
Y2 = Math.max(Y2, y2);
// 累加小矩形的面积
actual_area += (x2 - x1) * (y2 - y1);
// 记录最终形成的图形中的顶点
const p1 = [x1, y1], p2 = [x1, y2];
const p3 = [x2, y1], p4 = [x2, y2];
for (const p of [p1, p2, p3, p4]) {
if (points.has(p)) { points.delete(p); }
else { points.add(p); }
}
}
// 判断面积是否相同
const expected_area = (X2 - X1) * (Y2 - Y1);
if (actual_area !== expected_area) { return false; }
// 判断最终留下的顶点个数是否为 4
if (points.size !== 4) { return false; }
// 判断留下的 4 个顶点是否是完美矩形的顶点
if (!points.has([X1, Y1])) { return false; }
if (!points.has([X1, Y2])) { return false; }
if (!points.has([X2, Y1])) { return false; }
if (!points.has([X2, Y2])) { return false; }
// 面积和顶点都对应，说明矩形符合题意
return true;
}
🍭 代码可视化动画 🍭
这就是最终的解法代码，从「面积」和「顶点」两个维度来判断：
1、判断面积，通过完美矩形的理论坐标计算出一个理论面积，然后和 rectangles 中小矩形的实际面积和做对比。
2、判断顶点，points 集合中应该只剩下 4 个顶点且剩下的顶点必须都是完美矩形的理论顶点。
＿＿＿＿＿＿＿＿＿＿＿＿＿
《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：
共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释