Сложность: medium
Вам дан массив целых чисел nums с индексацией с нуля и длиной n. Изначально вы находитесь в позиции nums[0].
Каждый элемент nums[i] представляет максимальную длину прыжка вперед с индекса i. Другими словами, если вы находитесь в nums[i], вы можете прыгнуть на любой nums[i + j], где:
0 <= j <= nums[i] и
i + j < n
Верните минимальное количество прыжков, чтобы достичь nums[n - 1]. Тестовые случаи сгенерированы таким образом, что вы можете достичь nums[n - 1].
Пример:
Input: nums = [2,3,0,1,4]
Output: 2
👨💻 Алгоритм:
1⃣Инициализируйте curEnd = 0, curFar = 0 и количество прыжков как answer = 0.
2⃣Итерируйтесь по массиву nums. Для каждого индекса i наибольший индекс, до которого мы можем добраться из i, равен i + nums[i]. Обновите curFar = max(curFar, i + nums[i]).
3⃣Если i = curEnd, это означает, что текущий прыжок завершен, и следует перейти к следующему прыжку. Увеличьте answer и установите curEnd = curFar как наибольшее расстояние, которое мы можем преодолеть следующим прыжком. Повторите с шага 2.
😎 Решение:
function jump($nums) {
$answer = 0;
$n = count($nums);
$curEnd = 0;
$curFar = 0;
for ($i = 0; $i < $n - 1; ++$i) {
$curFar = max($curFar, $i + $nums[$i]);
if ($i === $curEnd) {
++$answer;
$curEnd = $curFar;
}
}
return $answer;
}Ставь 👍 и забирай 📚 Базу знаний