数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的完美矩形
假设我们有 N 个轴对齐的矩形，我们需要检查它们是否共同形成了一个精确的矩形区域的覆盖。这里每个矩形都表示为左下角点和右上角点。因此，一个单位正方形表示为 [1,1,2,2]。（左下角点为 (1, 1)，右上角点为 (2, 2)）。
所以，如果输入像 rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]，那么输出将为 true，因为所有 5 个矩形共同形成了一个精确的矩形区域的覆盖。
为了解决这个问题，我们将遵循以下步骤：
定义一个集合 visited
area := 0
x2 := -inf, x1 := inf
y2 := -inf, y1 := inf
对于给定列表 re 中的每个 r：
x1 := r[0] 和 x1 的最小值
x2 := r[2] 和 x2 的最大值
y1 := r[1] 和 y1 的最小值
y2 := r[3] 和 y2 的最大值
area := area + ((r[2] - r[0]) * (r[3] - r[1]))
s1 := r[0] 连接 r[1]
s2 := r[0] 连接 r[3]
s3 := r[2] 连接 r[3]
s4 := r[2] 连接 r[1]
如果 s1 已被访问，则：
从 visited 中删除 s1
否则
将 s1 插入 visited
如果 s2 已被访问，则：
从 visited 中删除 s2
否则
将 s2 插入 visited
如果 s3 已被访问，则：
从 visited 中删除 s3
否则
将 s3 插入 visited
如果 s4 已被访问，则：
从 visited 中删除 s4
否则
将 s4 插入 visited
s1 := 连接 x1 和 y1
s2 := 连接 x2 和 y1
s3 := 连接 x1 和 y2
s4 := 连接 x2 和 y2
如果 s1、s2、s3、s4 均未被访问，则
返回 false
当 area 等于 ((x2 - x1) * (y2 - y1)) 时返回 true
示例
让我们看看以下实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isRectangleCover(vector<vector<int>> &re) {
unordered_set<string> visited;
int area = 0;
int x2 = INT_MIN;
int x1 = INT_MAX;
int y2 = INT_MIN;
int y1 = INT_MAX;
for (auto &r : re) {
x1 = min(r[0], x1);
x2 = max(r[2], x2);
y1 = min(r[1], y1);
y2 = max(r[3], y2);
area += (r[2] - r[0]) * (r[3] - r[1]);
string s1 = to_string(r[0]) + to_string(r[1]);
string s2 = to_string(r[0]) + to_string(r[3]);
string s3 = to_string(r[2]) + to_string(r[3]);
string s4 = to_string(r[2]) + to_string(r[1]);
if (visited.count(s1)) {
visited.erase(s1);
}
else
visited.insert(s1);
if (visited.count(s2)) {
visited.erase(s2);
}
else
visited.insert(s2);
if (visited.count(s3)) {
visited.erase(s3);
}
else
visited.insert(s3);
if (visited.count(s4)) {
visited.erase(s4);
}
else
visited.insert(s4);
}
string s1 = to_string(x1) + to_string(y1);
string s2 = to_string(x2) + to_string(y1);
string s3 = to_string(x1) + to_string(y2);
string s4 = to_string(x2) + to_string(y2);
if (!visited.count(s1) || !visited.count(s2) || !visited.count(s3) || !visited.count(s4) || visited.size() != 4)
return false;
return area == (x2 - x1) * (y2 - y1);
}
};
main() {
Solution ob;
vector<vector<int>> v = {{1, 1, 3, 3}, {3, 1, 4, 2}, {3, 2, 4, 4}, {1, 3, 2, 4}, {2, 3, 3, 4}};
cout << (ob.isRectangleCover(v));
}输入
{{1, 1, 3, 3}, {3, 1, 4, 2}, {3, 2, 4, 4}, {1, 3, 2, 4}, {2, 3, 3, 4}}输出
1
177 次查看
