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 成为…...
《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
