Greedy algorithms 01

The original link

参 考 答 案 :

Leetcode-cn.com/problems/ju…

The code is as follows:

/* * Greedy algorithm * * pointer I goes through the array from beginning to end, assuming that the jump starts with each element * After each jump, find the farthest point that can jump, and record it with maxPosition, which is a variable. * If the pointer I traverses to the farthest point previously recorded (recorded with the boundary end), the boundary end is updated. * if the pointer I encounters the farthest point (end) before it encounters the farthest point (end) step++ * * Note: Pointer I can't iterate over the last element, because if you iterate over the previous element, you can jump to the last position. If you iterate over the last element, then step records one more step
class Solution {

//	public static void main(String[] args) {
// int[] kk = {2,3,1,1,4};
// System.out.println(Solution.jump(kk));
//	}

	public /* static */ int jump(int[] nums) {
	    int end = 0;
	    int maxPosition = 0; 
	    int steps = 0;
	    for(int i = 0; i < nums.length - 1; i++){
	        maxPosition = Math.max(maxPosition, nums[i] + i); // Look for the farthest jump
	        if( i == end){ 					// When a boundary is encountered, update the boundary and increment the number of steps by oneend = maxPosition; steps++; }}returnsteps; }}Copy the code