Leetcode3244. 新增道路查询后的最短距离 II

2024-09-02 10:12

本文主要是介绍Leetcode3244. 新增道路查询后的最短距离 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Every day a Leetcode

题目来源:3244. 新增道路查询后的最短距离 II

解法1:贪心

由于题目保证添加的边(捷径)不会交叉,从贪心的角度看,遇到捷径就走捷径是最优的。所有被跳过的城市都不可能再出现在最短路了,直接删除掉。

代码:

/** @lc app=leetcode.cn id=3244 lang=cpp** [3244] 新增道路查询后的最短距离 II*/// @lc code=start
class Solution
{
public:vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>> &queries){set<int> s; // 存储所有城市的编号// 将每个城市加入到 set 中for (int i = 0; i < n; i++)s.insert(i);vector<int> ans;for (vector<int> &q : queries){// [l, r) 之间的所有城市不可能在最短路里auto l = s.upper_bound(q[0]), r = s.lower_bound(q[1]);s.erase(l, r);// 剩余节点数减 1 即为当前的最短路径长度ans.push_back(s.size() - 1);}return ans;}
};
// @lc code=end

结果:

在这里插入图片描述

复杂度分析:

时间复杂度:O((n+q)logn),其中 q 是数组 queries 的长度。

空间复杂度:O(n)。

解法2:并查集

由于题目保证添加的边(捷径)不会交叉,从贪心的角度看,遇到捷径就走捷径是最优的。

把目光放在边上。

用并查集实现边的合并。初始化一个大小为 n−1 的并查集,并查集中的节点 i 表示题目的边 i→(i+1)。(相当于给每条边编号 0,1,2,…n−2。)

连一条从 L 到 R 的边,相当于把并查集中的节点 L,L+1,L+2⋯,R−2 合并到并查集中的节点 R−1 上。

合并的同时,维护并查集连通块个数。

答案就是每次合并后的并查集连通块个数。

// 并查集class Solution
{
public:vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>> &queries){vector<int> fa(n - 1);iota(fa.begin(), fa.end(), 0);// 非递归并查集auto find = [&](int x) -> int{int rt = x;while (fa[rt] != rt){rt = fa[rt];}while (fa[x] != rt){int tmp = fa[x];fa[x] = rt;x = tmp;}return rt;};vector<int> ans(queries.size());int cnt = n - 1; // 并查集连通块个数for (int qi = 0; qi < queries.size(); qi++){int l = queries[qi][0], r = queries[qi][1] - 1;int fr = find(r);for (int i = find(l); i < r; i = find(i + 1)){fa[i] = fr;cnt--;}ans[qi] = cnt;}return ans;}
};

结果:

在这里插入图片描述

复杂度分析:

时间复杂度:O(n+q),其中 q 是数组 queries 的长度。注意每个点只会被合并一次,在后面的循环中会被 i = find(l) 以及 i = find(i + 1) 跳过。由于数组的特殊性,每次合并的复杂度为 O(1)。

空间复杂度:O(n)。返回值不计入。

这篇关于Leetcode3244. 新增道路查询后的最短距离 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1129681

相关文章

浅谈mysql的sql_mode可能会限制你的查询

《浅谈mysql的sql_mode可能会限制你的查询》本文主要介绍了浅谈mysql的sql_mode可能会限制你的查询,这个问题主要说明的是,我们写的sql查询语句违背了聚合函数groupby的规则... 目录场景:问题描述原因分析:解决方案:第一种:修改后,只有当前生效,若是mysql服务重启,就会失效;

MySQL多列IN查询的实现

《MySQL多列IN查询的实现》多列IN查询是一种强大的筛选工具,它允许通过多字段组合快速过滤数据,本文主要介绍了MySQL多列IN查询的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录一、基础语法:多列 IN 的两种写法1. 直接值列表2. 子查询二、对比传统 OR 的写法三、性能分析与优化1.

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固 通俗易懂版)

《MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固通俗易懂版)》本文主要讲解了MySQL中的多表查询,包括子查询、笛卡尔积、自连接、多表查询的实现方法以及多列子查询等,通过实际例子和操... 目录复合查询1. 回顾查询基本操作group by 分组having1. 显示部门号为10的部门名,员

mysql关联查询速度慢的问题及解决

《mysql关联查询速度慢的问题及解决》:本文主要介绍mysql关联查询速度慢的问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql关联查询速度慢1. 记录原因1.1 在一次线上的服务中1.2 最终发现2. 解决方案3. 具体操作总结mysql

mysql线上查询之前要性能调优的技巧及示例

《mysql线上查询之前要性能调优的技巧及示例》文章介绍了查询优化的几种方法,包括使用索引、避免不必要的列和行、有效的JOIN策略、子查询和派生表的优化、查询提示和优化器提示等,这些方法可以帮助提高数... 目录避免不必要的列和行使用有效的JOIN策略使用子查询和派生表时要小心使用查询提示和优化器提示其他常

SQL 中多表查询的常见连接方式详解

《SQL中多表查询的常见连接方式详解》本文介绍SQL中多表查询的常见连接方式,包括内连接(INNERJOIN)、左连接(LEFTJOIN)、右连接(RIGHTJOIN)、全外连接(FULLOUTER... 目录一、连接类型图表(ASCII 形式)二、前置代码(创建示例表)三、连接方式代码示例1. 内连接(I

轻松上手MYSQL之JSON函数实现高效数据查询与操作

《轻松上手MYSQL之JSON函数实现高效数据查询与操作》:本文主要介绍轻松上手MYSQL之JSON函数实现高效数据查询与操作的相关资料,MySQL提供了多个JSON函数,用于处理和查询JSON数... 目录一、jsON_EXTRACT 提取指定数据二、JSON_UNQUOTE 取消双引号三、JSON_KE

查询SQL Server数据库服务器IP地址的多种有效方法

《查询SQLServer数据库服务器IP地址的多种有效方法》作为数据库管理员或开发人员,了解如何查询SQLServer数据库服务器的IP地址是一项重要技能,本文将介绍几种简单而有效的方法,帮助你轻松... 目录使用T-SQL查询方法1:使用系统函数方法2:使用系统视图使用SQL Server Configu