Даны положительное целое число N и массив из N целых чисел A[]. Каждый элемент массива обозначает максимальную длину прыжка, которую вы можете преодолеть. Узнайте, сможете ли вы добраться до последнего индекса, если начнете с первого индекса списка.
Я думаю, большинству из нас задавали этот вопрос (или с небольшой поправкой) на этапе кодирования. Сегодня мы попытаемся решить этот вопрос самым простым способом, который я могу объяснить.
Прежде всего, мы должны получить понимание проблемы, и для этого мы должны рассмотреть рисунок ниже.
На рисунке видно, что в массиве каждый индекс показывает число, которое говорит нам, на сколько шагов мы можем перейти от этого конкретного индекса. Скажем, по индексу 1 у нас есть значение 2; это означает, что мы можем перейти на два шага дальше от индекса 1, то есть до индекса 1+2=3. И, таким образом, следуя этому вычислению по всему массиву, мы должны вычислить, можно ли достичь конца массива или нет.
Давайте напишем код…
Для этого нам нужно взять две переменные: maxReachдля расчета максимальной достижимости по индексу i и >текущий, чтобы вести запись того, где мы можем достичь максимума из текущего индекса.
Теперь мы будем перебирать массив, чтобы вычислить упомянутые выше переменные. Во-первых, мы рассчитаем maxReach, получив максимальное значение между maxReach и суммой индекса и максимально возможного перейти от этого индекса (i + A[i]). Так как у нас есть maxReach, теперь мы посчитаем то, где мы можем достичь максимума из текущего индекса. Для этого мы проверим, равен ли current i, если да, то обновим текущийсо следующим максимально достижимым индексом, например maxReach.
После завершения итерации у нас будет максимально достижимый индекс в current. Если это больше или равно последнему индексу массива, то мы успешны и вернем true, иначе false.
Сложность:
Общая временная сложность для этого метода составляет O(N), потому что мы прошли весь массив один раз, длина которого равна N. В то время как пространственная сложность для этого будет O(1), потому что мы использовали две дополнительные переменные, которые будут занимать постоянное место.
Для получения полного исходного кода посетите репозиторий Github.
Спасибо, что прочитали.
