首页 > 其他 > 详细

Leetcode 贪心 Jump Game II

时间:2014-09-10 01:38:59      阅读:253      评论:0      收藏:0      [点我收藏+]

Jump Game II

 Total Accepted: 16242 Total Submissions: 65802My Submissions

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


题意:
给一个包含非负整数的数组,每个数表示最大能跳跃的距离,最初的位置在
下标 0处,求跳到数组的最后一个位置所需的最少步数
思路:贪心
定义两个变量start和 end,
start 表示还没扫描的数组元素的起点,
end 表示当前能到达的位置,
扫描数组,不断扩大 end,更新 start。每这样一个过程为一步

复杂度:O(n)


int jump(int A[], int n) {
	if(n <= 1) return 0;
	int start = 0, end = 0, count = 0;
	while (1)
	{
		count ++;
		int _max = end; //_max表示[start, end]区间能达到的最远的位置 
		for(int i = start, i <= end; ++i){
			_max = max(_max, i + A[i]);
			if(_max >= n - 1){
				return count;
			}
		}
		start = end;
		end = _max;
	}
}


Leetcode 贪心 Jump Game II

原文:http://blog.csdn.net/zhengsenlie/article/details/39166719

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!