This is the sixth day of my participation in the August More text Challenge. For details, see: August More Text Challenge

preface

About the LeetCode array type problem related solutions, it can be seen that LeetCode array type problem before doing must see, classification solution summarized the problem, can be used to improve a single. If you think it is helpful, remember to give more likes and attention, thank you!

Topic describes

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

Example 2: Input: nums = [2,3,0,1,4] Output: 2

Link: leetcode-cn.com/problems/ju…

Answer key

This problem mainly uses the greedy algorithm, what is the greedy algorithm? Generally, the solution process is divided into several steps, but each step applies the greedy principle to select the best/optimal choice (the local most favorable choice) in the current state, and hope that the final stacking result is also the best/optimal solution. In short, it means minimizing the cost of the problem each time. This is a typical greedy algorithm. You can get a taste of the greedy algorithm in the following explanation.

  1. The backward greedy algorithm, which is basically we’re thinking backwards, assuming we’ve jumped to the last position, so the greedy algorithm is to find the element that can jump to the last position and is farthest from the last position. Once the element is found, the problem is narrowed down to how to jump to the current element with the minimum number of jumps. Because every time we find the element that jumps furthest to the last position, the final answer must be optimal. So there’s an element at index I and the farthest it can go is I + nums[I]. The specific code is as follows: time complexity O(n²), space complexity O(1)
/ * * *@param {number[]} nums
 * @return {number}* /
var jump = function(nums) {
   const n = nums.length 
   let last_position = n - 1
   let ans = 0
   while (last_position > 0) {
       // Find the furthest element that can reach the last position
       for (let i = 0; i < n; ++i) {
           if (i + nums[i] >= last_position) {
               last_position = i
               ++ans
               break}}}return ans
};
Copy the code
  1. In method 1, each time we loop through the element to find the furthest to the last position, and then update the last_position with the subscript of that element. In fact, we can go the farthest in the same number of steps by going forward, which is the optimal solution to this problem. How do you do that? Define two variables, currLastPosition and maxLastPosition, where currLastPosition is the farthest subscript we can reach with the current number of steps, MaxLastPosition is the farthest index we can reach with the number of steps increased by one. We just need to find the maximum maxLastPosition in the range of subindices that the current step can reach. When the current step reaches the currLastPosition, the step is increased by 1. Assign the value of maxLastPosition to currLastPosition and gradually update the value of maxLastPosition again until the last position. So that’s the whole process, the whole idea is how to get the most distance with the same number of steps. See the code for the specific algorithm. The time complexity is O(n), the space complexity is O(1)
/ * * *@param {number[]} nums
 * @return {number}* /
var jump = function(nums) {
    let i = 0
    let lastMaxPosition = 0
    let maxPosition = 0
    let step = 0
    for (let i = 0; i < nums.length - 1; i++) {
      // Update the maximum distance to be reached in the next step
      maxPosition = Math.max(maxPosition, i + nums[i])
      // Reach the current step furthest position
      if (i === lastMaxPosition) {
        step ++
        lastMaxPosition = maxPosition
      }
    }
    return step
};
Copy the code