: hard
Дан массив routes, представляющий автобусные маршруты, где routes[i] - это автобусный маршрут, который i-й автобус повторяет бесконечно.
Например, если routes[0] = [1, 5, 7], это означает, что 0-й автобус путешествует в последовательности 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... бесконечно.
Вы начинаете на автобусной остановке source (вы изначально не находитесь в автобусе) и хотите добраться до автобусной остановки target. Перемещаться между автобусными остановками можно только на автобусах.
Верните наименьшее количество автобусов, которые вам нужно взять, чтобы доехать от source до target. Верните -1, если это невозможно.
Пример:
Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
C# решение
сопоставлено/оригиналpublic class Solution {
public int NumBusesToDestination(int[][] routes, int source, int target) {
if (source == target) return 0;
var adjList = new Dictionary<int, List<int>>();
for (int route = 0; route < routes.Length; route++) {
foreach (int stop in routes[route]) {
if (!adjList.ContainsKey(stop)) {
adjList[stop] = new List<int>();
}
adjList[stop].Add(route);
}
}
var q = new Queue<int>();
var vis = new HashSet<int>();
foreach (int route in adjList.GetValueOrDefault(source, new List<int>())) {
q.Enqueue(route);
vis.Add(route);
}
int busCount = 1;
while (q.Count > 0) {
int size = q.Count;
for (int i = 0; i < size; i++) {
int route = q.Dequeue();
foreach (int stop in routes[route]) {
if (stop == target) return busCount;
foreach (int nextRoute in adjList.GetValueOrDefault(stop, new List<int>())) {
if (!vis.Contains(nextRoute)) {
vis.Add(nextRoute);
q.Enqueue(nextRoute);
}
}
}
}
busCount++;
}
return -1;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int NumBusesToDestination(int[][] routes, int source, int target) {
if (source == target) return 0;
var adjList = new unordered_map<int, List<int>>();
for (int route = 0; route < routes.size(); route++) {
foreach (int stop in routes[route]) {
if (!adjList.count(stop)) {
adjList[stop] = new List<int>();
}
adjList[stop].push_back(route);
}
}
var q = new queue<int>();
var vis = new HashSet<int>();
foreach (int route in adjList.GetValueOrDefault(source, new List<int>())) {
q.Enqueue(route);
vis.push_back(route);
}
int busCount = 1;
while (q.size() > 0) {
int size = q.size();
for (int i = 0; i < size; i++) {
int route = q.Dequeue();
foreach (int stop in routes[route]) {
if (stop == target) return busCount;
foreach (int nextRoute in adjList.GetValueOrDefault(stop, new List<int>())) {
if (!vis.Contains(nextRoute)) {
vis.push_back(nextRoute);
q.Enqueue(nextRoute);
}
}
}
}
busCount++;
}
return -1;
}
}Java решение
сопоставлено/оригиналclass Solution {
public int numBusesToDestination(int[][] routes, int source, int target) {
if (source == target) return 0;
Map<Integer, List<Integer>> adjList = new HashMap<>();
for (int route = 0; route < routes.length; route++) {
for (int stop : routes[route]) {
adjList.computeIfAbsent(stop, k -> new ArrayList<>()).add(route);
}
}
Queue<Integer> q = new LinkedList<>();
Set<Integer> vis = new HashSet<>();
for (int route : adjList.getOrDefault(source, Collections.emptyList())) {
q.add(route);
vis.add(route);
}
int busCount = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int route = q.poll();
for (int stop : routes[route]) {
if (stop == target) {
return busCount;
}
for (int nextRoute : adjList.getOrDefault(stop, Collections.emptyList())) {
if (!vis.contains(nextRoute)) {
vis.add(nextRoute);
q.add(nextRoute);
}
}
}
}
busCount++;
}
return -1;
}JavaScript решение
сопоставлено/оригиналvar numBusesToDestination = function(routes, source, target) {
if (source === target) return 0;
const adjList = new Map();
routes.forEach((stops, route) => {
stops.forEach(stop => {
if (!adjList.has(stop)) {
adjList.set(stop, []);
}
adjList.get(stop).push(route);
});
});
const q = [];
const vis = new Set();
(adjList.get(source) || []).forEach(route => {
q.push(route);
vis.add(route);
});
let busCount = 1;
while (q.length > 0) {
const size = q.length;
for (let i = 0; i < size; i++) {
const route = q.shift();
for (const stop of routes[route]) {
if (stop === target) return busCount;
for (const nextRoute of (adjList.get(stop) || [])) {
if (!vis.has(nextRoute)) {
vis.add(nextRoute);
q.push(nextRoute);
}
}
}
}
busCount++;
}
return -1;Python решение
сопоставлено/оригиналclass Solution:
def numBusesToDestination(self, routes, source, target):
if source == target:
return 0
from collections import defaultdict, deque
adjList = defaultdict(list)
for route, stops in enumerate(routes):
for stop in stops:
adjList[stop].append(route)
q = deque()
vis = set()
for route in adjList[source]:
q.append(route)
vis.add(route)
busCount = 1
while q:
for _ in range(len(q)):
route = q.popleft()
for stop in routes[route]:
if stop == target:
return busCount
for nextRoute in adjList[stop]:
if nextRoute not in vis:
vis.add(nextRoute)
q.append(nextRoute)
busCount += 1
return -1Go решение
сопоставлено/оригиналfunc numBusesToDestination(routes [][]int, source int, target int) int {
if source == target {
return 0
}
adjList := make(map[int][]int)
for route, stops := range routes {
for _, stop := range stops {
adjList[stop] = append(adjList[stop], route)
}
}
q := []int{}
vis := make(map[int]bool)
for _, route := range adjList[source] {
q = append(q, route)
vis[route] = true
}
busCount := 1
for len(q) > 0 {
size := len(q)
for i := 0; i < size; i++ {
route := q[0]
q = q[1:]
for _, stop := range routes[route] {
if stop == target {
return busCount
}
for _, nextRoute := range adjList[stop] {
if !vis[nextRoute] {
vis[nextRoute] = true
q = append(q, nextRoute)
}
}
}
}
busCount++
}
return -1
}Algorithm
1⃣Верните 0, если source и target совпадают. Инициализируйте пустую карту adjList, чтобы хранить ребра, где ключ - это автобусная остановка, а значение - список целых чисел, обозначающих индексы маршрутов, которые имеют эту остановку. Инициализируйте пустую очередь q и неупорядоченное множество vis, чтобы отслеживать посещенные маршруты. Вставьте начальные маршруты в очередь q и отметьте их посещенными в vis.
2⃣Итерация по очереди, пока она не пуста: извлеките маршрут из очереди, итерируйтесь по остановкам в маршруте. Если остановка равна target, верните busCount. В противном случае, итерируйтесь по маршрутам для этой остановки в карте adjList, добавьте непосещенные маршруты в очередь и отметьте их посещенными.
3⃣Верните -1 после завершения обхода в ширину (BFS).
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.