Учитывая массив целых чисел arr, вы изначально позиционируетесь в первом индексе массива.

За один шаг вы можете перейти от индекса i к индексу:

  • i + 1 где: i + 1 < arr.length.
  • i - 1 где: i - 1 >= 0.
  • j где: arr[i] == arr[j] и i != j.

Возвращает минимальное количество шагов для достижения последнего индекса массива.

Обратите внимание, что вы не можете выйти за пределы массива в любое время.

Пример 1:

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 <= arr.length <= 5 * 104
  • -108 <= arr[i] <= 108

Решение:

Это сложный вопрос о литкоде. Честно говоря, я не смог решить ее самостоятельно, и мне пришлось прибегнуть к помощи друзей и некоторых редакций. Но теперь я думаю, что мне совершенно ясно, как это решить. Итак, начнем.

В нем говорится, что мы можем перейти от индекса i к:
: i+1, если он находится в границах массива
: i -1, если он находится в границах массива
: j , где arr[i] == arr[j] и i != j

Таким образом, мы видим, что это проблема исследования, и мы должны вернуть минимальное количество шагов, чтобы достичь последнего индекса. Поскольку требуется минимальный индекс, мы можем исследовать все возможные сценарии, используя поиск в ширину, где каждый уровень будет действовать как один шаг. Это главное, что нужно знать при использовании BFS. Каждый уровень действует как один шаг. А так как все сценарии для одного шага исследуются на первом уровне, мы можем быть уверены, что получаем правильный ответ. Теперь перейти к i+1 и i-1 легко, просто перейдите на один индекс вперед и назад, если он находится в границах массива. Но добраться до j не так просто. Мы всегда можем пройтись по массиву, чтобы узнать, по какому индексу arr[i] == arr[j], но это отнимает много времени. Итак, мы создадим словарь, хэш-карту для хранения всех индексов arr[i] == arr[j], то есть индексов одинаковых элементов в массиве. В примере для aray = [100, -23, -23, 404, 100, 23, 23, 23, 3, 404] хэш-карта будет {100: [0, 3], -23: [1, 2], 404: [3, 9], 23: [5, 6, 7], 3: [8]}.

Теперь мы можем найти индексы для всех трех условий за время O(1). Мы начнем с узла 0, поскольку ограничения говорят, что у нас будет хотя бы один элемент. Мы будем поддерживать посещенный набор, чтобы не посещать уже посещенные индексы. Также поддерживается переменный шаг для хранения количества шагов, и, поскольку каждый уровень в BFS означает один шаг, переход обновляется, когда один уровень полностью завершен. А чтобы не делать лишние поиски, мы также удалим элементы с карты, как только мы ее используем. Давайте посмотрим код:

from collections import deque
def minJumps(self, arr: List[int]) -> int:
    hash_map = {} // indexes of same element in array
    for i in range(len(arr)):
        if arr[i] not in hash_map:
            hash_map[arr[i]] = []
        hash_map[arr[i]].append(i)
    visited = {0} # maintain nodes visited
    q = deque()
    q.append(0) #it will maintain all nodes in one level
    steps = 0
    while q:
        nx = deque() # at each level, we will create the queue for next level by adding all legal elements we get from 3 conditions.
        for node in q:
            if node == len(arr) - 1: return steps
            back = node - 1
            front = node + 1
            if 0 <= back < len(arr) and back not in visited:
                nx.append(back)
                visited.add(back)
            if 0 <= front < len(arr) and front not in visited:
                visited.add(front)
                nx.append(front)
            for same_node in hash_map[arr[node]]:
                if same_node not in visited:
                    visited.add(same_node)
                    nx.append(same_node)
            hash_map[arr[node]].clear()
            q = nx
        steps += 1
    return -1

Это довольно просто после того, как мы получим детали. Сначала мы создаем хэш-карту, затем мы создаем первый уровень вручную как [0]. Пройдите все элементы на текущем уровне и для каждого узла на уровне попробуйте все 3 условия. Проверьте, можем ли мы перейти к i+1 или к i-1. А затем проверьте, можем ли мы перейти к индексам того же элемента в массиве. Поскольку мы прошли все те же элементы для ex-›, как мы прошли все 100, присутствующие в массиве, поэтому мы очищаем этот массив, чтобы уменьшить избыточность. И затем продолжаем обход, пока не получим node == i-1, который является ответом, и мы вернем шаги, то есть уровни.

Спасибо.