This is the fifth day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

Today’s brush problem training is still done in Leetcode, continue to greedy algorithm practice.

Jumping games

Subject address: leetcode-cn.com/problems/ju…

Given an array of non-negative integers, nums, you start at the first index of the array.

Each element in the array represents the maximum length you can jump at that location.

Determine if you can reach the last index.

The sample

Example 1:

Nums = [2,3,1,1,4] output: true

Explanation: you can jump 1 step from subscript 0 to subscript 1, and then jump 3 steps from subscript 1 to the last subscript.

Example 2:

Input: nums = [3,2,1,0,4

Explanation: no matter what, it always gets to the position of subscript 3. But this subscript has a maximum jump length of 0, so you can never reach the last subscript.

In this case, if you follow the normal idea of walking one step at a time, if you don’t succeed, go back and take another route. (Of course you can do this, but it’s a brute force solution, and there’s some recursion involved.)

So in the face of this kind of problem, we need to clarify the logic and find ideas.

In this case, you can think backwards, because you want to get to the end point, so you can go from the end point, you just need to find the index plus the number of steps that you can take off is greater than or equal to the end point.

If the index of the current array element is less than or equal to maxDis, then this point can be used as the starting point.

Answer:

var canJump = function(nums) {
   if (nums.length <= 1) return true;
    let maxDis = 0, needDis = nums.length - 1;  // maxDis Specifies the maximum distance from the needDis endpoint
   
    for(let i = 0; i < needDis; i++) {
        if (i <= maxDis) {  // Jump point position <= maximum distance
            maxDis = maxDis > nums[i] + i ? maxDis : nums[i] + i;
            if (needDis <= maxDis) {
                return true; }}}return false;
};
Copy the code

The maximum distance maxDis is also dynamically changing so that all jump points can be tried. This problem in leetcode jumping game should be the easiest one, the later variations on this problem will be more troublesome.