LeetCode - 850 矩形面积 II

题目来源

850. 矩形面积 II - 力扣(LeetCode)

 

题目描述

给你一个轴对齐的二维数组 rectangles 。

对于 rectangle[i] = [x1, y1, x2, y2],其中(x1,y1)是矩形 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 <= 200
  • rectanges[i].length = 4
  • 0 <= xi1, yi1, xi2, yi2 <= 10^9

题目解析

本题如果从 ”面“ 的角度去思考,比如:所有矩形的面积 - 矩形交集部分的面积 = 最终面积。

两个矩形的交集很容易求解,比如下面图示

虽然矩形交集很容易求解,但是想要求出所有交集,则需要让每个矩形和剩余其他矩形尝试比较,得出交集。同时求出交集矩形后,这些交集矩形也是可能互相重叠的 。。。交集的交集矩形也是可能互相重叠的。。。这样是无穷无尽的求解。因此这个思路不可取。

本题如果从 ”线“ 的角度去思考,如下图所示,从假设有一条扫描线 x = c(x1 ≤ 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。
  1. 首先,排序区间,按照起始位置升序,如果起始位置相同,则按照结束位置降序
  2. 然后,遍历区间,假设当前区间是 [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
  3. 最后,我们就求出了区间组所有区间覆盖的不重叠长度了。

上面这种思路就是 ”扫描线算法“,扫描线法可以将 "面" 的问题,分解为 "线" 的问题,将 "矩形(面)交集问题" 降解为 "区间(线)交集问题"。

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(vector<vector<int>>& rectangles) {// 统计所有矩形的左边边、右边边所在位置的x坐标vector<int> listX;for (vector<int>& 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]区间上的矩形片段(垂直方向高度区间)收集起来vector<vector<int>> lines;// 遍历每个矩形for (vector<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.emplace_back(vector<int>{y1, y2});}}// 将处于水方向区间 [x1, x2]// 的所有垂直方向区间排序:按照起始位置升序, 如果起始位置相同,// 则按照结束位置降序,这样排序的目的是保证排序后,前面的区间尽可能可以覆盖后面的区间sort(lines.begin(), lines.end(),[](vector<int>& lineA, vector<int>& 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 (vector<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 - 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坐标ArrayList<Integer> 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]区间上的矩形片段(垂直方向高度区间)收集起来ArrayList<int[]> 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(key=lambda 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);
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1547432.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

通信工程学习:什么是VIM虚拟化基础设施管理器

VIM:虚拟化基础设施管理器 VIM(Virtualized Infrastructure Manager)虚拟化基础设施管理器,是一种负责管理和控制虚拟化环境中所有虚拟资源的工具和系统。以下是关于VIM虚拟化基础设施管理器的详细解释: 一、定义与功能 VIM是网络功能虚拟化(NFV)架构中…

李宏毅机器学习2023-HW10-Adversarial Attack

文章目录 TaskBaselineFGSM (Fast Gradient Sign Method (FGSM)I-FGSM(Iterative Fast Gradient Sign Method)MI-FGSM(Momentum Iterative Fast Gradient Sign Method)M-DI2-FGSM(Diverse Input Momentum Iterative Fast Gradient Sign Method) Reportfgsm attackJepg Compress…

探索5 大 Node.js 功能

目录 单线程 Node.js 工作线程【Worker Threads】 Node.js 进程 进程缺点 工作线程 注意 集群进程模块【Cluster Process Module】 内部发生了什么&#xff1f; 为什么要使用集群 注意&#xff1a; 应用场景&#xff1a; 内置 HTTP/2 支持 这个 HTTP/2 是什么&…

Windows安装Vim,并在PowerShell中直接使用vim

大家好啊&#xff0c;我是豆小匠。 这期介绍下怎么在windows的PowerShell上使用vim&#xff0c;方便在命令行里修改配置文件等。 先上效果图&#xff1a; 1、下载Vim GitHub传送门&#xff1a;https://github.com/vim/vim-win32-installer/releases 选择win-64的版本下载即可&…

VS Code使用Git Bash终端

Git Bash可以运行linux命令&#xff0c;在VS Code的终端界面&#xff0c;找到号旁边的箭头&#xff0c;就能直接切换了 当然&#xff0c;前提是安装了Git Bash&#xff0c;并且在资源管理器里&#xff0c;能鼠标右键出"Git Bash Here"

node.js从入门到快速开发一个简易的web服务器

浏览器中JavaScript学习路径: JavaScript基础语法浏览器内置API(DOMBOM)第三方库(jQuery,art-template等) Node.js的学习路径 JavaScript基础语法Node.js内置API模块(fs、path、http等)第三方API模块(express、mysql等) Node.js安装 通过Node.js 来运行Javascript 代码&am…

[已解决]npm install报错

问题分析&#xff1a; 想执行文件夹下的npm install&#xff0c;通过以及cmd进入&#xff0c;都会报错权限不够 如下报错&#xff08;哪一张不清楚&#xff0c;只知道是权限不够导致的&#xff09; 问题解决&#xff1a; 搜索Windows powershell 然后用管理员权限启动&#x…

【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器

文章目录 C list 容器详解&#xff1a;从入门到精通前言第一章&#xff1a;C list 容器简介1.1 C STL 容器概述1.2 list 的特点 第二章&#xff1a;list 的构造方法2.1 常见构造函数2.1.1 示例&#xff1a;不同构造方法2.1.2 相关文档 第三章&#xff1a;list 迭代器的使用3.1 …

基于skopt的贝叶斯优化基础实例学习实践

贝叶斯方法是非常基础且重要的方法&#xff0c;在前文中断断续续也有所介绍&#xff0c;感兴趣的话可以自行移步阅读即可&#xff1a; 《数学之美番外篇&#xff1a;平凡而又神奇的贝叶斯方法》 《贝叶斯深度学习——基于PyMC3的变分推理》 《模型优化调参利器贝叶斯优化bay…

使用API有效率地管理Dynadot域名,设置域名服务器(NS)

前言 Dynadot是通过ICANN认证的域名注册商&#xff0c;自2002年成立以来&#xff0c;服务于全球108个国家和地区的客户&#xff0c;为数以万计的客户提供简洁&#xff0c;优惠&#xff0c;安全的域名注册以及管理服务。 Dynadot平台操作教程索引&#xff08;包括域名邮箱&…

Type-C接口相关知识:【总结大全】

Type-c现在非常通用了&#xff0c;所以了解Type-c也变得十分有必要了&#xff0c;还是秉承了解就要了解清楚的原则&#xff0c;我们深入的看看Type-c接口。 Type-c主要是取代上一代Micro usb接口&#xff0c;那么Type-c有什么优点呢&#xff1f; 正反可插&#xff0c;使用时不…

电脑usb接口封禁如何实现?5种禁用USB接口的方法分享!(第一种你GET了吗?)

“防患于未然&#xff0c;安全始于细节。”在信息技术飞速发展的今天&#xff0c;企业的信息安全问题日益凸显。 USB接口作为数据传输的重要通道&#xff0c;在带来便利的同时&#xff0c;也成为了数据泄露和安全风险的高发地。 因此&#xff0c;对电脑USB接口进行封闭管理&a…

植物大战僵尸杂交版V2.5.1下载(最新版)

2.5.1版本更新公告&#xff1a; 在最新的2.5.1版本中&#xff0c;游戏对“两面夹击”关卡进行了多项重要调整。出怪倍率和种类均有所降低&#xff0c;部分关卡的初始阳光量也得到了调整&#xff0c;以增强玩家的策略性。同时&#xff0c;玩家可以在这些关卡中使用投手类植物&a…

视频集成与融合项目中需要视频编码,但是分辨率不兼容怎么办?

在众多视频整合项目中&#xff0c;一个显著的趋势是融合多元化的视频资源&#xff0c;以实现统一监管与灵活调度。这一需求促使项目团队不断探索新的集成方案&#xff0c;确保不同来源的视频流能够无缝对接&#xff0c;共同服务于统一的调看与管理平台&#xff0c;进而提升整体…

基于SSM+小程序的英语学习交流平台管理系统(学习3)(源码+sql脚本+视频导入教程+文档)

&#x1f449;文末查看项目功能视频演示获取源码sql脚本视频导入教程视频 1 、功能描述 本英语学习交流平台小程序有管理员和用户两个角色。 1、管理员功能有&#xff0c;个人中心&#xff0c;用户管理&#xff0c;每日打卡管理&#xff0c;备忘录管理&#xff0c;学习计划管…

【传感器技术】【第1章 传感器与检测技术的理论基础,测量系统,测量分类,误差分析,估计和处理】

目录 第1章 传感器与检测技术的理论基础 1.1 测量系统 2&#xff0e;开环测量系统与闭环测量系统 3、 测量概念 1.2 测量分类 1&#xff0e; 直接测量、 间接测量与组合测量 2&#xff0e; 等精度测量与不等精度测量 3&#xff0e; 偏差式测量、 零位式测量与微差式测量…

相机、镜头参数详解以及相关计算公式

一、工业相机参数 1、分辨率 相机每次采集图像的像素点数&#xff0c;也是指这个相机总共有多少个感光晶片。在采集图像时&#xff0c;相机的分辨率对检测精度有很大的影响&#xff0c;在对同样打的视场成像时&#xff0c;分辨率越高&#xff0c;对细节的展示越明显。 相机像素…

微信小程序配置prettier+eslint

虽然微信开发者工具是基于vscode魔改的.但是由于版本过低,导致很多插件也用不上新版本.所以在微信开发者工具限制的版本下使用的prettier,eslint也是有版本要求. 本文主要就是记录一下需要的版本号 1.微信开发者工具安装插件 2.package.json中添加以下依赖及安装依赖 "de…

STM32通过HAL库编码方式,在烧写一次程序后,单片机在仿真器上识别不到

在将项目从裸机移植到rtt过程中&#xff0c;总体调试跑不通ADC&#xff0c;进行了单独调试&#xff0c;新程序烧写进单片机后&#xff0c;仿真器再也识别不到单片机。一遍遍检查后发现HAL库没有配置完全。 SYS需要设置成 Serial Wire&#xff0c;忘记设置就成了No Debug,写这么…

2023_Spark_实验十一:RDD基础算子操作

一、RDD的练习可以使用两种方式 使用Shell使用IDEA 二、使用Shell练习RDD 当你打开 Spark 的交互式命令行界面&#xff08;也就是 Spark shell&#xff09;的时候&#xff0c;它已经自动为你准备好了一个叫做 sc 的特殊对象&#xff0c;这个对象是用来和 Spark 集群沟通的。你…