理清关系简化LeetCode题库第3047题求交集区域内的最大正方形面积问题求解

3047. 求交集区域内的最大正方形面积

难度:中等

问题描述:

在二维平面上存在 n 个矩形。给你两个下标从 0 开始的二维整数数组 bottomLeft 和 topRight,两个数组的大小都是 n x 2 ,其中bottomLeft[i]和topRight[i]分别代表第i个矩形的左下角和右上角坐标。我们定义向右的方向为x轴正半轴x坐标增加),向左的方向为x轴负半轴(x坐标减少)。

同样地,定义 向上的方向为y轴正半轴(y 坐标增加),向下 的方向为 y 轴负半轴(y 坐标减少)。你可以选择一个区域,该区域由两个矩形的交集形成。你需要找出能够放入该区域内的最大正方形面积,并选择最优解。

返回能够放入交集区域的正方形的最大可能面积,如果矩形之间不存在任何交集区域,则返回 0。

示例 1:

输入:bottomLeft = [[1,1],[2,2],[3,1]], topRight = [[3,3],[4,4],[6,6]]

输出:1

解释:边长为 1 的正方形可以放入矩形 0 和矩形 1 的交集区域,或矩形 1 和矩形 2 的交集区域。因此最大面积是边长 * 边长,即 1 * 1 = 1。

可以证明,边长更大的正方形无法放入任何交集区域。

示例 2:

输入:bottomLeft = [[1,1],[2,2],[1,2]], topRight = [[3,3],[4,4],[3,4]]

输出:1

解释:边长为 1 的正方形可以放入矩形 0 和矩形 1,矩形 1 和矩形 2,或所有三个矩形的交集区域。因此最大面积是边长 * 边长,即 1 * 1 = 1。

可以证明,边长更大的正方形无法放入任何交集区域。

请注意,区域可以由多于两个矩形的交集构成。

示例 3:

输入:bottomLeft = [[1,1],[3,3],[3,1]], topRight = [[2,2],[4,4],[4,2]]

输出:0

解释:不存在相交的矩形,因此,返回 0 。

分析:
拿到题目之后,大致上的思路:
1、先将两个矩形交集上能产生的最大正方形面积求出
由此设计函数max_square(one,two),其中one和two表示两个矩形,其数据格式为[bottomLeft,topRight],bottomLeft和topRight分别是矩形左下角和右上角坐标
2、对于多个矩形,先将矩形两两组合交集上产生的最大正方形面积分别求出,然后找出其中的最大值即为问题的解

思路虽说理出来了,但问题的关键是如何设计出计算两个矩形交集上产生最大正方形面积的函数max_square(one,two)?
我在草稿纸上画了几种两个矩形相交或不相交的图,分析来分析去,总感觉涉及的要素多,难以理出头绪,很是考查一个人耐心和细致方面的素质
经过反复思考,最后确定水平方向两个矩形是否相交与竖直方向两个矩形是否相交没有相关性,因此可以考虑单独分析水平方向和竖直方向。只要分析清楚水平方向的情况,竖直方向应该可以类似处理
先看水平方向,因为不考虑竖直方向,所以可以用两条水平线段代替两个矩形,如图1所示。
分别用

xoL表示矩形one的左下角横坐标
xoR表示矩形one的右上角横坐标
xtL表示矩形two的左下角横坐标
xtR表示矩形two的右上角横坐标
 

从图1可以看出矩形one和two在水平方向上的交集为w=min(xoR,xtR)-max(xoL,xtL)
从图2可以看出w=min(xoR,xtR)-max(xoL,xtL)=xoR-xtL<0,两个矩形 没有交集


从图3可以看出w=min(xoR,xtR)-max(xoL,xtL)=xtR-xoL<0,两个矩形没有交集


从图2图3可以推测出,如果w=0,只表示有左右边界的重合,交集依然为0
从上面的情况可以看出,只要w=min(xoR,xtR)-max(xoL,xtL)>0,在水平方向上就一定有交集,且交集长度为w

根据同样的道理,在竖直方向上,同样不考虑水平方向,可以用两条竖直线段代替两个矩形
分别用

yoL表示矩形one的左下角纵坐标
yoR表示矩形one的右上角纵坐标
ytL表示矩形two的左下角纵坐标
ytR表示矩形two的右上角纵坐标
则只要h=min(yoR,ytR)-max(yoL,ytL)>0,在竖直方向上也一定有交集,且交集长度为h

因此交集区域上的最大正方形边长应该为a=min(w,h),最大正方形面积也就可以求出了

程序如下:

