Leetcode--45. jumping game II (greed)

1. Title Description

difficulty ： difficult

2. Topic analysis

The subject is LeetCode55. Jump algorithm An advanced version of , There are several points to note ：

• Suppose you can always reach the last position of the array
• Use the least number of jumps

There are two ways to do it ：

• Maximum crossing point algorithm
  Find the point with the lowest subscript that can reach the last element , That is, it can reach the maximum point of the spanning degree of the last element . Then start at this point , Continue to find the point with the smallest subscript that can reach this point , Know that the subscript of the found point is 0, That is, the first place of the array . The best time complexity is O(n), The worst case scenario is O(n^2)
• Greedy Algorithm
  Traversing the array from left to right , Calculate the maximum distance that can be reached at each step , And update the maximum distance value . When the subscript of traversal is equal to the maximum distance , It means that you should take a step at this time , Until we're done traversing the array . The time complexity is O(n)

3. C Language implementation

3.1 Maximum crossing point algorithm

The code is as follows ：

//  Find the maximum crossing point 
int findMaxPoint(int* nums, int index){
    
    int i;
    for(i = 0; i < index; i++){
    
        if(nums[i]>= index-i)
            return i;
    }
    return i;
}
int jump(int* nums, int numsSize){
    
    int i, index, count;
    index = numsSize-1;
    count = 0;
    if(numsSize == 1) return 0;
    while(index != 0){
    
        index = findMaxPoint(nums, index);
        count++;
    }
    return count;
}

The running result is ：

3.2 Greedy Algorithm

The code is as follows ：

int jump(int* nums, int numsSize){
    
	// ans For the number of times to jump  
    int ans = 0;
    // end So far , The largest point that the previous element can reach 
    int end = 0;
    // maxPos Is the maximum value that is constantly updated 
    int maxPos = 0;
    for (int i = 0; i < numsSize - 1; i++)
    {
    
        maxPos = nums[i]+i>maxPos?nums[i]+i:maxPos;
        //  When the subscript of traversal encounters end when , It means it's time to jump ,ans Add one 
        if (i == end)
        {
    
            end = maxPos;
            ans++;
        }
    }
    return ans;
}

The running result is ：