Код Middle Жадные обновлено
Можно ли дойти до конца
Условие
В массиве на каждой позиции - максимальная длина прыжка. Можно ли дойти с первой позиции до последней?
Примеры
canJump([2, 3, 1, 1, 4]) // true
canJump([3, 2, 1, 0, 4]) // false
canJump([0]) // true
Как подойти
Жадность вместо динамики: достаточно одной величины - максимального достижимого индекса. O(n) времени, O(1) памяти. Проверку i > reach надо делать до обновления, иначе застрявший ноль пройдёт.
Подсказки: 2
- Веди самую дальнюю достижимую позицию.
- Если текущий индекс её обогнал - дальше пути нет.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.