当前位置: 首页 > 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;以及对应的线程栈切换者操作系统操作系统切换过程用…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

WPF八大法则:告别模态窗口卡顿

⚙️ 核心问题&#xff1a;阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程&#xff0c;导致后续逻辑无法执行&#xff1a; var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题&#xff1a…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...

【iOS】 Block再学习

iOS Block再学习 文章目录 iOS Block再学习前言Block的三种类型__ NSGlobalBlock____ NSMallocBlock____ NSStackBlock__小结 Block底层分析Block的结构捕获自由变量捕获全局(静态)变量捕获静态变量__block修饰符forwarding指针 Block的copy时机block作为函数返回值将block赋给…...