Make writing a habit together! This is the 15th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

Jump game I

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.

Example 1:

Enter: nums = [2.3.1.1.4] output:trueExplanation: You can jump first1Step from the subscript0Reach the subscript1And then we go from the subscript1 跳 3Step to the last subscript.Copy the code

Example 2:

Enter: nums = [3.2.1.0.4] output:falseExplanation: No matter what, it always reaches subscript3The location of the. But the maximum jump length of this subscript is0So you can never get to the last index.Copy the code

leetcode

1, analysis,

The figure wants to jump from position 0 to position N-1, and the value in the array represents the maximum number of steps that can be jumped

Array subscript conversion problem, set a variable Max, representing the largest position can jump to the right

2, implementation,

public static boolean canJump(int[] nums) {
    if (nums == null || nums.length < 2) {
        return true;
    }
    // Max represents the maximum position to jump to the right
    int max = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (i > max) {
            return false;
        }
        max = Math.max(max, i + nums[i]);
    }
    return true;
}
Copy the code

Jump game II

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.

Example 1:

Enter: nums = [2.3.1.1.4] output:2Explanation: The minimum number of jumps to the last position is2. From the subscript for0Skip to subscript1The position of jump1Step, then jump3Step to the last position in the array.Copy the code

Example 2:

Enter: nums = [2.3.0.1.4] output:2
Copy the code

leetcode

1, analysis,

Number of jumps: not the meaning of a jump step, such as the meaning of the longest jump in 1 step.

Set three variables: step number of jump steps, cur Which step is the furthest you can jump to within the current jump steps, and next which step is the furthest you can jump to next

A few steps to the right (cur) and one more jump to the right (next)

The initial values of step, cur, and next are as follows:

0 step jump step=0, can reach the right position cur=0, in the jump step can reach the right position next=arr[0]

  • Step: the current minimum number of jumping steps can reach I position
  • Cur: Jump no more than a step to the right
  • Next: jump the number of steps not more than step+1, the most right can be reached

I > cur, step is not enough to go to I, step++, increase the number of steps (jump number), cur = next, frankly, next is prepared in advance, in case the next step fails to cover, next will give cur

Next (next = Max (next, I +arr[I])); next = Max (next, I +arr[I])

2, implementation,

public static int jump(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int step = 0;
    int cur = 0;
    int next = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (cur < i) {
            step++;
            cur = next;
        }
        next = Math.max(next, i + arr[i]);
    }
    return step;
}
Copy the code

Jump Game III

So here’s an array of non-negative integers, arr, and you start at the start index of that array. When you are 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 = 5Output:trueExplanation: The arrival value is0The subscript3There are the following possible scenarios: subscript5- > subscript4- > subscript1- > subscript3The subscript5- > subscript6- > subscript4- > subscript1- > subscript3
Copy the code

Example 2:

Input: arr = [4.2.3.0.3.1.2], start = 0Output:trueExplanation: The arrival value is0The subscript3There are the following possible scenarios: subscript0- > subscript4- > subscript1- > subscript3
Copy the code

Example 3:

Input: arr = [3.0.2.1.2], start = 2Output:falseDescription: Cannot reach a value of0The subscript1Place.Copy the code

leetcode

1, analysis,

Now, when I get to I, there are only two choices, jump to the left or jump to the right, like a binary tree.

What width-first traversal does: a binary tree, with two branches that can either go left or right

  • Key: array subscript, value: layer number
  • Go heavy, record the decisions that go through

2, implementation,

public static boolean canReach(int[] arr, int start) {
    if (arr == null || start < 0 || start > arr.length - 1) {
        return false;
    }
    // Implement width first traversal through queues
    Queue<Integer> queue = new LinkedList<>();
    // iterate through the layers
    HashMap<Integer, Integer> levelMap = new HashMap<>();
    queue.add(start);
    levelMap.put(start, 0);
    while(! queue.isEmpty()) {int cur = queue.poll();
        int level = levelMap.get(cur);
        if (cur + arr[cur] < arr.length && arr[cur + arr[cur]] == 0) {
            return true;
        } else {
            int left = cur - arr[cur];
            if (left >= 0 && !levelMap.containsKey(left)) {
                queue.add(left);
                levelMap.put(left, level + 1);
            }
            int right = cur + arr[cur];
            if(right < arr.length && ! levelMap.containsKey(right)) { queue.add(right); levelMap.put(right, level +1); }}}return false;
}
Copy the code