冷库建设网站,django网站开发实例,移动网站建设推荐,企业邮箱域名怎么写题目来源
850. 矩形面积 II - 力扣#xff08;LeetCode#xff09; 题目描述
给你一个轴对齐的二维数组 rectangles 。
对于 rectangle[i] [x1, y1, x2, y2]#xff0c;其中#xff08;x1#xff0c;y1#xff09;是矩形 i 左下角的坐标#xff0c; (xi1, yi1) 是该…题目来源
850. 矩形面积 II - 力扣LeetCode 题目描述
给你一个轴对齐的二维数组 rectangles 。
对于 rectangle[i] [x1, y1, x2, y2]其中x1y1是矩形 i 左下角的坐标 (xi1, yi1) 是该矩形 左下角 的坐标 (xi2, yi2) 是该矩形 右上角 的坐标。
计算平面中所有 rectangles 所覆盖的 总面积 。任何被两个或多个矩形覆盖的区域应只计算 一次 。
返回 总面积 。因为答案可能太大返回 10^9 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
解释答案是 1018 对 (109 7) 取模的结果 即 49 。提示
1 rectangles.length 200rectanges[i].length 40 xi1, yi1, xi2, yi2 10^9 题目解析
本题如果从 ”面“ 的角度去思考比如所有矩形的面积 - 矩形交集部分的面积 最终面积。 两个矩形的交集很容易求解比如下面图示 虽然矩形交集很容易求解但是想要求出所有交集则需要让每个矩形和剩余其他矩形尝试比较得出交集。同时求出交集矩形后这些交集矩形也是可能互相重叠的 。。。交集的交集矩形也是可能互相重叠的。。。这样是无穷无尽的求解。因此这个思路不可取。 本题如果从 ”线“ 的角度去思考如下图所示从假设有一条扫描线 x cx1 ≤ c ≤ x4从左向右扫描每扫描到一个位置则判断该位置是否有矩形覆盖如果有矩形覆盖比如
图1 ~ 图3 中扫描线只覆盖到了矩形[左下角(x1,y1),右上角(x2,y2)]因此矩形覆盖的高度为 ( y2 - y1)对应扫描线扫描出的矩形面积 (x3 - x1) * ( y2 - y1)图4 ~ 图5 中扫描线覆盖了两个矩形分别是 [左下角(x1,y1),右上角(x2,y2)] 和 [左下角(x3,y3),右上角(x4,y4)]因此矩形覆盖的高度区间也有两个 [y1, y2] 和 [y3, y4]而这两个区间又是具有重叠部分的因此我们可以转化为区间问题利用区间问题解法求解出所有区间的不重叠长度之和 height 。具体求解过程在下面。那么扫描线扫描出来的面积为 (x2 - x3) * h。
首先排序区间按照起始位置升序如果起始位置相同则按照结束位置降序然后遍历区间假设当前区间是 [start, end]上一个区间是 [last_start, last_end] 若 last_end end那么说明当前区间被上一个区间完全覆盖可以继续忽略当前区间因为当前区间的长度已经在上一个区间被统计过了 若 last_end end那么当前区间的非重叠部分为 [max(start, last_end), end]统计该部分长度height end - max(start, last_end)并更新last_end end最后我们就求出了区间组所有区间覆盖的不重叠长度了。 上面这种思路就是 ”扫描线算法“扫描线法可以将 面 的问题分解为 线 的问题将 矩形面交集问题 降解为 区间线交集问题。 C源码实现
#define MAX_N 200
#define MOD (1e9 7)int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }int cmp2(const void* a, const void* b) {int* A (int*)a;int* B (int*)b;return A[0] ! B[0] ? A[0] - B[0] : B[1] - A[1];
}int rectangleArea(int** rectangles, int rectanglesSize, int* rectanglesColSize) {// 统计所有矩形的左边边、右边边所在位置的x坐标int listX[MAX_N];int listX_size 0;for (int i 0; i rectanglesSize; i) {listX[listX_size] rectangles[i][0]; // 矩形左边边x坐标位置listX[listX_size] rectangles[i][2]; // 矩形右边边x坐标位置}// 所有x坐标升序每个x视为一条扫描线qsort(listX, listX_size, sizeof(int), cmp);// 记录所有矩形并集面积long ans 0;for (int i 1; i listX_size; i) {// 前一个扫描线x坐标int preX listX[i - 1];// 当前扫描线x坐标int curX listX[i];// 相邻两个扫描线的距离long width curX - preX;// 距离为0, 则跳过if (width 0)continue;// 将在[x1,x2]区间上的矩形片段垂直方向高度区间收集起来int lines[MAX_N][2];int lines_size 0;// 遍历每个矩形for (int j 0; j rectanglesSize; j) {// 矩形左上角坐标(x1,y1), 矩形右下角坐标(x2,y2)int x1 rectangles[j][0], y1 rectangles[j][1],x2 rectangles[j][2], y2 rectangles[j][3];// 如果矩形包含了 [x1, x2] 区间if (x1 preX curX x2) {// 那么该矩形在 水平方向区间[x1, x2] 对应的 垂直方向区间为 [y2, y1]lines[lines_size][0] y1;lines[lines_size][1] y2;lines_size;}}// 将处于水方向区间 [x1, x2] 的所有垂直方向区间排序按照起始位置升序, 如果起始位置相同, 则按照结束位置降序这样排序的目的是保证排序后前面的区间尽可能可以覆盖后面的区间qsort(lines, lines_size, sizeof(lines[0]), cmp2);// 记录lines多个区间求长度之和重叠部分只计算一次long height 0;int last_end -1;for (int j 0; j lines_size; j) {int start lines[j][0];int end lines[j][1];// 如果 last_end end, 则当前区间被上一个区间完全覆盖因此可以跳过// 如果 last_end endif (last_end end) {// 则当前区间的不重叠部分是 [max(start, last_end), end]height end - (int)fmax(start, last_end);// 更新last_endlast_end end;}}// 当前扫描线扫描到的面积为 width * heightans width * height;ans % (int)MOD;}return (int)ans;
} C源码实现
#define MOD (1E9 7)class Solution {
public:int rectangleArea(vectorvectorint rectangles) {// 统计所有矩形的左边边、右边边所在位置的x坐标vectorint listX;for (vectorint rect : rectangles) {listX.emplace_back(rect[0]); // 矩形左边边x坐标位置listX.emplace_back(rect[2]); // 矩形右边边x坐标位置}// 所有x坐标升序每个x视为一条扫描线sort(listX.begin(), listX.end());// 记录所有矩形并集面积long ans 0;for (int i 1; i listX.size(); i) {// 前一个扫描线x坐标int preX listX[i - 1];// 当前扫描线x坐标int curX listX[i];// 相邻两个扫描线的距离long width curX - preX;// 距离为0, 则跳过if (width 0)continue;// 将在[x1,x2]区间上的矩形片段垂直方向高度区间收集起来vectorvectorint lines;// 遍历每个矩形for (vectorint rect : rectangles) {// 矩形左下角坐标(x1,y1), 矩形右上角坐标(x2,y2)int x1 rect[0], y1 rect[1], x2 rect[2], y2 rect[3];// 如果矩形包含了 [x1, x2] 区间if (x1 preX curX x2) {// 那么该矩形在 水平方向区间[x1, x2] 对应的 垂直方向区间为 [y1, y2]lines.emplace_back(vectorint{y1, y2});}}// 将处于水方向区间 [x1, x2]// 的所有垂直方向区间排序按照起始位置升序, 如果起始位置相同,// 则按照结束位置降序这样排序的目的是保证排序后前面的区间尽可能可以覆盖后面的区间sort(lines.begin(), lines.end(),[](vectorint lineA, vectorint lineB) {if (lineA[0] ! lineB[0]) {return lineA[0] lineB[0];} else {return lineA[1] lineB[1];}});// 记录lines多个区间求长度之和重叠部分只计算一次long height 0;int last_end INT_MIN;for (vectorint line : lines) {int start line[0];int end line[1];// 如果 last_end end,// 则当前区间被上一个区间完全覆盖因此可以跳过 如果 last_end // endif (last_end end) {// 则当前区间的不重叠部分是 [max(start, last_end), end]height end - max(start, last_end);// 更新last_endlast_end end;}}// 当前扫描线扫描到的面积为 width * heightans width * height;ans % (int) MOD;}return (int) ans;}
}; Java源码实现
class Solution {public int rectangleArea(int[][] rectangles) {// 统计所有矩形的左边边、右边边所在位置的x坐标ArrayListInteger listX new ArrayList();for (int[] rect : rectangles) {listX.add(rect[0]);listX.add(rect[2]);}// 所有x坐标升序每个x视为一条扫描线listX.sort((a, b) - a - b);// 记录所有矩形并集面积long ans 0;for (int i 1; i listX.size(); i) {// 前一个扫描线x坐标int preX listX.get(i - 1);// 当前扫描线x坐标int curX listX.get(i);// 相邻两个扫描线的距离int width curX - preX;// 距离为0, 则跳过if (width 0)continue;// 将在[x1,x2]区间上的矩形片段垂直方向高度区间收集起来ArrayListint[] lines new ArrayList();// 遍历每个矩形for (int[] rect : rectangles) {// 矩形左下角坐标(x1,y1), 矩形右上角坐标(x2,y2)int x1 rect[0], y1 rect[1], x2 rect[2], y2 rect[3];// 如果矩形包含了 [x1, x2] 区间if (x1 preX curX x2) {// 那么该矩形在 水平方向区间[x1, x2] 对应的 垂直方向区间为 [y1, y2]lines.add(new int[] { y1, y2 });}}// 将处于水方向区间 [x1, x2] 的所有垂直方向区间排序按照起始位置升序, 如果起始位置相同,则按照结束位置降序// 这样排序的目的是保证排序后前面的区间尽可能可以覆盖后面的区间lines.sort((lineA, lineB) - lineA[0] ! lineB[0] ? lineA[0] - lineB[0] : lineB[1] - lineA[1]);// 记录lines多个区间求长度之和重叠部分只计算一次int height 0;int last_end -1;for (int[] line : lines) {int start line[0];int end line[1];// 如果 last_end end, 则当前区间被上一个区间完全覆盖因此可以跳过// 如果 last_end endif (last_end end) {// 则当前区间的不重叠部分是 [max(start, last_end), end]height end - Math.max(start, last_end);// 更新last_endlast_end end;}}// 当前扫描线扫描到的面积为 width * heightans (long) width * height;ans % (int) (1e9 7);}return (int) ans;}
} Python源码实现
class Solution(object):def rectangleArea(self, rectangles)::type rectangles: List[List[int]]:rtype: int# 统计所有矩形的左边边、右边边所在位置的x坐标listX []for rect in rectangles:listX.append(rect[0]) # 矩形左边边x坐标位置listX.append(rect[2]) # 矩形右边边x坐标位置# 所有x坐标升序每个x视为一条扫描线listX.sort()# 记录所有矩形并集面积ans 0for i in range(1, len(listX)):# 前一个扫描线x坐标preX listX[i - 1]# 当前扫描线x坐标curX listX[i]# 相邻两个扫描线的距离width curX - preX# 距离为0, 则跳过if width 0:continue# 将在[x1,x2]区间上的矩形片段垂直方向高度区间收集起来lines []# 遍历每个矩形# 矩形左下角坐标(x1,y1)矩形右上角坐标(x2,y2)for x1, y1, x2, y2 in rectangles:# 如果矩形包含了 [x1, x2] 区间if x1 preX and curX x2:# 那么该矩形在 水平方向区间[x1, x2] 对应的 垂直方向区间为 [y1, y2]lines.append((y1, y2))# 将处于水方向区间 [x1, x2] 的所有垂直方向区间排序按照起始位置升序, 如果起始位置相同, 则按照结束位置降序这样排序的目的是保证排序后前面的区间尽可能可以覆盖后面的区间lines.sort(keylambda line: (line[0], -line[1]))# 记录lines多个区间求长度之和重叠部分只计算一次height 0# 题目说坐标范围 [-100, 100], 因此对应 [?, -101] 的区间必然不会和任何区间相交last_end -1# 如果 last_end end, 则当前区间被上一个区间完全覆盖因此可以跳过# 如果 last_end endfor start, end in lines:if last_end end:# 则当前区间的不重叠部分是 [max(start, last_end), end]height end - max(start, last_end)# 更新last_endlast_end end# 当前扫描线扫描到的面积为 width * heightans width * heightreturn ans % 1000000007 JavaScript源码实现
/*** param {number[][]} rectangles* return {number}*/
var rectangleArea function (rectangles) {// 统计所有矩形的左边边、右边边所在位置的x坐标const listX [];for (let rect of rectangles) {listX.push(rect[0]); // 矩形左边边x坐标位置listX.push(rect[2]); // 矩形右边边x坐标位置}// 所有x坐标升序每个x视为一条扫描线listX.sort((a, b) a - b);// 记录所有矩形并集面积let ans 0n;for (let i 1; i listX.length; i) {// 前一个扫描线x坐标const preX listX[i - 1];// 当前扫描线x坐标const curX listX[i];// 相邻两个扫描线的距离const width curX - preX;// 距离为0, 则跳过if (width 0) continue;// 将处于[x1,x2]区间上的矩形片段垂直方向高度区间收集起来const lines [];// 遍历每个矩形// 矩形左下角坐标(x1,y1)矩形右上角坐标(x2,y2)for (let [x1, y1, x2, y2] of rectangles) {// 如果矩形有片段处于 [x1, x2] 区间if (x1 preX curX x2) {// 那么该矩形在 水平方向区间[x1, x2] 对应的 垂直方向区间为 [y1, y2]lines.push([y1, y2]);}}// 将处于水方向区间 [x1, x2] 的所有垂直方向区间排序按照起始位置升序, 如果起始位置相同, 则按照结束位置降序这样排序的目的是保证排序后前面的区间尽可能可以覆盖后面的区间lines.sort((lineA, lineB) lineA[0] ! lineB[0] ? lineA[0] - lineB[0] : lineB[1] - lineA[1]);// 记录lines多个区间求长度之和重叠部分只计算一次let height 0;let last_end -1;for (let [start, end] of lines) {// 如果 last_end end, 则当前区间被上一个区间完全覆盖因此可以跳过// 如果 last_end endif (last_end end) {// 则当前区间的不重叠部分是 [max(start, last_end), end]height end - Math.max(start, last_end);// 更新last_endlast_end end;}}// 当前扫描线扫描到的面积为 width * heightans BigInt(width) * BigInt(height);}return Number(ans % 1000000007n);
};
