Topic describes

leetcode45

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. Description:

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

solution

Greedy algorithm

Characteristics of greedy algorithms

1. Greedy choice The global optimal solution of a problem can be reached through a series of choices of local optimal solutions, and each choice can depend on previous choices, but not on the choices to be made later. That’s the greedy selection property. For a specific problem, to determine whether it has the property of greedy choice, it must be proved that the greedy choice made in each step leads to the overall optimal solution of the problem.

2. Optimal substructure Properties When the optimal solution of a problem contains the optimal solution of its subproblems, the problem is said to have optimal substructure properties. The property of optimal substructure is the key to solve the problem by greedy method. In practical application, as for what kind of problem has what kind of greedy choice nature is uncertain, need to be analyzed on a case-by-case basis

Analysis of the subject

We want to find the lowest number of hops to the last position in the array, which is obviously the optimal solution, so let’s think about the 🤔 subproblem, which is where I am at each jump, which is obviously the optimal solution.

At this point we are satisfied with the optimal solution and the optimal solution of the subproblem, so let’s think of a problem like this: I can jump two places at zero, but it’s obviously better to jump to one. So the optimal solution for me to jump at my current location is the maximum distance that I can choose to jump to the next location at my current location, that is, every time we jump to A, a has the highest value.

The above case solution

Subscript 0 – can jump to 1 and 2, but we chose 1 because 1 can jump further

code

class Solution {
    public int jump(int[] nums) {
        int maxLength = 0;
        int end = 0;
        int step = 0;
        for(int i = 0; i<nums.length-1; i++){
            // We find the maximum value of the index of the jumping position in each loop. This is the process of finding the optimal solution
            maxLength = Math.max(maxLength,i+nums[i]);
            // A loop index equal to end indicates that we have traversed all jump possibilities at this position and found the optimal solution
            if(i==end){ end = maxLength; step++; }}returnstep; }}Copy the code

reference

Leetcode official solution