Сложность: 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.
😎 Решение:
var jump = function (nums) {
let answer = 0,
n = nums.length;
let curEnd = 0,
curFar = 0;
for (let i = 0; i < n - 1; ++i) {
curFar = Math.max(curFar, i + nums[i]);
if (i === curEnd) {
++answer;
curEnd = curFar;
}
}
return answer;
};Ставь 👍 и забирай 📚 Базу знаний