力扣题解3243 新增道路查询后的最短距离 I

embedded/2024/11/20 7:43:36/

题目:

给你一个整数 n 和一个二维整数数组 queries。

有 n 个城市,编号从 0 到 n - 1。初始时,每个城市 i 都有一条单向道路通往城市 i + 1( 0 <= i < n - 1)。

queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后,你需要找到从城市 0 到城市 n - 1 的最短路径的长度。

返回一个数组 answer,对于范围 [0, queries.length - 1] 中的每个 i,answer[i] 是处理完前 i +1 个查询后,从城市 0 到城市 n - 1 的最短路径的长度。
在这里插入图片描述
在这里插入图片描述

1. 题目重述及关键字提取

题目重述:
给定一个整数 n 和一个二维整数数组 queries,表示有 n 个城市,城市编号从 0n - 1。每个城市 i 有一条单向道路通往城市 i + 1。对于每个查询 queries[i] = [ui, vi],意味着新建一条从城市 ui 到城市 vi 的单向道路。每次查询后,需要计算从城市 0 到城市 n - 1 的最短路径长度,并返回这些长度的数组。

关键字提取:

  • 城市 (cities)
  • 单向道路 (directed roads)
  • 最短路径 (shortest path)
  • 查询 (queries)
  • 数组结果 (result array)

2. 解题思路与分析

方法一:广度优先遍历 (BFS)

思路:
广度优先搜索是解决最短路径问题的有效方式,尤其是在图的边权均为 1 的情况下(每条边的权重相同)。首先,构建一个图结构来表示城市和道路,然后从城市 0 开始进行 BFS,记录到每个城市的最短距离。

步骤:

  1. 初始化一个图的邻接表。
  2. 将初始的单向道路添加到图中。
  3. 对于每个查询,将新道路添加到图中。
  4. 使用 BFS 从城市 0 开始,寻找最短路径到城市 n - 1
  5. 返回每一步的最短路径长度。
C++代码(广度优先搜索)
vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {unordered_map<int, vector<int>> graph;// Initialize the graph with initial roadsfor (int i = 0; i < n - 1; ++i) {graph[i].push_back(i + 1);}vector<int> answer;for (auto& query : queries) {int u = query[0], v = query[1];graph[u].push_back(v);  // Add the new road// BFS to find the shortest path from 0 to n-1vector<int> dist(n, -1);dist[0] = 0;queue<int> q;q.push(0);while (!q.empty()) {int node = q.front(); q.pop();for (int neighbor : graph[node]) {if (dist[neighbor] == -1) {  // Not visiteddist[neighbor] = dist[node] + 1;q.push(neighbor);}}}answer.push_back(dist[n - 1]);}return answer;
}
Java代码(广度优先搜索)
public class Solution {public int[] shortestDistanceAfterQueries(int n, int[][] queries) {Map<Integer, List<Integer>> graph = new HashMap<>();// Initialize the graph with initial roadsfor (int i = 0; i < n - 1; i++) {graph.putIfAbsent(i, new ArrayList<>());graph.get(i).add(i + 1);}int[] answer = new int[queries.length];for (int i = 0; i < queries.length; i++) {int u = queries[i][0], v = queries[i][1];graph.putIfAbsent(u, new ArrayList<>());graph.get(u).add(v);  // Add the new road// BFS to find the shortest path from 0 to n-1int[] dist = new int[n];Arrays.fill(dist, -1);dist[0] = 0;Queue<Integer> queue = new LinkedList<>();queue.add(0);while (!queue.isEmpty()) {int node = queue.poll();for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {if (dist[neighbor] == -1) {  // Not visiteddist[neighbor] = dist[node] + 1;queue.add(neighbor);}}}answer[i] = dist[n - 1];}return answer;}
}
方法二:动态规划 (Dynamic Programming)

思路:
在动态规划中,我们维护一个数组 dpdp[i] 表示从城市 0 到城市 i 的最短距离。初始时,起点城市 0 的距离设置为 0,其他城市的距离设置为无穷大(表示尚未到达)。通过逐步处理每个查询,我们可以利用新添加的道路更新各个城市的最短距离。

步骤:

  1. 初始化 dp 数组:

    • 创建一个大小为 n 的数组 dp,初始化为无穷大(numeric_limits<int>::max())。
    • 设置 dp[0] = 0,表示从城市 0 到自身的距离为 0
  2. 初始化前驱信息:

    • 为了便于后续更新,维护一个二维数组 prevprev[i] 存储所有可以到达城市 i 的前驱城市。
    • 对于每个城市 i(从 1n-1),将城市 i-1 添加为它的前驱,并初始设置 dp[i] = i,这代表最坏情况下通过 i-1 次到达城市 i
  3. 处理每个查询:

    • 对于每个查询 [u, v],将城市 u 添加到城市 v 的前驱列表 prev[v] 中,表示新建了从 uv 的单向道路。
  4. 状态转移:

    • 从城市 v 开始,遍历城市 w(从 vn-1),对于每个城市 w,检查其所有前驱城市 u(从 prev[w] 中获取)。
    • 通过公式 dp[w] = min(dp[w], dp[u] + 1) 更新城市 w 的最短距离。此步骤确保在新道路添加后,所有通过该新道路可到达的城市的最短路径都得到更新。
  5. 记录结果:

    • 在处理完每个查询后,将当前城市 n-1 的最短距离 dp[n - 1] 添加到结果数组 res 中。如果 dp[n - 1] 仍然为无穷大,表示不可达,返回 -1
  6. 返回结果:

