Leetcode jump Game II

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.)

题目是假设输入数组能满足到达数组末尾的条件,求出最少的跳数。

题目给出的测试用例是[2,3,1,1,4]

第一次从开头跳,则跳得位置为0+A[0]=2,故在位置2

根据贪心策略下次跳的时候应该选择1~2之间跳的最远的位置开始跳

1的位置跳的距离为1+A[1]=4

2的位置跳的距离为2+A[2]=3

故下一步选择从1的位置开始跳刚好能跳到最后结束

class Solution {
public:
int jump(int A[], int n) {
int res = , last = , cur = ;
for(int i = ; i < n; ++ i){
if(i > last) last = cur,res++;
cur = max(cur,A[i]+i);
}
return res;
}
};
上一篇:前端知识概述----公司内部的一次分享 分类: JavaScript HTML+CSS 2015-04-16 21:24 2593人阅读 评论(2) 收藏


下一篇:strstr()查找函数,strchr(),strrchr(),stristr()/strpos(),strrpos()查找字符串位置