This is the 12th day of my participation in the August More Text Challenge. For details, see:August is more challenging

preface

Force 45 jump game II as follows:

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 position.

Your goal is to get to the last position in the array with the least number of jumps.

Suppose you can always get to the end of the array.

Example 1:

Input: NUMs = [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to the last position is 2. Jump one step from index 0 to index 1, then three steps to the last position in the array.Copy the code

Example 2:

Input: NUMs = [2,3,0,1,4] Output: 2Copy the code

Tip:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000

A, thinking

This is a problem that I initially thought was a greedy algorithm, taking a large value in the reachable range, all the way to the end of the array. Until test cases beat me TNT for the umpteenth time

The next position is: the distance traveled + the maximum distance traveled

Nums = [4, 3, 1, 1, 2, 1, 1]

Do you know what the right jump path is? Answer: 4 -> 2 -> 1

Why not select nums[1] = 3 for the first jump?

  • Because if you choose4 - > 3For this path, the distance traveled is zero1-0 = 1, the distance traveled isnums[1] = 3, and for1 + 3 = 4
  • And choose4 - > 2This path, the distance traveled is zero4-0 = 4, the distance traveled isnums[4] = 2, and for4 + 2 = 6
  • Obviously choose4 - > 2Can go further!

For example

Here, nums = [4, 3, 1, 1, 2, 1, 1] is used as an example

  1. i=1, the available range isnums[1] ~ nums[4], after the maximum distance screening, the final selectionnums[4] = 2, the jump path is4 - > 2
  2. To the next starting position,i=4, the optional range isnums[5] ~ nums[6], after the maximum distance screening, the final selectionnums[6] = 1, the jump path is4 -> 2 -> 1
  3. Returns the number of selections3Can be

Second, the implementation

The implementation code

The implementation code is consistent with the idea

    /** * Greedy algorithm *@param nums
     * @return* /
    public int jump(int[] nums) {
        if (nums.length == 1)
            return 0;
        int ret = 0;
        int len = nums.length;
        // From front to back
        out:for (int i=0; i<len;) {
            int n = nums[i];
            int next = -1;   // The next position is: distance traveled + maximize distance traveled
            for (int j=i+1; j<n+i+1; j++) {
                if (j == len -1) {
                    ret ++;
                    break out;
                }
                if (next == -1) {
                    next = j;
                    continue;
                }
                int currentDistance = (j-i) + nums[j];  // The current distance sum
                int nextDistance = (next-i) + nums[next];   // Next distance sum
                if (currentDistance > nextDistance) {
                    next = j;
                }
            }
            ret ++;
            i = next;
        }
        return ret;
    }
Copy the code

The test code

    public static void main(String[] args) {
        int[] nums = {4.1.1.3.1.1.1};
        new Number45().jump(nums);
    }
Copy the code

The results of

Third, summary

Thank you for seeing the end, it is my great honor to help you ~♥