IT虾米网

跳跃游戏算法 II详解

itxm 2020年11月13日 编程语言 165 0

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
  从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
说明:

假设你总是可以到达数组的最后一个位置。

解:

对于这道题,最先想到的是动态规划,从后面向前计算,这样就知道前一个的最优步数,不用重复计算。但面对某些测试用例情况下

会显示超时,以下为动态规划的方法

 1 class Solution { 
 2 public: 
 3     int jump(vector<int>& nums) { 
 4         map<int,int> map_index_length; 
 5         map_index_length[nums.size()-1]=0; 
 6         for(int i=nums.size()-2;i>=0;i--) 
 7         { 
 8             int best_length=INT_MAX-1; 
 9             int step=1;
         //step小于当前大小可以移动距离
10 for(int j=i+1;j<nums.size()&&step<=nums[i];j++,step++) 11 { 12 best_length=min(best_length,map_index_length[j]); 13 } 14 15 map_index_length[i]=best_length+1; 16 17 } 18 return map_index_length[0]; 19 } 20 };

后面看别人解法,因为可以跳跃的步数小于当前数字大小而不是等于,发现此题应该考察的是贪心的方法

只要选择当前范围内最大的能达到的数字跳跃即可(可能有点难理解,比如3,3,2,2,1,2第一步应该选滴4位数2,即范围内nums[i]+i最大的数)

class Solution { 
public: 
    int jump(vector<int>& nums) { 
        //转化问题为找到每个范围内的最大值 
        int step=0; 
        //记录下一次最长能到的下标 
        int maxLength=0; 
        // 
        int end=0; 
        for(int i=0;i<nums.size()-1;i++) 
        { 
            //寻找可以到的范围内最大的数 
            maxLength=max(maxLength,nums[i]+i); 
            //所选点的全部范围走完
if(i==end) { end=maxLength; //保存此次范围内最远的坐标
step
++; } } return step; } };

 

所选点的全部范围走完
发布评论

分享到:

IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

对称的二叉树算法详解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。