【离散化二维差分】850. 矩形面积 II

本文涉及知识点

离散化二维差分

LeetCode850. 矩形面积 II

给你一个轴对齐的二维数组 rectangles 。对于 rectangle[i] = [x1, y1, x2, y2]，其中（x1，y1）是矩形 i 左下角的坐标， (xi1, yi1) 是该矩形左下角的坐标， (xi2, yi2) 是该矩形右上角的坐标。
计算平面中所有 rectangles 所覆盖的总面积。任何被两个或多个矩形覆盖的区域应只计算一次。
返回总面积。因为答案可能太大，返回 109 + 7 的模。

示例 1：
在这里插入图片描述

输入：rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
输出：6
解释：如图所示，三个矩形覆盖了总面积为 6 的区域。
从(1,1)到(2,2)，绿色矩形和红色矩形重叠。
从(1,0)到(2,3)，三个矩形都重叠。
示例 2：

输入：rectangles = [[0,0,1000000000,1000000000]]
输出：49
解释：答案是 10¹⁸ 对 (109 + 7) 取模的结果，即 49 。

提示：

1 <= rectangles.length <= 200
rectanges[i].length = 4
0 <= xi1, yi1, xi2, yi2 <= 10⁹

离散化、二维差分

注意：忽略xi1 等于 xi2或yi1等于yi2得。确保xi1<xi2和yi1<yi2。
一，利用vCodex将所有xi1,xi2编码。
二，vCodey将所有yi1,yi2编码。
三，利用二维差分记录那些点（编码）被覆盖。
令点x1,y1被覆盖则面积为(vCodex[x1+1]-vCodex[x1])*(vCodey[y1+1]-vCodey[y1])

代码

核心代码

template<int MOD = 1000000007>
class C1097Int
{
public:C1097Int(long long llData = 0) :m_iData(llData% MOD){}C1097Int  operator+(const C1097Int& o)const{return C1097Int(((long long)m_iData + o.m_iData) % MOD);}C1097Int& operator+=(const C1097Int& o){m_iData = ((long long)m_iData + o.m_iData) % MOD;return *this;}C1097Int& operator-=(const C1097Int& o){m_iData = (m_iData + MOD - o.m_iData) % MOD;return *this;}C1097Int  operator-(const C1097Int& o){return C1097Int((m_iData + MOD - o.m_iData) % MOD);}C1097Int  operator*(const C1097Int& o)const{return((long long)m_iData * o.m_iData) % MOD;}C1097Int& operator*=(const C1097Int& o){m_iData = ((long long)m_iData * o.m_iData) % MOD;return *this;}C1097Int  operator/(const C1097Int& o)const{return *this * o.PowNegative1();}C1097Int& operator/=(const C1097Int& o){*this /= o.PowNegative1();return *this;}bool operator==(const C1097Int& o)const{return m_iData == o.m_iData;}bool operator<(const C1097Int& o)const{return m_iData < o.m_iData;}C1097Int pow(long long n)const{C1097Int iRet = 1, iCur = *this;while (n){if (n & 1){iRet *= iCur;}iCur *= iCur;n >>= 1;}return iRet;}C1097Int PowNegative1()const{return pow(MOD - 2);}int ToInt()const{return m_iData;}
private:int m_iData = 0;;
};
class CDiscretize //离散化
{
public:CDiscretize(vector<int> nums){sort(nums.begin(), nums.end());nums.erase(std::unique(nums.begin(), nums.end()), nums.end());m_nums = nums;for (int i = 0; i < nums.size(); i++){m_mValueToIndex[nums[i]] = i;}}int operator[](const int value)const{auto it = m_mValueToIndex.find(value);if (m_mValueToIndex.end() == it){return -1;}return it->second;}int size()const{return m_mValueToIndex.size();}vector<int> m_nums;
protected:	unordered_map<int, int> m_mValueToIndex;
};template<class T = int >
class CDiff2
{
public:CDiff2(int r, int c):m_iR(r),m_iC(c) {m_vDiff.assign(m_iR, vector<T>(m_iC));}void Set(int r1, int c1, int r2Exinc, int c2Exinc,int iAdd) {m_vDiff[r1][c1] += iAdd;m_vDiff[r2Exinc][c2Exinc] += iAdd;m_vDiff[r1][c2Exinc] -= iAdd;m_vDiff[r2Exinc][c1] -= iAdd;}vector<vector<T>> Ans()const {vector<vector<T>> res(m_iR, vector<T>(m_iC));vector<T> vCols(m_iC);for (int r = 0; r < m_iR; r++) {T iSum = 0;for (int c = 0; c < m_iC; c++) {vCols[c] += m_vDiff[r][c];iSum += vCols[c];res[r][c] = iSum;}}return res;}const int m_iR, m_iC;
protected:vector<vector<T>> m_vDiff;
};
class Solution {
public:int rectangleArea(vector<vector<int>>& rectangles) {vector<vector<int>> tmp;vector<int> xs, ys;for (auto& v : rectangles) {if ((v[0] == v[2]) || (v[1] == v[3])) { continue; }if (v[0] > v[2]) { swap(v[0], v[2]); }if (v[1] > v[3]) { swap(v[1], v[3]); }tmp.emplace_back(v);xs.emplace_back(v[0]);xs.emplace_back(v[2]);ys.emplace_back(v[1]);ys.emplace_back(v[3]);}CDiscretize xCode(xs), yCode(ys);CDiff2<> diff(xCode.size() + 1, yCode.size() + 1);for (const auto& v : tmp) {diff.Set(xCode[v[0]], yCode[v[1]],xCode[v[2]], yCode[v[3]],1);}auto res = diff.Ans();C1097Int<> biRet;for (int r = 0; r+1 < diff.m_iR; r++) {			for (int c = 0; c+1 < diff.m_iC; c++) {				if (res[r][c] > 0) {C1097Int<> cur = ((long long)xCode.m_nums[r + 1] - xCode.m_nums[r]) * (yCode.m_nums[c + 1] - yCode.m_nums[c]);biRet += cur;}}}return biRet.ToInt();}
};

单元测试

template<class T1,class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1 , t2);
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size());	for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{vector<vector<int>> rectangles;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod0){rectangles = { {0,0,2,2},{1,0,2,3},{1,0,3,1} };auto res = Solution().rectangleArea(rectangles);AssertEx( 6, res);}TEST_METHOD(TestMethod1){rectangles = { {0,0,1000000000,1000000000} };auto res = Solution().rectangleArea(rectangles);AssertEx(49, res);}TEST_METHOD(TestMethod2){rectangles = { {93516, 44895, 94753, 69358}, { 13141,52454,59740,71232 }, { 22877,11159,85255,61703 }, { 11917,8218,84490,36637 }, { 75914,29447,83941,64384 }, { 22490,71433,64258,74059 }, { 18433,51177,87595,98688 }, { 70854,80720,91838,92304 }, { 46522,49839,48550,94096 }, { 95435,37993,99139,49382 }, { 10618,696,33239,45957 }, { 18854,2818,57522,78807 }, { 61229,36593,76550,41271 }, { 99381,90692,99820,95125 } };auto res = Solution().rectangleArea(rectangles);AssertEx(971243962, res);}};
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