資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的矩形面積 II
假設我們有一系列（軸對齊的）矩形。這裡每個矩形[i] = {x1, y1, x2, y2}，其中 (x1, y1) 是左下角的點，(x2, y2) 是第 i 個矩形的右上角的點。
我們必須找到平面上所有矩形覆蓋的總面積。答案可能非常大，所以我們可以使用模 10^9 + 7。
因此，如果輸入類似於
則輸出將為 6。
為了解決這個問題，我們將遵循以下步驟 -
m = 10^9 + 7
定義一個函式 add()，它將接收 a、b，
返回 ((a mod m) + (b mod m) mod m)
定義一個函式 compress，它將接收二維矩陣 v
定義一個數組 temp
對於初始化 i := 0，當 i < v 的大小，更新（i 增加 1），執行 -
將 v[i, 0] 插入到 temp 的末尾
將 v[i, 2] 插入到 temp 的末尾
對陣列 temp 進行排序
定義一個對映 ret
idx := 0
對於初始化 i := 0，當 i < temp 的大小，更新（i 增加 1），執行
如果 temp[i] 不是 ret 的成員，則 -
ret[temp[i]] := idx
（idx 增加 1）
返回 ret
從主方法執行以下操作 -
定義一個數組 xv
將 { 0 } 插入到 xv 的末尾
對於初始化 i := 0，當 i < v 的大小，更新（i 增加 1），執行 -
將 v[i, 0] 插入到 xv 的末尾
將 v[i, 2] 插入到 xv 的末尾
對陣列 xv 進行排序
uniItr = 包含 xv 的唯一元素的列表的第一個元素
從 xv 中刪除 uniItr
定義一個對映 index
idx := 0
對於初始化 i := 0，當 i < xv 的大小，更新（i 增加 1），執行 -
index[xv[i]] := i
定義一個大小與 index 大小相同的陣列 count
定義一個二維陣列 x
對於初始化 i := 0，當 i < v 的大小，更新（i 增加 1），執行 -
x1 := v[i, 0], y1 := v[i, 1]
x2 := v[i, 2], y2 := v[i, 3]
將 { y1, x1, x2, 1 } 插入到 x 的末尾
將 { y2, x1, x2, -1 } 插入到 x 的末尾
對陣列 x 進行排序
ret := 0
sum := 0, currentY := 0
對於初始化 i := 0，當 i < x 的大小，更新（i 增加 1），執行 -
y := x[i, 0]
x1 := x[i, 1], x2 := x[i, 2]
sig := x[i, 3]
ret := add(ret, (y - currentY) * sum)
currentY := y
對於初始化 i := index[x1]，當 i < index[x2]，更新（i 增加 1），執行 -
count[i] := count[i] + sig
sum := 0
對於初始化 i := 0，當 i < count 的大小，更新（i 增加 1），執行 -
如果 count[i] > 0，則
sum := sum + (xv[i + 1] - xv[i])
返回 ret mod m
讓我們看看以下實現以更好地理解 -
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return ((a % m) + (b % m) % m);
}
map<int, int> compress(vector<vector<int> >& v){
vector<int> temp;
for (int i = 0; i < v.size(); i++) {
temp.push_back(v[i][0]);
temp.push_back(v[i][2]);
}
sort(temp.begin(), temp.end());
map<int, int> ret;
int idx = 0;
for (int i = 0; i < temp.size(); i++) {
if (!ret.count(temp[i])) {
ret[temp[i]] = idx;
idx++;
}
}
return ret;
}
int rectangleArea(vector<vector<int> >& v){
vector<int> xv;
xv.push_back({ 0 });
for (int i = 0; i < v.size(); i++) {
xv.push_back(v[i][0]);
xv.push_back(v[i][2]);
}
sort(xv.begin(), xv.end());
vector<int>::iterator uniItr = unique(xv.begin(), xv.end());
xv.erase(uniItr, xv.end());
map<int, int> index;
int idx = 0;
for (int i = 0; i < xv.size(); i++) {
index[xv[i]] = i;
}
vector<int> count(index.size());
vector<vector<int> > x;
int x1, x2, y1, y2;
for (int i = 0; i < v.size(); i++) {
x1 = v[i][0];
y1 = v[i][1];
x2 = v[i][2];
y2 = v[i][3];
x.push_back({ y1, x1, x2, 1 });
x.push_back({ y2, x1, x2, -1 });
}
sort(x.begin(), x.end());
lli ret = 0;
lli sum = 0, currentY = 0;
for (int i = 0; i < x.size(); i++) {
lli y = x[i][0];
x1 = x[i][1];
x2 = x[i][2];
int sig = x[i][3];
ret = add(ret, (y - currentY) * sum);
currentY = y;
for (int i = index[x1]; i < index[x2]; i++) {
count[i] += sig;
}
sum = 0;
for (int i = 0; i < count.size(); i++) {
if (count[i] > 0) {
sum += (xv[i + 1] - xv[i]);
}
}
}
return ret % m;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,0,2,2},{1,0,2,3},{1,0,3,1}};
cout << (ob.rectangleArea(v));
}輸入
{{0,0,2,2},{1,0,2,3},{1,0,3,1}}輸出
6
344 次檢視
