45. Игра в прыжки II (Jump Game II)

Задание.

Вам дается 0-индексированный массив целых чисел 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].

Пример 1.

Входные данные: nums = [2,3,1,1,4]

Результат: 2

Пояснение: Минимальное количество переходов для достижения последнего индекса равно 2. Перейдите на 1 шаг от индекса 0 к 1, затем на 3 шага к последнему индексу.

Пример 2.

Входные данные: nums = [2,3,0,1,4]

Результат: 2

Решение.

class Solution {
public:
    int jump(vector<int>& nums) {
        int len = nums.size();
        if(len == 1){
            return 0;
        }
        int max = 0;
        int curr = 0;
        int count = 0;
        for(int i = 0 ; i < len - 1 ; i++) {
            if(i + nums[i] > max) {
                max = i + nums[i];
            }
            if(curr == i) {
                curr = max;
                count++;
            }
            if(curr >= len-1) {
                break;
            }
        }

        return count;
    }
};

Способ решения

Используются указатели:

• curr – для отслеживания текущей максимально достижимой позиции

• max – для отслеживания следующей максимально достижимой позиции.

Переменная count отслеживает количество прыжков, сделанных на данный момент.

На каждой итерации цикла for код обновляет max до максимума текущего max и достижимой позиции из текущего элемента i + nums[i].

Если curr достиг i, код обновляет curr до max и увеличивает count на 1. Если curr становится больше последнего индекса массива, функция возвращает count.

Пример: nums = [3,4,2,1,1,3,5,2,1]

лучший прыжок: 0 -> 1 -> 5 -> 8