(Greedy) leetcode 55. 45. Jump Game I II

Title: The index from the array is Starting at 0, the number of steps that can be jumped at the current index is stored in the array, such as arr[0] = 2, which means that indexes 1 and 2 can be reached from index 0. Ask whether the final index can be reached at the end.

Idea: Use reach: to record the farthest position that can be reached from the current position (counting from 0) to take the maximum value that can be reached each time.

class Solution {

public:

 bool canJump(vector<int>& nums) {

 if(nums.size()<2< span style="color: #000000;">)

 return true;

 int reach = 0; //reach: record the farthest position that can be reached from the current position

 for(int i=0; i<=reach && ii){

 reach = max(reach, i+nums[i]);

 if(reach >= nums.size()-1) //Able to reach the end of the line

 return true ;

}

 return false;

}

};

Question meaning: return the minimum number of steps to reach the final position.

class Solution {

public:

 int jump(vector<int>& nums) {

 if(nums.empty() || nums.size() <=1)

 return 0;

 //cur_max: the farthest position that the current position can reach, next_max: the farthest position that can be reached in the next step

 int cur_max = 0, next_max = 0, step = 0, index = 0 ;

 while(index <= cur_max){



 while(index <= cur_max){

 //Calculate the maximum position that can be reached in each step span>

 next_max = max(next_max, index+nums[index]);

 index ++;

}

 cur_max = next_max;

 step ++;

 if(cur_max >= nums.size()-1)

 return step;

}

 return 0;

}

};

class Solution {

public:

 bool canJump(vector<int>& nums) {

 if(nums.size()<2< span style="color: #000000;">)

 return true;

 int reach = 0; //reach: record the farthest position that can be reached from the current position

 for(int i=0; i<=reach && ii){

 reach = max(reach, i+nums[i]);

 if(reach >= nums.size()-1) //Able to reach the end of the line

 return true ;

}

 return false;

}

};

class Solution {

public:

 int jump(vector<int>& nums) {

 if(nums.empty() || nums.size() <=1)

 return 0;

 //cur_max: the farthest position that the current position can reach, next_max: the farthest position that can be reached in the next step

 int cur_max = 0, next_max = 0, step = 0, index = 0 ;

 while(index <= cur_max){



 while(index <= cur_max){

 //Calculate the maximum position that can be reached in each step span>

 next_max = max(next_max, index+nums[index]);

 index ++;

}

 cur_max = next_max;

 step ++;

 if(cur_max >= nums.size()-1)

 return step;

}

 return 0;

}

};