def max_square(one,two):#one,two表示两个矩形区域其数据格式为[[左下角坐标x,y],[右上角坐标x,y]]    xoL=one[0][0] yoL=one[0][1]xoR=one[1][0]yoR=one[1][1]    xtL=two[0][0]ytL=two[0][1]xtR=two[1][0]ytR=two[1][1]w=min(xoR,xtR)-max(xoL,xtL)h=min(yoR,ytR)-max(yoL,ytL)if w>0 and h>0:return min(w,h)*min(w,h)else:return 0bottomLeft=eval(input('bottomLeft='))
topRight=eval(input('topRight='))
recTanges=list(zip(bottomLeft,topRight))
n=len(recTanges)
s=[]
for i in range(n-1):    for j in range(i+1,n):s.append(max_square(recTanges[i],recTanges[j]))
print(max(s))

运行实例1
bottomLeft=[[1,1],[2,1]]
topRight=[[4,3],[5,4]]
4

运行实例2
bottomLeft=[[1,1],[2,2],[3,1]]
topRight=[[3,3],[4,4],[6,6]]
1

运行实例3
bottomLeft=[[1,1],[3,3],[3,1]]
topRight=[[2,2],[4,4],[4,2]]
0

感悟:要善于从纷繁复杂的数据关系中理出关键要素,从而简化问题求解。
 

 

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

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

相关文章

爬虫(五)

1. 前端JS相关 三元运算 v1 条件 ? 值A : 值B; # 如果条件成立v1值A&#xff0c;不成立v1等于值Bres 1 1 ? 99 : 88 # res99特殊的逻辑运算 v1 11 || 22 # Ture v2 9 || 14 # 9 v3 0 || 15 # 15 v3 0 || 15 || "zhangfei" # 15赋值和…

Java二叉树 (2)

&#x1f435;本篇文章将对二叉树的一些基础操作进行梳理和讲解 一、操作简述 int size(Node root); // 获取树中节点的个数int getLeafNodeCount(Node root); // 获取叶子节点的个数int getKLevelNodeCount(Node root,int k); // 获取第K层节点的个数int getHeight(Node r…

【Claude3】利用Python中完成对Bedrock上的Claude的API调用

文章目录 1. 前期准备工作2. 安装和配置AWS CLI v23. 使用AWS configure命令配置AWS凭据4. 安装访问Bedrock的SDK5. 访问Amazon Bedrock UI6. 订阅Bedrock上的Claude模型7. 通过CLI命令列出所有可用的Claude模型8. 向Claude 3 Sonnet on Bedrock生成文本9. 参考链接 1. 前期准备…

云原生架构设计:分布式消息队列技术解析

消息队列是在消息传输过程中保存消息的容器&#xff0c;消息队列管理器在将消息从源到目标时充当中间人的角色&#xff0c;消息队列的主要目的是提供路由并保证消息的可靠传递。如果发送消息时接收者不可用&#xff0c;那消息队列就会保留消息&#xff0c;直到下次成功消费为止…

Excel 快速填充/输入内容

目录 一. Ctrl D/R 向下/右填充二. 批量输入内容 一. Ctrl D/R 向下/右填充 ⏹如下图所示&#xff0c;通过快捷键向下和向右填充数据 &#x1f914;当选中第一个单元格之后&#xff0c;可以按住Shift后&#xff0c;再选中最后一个单元格&#xff0c;可以选中第一个单元格和最…

CleanMyMac X4.14.7永久免费Mac电脑清理和优化软件

CleanMyMac X 是一款功能强大的 Mac 清理和优化软件&#xff0c;适合以下几类人群使用&#xff1a; 需要定期清理和优化 Mac 的用户&#xff1a;随着时间的推移&#xff0c;Mac 设备上可能会积累大量的无用文件、缓存和垃圾&#xff0c;导致系统运行缓慢。CleanMyMac X 的智能扫…

DataLoader

import torchvision from torch.utils.data import DataLoader from torch.utils.tensorboard import SummaryWriter# 准备的测试数据集 数据放在了CIFAR10文件夹下test_data torchvision.datasets.CIFAR10("./CIFAR10",trainFalse, transformtorchvision.transfor…

React useMemo钩子指南:优化计算性能

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

【解读】OWASP大语言模型应用程序十大风险

OWASP大型语言模型应用程序前十名项目旨在教育开发人员、设计师、架构师、经理和组织在部署和管理大型语言模型&#xff08;LLM&#xff09;时的潜在安全风险。该项目提供了LLM应用程序中常见的十大最关键漏洞的列表&#xff0c;强调了它们的潜在影响、易利用性和在现实应用程序…

[Spring] IoC 控制反转和DI依赖注入和Spring中的实现以及常见面试题

