用最短长度的绳子把整个花园围起来

给定一个数组 trees,其中 trees[i] = [xi, yi] 表示树在花园中的位置。

你被要求用最短长度的绳子把整个花园围起来,因为绳子很贵。只有把 所有的树都围起来,花园才围得很好。

返回恰好位于围栏周边的树木的坐标

示例 1:

输入: points = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
输出: [[1,1],[2,0],[3,3],[2,4],[4,2]]

示例 2:

输入: points = [[1,2],[2,2],[4,2]]
输出: [[4,2],[2,2],[1,2]]

class Solution {
public:vector<vector<int>> outerTrees(vector<vector<int>>& trees) {// 如果树的数量小于等于 1,直接返回if (trees.size() <= 1) return trees;// 自定义比较函数auto cmp = [](vector<int>& p1, const vector<int>& p2) {return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]);};sort(trees.begin(), trees.end(), cmp);// 构建下凸包vector<vector<int>> lower;for (auto& tree : trees) {while (lower.size() >= 2 && cross(lower[lower.size() - 2], lower.back(), tree) < 0) {lower.pop_back();}lower.push_back(tree);}// 构建上凸包vector<vector<int>> upper;for (int i = trees.size() - 1; i >= 0; i--) {auto& tree = trees[i];while (upper.size() >= 2 && cross(upper[upper.size() - 2], upper.back(), tree) < 0) {upper.pop_back();}upper.push_back(tree);}vector<vector<int>> result(lower);result.insert(result.end(), upper.begin(), upper.end());set<vector<int>> res(result.begin(), result.end());// 去掉重复的点return vector<vector<int>>(res.begin(),res.end());//返回vector<vector<int>>类型}// 计算叉积int cross(vector<int>& O, vector<int>& A, vector<int>& B) {return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0]);}
};

auto cmp = [](vector<int>& p1, const vector<int>& p2) {

            return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]);

        };

这个比较函数用于根据树木的位置对它们进行排序。首先按 x 坐标排序,如果 x 坐标相同,则按 y 坐标排序。

叉积 A×B=Ax​⋅By​−Ay​⋅Bx​ 可以帮助判断三点之间的相对方向。给定三点 O(原点)、A 和 B,叉积的结果可以用来判断 A 和 B 相对于 O 的位置关系:

  • 正数:表示 B 在 A 的左侧,形成的角度是逆时针(O -> A -> B 是一个左转)。
  • 负数:表示 B 在 A 的右侧,形成的角度是顺时针(O -> A -> B 是一个右转)。
  • :表示 A 和 B 在同一条直线上。

构建凸包:

while (lower.size() >= 2 && cross(lower[lower.size() - 2], lower.back(), tree) < 0)

构建下凸包时,必须要保证有至少两个点,才能进行三点之间的相对方向判断。while 循环可以确保我们在引入每一个新点时,能够动态地调整 lower 中的点,以确保所有点都能形成一个外包围的凸形结构。

举个例子:第一个点 [1, 1]

加入 lower,当前 lower = [[1, 1]]

第二个点 [2, 0]

加入 lower,当前 lower = [[1, 1], [2, 0]]

第三个点 [3, -1]

现在 lower.size() == 2,计算叉积:

cross([1, 1], [2, 0], [3, -1])

(2 - 1) * (-1 - 1) - (0 - 1) * (3 - 2) = 1 * (-2) - (-1) * 1 = -2 + 1 = -1

叉积为负数,说明这三个点构成了 顺时针方向,这通常意味着形成了一个凹形。因此,进入 while 循环,移除 [2, 0],然后再将 [3, -1] 加入 lower

lower 最终包含的是所有位于下边界上的点,这些点构成了围绕给定树木坐标的下半部分的凸包。具体来说,lower 会包含从最左侧的点到最右侧的点,形成一个向上的弯曲结构。

upper 构建上凸包。代码的逻辑与构建下凸包的过程相似,但它从树木坐标的最后一个点开始逆序遍历,直到第一个点。

最后将将 lowerupper 两个 vector 合并为一个新的 vector

result.insert(result.end(), upper.begin(), upper.end());

  • result.end() 表示插入的位置是 result 的末尾。
  • upper.begin()upper.end() 表示要插入的元素范围,即从 upper 的起始位置到结束位置。

