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

咸阳学校网站建设哪家专业重庆百度推广电话

咸阳学校网站建设哪家专业,重庆百度推广电话,建设应用型网站的意义,建站abc怎么备案题目链接 Leetcode.939 最小面积矩形 Rating : 1752 题目描述 给定在 xy平面上的一组点,确定由这些点组成的矩形的最小面积,其中矩形的边平行于 x 轴和 y 轴。 如果没有任何矩形,就返回 0。 示例 1: 输入&#xff1…

题目链接

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;}
};
http://www.tj-hxxt.cn/news/124918.html

相关文章:

  • 教师个人网站建设推销一个产品的方案
  • 24小时学会网站建设哈尔滨百度推广公司
  • 广州智迅网络做网站湖南株洲疫情最新情况
  • 宁晋网站建设设计世界杯最新排名
  • 网站宣传虚假处罚标准高报师培训机构排名
  • 云服务器建立多个网站吗韩国比分预测
  • 湖南省交通建设质监局网站百度热搜榜排名今日第一
  • 专业做网站技术西安seo代运营
  • 网站常用的推广方法有哪些百度广告怎么投放多少钱
  • 网站建设的标准seo独立站
  • 如何自己动手做网站软文的目的是什么
  • 响应式表白网站源码百度知道一下
  • 网络公司构建网站北京已感染上千万人
  • 聊城网站建设制作开发公司北京快速优化排名
  • 网站域名免费申请2024年新闻时事热点论文
  • 门户网站的发布特点宁波seo搜索引擎优化公司
  • 网站管理和维护如何让百度快速收录
  • 新手建网站需要怎么做呢郑州众志seo
  • 做房产网站哪个好杭州百家号优化
  • 上海做网站报价零食软文范例300字
  • 凡科网骗局seo百度关键词优化软件
  • C语言也能干大事网站开发pdf网络营销环境的分析主要是
  • 科技魏玄成盐城网站优化
  • 长沙做网站的公司对比seo网络排名优化哪家好
  • 网站不备案百度收录吗网络营销品牌策划
  • 做网站推广可行吗seo课
  • 郑州网站建设电话郑州seo优化外包顾问阿亮
  • 现在那个网站做推广效果会好点公司网站推广
  • 网站建设公司studstu口碑营销的概念是什么
  • wordpress网站添加背景音乐自己怎么注册网站