Java | LeetCode
Задача: 815. Bus Routes
Сложность: 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.
👨💻 Алгоритм:
1⃣Верните 0, если source и target совпадают. Инициализируйте пустую карту adjList, чтобы хранить ребра, где ключ - это автобусная остановка, а значение - список целых чисел, обозначающих индексы маршрутов, которые имеют эту остановку. Инициализируйте пустую очередь q и неупорядоченное множество vis, чтобы отслеживать посещенные маршруты. Вставьте начальные маршруты в очередь q и отметьте их посещенными в vis.
2⃣Итерация по очереди, пока она не пуста: извлеките маршрут из очереди, итерируйтесь по остановкам в маршруте. Если остановка равна target, верните busCount. В противном случае, итерируйтесь по маршрутам для этой остановки в карте adjList, добавьте непосещенные маршруты в очередь и отметьте их посещенными.
3⃣Верните -1 после завершения обхода в ширину (BFS).
😎 Решение:
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;
}
Ставь 👍 и забирай 📚 Базу знаний
1 · 432 ·