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.rhkb.cn/news/432924.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【机器学习】探索LSTM:深度学习领域的强大时间序列处理能力

目录 &#x1f354; LSTM介绍 &#x1f354; LSTM的内部结构图 2.1 LSTM结构分析 2.2 Bi-LSTM介绍 2.3 使用Pytorch构建LSTM模型 2.4 LSTM优缺点 &#x1f354; 小结 学习目标 &#x1f340; 了解LSTM内部结构及计算公式. &#x1f340; 掌握Pytorch中LSTM工具的使用. &…

【react案例】实现评论列表

1. 需求 展示评论列表实现删除功能 2.1 只有自己的评论才展示删除按钮 2.2 点击删除按钮&#xff0c;删除当前评论tab切换&#xff08;点击对应tab&#xff0c;对tab文案高亮处理&#xff09;评论高亮评论排序&#xff08;最新、最热&#xff09; 2. 实现思路 useState维护评…

【小程序】uniapp自定义图标组件可动态更换svg颜色

组件描述 通过图标名称加载对应svg&#xff0c;size参数调整图标大小&#xff0c;color参数调整图标颜色 解决思路&#xff1a; 存svg获svg&#xff0c;对象方式正则替换svg的fill值&#xff0c;不改变源文件&#xff0c;通过base64直接加载缓存svg源文件&#xff0c;避免重…

Android 通过自定义注解实现Activity间跳转时登录路由的自动拦截

应用场景 在Android 中部分软件需要登录才能使用&#xff0c;但是有的页面又不需要登录&#xff0c;Android不同于Web可以直接拦截重定向路由&#xff0c;因此如果在Android中如果需要检测是否登录&#xff0c;如果没登录跳转登录的话就需要再每个页面中判断&#xff0c;当然也…

Leetcode面试经典150题-39.组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target &#xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 &#xff0c;并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如…

高级算法设计与分析 学习笔记9 跳表

单链表的样子我们很熟悉了&#xff1a; 怎么加快查找&#xff1f;&#xff1a; 查找的具体方法&#xff1a; 超过了就回头下去。 这条“快速路”最好是几个节点呢&#xff1f;&#xff1a; 假如我们弄好多层跳表呢&#xff1f;&#xff1a; 给弄成2叉树了&#xff01; 如何插入…

堆的数组实现

目录 一、堆 二叉树的顺序结构 堆的概念及结构 1.概念 2.堆的分类 (1)大堆 (2)小堆 二、利用数组(顺序结构)实现堆的过程 1.利用数组实现堆的思路 2.堆是用数组实现的&#xff0c;在数组中通过双亲找自己左右孩子、通过左右孩子找自己双亲的思路 2.1.思路 2.2.孩子与…

【YashanDB知识库】YMP迁移oracle不兼容给用户授权高级包

本文转自YashanDB官网&#xff0c;具体内容请见https://www.yashandb.com/newsinfo/7441382.html?templateId1718516 【标题】YMP迁移oracle不兼容给用户授权高级包 【关键字】oracle迁移&#xff0c;高级包授权 【问题描述】迁移评估任务中&#xff0c;oracle迁移YashanDB…

FOC电机驱动开发踩坑记录

关键技术 SVPWM电机磁场控制电流采样park变换和Clark变换滑膜观测器&#xff08;无感FOC&#xff09; SVPWM电机磁场控制 SVPWM主要思想是通过精确的对UVW三相电流的分时控制&#xff0c;来控制转子的合成力矩&#xff0c;达到目标方向&#xff0c;常用的是6分区的设计&…

RabbitMQ 高级特性——重试机制

文章目录 前言重试机制配置文件设置生命交换机、队列和绑定关系生产者发送消息消费消息 前言 前面我们学习了 RabbitMQ 保证消息传递可靠性的机制——消息确认、持久化和发送发确认&#xff0c;那么对于消息确认和发送方确认&#xff0c;如果接收方没有收到消息&#xff0c;那…

C++类和对象——第二关