目录 1. 什么是Spring 2.什么是IoC容器 3.通过实例来深入了解IoC容器的作用 3.1造一量可以定义车辆轮胎尺寸的车出现的问题 3.2解决方法 3.3IoC优势 4.DI介绍 5.Spring中的IoC和DI的实现 5.1.存对象 5.1.2 类注解 5.1.3 方法注解 5.2取对像 (依赖注入) 5.2.1.属性…

如何使用Hexo搭建个人博客

文章目录 如何使用Hexo搭建个人博客环境搭建连接 Github创建 Github Pages 仓库本地安装 Hexo 博客程序安装 HexoHexo 初始化和本地预览 部署 Hexo 到 GitHub Pages开始使用发布文章网站设置更换主题常用命令 插件安装解决成功上传github但是web不更新不想上传文章处理方式链接…

复盘-word

word-大学生网络创业交流会 设置段落&#xff0c;段后行距才有分 word-选中左边几行字进行操作 按住alt键进行选中 word复制excel随excel改变&#xff08;选择性粘贴&#xff09; 页边距为普通页边距定义 ##### word 在内容控件里面填文字&#xff08;调属性&#xff09…

BC134 蛇形矩阵

一&#xff1a;题目 二&#xff1a;思路分析 2.1 蛇形矩阵含义 首先&#xff0c;这道题我们要根据这个示例&#xff0c;找到蛇形矩阵是怎么移动的 这是&#xff0c;我们可以标记一下每次移动到方向 我们根据上图可以看出&#xff0c;蛇形矩阵一共有两种方向&#xff0c;橙色…

LLM 推理优化探微 (2) :Transformer 模型 KV 缓存技术详解

编者按&#xff1a;随着 LLM 赋能越来越多需要实时决策和响应的应用场景&#xff0c;以及用户体验不佳、成本过高、资源受限等问题的出现&#xff0c;大模型高效推理已成为一个重要的研究课题。为此&#xff0c;Baihai IDP 推出 Pierre Lienhart 的系列文章&#xff0c;从多个维…

模板不存在:./Application/Home/View/OnContact/Index.html 错误位置

模板不存在:./Application/Home/View/OnContact/Index.html 错误位置FILE: /home/huimingdedhpucixmaihndged5e/wwwroot/ThinkPHP123/Library/Think/View.class.php  LINE: 110 TRACE#0 /home/huimingdedhpucixmaihndged5e/wwwroot/ThinkPHP123/Library/Think/View.class.php(…

Flutter 开发环境搭建-VS Code篇

1.准备环境 Java SDK 下载及安装Flutter SDK 安装及配置环境变量 下载地址将flutter sdk解压目录下的bin目录放到系统环境变量中 检查环境&#xff0c;在系统终端中输入&#xff1a; # 打印flutter sdk版本号 flutter --version# 检查flutter运行环境 flutter doctor第一次运…

弹性地基梁matlab有限元编程 | 双排桩支护结构 | Matlab源码 | 理论文本

专栏导读 作者简介&#xff1a;工学博士&#xff0c;高级工程师&#xff0c;专注于工业软件算法研究本文已收录于专栏&#xff1a;《有限元编程从入门到精通》本专栏旨在提供 1.以案例的形式讲解各类有限元问题的程序实现&#xff0c;并提供所有案例完整源码&#xff1b;2.单元…

uniapp小程序获取位置权限(不允许拒绝)

需求 小程序上如果需要一些定位功能&#xff0c;那么我们需要提前获取定位权限。我们页面的所有功能后续都需要在用户同意的前提下进行&#xff0c;所以一旦用户点了拒绝&#xff0c;我们应该给予提示&#xff0c;并让用于修改为允许。 实现 1.打开手机GPS 经过测试发现即使…

R语言更新版本

目录 一、更新R语言 1、安装最新的R语言版本 2、移动之前安装的packages 3、将Rstudio连接到最新的R语言 二、Rstudio更新 一、更新R语言 1、安装最新的R语言版本 查看当前R语言版本&#xff1a; R.version.string 下载最新的R语言安装包&#xff1a;R: The R Project…

图神经网络实战(4)——基于Node2Vec改进嵌入质量

图神经网络实战&#xff08;4&#xff09;——基于Node2Vec改进嵌入质量 0. 前言1. Node2Vec 架构1.2 定义邻居1.2 在随机游走中引入偏向性1.3 实现有偏随机游走 2. 实现 Node2Vec小结系列链接 0. 前言 Node2Vec 是一种基于 DeepWalk 的架构&#xff0c;DeepWalk 主要由随机游…