Задача
Дан целочисленный массив nums. Вначале мы находимся на первом индексе массива, и каждое значение в массиве представляет максимальную длину прыжка с этой позиции.
Нужно вернуть true, если мы можем достичь последний индекс, иначе false.
Пример 1:
nums = [2,3,1,1,4]
Результат: true
Прыжок на 1 шаг с индекса 0 до 1, затем прыжок на 3 шага до последнего индекса.
Пример 2:
nums = [3,2,1,0,4]
Результат: false
Вы всегда окажетесь на индексе 3, независимо от выбора. Максимальная длина прыжка на этом индексе — 0, что делает невозможным достижение последнего индекса.
Ссылка на leetcode: https://leetcode.com/problems/jump-game
Решение
Решение описал тут: Jump Game
Код решения:
public boolean canJump(int[] nums) {
int goal = nums.length - 1;
for (int i = nums.length - 2; i >= 0; i--) {
if (i + nums[i] >= goal) {
goal = i;
}
}
return goal == 0;
}Смотри также разбор 44 других типичных алгоритмических задач в FAANG: https://t.me/faangmaster/648