目录 类的默认成员函数&#xff1a; &#xff08;一&#xff09;构造函数 &#xff08;二&#xff09;析构函数 &#xff08;三&#xff09;拷贝构造函数 类的默认成员函数&#xff1a; 类里面有6个特殊的成员函数分别包揽不同的功能; &#xff08;一&#xff09;构造函数…

极狐GitLab 17.4 升级指南

GitLab 是一个全球知名的一体化 DevOps 平台&#xff0c;很多人都通过私有化部署 GitLab 来进行源代码托管。极狐GitLab https://dl.gitlab.cn/6y2wxugm 是 GitLab 在中国的发行版&#xff0c;专门为中国程序员服务。可以一键式部署极狐GitLab。 本文分享极狐GitLab 17.4 升级…

老人跌倒扶不扶?涪城三职工给出响亮答案

一、关键时刻的选择 于绵阳市三江湖湿地公园&#xff0c;平凡午后&#xff0c;三名环卫人员刘后刚、严荣礼及杨树坤正紧张作业。突闻呼救声&#xff0c;一位老人在石阶上跌倒需援手。在紧急关头&#xff0c;他们果断抛却工具&#xff0c;疾速赶至老人身边。此举不仅展现了他们…

MySQL数据库进阶知识(四)《视图、存储过程、触发器》

学习目标&#xff1a; 掌握数据库视图基础知识 掌握数据库存储过程原理 掌握数据库触发器相关知识 学习内容&#xff1a; 一. 视图 介绍 视图&#xff08;View&#xff09;是一种虚拟存在的表。视图中的数据并不在数据库中实际存在&#xff0c;行和列数据来自定义视图的查询…

JPEG图像的DCT(Discrete Cosine Transform)变换公式代码详解

引 言 网络上图像在传输过程中为节省内存空间主要采用jpeg格式。jpeg图属于有损压缩图像的一种。在图像篡改检测过程中&#xff0c;可以利用jpeg图像的单双压缩伪影的不同而判别图像为伪造图并可以定位伪造区域。RGB图像变成jpeg图像过程中涉及从RGB图变成YCbCr图像&#xff0c…

FreeRTOS(四)FreeRTOS列表与列表项

目录 列表 列表项 迷你列表项 列表和列表项的关系 列表相关API函数 列表初始化 列表项初始化 列表项插入 列表项末尾插入 列表项删除 列表遍历 在 FreeRTOS 中&#xff0c;列表&#xff08;List&#xff09;和列表项&#xff08;ListItem&#xff09;是核心数据结构&…

Centos7系统根分区空间小home空间大如何增加分区

Centos7 默认安装&#xff0c;区划默认划分&#xff0c;用着怎么感觉有问题&#xff0c;根分区太小50G&#xff0c;而home分区太大。 如果处理&#xff0c;能扩大根分区呢&#xff1f;如果是新安装的&#xff0c;可以先删除home&#xff0c;然后再扩容 根分区。最后使其生效。…

计算机视觉硬件整理(四):相机与镜头参数介绍

文章目录 前言一、工业相机常用分类二、工业相机的基本参数三、工业相机的接口四、工业镜头的参数五、工业镜头的选择要点 前言 随着科技的飞速发展&#xff0c;工业自动化和智能制造在当今社会扮演着越来越重要的角色。在这个背景下&#xff0c;工业相机作为一种关键的视觉检…

Qualitor processVariavel.php 未授权命令注入漏洞复现(CVE-2023-47253)

0x01 漏洞概述 Qualitor 8.20及之前版本存在命令注入漏洞,远程攻击者可利用该漏洞通过PHP代码执行任意代码。 0x02 复现环境 FOFA&#xff1a;app"Qualitor-Web" 0x03 漏洞复现 PoC GET /html/ad/adpesquisasql/request/processVariavel.php?gridValoresPopHi…

【azure-openai】批量翻译demo【python】【gradio】

要求&#xff1a;拥有azure-openai-api&#xff0c;上传文件为csv格式&#xff0c;utf-8编码。 注意&#xff1a;如果出现乱码&#xff0c;重新运行&#xff0c;换种方式打开&#xff0c;有时候wps会自动改编码。 实现功能&#xff1a;选择语言&#xff0c;使用gpt4omini&…