贪心的题目。使用的每次找自己周围最大可达范围,如果最大可达范围是自身,那就跳到最大可达的位置,如果不是,就跳到最大的位置。
class Solution {
public:
int jump(vector<int>& nums) {
int len = nums.size();
if(len==1)return 0;
int footstep=0,Max_reach=0,next;
for(int i=0;i<len;){
Max_reach = 0;
//cout<<i<<endl;
for(int k=0;k<=nums[i];k++){
if(k+i==len-1){
footstep++;
return footstep;
}
if(Max_reach<nums[i+k]+i+k){
next = i+k;
Max_reach=nums[i+k]+i+k;
}
}
if(next==i)
i=Max_reach;
else
i=next;
footstep++;
}
return footstep;
}
};
转载请注明原文地址: https://ju.6miu.com/read-1295709.html