LeetCode-day37-2940. 找到 Alice 和 Bob 可以相遇的建筑
LeetCode-day37-2940. 找到 Alice 和 Bob 可以相遇的建筑
- 题目描述
- 示例
- 示例1:
- 示例2:
- 思路
- 代码
题目描述
给你一个下标从 0 开始的正整数数组 heights ,其中 heights[i] 表示第 i 栋建筑的高度。
如果一个人在建筑 i ,且存在 i < j 的建筑 j 满足 heights[i] < heights[j] ,那么这个人可以移动到建筑 j 。
给你另外一个数组 queries ,其中 queries[i] = [ai, bi] 。第 i 个查询中,Alice 在建筑 ai ,Bob 在建筑 bi 。
请你能返回一个数组 ans ,其中 ans[i] 是第 i 个查询中,Alice 和 Bob 可以相遇的 最左边的建筑 。如果对于查询 i ,Alice 和 Bob 不能相遇,令 ans[i] 为 -1 。
示例
示例1:
输入:heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
输出:[2,5,-1,5,2]
解释:第一个查询中,Alice 和 Bob 可以移动到建筑 2 ,因为 heights[0] < heights[2] 且 heights[1] < heights[2] 。
第二个查询中,Alice 和 Bob 可以移动到建筑 5 ,因为 heights[0] < heights[5] 且 heights[3] < heights[5] 。
第三个查询中,Alice 无法与 Bob 相遇,因为 Alice 不能移动到任何其他建筑。
第四个查询中,Alice 和 Bob 可以移动到建筑 5 ,因为 heights[3] < heights[5] 且 heights[4] < heights[5] 。
第五个查询中,Alice 和 Bob 已经在同一栋建筑中。
对于 ans[i] != -1 ,ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ,不存在 Alice 和 Bob 可以相遇的建筑。
示例2:
输入:heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]
输出:[7,6,-1,4,6]
解释:第一个查询中,Alice 可以直接移动到 Bob 的建筑,因为 heights[0] < heights[7] 。
第二个查询中,Alice 和 Bob 可以移动到建筑 6 ,因为 heights[3] < heights[6] 且 heights[5] < heights[6] 。
第三个查询中,Alice 无法与 Bob 相遇,因为 Bob 不能移动到任何其他建筑。
第四个查询中,Alice 和 Bob 可以移动到建筑 4 ,因为 heights[3] < heights[4] 且 heights[0] < heights[4] 。
第五个查询中,Alice 可以直接移动到 Bob 的建筑,因为 heights[1] < heights[6] 。
对于 ans[i] != -1 ,ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ,不存在 Alice 和 Bob 可以相遇的建筑。
思路
采用最小堆
算法涉及到三个位置,假定 a≤b,按照从左到右的顺序,它们分别是:
- a:回答询问时,用其高度 heights[a] 和当前高度 heights[i] 比大小,如果heights[a]<heights[i] 则找到答案。
- b:决定了在什么位置把询问加入堆中。注意在遍历到位置 b之前是不能入堆的。在遍历到位置 b 时入堆,这样后续只需要比较 heights[a]<heights[i],如果成立,就间接地说明heights[b]<heights[i] 也成立。并且,由于我们是从左往右遍历 heights 的,当前下标 i 就是 Alice 和Bob 可以相遇的最左边建筑的下标。
- 回答询问的位置 i。如果堆顶 heights[a] 小于当前位置的高度heights[i],则回答堆顶询问,并弹出堆顶。
代码
class Solution:def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:ans = [-1] * len(queries)qs = [[] for _ in heights]for i,(a,b) in enumerate(queries):if a > b:a,b = b,aif a == b or heights[a]<heights[b]:ans[i] = belse:qs[b].append((heights[a],i))h = []for i,x in enumerate(heights):while h and h[0][0] < x:ans[heappop(h)[1]] = ifor q in qs[i]:heappush(h,q)return ans
相关文章:
LeetCode-day37-2940. 找到 Alice 和 Bob 可以相遇的建筑
LeetCode-day37-2940. 找到 Alice 和 Bob 可以相遇的建筑 题目描述示例示例1:示例2: 思路代码 题目描述 给你一个下标从 0 开始的正整数数组 heights ,其中 heights[i] 表示第 i 栋建筑的高度。 如果一个人在建筑 i ,且存在 i &…...
unity 判断平台
原文链接 Unity中判断平台的方法 Unity提供了一些方法来判断当前运行的平台,其中包括了判断是否为i0S平台。以下是几种常用的方法1.Application.platform Applicaion,platom 是Unity中的一个枚举类型,用于表示当前运行的平台。可以通过比较 Apication,p…...
PyCharm找不到Python了咋办
Python发生了重装的,且新的路径和原有路径不同,就会出现如下的错误: 解决办法: 点开PyCharm菜单的File/Setting 然后: 有上图的提示,说明需要将原来的venv进行清空。 如此操作之后,原来的红色…...
BRC-100 协议
BRC-100 协议 BRC-100 是一种基于序数理论的可扩展的去中心化计算协议。 BRC-100 协议会以下面的方式定义。未来所有的 BRC-100 协议栈都应该使用类似的规范来定义。 1. 摘要 BRC-100 协议是一种基于序数理论的可扩展的去中心化计算协议。 2. 抽象 BRC-100 协议本质上描述…...
茶余饭后(六)
年少成长的时候,多遇到一些所谓的“坏人”,“烂人”,其实是好的,因为这些人让你见识到了人性最丑陋的一面,他们让你磨炼了心性,在以后遇到难处理的人或事的时候,能够有一定的心理承受能力。遇见…...
秋招复习笔记——八股文部分:网络IP
终于来到了网络的最后一篇,继续加油! IP 知识全家桶 IP 基本认识 IP 在 TCP/IP 参考模型中处于第三层,也就是网络层。 网络层的主要作用是:实现主机与主机之间的通信,也叫点对点(end to end)…...
量化投资基础(四)之AR、MA、ARMA与ARIMA模型
点赞、关注,养成良好习惯 Life is short, U need Python 量化投资基础系列,不断更新中 1 引言 时间序列经典模型主要有: 自回归模型(Auto Regressive,AR)移动回归模型(Moving Average,MA&…...
LVS(Linux Virtual Server)详解
LVS(Linux Virtual Server)是一个用于负载均衡的开源软件项目,旨在通过集群技术实现高性能、高可用的服务器系统。它运行在Linux操作系统上,并且可以利用内核级的资源来提高性能和稳定性。 思维导图 LVS的工作原理 LVS主要基于Ne…...
uniapp版本更新除了plus.runtime.getProperty的解决办法
以下是展示图 带尺寸的图片: 首先把以下代码放到想要更新弹出的页面 //template部分<uni-popup ref"popup" background-color"#fff"><versionUp handleCloseVersion"closeVersion"></versionUp></uni-popup>//script…...
MySQL笔记-基础篇(二):多表查询
博客主页: 南来_北往 系列专栏:Spring Boot实战 前言 MySQL的多表查询是一项非常实用的数据库操作技术,它能够通过关联不同表中的数据来提供更加丰富和准确的信息。在实际应用中,数据通常不是孤立存在的,而是分布在多个…...
备战秋招60天算法挑战,Day15
题目链接: https://leetcode.cn/problems/minimum-window-substring/ 视频题解: https://www.bilibili.com/video/BV1sJ4m1g727/ LeetCode 76. 最小覆盖子串 题目描述 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s …...
【学习笔记】Matlab和python双语言的学习(整数规划和0-1规划)
文章目录 前言一、整数规划和0-1规划二、典型示例1.背包问题2.指派问题 三、代码实现----Matlab1.Matlab 的 intlinprog 函数2.Matlab 代码背包问题指派问题 四、代码实现----python背包问题指派问题 总结 前言 通过模型算法,熟练对Matlab和python的应用。 学习视频…...
【连续4届EI检索,SPIE 出版】第五届信号处理与计算机科学国际学术会议(SPCS 2024,8月23-25)
第五届信号处理与计算机科学国际学术会议(SPCS 2024) 将于2024年8月23-25日在中国哈尔滨举行。会议主要围绕信号处理与计算机科学等研究领域展开讨论。 会议旨在为从事信号处理与计算机科学研究的专家学者、工程技术人员、技术研发人员提供一个共享科研成果和前沿技…...
Vue屏蔽Console.Log打印信息
Vue屏蔽打印信息 安装 npm install uglifyjs-webpack-plugin --save-dev 在vue.config.js文件或者webpack.prod.conf.js中配置 vue.config中 const UglifyJsPlugin require(uglifyjs-webpack-plugin) // 屏蔽打印数据 module.exports {optimization: {minimizer: [new Ugl…...
数据结构之《二叉树》(下)
在二叉树(中)了解了堆的相关概念后还实现了堆,并且还实现了堆排序,以及解决了TOP-K问题。接下来在本篇中将继续学习二叉树中的链式结构,会学习二叉树中的前、中、后三种遍历并实现链式结构的二叉树,接下来就开始本篇的学习吧&…...
用Python打造精彩动画与视频,9.3 项目案例分享与反思
第九章:综合项目 9.3 项目案例分享与反思 在本节中,我们将分享几个成功的项目案例,并进行反思总结。这些案例将展示如何将前面所学的Python技术运用于实际项目中,同时我们将讨论项目中的挑战和解决方案,以及从中得到…...
分布式主键 详解
文章目录 雪花算法结合分库分表的问题问题出现原因分析解决思路 分布式主键要考虑的问题主键生成策略雪花算法详解时间戳位问题工作进程位问题序列号位问题根据雪花算法扩展基因分片法 雪花算法结合分库分表的问题 问题出现 使用ShardingSphere框架自带的雪花算法生成分布式主…...
synchronzed为什么要升级为重量级锁,轻量级锁不好吗?
轻量级锁和重量级锁各有其适用场景和优缺点。轻量级锁旨在减少在无竞争情况下的同步开销,而重量级锁则在竞争激烈的情况下确保线程的同步。以下是为什么在某些情况下需要将轻量级锁升级为重量级锁的原因,以及轻量级锁的不足之处: 为什么需要…...
.NET 项目中发送电子邮件异步处理和错误机制的解决方案
在 .NET 中处理电子邮件,可以使用多种技术和库来实现高效的电子邮件发送、接收和管理。以下是一些常见的解决方案和最佳实践: 目录 1. 使用 SMTP 发送电子邮件 2. 使用 IMAP/POP3 接收电子邮件 3. 异步处理电子邮件 4. 处理大型邮件队列 5. 错误处…...
如何在银河麒麟操作系统上搭建 Electron (含 Electron 打包指南)
本次教程所用版本 Eletron版本:31.3.1 Electron-packager版本:17.1.2 VScode版本:1.92.0 Node版本:18.19.0 npm版本:10.2.3 前言: 随着跨平台应用开发的需求日益增长,Electron 和 Qt 成为…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
