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

Compared with the previous jump game, this topic is more difficult

Jump Game ii

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

Title description:

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

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

Your goal is to get to the last position in the array with the fewest hops.

Suppose you can always get to the last place in the array.

The sample

Example 1: Input: nums = [2,3,1,1,4] Output: 2

Explanation: The minimum number of jumps to the last position is 2. Jump from subscript 0 to subscript 1, one step, then three steps to the last position in the array.

Example 2: Input: nums = [2,3,0,1,4] Output: 2

Subject analysis

In this case, the jumps are the same as before, but consider the least number of jumps. In this case, the greedy way is to go from this jump point to the next point, the farthest point that the next point can reach, and choose the farthest point as the next point.

My own initial solution to this problem is to use recursion:

Define the recursive method jump, with two parameters, start is the jump point position, end is the current jump point can reach the boundary value. Step count for each jump +1. In the jump method, judge the next jump point according to the jump position and the end position. If the jump above the next jump point can be greater than or equal to the end position, the number of steps increases by 1 again to return to steps. Otherwise, the position of the next jump point and the maximum distance are passed into the jump, and the recursion continues until the end point is reached

var jump = function(nums) {
    if (nums.length <= 1) return 0;
    NeedDis end position steps Number of jump steps
    let needDis = nums.length - 1, steps = 0;
    function jump(start, end) {
        let maxDis = 0, curIndex = 0;
        steps ++;
        for(let i = start; i <= end; i++) { 
            if ( maxDis <= nums[i] + i ) {
                maxDis = nums[i] + i;
                curIndex = i;
            }
            if (maxDis >= needDis) {
                if(i ! =0) { steps ++; }
                returnsteps; }}return jump(curIndex, curIndex + nums[curIndex])
    }
    
    steps = jump(0, nums[0]);
    return steps;
};
Copy the code

Of course, I looked at other people’s solutions later, and suddenly my recursive solution didn’t smell good. The general idea is the same, but there is a gap in the code

That’s the same idea

let steps = 0, start = 0, end = 1;
while (end < nums.length) {
    let maxDis = 0;
    steps ++;
    for(let i = start; i < end; i++) {
        maxDis = Math.max(maxDis, i + nums[i]);  // The maximum distance that the current jump can reach
    }
    start = end;  // Start of the next jump range
    end = maxDis + 1; // The end of the next jump range
}
return steps;
Copy the code

It turns out that the internal I actually goes through every point, so we can simplify. Just update the maximum distance you can jump to the next time each step completes, and use that moment as the time to update the steps.

let steps = 0, maxDis = 0, end = 0, needDis = nums.length - 1;
for(let i = 0; i < needDis ; i++ ) {
    maxDis = Math.max(maxDis, i + nums[i]); 
    if( i == end ) { steps++; end = maxDis; }}return steps;
Copy the code

Here you can see that the big guys’ code execution efficiency and memory consumption is much better than my recursion, the solution is only the first step, if you can optimize the code better


Jumping Game ⅲ

Then strike while the iron is hot, continue to do a jumping game

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

Title description:

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.

The sample

Input: arr = [4,2,3,0,3,1,2], start = 5

Output: true,

Explanation: Arriving at subscript 3 with a value of 0 has the following possible scenarios

Scheme 1: subscript 5 -> subscript 4 -> subscript 1 -> subscript 3

Scheme 2: subscript 5 -> subscript 6 -> subscript 4 -> subscript 1 -> subscript 3

Subject analysis

In fact, the test is not greedy algorithm, but traversal method.

My solution is actually similar to the previous one, recursively (even if it is depth-first traversal, it is not necessary to solve recursively, because it is too efficient and consumes too much memory).

Sets the jump method, taking the current jump point position and the distance that the current jump point can jump.

  • Record the points that have been jumped as you jump
  • Determines whether the current jump point position exceeds the array
  • Whether the current jump point can jump left to right value is 0
  • If not, proceed with the jump, and the jump point is left and right (and the jump point is not recorded).
var canReach = function(arr, start) {
    if (arr[start] == 0) return true;
    let len = arr.length, hasPass = [];
    function jump(curPos, jumpDis) {
        hasPass.push(curPos);
        if (curPos > len && curPos < 0) {
            return false;
        } else {
            if (arr[curPos + jumpDis] == 0 || arr[curPos - jumpDis] == 0) { return true; } else {
                if (curPos + jumpDis <= len && hasPass.indexOf(curPos + jumpDis) == -1) {
                    let resr = jump(curPos + jumpDis, arr[curPos + jumpDis]);
                    if (resr) { return true; }}if (curPos - jumpDis >= 0 && hasPass.indexOf(curPos - jumpDis) == -1) {
                    let resl = jump(curPos - jumpDis, arr[curPos - jumpDis]);
                    if (resl) { return true; }}return false}}}let res = jump(start, arr[start]);
    return res;
};
Copy the code

Other people’s problems mostly use breadth traversal, so here I write breadth traversal again:

In fact, the breadth traversal is very simple, starting with the starting point and adding the starting point to the hasSteps and Queue array

  • Define two arrays, hasSteps for the queried array and Queue for the jump points group at the current breadth level
  • Queue array, while loop queue, queue[0] as the current jump, remove the last jump (Because the last digit must be the jump point on the next level)
  • Checks whether the current jump point value is 0, and returns true
  • Otherwise, add the next layer of the jump point to hasSteps and Queue, checking whether the jump point is out of range and has been queried before joining

Jump hierarchy diagram:

let hasSteps = [], queue = [];
hasSteps.push(start);
queue.push(start);
while( queue.length > 0) {
    let curIndex = queue[0];
    queue.shift();  // Remove the last jump point
    if (arr[curIndex] == 0) return true;
    let left = curIndex - arr[curIndex], right = curIndex + arr[curIndex];
    if ( left >= 0 && hasSteps.indexOf(left) == -1 ) {
        hasSteps.push(left);
        queue.push(left)
    }
    if (right < arr.length && hasSteps.indexOf(right) == -1) { hasSteps.push(right); queue.push(right); }}return false;
Copy the code