首页 > 代码库 > Leetcode 贪心 Jump Game II
Leetcode 贪心 Jump Game II
Jump Game II
Total Accepted: 16242 Total Submissions: 65802My SubmissionsGiven 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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。