Leetcode-Jump Game II

Nov 18, 2013

题目描述

• Given an array of non-negative integers, you are initially positioned at the first index of the array.

• Each element in the array represents your maximum jump length at that position.

• Your goal is to reach the last index in the minimum number of jumps.

• For example: Given array A = [2,3,1,1,4]

• The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

AC代码

#include <iostream>
#include <cstdio>

using namespace std;

//从第一个数开始，从它的所有可能性中选择可以跳的最远的那个点，跳到那个点，继续上述过程。
int jump(int A[], int n)
{
    	int curmax = 0,nextmax = 0, count = 0;
    	for(int i = 0; i < n; i++)
	{
		if(i  > curmax)
		{
			curmax = nextmax;
			count++;
		}
		nextmax = nextmax > (A[i] + i) ? nextmax : (A[i] + i);
	}
	   return count;
}

int main()
{
    	int n;
    	cin>>n;
    	int A[n];
    	for(int i = 0; i < n; i++)
    		cin>>A[i];
    	cout<<jump(A,n)<<endl;
    	return 0;
}