Nuggets team number online, help you Offer impromptu! Click for details

preface

Yesterday did the jump game, mainly shared the greedy algorithm to solve the problem ideas, today to jump together. It is still a greedy algorithm problem, the idea is probably the same as before, not much to say, directly on the topic.

Topic describes

Given an array of non-negative integers, 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.

Example:

Input: [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. Copy the codeCopy the code

Note: Assume you can always reach the last position in the array.

Source: LeetCode link: leetcode-cn.com/problems/im… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

The difference between this problem and yesterday’s jump game is that yesterday we had to decide whether we could jump to the last coordinate, which is possible by default. Next, a simple analysis of the solution to this problem.

It is still a greedy algorithm, each time in the jump range can choose to jump further position. As shown in the figure, the solid line represents the jump range of the current coordinate, and the dotted line represents the furthest distance that the jump range coordinate can jump. For the current coordinates, the jump range is 2 and 3. But because the three can jump further out to the two. And the 2 can only go up to the 1, so go up to the 3.

So if you jump to 3, you can jump to 1, 5, 2, and obviously 5 can go the farthest, so you can jump to 5. The minimum number of steps is 2.

If we define a variable maxLength to maintain the current maximum jump distance. We also define a variable border to represent the current bounding range. Because you can always skip to the end. That is, when the current jump range is traversed. The new leapable range is the current border to maxLength, which indicates that it has been skipped, so increase the number of steps. We assign maxLength to border. If you repeat this logic, the border must be greater than or equal to the length of the array until the last time.

The final code

class Solution {
    
    public int jump(int[] nums) {
        int border = 0;
        int maxLength = 0; 
        int steps = 0;
        for(int i = 0; i < nums.length - 1; i++){
            maxLength = Math.max(nums[i] + i,maxLength); 
            if( i == border){ border = maxLength; steps++; }}returnsteps; }}Copy the code

conclusion

This is a typical greedy algorithm. A typical greedy algorithm obtains a global optimal solution from a local optimal solution. The time complexity of the solution is O(n). But we need to pay attention to one detail in this case, because the first hop is guaranteed to count once, so when I ==0, we set border to 0. The second point is that we are done when we jump to the last element of num[]. If we loop with I < nums.length, if we skip to the last element, we still satisfy the current element. In this case I == border is still counted once. So you need to control the cycle conditions.

This article is participating in “Digging gold in April 2021 swipe card”, click to see the activity details. Give it a thumbs up if you like.