Jump Game II

Средняя№45

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

45 Jump Game IIРазбор · 1×

Пример: [2, 4, 1, 2, 3, 1, 1, 0]. end — самый дальний индекс, куда доходят сделанные прыжки, far — куда достанет ещё один. Дуга цвета i — самый длинный прыжок из i, дуга другого цвета — прыжок, который засчитываем, когда i доходит до end.

0214213243516170
пока недостижимдостижим за jumps прыжковнужен ещё прыжоктекущий индекс iпройден или цель

Прыжков пока нет

01/32
сначала · назад · пуск · шаг
Скорость
1function jump(nums):
2 jumps = 0
3 end = 0 // how far the jumps so far reach
4 far = 0 // how far one more jump reaches
5 for i from 0 to len(nums) - 2:
6 far = max(far, i + nums[i])
7 if i == end:
8 jumps = jumps + 1
9 end = far
10 return jumps
состояние
jumps
0
end
–
far
–
i
–
историянажмите шаг, чтобы вернуться

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

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

  1. Клетки до end — ровно те, до которых можно дойти за jumps прыжков, а клетки после end до far требуют ещё одного. Проход идёт по массиву отрезок за отрезком, как поиск в ширину, только без очереди.
  2. Из какой клетки будет следующий прыжок, решается только когда i дошёл до end: к этому моменту все клетки отрезка уже просмотрены, и far — самый дальний из их прыжков. Ничего не выбирается раньше, чем известны все варианты.
  3. Цикл кончается до последнего индекса: встать на него — значит дойти, а прыжок оттуда добавил бы лишний.

Сложность

Время O(n): один проход по массиву. Память O(1): только jumps, end и far.

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

Решить на LeetCode ↗

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