您的位置:首页 > 房产 > 建筑 > 建网站的公司赚钱吗_莱芜网络小说作家_如何快速推广网站_百度快照替代

建网站的公司赚钱吗_莱芜网络小说作家_如何快速推广网站_百度快照替代

2024/12/23 9:09:46 来源:https://blog.csdn.net/sinat_41679123/article/details/144076548  浏览:    关键词:建网站的公司赚钱吗_莱芜网络小说作家_如何快速推广网站_百度快照替代
建网站的公司赚钱吗_莱芜网络小说作家_如何快速推广网站_百度快照替代

Description

You are given an integer n and a 2D integer array queries.

There are n cities numbered from 0 to n - 1. Initially, there is a unidirectional road from city i to city i + 1 for all 0 <= i < n - 1.

queries[i] = [ui, vi] represents the addition of a new unidirectional road from city ui to city vi. After each query, you need to find the length of the shortest path from city 0 to city n - 1.

There are no two queries such that queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1].

Return an array answer where for each i in the range [0, queries.length - 1], answer[i] is the length of the shortest path from city 0 to city n - 1 after processing the first i + 1 queries.

Example 1:

Input: n = 5, queries = [[2,4],[0,2],[0,4]]Output: [3,2,1]Explanation:

在这里插入图片描述

After the addition of the road from 2 to 4, the length of the shortest path from 0 to 4 is 3.

在这里插入图片描述

After the addition of the road from 0 to 2, the length of the shortest path from 0 to 4 is 2.

在这里插入图片描述

After the addition of the road from 0 to 4, the length of the shortest path from 0 to 4 is 1.

Example 2:

Input: n = 4, queries = [[0,3],[0,2]]Output: [1,1]Explanation:

在这里插入图片描述

After the addition of the road from 0 to 3, the length of the shortest path from 0 to 3 is 1.

在这里插入图片描述

After the addition of the road from 0 to 2, the length of the shortest path remains 1.

Solution

Similar to 3243. Shortest Distance After Road Addition Queries I, but this time with more data and an additional rule: no overlapped queries.

So we have a tricky way to solve this, because we don’t have overlapped queries, so we could just drop the nodes between each query. And the length of the graph would be our answer.
Here we use a hash map to denote the graph.

Time complexity: o ( n + q ) o(n+q) o(n+q)
Space complexity: o ( n ) o(n) o(n)

Code

class Solution:def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:neighbors = {i: i + 1 for i in range(n - 1)}res = []for each_query in queries:start_city, end_city = each_query# if start_city is in the graph and the new query gives us a shorter wayif start_city in neighbors and neighbors[start_city] < end_city:cur_city = neighbors[start_city]while cur_city < end_city:cur_city = neighbors.pop(cur_city)neighbors[start_city] = end_cityres.append(len(neighbors))return res

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com