Java | LeetCode
Задача: 1345. Jump Game IV
Сложность: hard
Дан массив целых чисел arr, изначально вы находитесь на первом индексе массива.
За один шаг вы можете прыгнуть с индекса i на индекс:
- i + 1, где: i + 1 < arr.length.
- i - 1, где: i - 1 >= 0.
- j, где: arr[i] == arr[j] и i != j.
Вернуть минимальное количество шагов, чтобы достичь последнего индекса массива.
Обратите внимание, что нельзя прыгать за пределы массива в любой момент времени.
Пример:
Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.
👨💻 Алгоритм:
1⃣Построить граф, где ключи - значения из массива, а значения - списки индексов этих значений. Начать с первого индекса, добавив его в очередь текущего слоя и инициализировать набор посещенных индексов.
2⃣Выполнять BFS: для каждого индекса текущего слоя проверять соседние индексы (i + 1, i - 1 и все j, где arr[i] == arr[j]), добавляя непосещенные индексы в очередь следующего слоя.
3⃣Повторять шаг 2, увеличивая счетчик шагов до достижения последнего индекса или пока не закончится очередь.
😎 Решение:
class Solution {
public int minJumps(int[] arr) {
int n = arr.length;
if (n <= 1) {
return 0;
}
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++) {
graph.computeIfAbsent(arr[i], v -> new LinkedList<>()).add(i);
}
List<Integer> curs = new LinkedList<>();
curs.add(0);
Set<Integer> visited = new HashSet<>();
int step = 0;
while (!curs.isEmpty()) {
List<Integer> nex = new LinkedList<>();
for (int node : curs) {
if (node == n - 1) {
return step;
}
for (int child : graph.get(arr[node])) {
if (!visited.contains(child)) {
visited.add(child);
nex.add(child);
}
}
graph.get(arr[node]).clear();
if (node + 1 < n && !visited.contains(node + 1)) {
visited.add(node + 1);
nex.add(node + 1);
}
if (node - 1 >= 0 && !visited.contains(node - 1)) {
visited.add(node - 1);
nex.add(node - 1);
}
}
curs = nex;
step++;
}
return -1;
}
}
Ставь 👍 и забирай 📚 Базу знаний
1 · 269 ·