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索引的优化之LIKE模糊查询功能实现

《MySQL索引的优化之LIKE模糊查询功能实现》:本文主要介绍MySQL索引的优化之LIKE模糊查询功能实现,本文通过示例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录一、前缀匹配优化二、后缀匹配优化三、中间匹配优化四、覆盖索引优化五、减少查询范围六、避免通配符开头七、使用外部搜索引擎八、分

SQL表间关联查询实例详解

《SQL表间关联查询实例详解》本文主要讲解SQL语句中常用的表间关联查询方式,包括:左连接(leftjoin)、右连接(rightjoin)、全连接(fulljoin)、内连接(innerjoin)、... 目录简介样例准备左外连接右外连接全外连接内连接交叉连接自然连接简介本文主要讲解SQL语句中常用的表

MySQL高级查询之JOIN、子查询、窗口函数实际案例

《MySQL高级查询之JOIN、子查询、窗口函数实际案例》:本文主要介绍MySQL高级查询之JOIN、子查询、窗口函数实际案例的相关资料,JOIN用于多表关联查询,子查询用于数据筛选和过滤,窗口函... 目录前言1. JOIN(连接查询)1.1 内连接(INNER JOIN)1.2 左连接(LEFT JOI

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2

MySQL中的交叉连接、自然连接和内连接查询详解

《MySQL中的交叉连接、自然连接和内连接查询详解》:本文主要介绍MySQL中的交叉连接、自然连接和内连接查询,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、引入二、交php叉连接(cross join)三、自然连接(naturalandroid join)四

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》:本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》:本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的

浅谈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. 不同操作