    • 返回所有查询的结果数组 res,其中每一项表示在当前查询后从城市 0 到城市 n - 1 的最短距离。
C++代码(动态规划)
vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>> &queries) {  vector<vector<int>> prev(n);  vector<int> dp(n, numeric_limits<int>::max());  // 使用无穷大进行初始化  dp[0] = 0;  // 起点到自身的距离为0  // 初始填充前驱信息  for (int i = 1; i < n; i++) {  prev[i].push_back(i - 1);  dp[i] = i; // 最坏情况是 n-1 步到达 i  }  vector<int> res;  // 处理每个查询  for (auto &query : queries) {  int u = query[0], v = query[1];  prev[v].push_back(u); // 更新前驱  // 状态转移  for (int w = v; w < n; w++) {  for (int u : prev[w]) {  dp[w] = min(dp[w], dp[u] + 1);  }  }  // 记录到最后一座城市的距离  res.push_back(dp[n - 1] != numeric_limits<int>::max() ? dp[n - 1] : -1);  }  return res;  }  
Java代码(动态规划)
public int[] shortestDistanceAfterQueries(int n, int[][] queries) {  List<List<Integer>> prev = new ArrayList<>();  for (int i = 0; i < n; i++) {  prev.add(new ArrayList<>());  }  int[] dp = new int[n];  Arrays.fill(dp, Integer.MAX_VALUE); // 使用无穷大进行初始化  dp[0] = 0; // 起点到自身的距离为0  // 初始填充前驱信息  for (int i = 1; i < n; i++) {  prev.get(i).add(i - 1);  dp[i] = i; // 最坏情况是 n-1 步到达 i  }  int[] res = new int[queries.length];  // 处理每个查询  for (int i = 0; i < queries.length; i++) {  int u = queries[i][0], v = queries[i][1];  prev.get(v).add(u); // 更新前驱  // 状态转移  for (int w = v; w < n; w++) {  for (int j : prev.get(w)) {  dp[w] = Math.min(dp[w], dp[j] + 1);  }  }  // 记录到最后一座城市的距离  res[i] = dp[n - 1] != Integer.MAX_VALUE ? dp[n - 1] : -1;  }  return res;  }

3. 总结分析

广度优先遍历 (BFS) 与动态规划 (Dynamic Programming):

  • 广度优先遍历:

    • BFS 适用于图的最短路径问题,尤其是所有边的权值相同的情况。通过逐层遍历,可以有效找到从起点到终点的最短路径。
  • 动态规划:

    • 动态规划适合在路径长度需要动态更新的情况下,通过不断维护到达每个节点的最小路径,还可以在每次查询后直接更新结果。

http://www.ppmy.cn/embedded/139010.html

相关文章

【前端学习笔记】Javascript学习二(运算符、数组、函数)

一、运算符 运算符&#xff08;operator&#xff09;也被称为操作符&#xff0c;是用于实现赋值、比较和执行算数运算等功能的符号。 JavaScript中常用的运算符有&#xff1a; 算数运算符、递增和递减运算符、比较运算符、逻辑运算符、赋值运算符 算数运算符&#xff1a; 、-…

刷题训练之深搜(DFS)-----(二叉树的所有路径,全排列,子集)

二叉树的所有路径 给你一个二叉树的根节点 root &#xff0c;按 任意顺序 &#xff0c;返回所有从根节点到叶子节点的路径。 题目分析&#xff1a; 题目要我们找到一个课的所有路径&#xff0c;就是要找到从根节点到每一个叶子节点的路径 终止条件就是当遇到叶子节点的时候 用…

【RabbitMQ】10-抽取MQ工具

1. Nacos共享配置 shared-mq.yaml spring:rabbitmq:host: ${hm.mq.host:*.*.*.*} # 你的虚拟机IPport: ${hm.mq.port:5672} # 端口virtual-host: ${hm.mq.vhost:/hmall} # 虚拟主机username: ${hm.mq.un:hmall} # 用户名password: ${hm.mq.pw:***} # 密码2. Common包下引入依…

Flutter开发者进阶:接入安卓原生页面

Flutter开发者进阶&#xff1a;接入安卓原生页面 前言 在 Flutter APP 的开发过程中&#xff0c;有时不仅需要使用 Flutter 提供的组件&#xff0c;还需要使用原生的组件。 例如在对接外部 SDK 时&#xff0c;如果自己重新实现 SDK 的逻辑&#xff0c;无疑是本末倒置。 在这…

多邻国网页版怎么登录?

我之前一直用APP&#xff0c;最近才发现还有多邻国网页版&#xff0c;感觉网页版的多邻国使用感觉比APP舒服好多&#xff0c;而且很多功能只有网页版才有&#xff0c;多邻国网页版登录其实很简单&#xff0c;直接在官网www.duolingo.cn登录就可以。 一、多邻国是什么&#xff1…

Java项目实战II基于微信小程序的私家车位共享系统(开发文档+数据库+源码)

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。获取源码联系方式请查看文末 一、前言 在城市化进…

算法——环形链表(leetcode141)

判断一个链表是否是环形链表&#xff0c;这题可以用快慢指针来解决&#xff0c;首先令快慢指针fastIndex、slowIndex等于head头节点,接着来一个循环 循环体是fastIndex步进两个单位slowIndex步进一个单位判断如果slowIndex等于fastIndex则是有环 因为fastIndex走的比slowIndex快…

华为VPN技术

1.启动设备 2.配置IP地址 [FW1]int g1/0/0 [FW1-GigabitEthernet1/0/0]ip add 192.168.1.254 24 [FW1-GigabitEthernet1/0/0]int g1/0/1 [FW1-GigabitEthernet1/0/1]ip add 100.1.1.1 24 [FW1-GigabitEthernet1/0/1]service-manage ping permit [FW2]int g1/0/0 [FW2-Gi…