Вопрос

В этой статье мы рассмотрим вопрос Leetcode ’55. Игра в прыжки». Этот вопрос является классической проблемой. Это проблема жадного алгоритма или проблема динамического программирования, в зависимости от вашей точки зрения.

Вопрос:

Вам дан целочисленный массив nums. Изначально вы располагаетесь на первом индексе массива, и каждый элемент массива представляет собой вашу максимальную длину прыжка на этой позиции.
Возвращается true, если вы можете достичь последнего индекса, или false в противном случае.

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Объяснение вопроса

Этот вопрос оценивается как средний. Я бы сказал, что это верно, если вы используете метод жадного алгоритма. Если же вы используете метод динамического программирования, то этот вопрос можно считать трудным. В этом вопросе мы будем использовать метод жадного алгоритма.

Нас просят сделать переход от индекса 0 к последнему индексу массива. Где каждый индекс представляет собой расстояние, на которое он может прыгнуть. Так, если вы находитесь на индексе со значением 2, вы можете прыгнуть на 2 индекса вперед (или на 1, если хотите). Эта проблема сначала кажется тривиальной: перебрать все пути, и если мы достигнем последнего индекса, то все будет кончено. Что означает, что это почти проблема графа. Хотя, это не самый эффективный способ решения этой проблемы. Это время O(n^n), это ужасно медленно.

Вместо этого мы воспользуемся методом жадности и решим эту задачу за время O(n).

Рекомендуемые знания

1. Массив
2. Жадный алгоритм
3. Большая нотация O

Что мы знаем?

1. Нам дан массив неотрицательных целых чисел.
2. Каждый index представляет собой расстояние, на которое мы можем прыгнуть, нам нужно прыгнуть до последнего индекса.

Как мы собираемся это сделать:

Изначально вы можете подумать: «Ну, начиная с индекса 0, продолжаем прыгать, пока не достигнем последнего индекса, и возвращаемся назад по недействительному пути». Это решение грубой силы, решение динамического программирования, которое очень похоже на решение задачи о графе с обратным ходом.

Вместо этого мы изменим логику, вместо того чтобы начинать с индекса 0, почему бы не начать с последнего индекса? У нас будет столб цели, который изначально является последним индексом, цель столба цели — достичь индекса 0. Мы будем перебирать массив в обратном порядке, спрашивая: «Может ли этот элемент допрыгнуть до столба ворот?» Если да, то этот элемент становится новым столбом ворот, потому что он может до него допрыгнуть. Мы продолжаем делать это до тех пор, пока не пройдем весь массив. Если мы достигли первого индекса, мы можем перепрыгнуть к последнему индексу, если столба ворот нет, мы не можем перепрыгнуть к нему.

1. Мы инициализируем столб ворот, который изначально является последним индексом.
2. Мы создадим цикл For Loop, который будет итерировать массив в обратном направлении.
3. Мы спрашиваем каждый элемент: «Можете ли вы отсюда перепрыгнуть к стойке ворот или через нее?» Если да, то мы устанавливаем стойку ворот на этот элемент.
4. Если нет, мы продолжаем цикл.
5. Мы повторяем эту логику до тех пор, пока не пройдем весь массив.
6. Находится ли штанга ворот на первом индексе? Если да, то мы можем перейти к последнему индексу, если нет, то мы не можем перейти к нему.

Нотация Big O:

• Временная сложность: O(n)| Где n — длина массива.
• Сложность пространства: O(1)| Поскольку мы никогда не выделяем дополнительную память.

Решение для Python

class Solution:
    def canJump(self, nums: List[int]) -> bool:

        goal_post = len(nums) - 1

        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= goal_post:
                goal_post = i

        return (goal_post == 0)

Решение на Java

class Solution {
    public boolean canJump(int[] nums) {

        int goal_post = nums.length - 1;

        for (int i = nums.length - 1; i >= 0; i--) {
            int jump_distance = i + nums[i];
            if (jump_distance >= goal_post) {
                goal_post = i;
            }
        }

        return (goal_post == 0) ? true : false;
    }
}

Решение на C++

class Solution {
public:
    bool canJump(vector<int>& nums) {

        int goal_post = nums.size() - 1;

        for (int i = nums.size() - 1; i >= 0; i--) {
            int jump_distance = i + nums[i];
            if (jump_distance >= goal_post){
                goal_post = i;
            }
        }

        return (!goal_post) ? true : false;
    }
};

Решение на Javascript

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function (nums) {

    let goal_post = nums.length - 1;

    for (let i = nums.length - 1; i >= 0; i--) {
        const jump_distance = i + nums[i];
        if (jump_distance >= goal_post) {
            goal_post = i;
        }
    }

    return !goal_post ? true : false;
};