国内高端医疗网站建设百度客服中心电话
题目链接:
45. 跳跃游戏 II - 力扣(LeetCode)
思路分析:这属于上一题的变种,思路有所不同,要用到贪心的思想。从第一步开始,在可以跳跃的范围内,选择能够到达最远位置的点将其作为下一次的跳点,然后逐次更新直到得到结果。题目中maxpos表示当前阶段内能够到达的最远距离,也就是下一次跳到的点,end表示查找的边界,step记录跳跃的步数。
算法分析:这道题目用到了贪心的算法思想,在保证局部最优的同时得到全局最优解,属于比较常见的一类题目。
参考代码
class Solution {
public:int jump(vector<int>& nums) {int maxpos=0,n=nums.size(),end=0,step=0;//maxpos表示当前阶段能跳跃的最大距离,end表示当前阶段的结尾for(int i=0;i<n-1;++i){//遍历数组,只到n-1是因为无需到最后一个元素,题目中说一定可以完成maxpos=max(maxpos,nums[i]+i);//寻找当前阶段内最大的条约距离if(i==end){//如果已经到当前阶段的末尾end=maxpos;//更新新的末尾step++;//增加一次条约的次数}}return step;//返回结果}
};