Jumping game ii[greedy practice]

Preface

For the problem of finding the minimum and maximum , Generally, it can be associated with greed , For example, find the minimum number of steps , You can find the longest distance you can walk every step , To achieve the minimum number of steps .

One 、 Jumping game II

Two 、 Practice greedy thinking

1、 Large top heap priority queue

//  Jumping game II
public class Jump {
    
    /* target： How many steps can you take to the last position .  Find the farthest you can reach with each step , When go n The maximum distance of steps is greater than nums.length when , Is the minimum number of steps . The longest distance minimizes the number of steps . */
    public int jump(int[] nums) {
    
        if (nums.length == 1) return 0;
        //  Big pile top .
        PriorityQueue<int[]> que = new PriorityQueue<>((o1, o2) -> o2[0] + o2[1] - o1[0] - o1[1]);
        que.offer(new int[]{
    0, nums[0]});
        int cnt = 1;
        while (!que.isEmpty()) {
    
            int[] arr = que.poll();
            if (arr[0] + arr[1] >= nums.length - 1) return cnt;
            for (int i = arr[0] + 1; i <= arr[0] + arr[1] && i < nums.length; i++) {
    
                que.offer(new int[]{
    i, nums[i]});
            }
            ++cnt;
        }
        return cnt;
    }
}

2、 improvement – Record the maximum value

//  Record the farthest position of the jump , There is no need to use a priority queue every time offer all logn
class Jump2 {
    
    /* target： How many steps can you take to the last position .  Find the farthest you can reach without taking a step , When go n The maximum distance of steps is greater than nums.length when , Is the minimum number of steps . The longest distance minimizes the number of steps . */
    public int jump(int[] nums) {
    
        if (nums.length == 1) return 0;
        // max( Subscript  +  Jump steps )
        int[] maxDis = new int[]{
    0, nums[0]};
        int cur = 1;
        int cnt = 1;
        while (true) {
    
            if (maxDis[0] + maxDis[1] >= nums.length - 1) return cnt;
            int end = maxDis[0] + maxDis[1];
            while (cur <= end) {
    
                if (cur + nums[cur] > maxDis[0] + maxDis[1]) {
    
                    maxDis[0] = cur;
                    maxDis[1] = nums[cur];
                }
                ++cur;
            }
            ++cnt;
        }
    }
}

summary

1） greedy , Looking for the smallest , We must stride forward , Want to 100 Good performance in meters , To run faster .

reference

[1] LeetCode Jumping game II