Сложность: medium
Дан массив
nums, где nums[i] — максимальная длина прыжка из позиции i. Нужно определить, можно ли добраться до последнего индекса. Пример:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Прыгаем 1 шаг с `0` на `1`, затем 3 шага на последний индекс.
👨💻 Алгоритм:
1⃣Завести переменную maxReach— максимальное положение, до которого можно допрыгнуть.
2⃣Идти по массиву, обновляясь maxReachна каждом шаге.
3⃣Если текущий индекс рассчитывается maxReach— путь прерывается, иначе возвращается true при выполнении конца.
😎 Решение:
public class Solution {
public bool CanJump(int[] nums) {
int maxReach = 0;
for (int i = 0; i < nums.Length; i++) {
if (i > maxReach) return false;
maxReach = Math.Max(maxReach, i + nums[i]);
if (maxReach >= nums.Length - 1) return true;
}
return false;
}
}Ставь 👍 и забирай 📚 Базу знаний