当前位置: 首页 > news >正文

Leetcode.939 最小面积矩形

题目链接

Leetcode.939 最小面积矩形 Rating : 1752

题目描述

给定在 xy平面上的一组点,确定由这些点组成的矩形的最小面积,其中矩形的边平行于 x 轴和 y 轴。

如果没有任何矩形,就返回 0

示例 1:

输入:[[1,1],[1,3],[3,1],[3,3],[2,2]]
输出:4

示例 2:

输入:[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
输出:2

提示:

  • 1<=points.length<=5001 <= points.length <= 5001<=points.length<=500
  • 0<=points[i][0]<=400000 <= points[i][0] <= 400000<=points[i][0]<=40000
  • 0<=points[i][1]<=400000 <= points[i][1] <= 400000<=points[i][1]<=40000
  • 所有的点都是不同的

解法:哈希表 + 枚举

对于每一个点 (x,y),我们都可以存入到一个哈希表 uset中。

因为每一个点的最大值是 40000。为了方便,我们可以存入 x * 40001 + y这样的一个数到 uset中。将两个点映射成一个数。

接下来枚举矩形的 左上角顶点(x1 , y1)右下角顶点(x2 , y2)。 再判断另外两个顶点在不在集合中,同时在的话,就可以构成一个矩形。

在这里插入图片描述

时间复杂度:O(n2)O(n^2)O(n2)

C++代码:

class Solution {
public:int minAreaRect(vector<vector<int>>& points) {unordered_set<int> uset;for(auto &p:points){uset.insert(p[0] * 40001 + p[1]);}int n = points.size();int s = 1e9;for(int i = 0;i < n;i++){int x1 = points[i][0] , y1 = points[i][1];for(int j = i + 1;j < n;j++){int x2 = points[j][0] , y2 = points[j][1];if(x1 == x2 || y1 == y2) continue;if(uset.count(x1 * 40001 + y2) && uset.count(x2 * 40001 + y1)){int a = abs(x1 - x2);int b = abs(y1 - y2);s = min(s,a * b);}}}return s == 1e9 ? 0 : s;}
};

相关文章:

Leetcode.939 最小面积矩形

题目链接 Leetcode.939 最小面积矩形 Rating &#xff1a; 1752 题目描述 给定在 xy平面上的一组点&#xff0c;确定由这些点组成的矩形的最小面积&#xff0c;其中矩形的边平行于 x 轴和 y 轴。 如果没有任何矩形&#xff0c;就返回 0。 示例 1&#xff1a; 输入&#xff1…...

Springboot项目快速实现过滤器功能

前言很多时候&#xff0c;当你以为掌握了事实真相的时间&#xff0c;如果你能再深入一点&#xff0c;你可能会发现另外一些真相。比如面向切面编程的最佳编程实践是AOP&#xff0c;AOP的主要作用就是可以定义切入点&#xff0c;并在切入点纵向织入一些额外的统一操作&#xff0…...

基于springboot的简历系统的实现

摘 要 随着科学技术的飞速发展&#xff0c;社会的方方面面、各行各业都在努力与现代的先进技术接轨&#xff0c;通过科技手段来提高自身的优势&#xff0c;简历系统当然也不能排除在外。简历系统是以实际运用为开发背景&#xff0c;运用软件工程原理和开发方法&#xff0c;采用…...

Vue3中watch的用法

watch函数用于侦听某个值的变化&#xff0c;当该值发生改变后&#xff0c;触发对应的处理逻辑。 一、watch的基本实例 <template><div><div>{{ count }}</div><button click"changCount">更改count的值</button></div> …...

MS python学习(18)

学习Pandas.DataFrame(2) load csv(comma seperated variable) files to DataFrame and vice versa upload csv files read/write csv files load data into jupyter notebook, create a new folder and then upload the csv files into it. (CSV comma seperated variable)…...

java笔记

前言 以下是一名java初学者在自学过程中所整理的笔记&#xff0c;欢迎大家浏览并留言&#xff0c;若有错误的地方请大家指正。 java语言特性 简单性&#xff1a;相对于其他编程语言而言&#xff0c;java较为简单&#xff0c;例如&#xff1a;java不再支持多继承&#xff0c;C…...

对象的构造及初始化

目录 一、如何初始化对象 二、构造方法 1.概念 2.特性 三、默认初始化 四、就地初始化 总结 一、如何初始化对象 在Java方法内部定义一个局部变量的时候&#xff0c;我们知道必须要进行初始化。 public class Test4 {public static void main(String[] args) {//未初始化…...

Socket 读取数据

1. Socket 配置参数中添加 1.1 读取 Socket 字节时的字节序 1.2 读取数据时&#xff0c;单次读取最大缓存值 1.3 从 Socket 读取数据时&#xff0c;遵从的数据包结构协议 1.4 服务器返回数据的最大值&#xff0c;防止客户端内存溢出 /*** Description: Socket 配置参数*/public…...

小白的Git入门教程(一)

这是本人的git的入门过程仅供参考 先是在官网下载git版本下载链接&#xff0c;安装步骤可以搜索其他大神的文章然后就是创建一个属于你的git本地库首先是创建一个文件夹作为根目录&#xff0c;这里我创建了一个叫test_git文件夹紧接着便进去新建文件夹&#xff0c;点击这里的g…...

第一个Vue程序

第一个Vue程序 <body> <!--view层 变成了一个模板--> <div id"app">{{message}} </div><!--导入vue.js--> <script src"https://cdn.jsdelivr.net/npm/vue2.5.16/dist/vue.min.js"></script> <script>va…...

2023上学期学习计划

目前&#xff1a;根据答辩的情况来看&#xff0c;目前去项目组&#xff0c;着重写好算法是相对较优的打算&#xff0c;先将项目写好&#xff0c;之后着重提升算法水平&#xff0c;这学期主要啃《算法导论》与《大话数据结构》这俩本书&#xff0c;同时刷题量要达到160题 四月份…...

深入了解MySQL锁机制及应用场景

深入了解MySQL锁机制及应用场景锁的概述锁的分类锁的应用场景数据库事务管理多线程程序开发数据库的备份和恢复对于在线游戏等高并发应用场景锁的具体使用方法锁的应用实例总结锁的概述 MySQL锁是操作MySQL数据库时常用的一种机制。MySQL锁可以保证多个用户在同时执行读写操作…...

Java类和对象

目录 一、什么是面向对象&#xff1f; 二、类与对象的基本概念 1.类 2.对象 三、类的定义格式 四、类与对象的定义与使用 1.什么是实例化 2.实例化对象 3.类的使用 4.类与对象的说明 总结 一、什么是面向对象&#xff1f; 面向对象是一种现在最为流行的程序设计方法&a…...

aspnet053+sqlserver在线考试系统xns

目 录 基于.NET的考试系统 1 摘 要 3 前 言 4 第一章  系统概述 5 1.1 本课题的研究意义 5 1.2 本论文的目的及内容 5 第二章 在线考试系统概述 7 2.1 现行在线考试系统现状 7 2.2 电子管理平台的开发方法介绍 8 2.2.1 B/S体系结构 8 2…...

新一代大学英语(提高篇)

词汇题&#xff08;55道&#xff09; 1. You should carefully think over_____ the manager said at the meeting. A. that B. which C. what D. whose 1.选C,考察宾语从句连接词&#xff0c;主句谓语动词think over后面缺宾语&#xff0c;后面的宾语从句谓语动…...

阿里云OSS 203 Non-Authoritative Information问题解决

问题描述&#xff1a; 203 Non-Authoritative Information 问题分析&#xff1a; 1、跨域问题&#xff0c;阿里云OSS没有配置跨域规则。 解决办法请参考以下博客。 阿里云OSS No ‘Access-Control-Allow-Origin‘ header is present on the requested resource问题解决_旭东…...

【数据结构】你真的认识“”吗?它真的就只是“取地址”吗?或许你一直都在误解它。

我们有时候在看数据结构相关书籍时&#xff0c;经常会看到这样的写法&#xff1a; void StackInit(ST& ps) {assert(ps);ps.a NULL;ps.top 0;ps.capacity 0; } 注意&#xff0c;这里的&可不是表示取地址。如果你把它理解为取地址&#xff0c;那就在错误的路上狂奔&…...

[深入理解SSD 21] 固态硬盘GC机制 | GC 分类 | GC 过程 | GC 和 Trim 的关系

Hello 大家好&#xff0c; 我是元存储~主页&#xff1a;元存储的博客_CSDN博客-深入理解SSD:固态存储特性与实践,深入浅出SSD:固态存储原理与特性,深入理解Flash:闪存特性与实践领域博主前言SSD上已经被写入过的Page页在重新被写入之前&#xff0c;必须要将page页所在的block块…...

大数据未来发展怎么样?

就目前情况来看&#xff0c;大数据行业前景不错薪资待遇好&#xff0c;也有越来越多的人选择大数据行业&#xff0c;各大名企对于大数据人才需求不断上涨。 大数据从业领域很宽广&#xff0c;不管是科技领域还是食品产业&#xff0c;零售业等都是需要大数据人才进行大数据的处…...

【Linux】进程和线程间的区别与联系

带你轻松理解进程与线程的区别与联系&#xff1a; 进程线程定义资源分配和拥有的基本单位CPU调度的基本单位切换情况对应进程的CPU环境的保存以及新进程环境的设置保存和设置程序计数器&#xff0c;少量的寄存器&#xff0c;以及对应的线程栈切换者操作系统操作系统切换过程用…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...