Учитывая массив целых чисел 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, который является ответом, и мы вернем шаги, то есть уровни.
Спасибо.