Задача: 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 {
    func minJumps(_ arr: [Int]) -> Int {
        let n = arr.count
        if n <= 1 { return 0 }

        var graph = [Int: [Int]]()
        for i in 0..<n {
            graph[arr[i], default: []].append(i)
        }

        var curs = [0]
        var visited = Set([0])
        var step = 0

        while !curs.isEmpty {
            var nex = [Int]()

            for node in curs {
                if node == n - 1 { return step }

                for child in graph[arr[node], default: []] {
                    if !visited.contains(child) {
                        visited.insert(child)
                        nex.append(child)
                    }
                }

                graph[arr[node]] = []

                if node + 1 < n && !visited.contains(node + 1) {
                    visited.insert(node + 1)
                    nex.append(node + 1)
                }
                if node - 1 >= 0 && !visited.contains(node - 1) {
                    visited.insert(node - 1)
                    nex.append(node - 1)
                }
            }

            curs = nex
            step += 1
        }

        return -1
    }
}

Ставь 👍 и забирай 📚 Базу знаний