45. Jump Game II 

 ----------------------------------------------------------------------------

Mean: 

给定一个数组a，玩家的初始位置在idx=0，玩家需要到达的位置是idx=a.size()-1.

如果玩家在idx处，那么他最多可以向后走a[idx]步，问最少多少步可以走到终点.

analyse:

方法非常巧妙，类似于BFS.

Time complexity: O(N)

 

view code

/**

* -----------------------------------------------------------------

* Copyright (c) 2016 crazyacking.All rights steperved.

* -----------------------------------------------------------------

*       Author: crazyacking

*       Date  : 2016-03-08-14.52

*/

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using

namespace

std;

typedef

long

long(

LL);

typedef

unsigned

long

long(

ULL);

const

double

eps(

1e-8);

class

Solution

{

public

:

   

int

jump(

vector

<

int

>&

nums)

   

{

       

int

i(

0

),

j(

1

),

steps(

0

), N(

nums

.

size());

       

while(

j

< N)

       

{

           

int

endj

=

min(

nums

[

i

]

+

i

, N);

           

while(

j

<

=

endj)

           

{

               

if(

nums

[

j

]

+

j

>

nums

[

i

]

+

i)

                   

i

=

j;

               

j

++;

           

}

           

steps

++;

       

}

       

return

steps;

   

}

};

// this is my TLE code :(

//class Solution

//{

//public:

//    int jump(vector<int>& nums)

//    {

//        queue<pair<int,int>> que; // pos,step

//        int res=INT_MAX;

//        que.push(make_pair(0,0));

//        while(!que.empty())

//        {

//            pair<int,int> top=que.front();

//            que.pop();

//            if(top.first>=nums.size()-1)

//                res=min(res,top.second);

//            for(int i=1;i<=nums[top.first] && i+top.first<=nums.size();++i)

//            {

//                que.push(make_pair(top.first+i,top.second+1));

//            }

//        }

//        return res;

//    }

//};

int

main()

{

   

int n;

   

while(

cin

>>n)

   

{

       

vector

<

int

>

ve;

       

for(

int

i

=

0;

i

<n;

++

i)

       

{

           

int

tempVal;

           

cin

>>

tempVal;

           

ve

.

push_back(

tempVal);

       

}

       

Solution

solution;

       

int

ans

=

solution

.

jump(

ve);

       

cout

<<

ans

<<

endl;

   

}

   

return

0;

}

/*

*/