set 去重:去除upper和lower重复的部分

set<vector<int>> res (result.begin(), result.end());  在构造过程中,set 会自动去除 result 中的重复元素,只保留唯一的元素

由于set 的返回值类型与 vector 不同。是set<vector<int>>,而我们需要的是vector<vector<int>>,所以最后 return vector<vector<int>>(res.begin(),res.end());

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

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

相关文章

【24最新亲试】ubuntu下载go最新版本

系列综述&#xff1a; &#x1f49e;目的&#xff1a;本系列是个人整理为了工具配置的&#xff0c;整理期间苛求每个知识点&#xff0c;平衡理解简易度与深入程度。 &#x1f970;来源&#xff1a;材料主要源于Ubuntu 升级 golang 版本完美步骤进行的&#xff0c;每个知识点的修…

C语言-了解程序环境和预处理看这一篇(超详解)

1.程序环境 在ANSIC的任何一种实现中&#xff0c;都会存在两个不同的环境。第1种是翻译环境&#xff0c;在这个环境中源代码被转换为可执行的机器指令&#xff0c;第2种是执行环境&#xff0c;它用于实际执行代码。如下图所示&#xff1a; 1.1 翻译环境 翻译环境会分几个步骤…

大数据处理从零开始————9.MapReduce编程实践之信息过滤之学生成绩统计demo

1.项目目标 1.1 需求概述 现在我们要统计某学校学生的成绩信息&#xff0c;筛选出成绩在60分及以上的学生。 1.2 业务分析 如果我们想实现该需求&#xff0c;可以通过编写一个MapReduce程序&#xff0c;来处理包含学生信息的文本文件&#xff0c;每行包含【学生的姓名&#x…

HCIP--以太网交换安全(二)端口安全

端口安全 一、端口安全概述 1.1、端口安全概述&#xff1a;端口安全是一种网络设备防护措施&#xff0c;通过将接口学习的MAC地址设为安全地址防止非法用户通信。 1.2、端口安全原理&#xff1a; 类型 定义 特点 安全动态MAC地址 使能端口而未是能Stichy MAC功能是转换的…

使用 Vertex AI Gemini 模型和 Elasticsearch Playground 快速创建 RAG 应用程序

作者&#xff1a;来自 Elastic Jeff Vestal 在这篇博客中&#xff0c;我们将使用 Elastic 的 Playground 和 Vertex AI API 将 Elasticsearch 连接到 Google 的 Gemini 1.5 聊天模型。将 Gemini 模型添加到 Playground 使 Google Cloud 开发人员能够快速建立 LLM、测试检索、调…

算法闭关修炼百题计划(四)

仅供个人复习 1.两数相加2.寻找峰值6.岛屿的最大面积3.最大数4.会议室5.最长连续序列6.寻找两个正序数组的中位数 1.两数相加 给你两个 非空 的链表&#xff0c;表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的&#xff0c;并且每个节点只能存储 一位 数字。 请…

滑动窗口_⽔果成篮找到字符串中所有字⺟异位词

⽔果成篮 904. 水果成篮 - 力扣&#xff08;LeetCode&#xff09; 相当于求数字种类不超过2的最长字字符串 我们先看一看例4.从第一个元素开始最长字符串3331&#xff0c;下一次从第二个位置数吗&#xff1f;没必要&#xff0c;因为只有当字符串中数字种类变为1时&#xff0c;…

pycharm里debug时如何看到数据的维度

使用表达式计算&#xff08;Evaluate Expression&#xff09; 调试时&#xff0c;使用 PyCharm 的 “Evaluate Expression” 功能可以动态查看或修改数据。具体步骤如下&#xff1a; 在调试模式中按 Alt F8&#xff08;Windows&#xff09;或 Option F8&#xff08;Mac&…

机器学习 | 特征选择如何减少过拟合?

在快速发展的机器学习领域&#xff0c;精确模型的开发对于预测性能至关重要。过度拟合的可能性&#xff0c;即模型除了数据中的潜在模式外&#xff0c;还拾取训练集特有的噪声和振荡&#xff0c;这是一个固有的问题。特征选择作为一种有效的抗过拟合武器&#xff0c;为提高模型…

JAVA科技赋能共享台球室无人系统小程序源码

