Jump Game

Средняя№55

Вы стоите на первой клетке массива. Каждое число — самый длинный прыжок из его клетки, прыгать короче тоже можно. Получится ли добраться до последней клетки? Наш пример: [1, 4, 2, 0, 0, 3, 0, 1] — да: 0 → 1 → 5 → 7. Нули на индексах 3 и 4 не мешают: их можно перепрыгнуть.

55 Jump GameРазбор · 1×

Пример: [1, 4, 2, 0, 0, 3, 0, 1]. reach — самый дальний индекс, до которого точно можно дойти; дуга — самый длинный прыжок из i.

0114223040536071
пока недостижимдостижимтекущий индекс iпройден или цель

Цель — индекс 7: last = 7

01/27
сначала · назад · пуск · шаг
Скорость
1function canJump(nums):
2 last = len(nums) - 1
3 reach = 0
4 for i from 0 to last:
5 if i > reach:
6 return false
7 reach = max(reach, i + nums[i])
8 if reach >= last:
9 return true
состояние
last
7
reach
–
i
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. На любой индекс до reach можно встать: прыжок до reach можно оборвать где угодно. Поэтому хватает одного числа, а не множества клеток.
  2. Клетка с 0 — тупик, только если её никто не перепрыгивает. Самый дальний reach по всем пройденным клеткам обходит её всякий раз, когда это вообще возможно.
  3. Если i оказался дальше reach, ни одна клетка до i так далеко не прыгает, а после i ничего не достижимо, и ответ — false. Как только reach накрыл последний индекс, ответ — true, остаток массива уже не важен.

Сложность

Время O(n): один проход, и он может закончиться раньше. Память O(1): только reach и i.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.