This is the 23rd day of my participation in the First Challenge 2022

The title

1306. Jumping Game III

So here’s an array of non-negative integers, arr, and you start at the start index of that array. When you’re at subscript I, you can jump to I + arr[I] or I – arr[I].

Determine if you can jump to any index of the corresponding element with a value of 0.

Note that in any case, you can’t jump out of the array.

 

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5 output: true Subscript 5 -> subscript 4 -> subscript 1 -> subscript 3 5 -> subscript 6 -> subscript 4 -> subscript 1 -> subscript 3Copy the code

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0 Output: true Description: Subscript 3 with the value of 0 has the following possible solutions: subscript 0 -> subscript 4 -> subscript 1 -> subscript 3Copy the code

Example 3:

Input: arr = [3,0,2,1,2], start = 2 output: false description: cannot reach subscript 1 of 0.Copy the code

 

Tip:

  • 1 <= arr.length <= 5 * 10^4
  • 0 <= arr[i] < arr.length
  • 0 <= start < arr.length

Train of thought

First we need to write a method to perform the jump. Each time a node is reached, we need to discuss the classification:

  • If the current value is 0, then we have found the destination and return true;

  • Before jumping to the left, we need to judge whether the jumping position of the element is beyond the range of our index. The index value of the left boundary is 0. If the jumping position of the index is greater than or equal to 0, it means that we can jump to the left. ,

  • Before jumping to the right, we also judge whether the position of the element jumping out is beyond the boundary. The index value of the right boundary is N-1. If the position of the index after jumping is less than N, it means that we can jump to the right and judge the result of jumping.

  • To prevent an infinite loop, we need to use an array index that ever jump to record each element, the initial value of 0, when the value changes into 1, each jump and then jump to the left and right before we judge the next node first before we have visited, came if you don’t have to jump in the past;

  • Finally, we try every possible way to jump to the left, and if we can’t jump out, we try every possible way to jump to the right, and we try both ways and it doesn’t work.

implementation

/ * * *@param {number[]} arr
 * @param {number} start
 * @return {boolean}* /
var canReach = function(arr, start) {
    const n = arr.length;
    // Record whether each node has jumped
    const list = new Array(n).fill(0);

    // Execute the jump method
    function findNextIndex(arr, start) {
        // If we find the node we want, we don't need to jump
        if (arr[start] === 0) {
            return true;
        }

        // The current coordinate is marked, we have been, to prevent repeated jumps
        list[start] = 1;

        // If the jump to the left does not exceed the boundary, and the left foot we have not been to, then jump to see
        if (
            start - arr[start] >= 0 
            && list[start - arr[start]] === 0 
            && findNextIndex(arr, start - arr[start])
        ) {
            return true;
        }

        // The same logic applies to jumping to the right
        if (
            start + arr[start] < n
            && list[start + arr[start]] === 0 
            && findNextIndex(arr, start + arr[start])
        ) {
            return true;
        }

        // I tried to go left and right, but nothing worked
        return false;
    }

    return findNextIndex(arr, start);
};
Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.