科技赋能共享台球室无人系统 —— 智慧台球新体验 &#x1f3b1; 科技引领&#xff0c;台球室迎来无人新纪元 在这个日新月异的科技时代&#xff0c;共享经济的浪潮席卷而来&#xff0c;为我们的生活带来了诸多便利。而今天&#xff0c;我要为大家介绍的&#xff0c;正是科技…

【高等代数笔记】线性空间(十九-二十四上半部分)

课程视频剪辑得太抽象了&#xff0c;一节课不能完整学完&#xff0c;拆的零零散散得。 3. 线性空间 3.19 满秩矩阵 【推论4】设 rank ( A ) r \text{rank}(\boldsymbol{A})r rank(A)r&#xff0c;则 A \boldsymbol{A} A的不为0的 r r r阶子式所在的列&#xff08;行&#x…

2.3MyBatis——插件机制

2.3MyBatis——插件机制 1.基本用法2.原理探究2.1加载过程2.2执行过程2.2.1 插件的执行点2.2.2 SQL执行的几个阶段2.2.3 如何梳理出执行流程 合集总览&#xff1a;Mybatis框架梳理 插件机制是一款优秀框架不可或缺的组成部分&#xff0c;比如spring、dubbo&#xff0c;还有…

链表(2)_两两交换链表中的节点_面试题

个人主页&#xff1a;C忠实粉丝 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 C忠实粉丝 原创 链表(2)_两两交换链表中的节点_面试题 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记&#xff0c;欢迎大家在评论区交流讨论&#x1f48c;…

T11:优化器对比实验

T11周&#xff1a;优化器对比实验 **一、前期工作**1.设置GPU,导入库 **二、数据预处理**1.导入数据2.检查数据3.配置数据集4.数据可视化 **三、构建模型****四、训练模型****五、模型评估**六、总结 &#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&a…

【前端碎片记录】大文件分片上传

大文件分片上传&#xff0c;主要是为了提高上传效率&#xff0c;避免网络问题或者其他原因导致整个上传失败。 HTML部分没什么特殊代码&#xff0c;这里只写js代码。用原生js实现&#xff0c;框架中可参考实现 // 获取上传文件的 input框 const ipt document.querySelector(…

aws(学习笔记第五课) AWS的firewall SecurityGroup,代理转发技术

aws(学习笔记第五课) AWS的firewall– SecurityGroup&#xff0c;代理转发技术 学习内容&#xff1a; AWS的firewall– SecurityGroup代理转发技术 1. AWS的filewall– SecurityGroup 控制进入虚拟服务器的网络流量 通常的firewall(防火墙)配置 AWS上使用安全组进行网络流量…

息肉检测数据集 yolov5 yolov8适用于目标检测训练已经调整为yolo格式可直接训练yolo网络

息肉检测数据集 yolov5 yolov8格式 息肉检测数据集介绍 数据集概述 名称&#xff1a;息肉检测数据集&#xff08;基于某公开的分割数据集调整&#xff09;用途&#xff1a;适用于目标检测任务&#xff0c;特别是内窥镜图像中的息肉检测格式&#xff1a;YOLO格式&#xff08;边…

Transactional注解导致Spring Bean定时任务失效

背景 业务需要定时捞取数据库中新增的数据做数据处理及分析&#xff0c;更新状态&#xff0c;处理结束。而我们不能随意定义线程池&#xff0c;规定使用统一的标准规范来定义线程池。如在配置文件中配置线程池的属性&#xff1a;名称&#xff0c;线程核心数等&#xff0c;任务…

04-SpringBootWeb案例(中)

3. 员工管理 完成了部门管理的功能开发之后&#xff0c;我们进入到下一环节员工管理功能的开发。 基于以上原型&#xff0c;我们可以把员工管理功能分为&#xff1a; 分页查询&#xff08;今天完成&#xff09;带条件的分页查询&#xff08;今天完成&#xff09;删除员工&am…

Linux_kernel内核定时器14

一、内核定时器 1、内核定时器 使用方法&#xff1a; 2、系统时钟中断处理函数 1&#xff09;更新时间 2&#xff09;检查当前时间片是否耗尽 Linux操作系统是基于时间片轮询的&#xff0c;属于抢占式的内核 3&#xff09;jiffies 3、基本概念 1&#xff09;HZ HZ决定了1秒钟产…