【算法狂想曲】回溯,动态规划,贪心 妙不可言解决 跳跃游戏问题

2020-04-03   113 次阅读


昨天飞行堡垒回归了,然而。。。并没有修好,于是又二进宫了,今天又拿着小电脑在LeetCode上刷题
今天看到一题 叫做 跳跃游戏的问题

题目

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

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

判断你是否能够到达最后一个位置。

比如给定数组[2,3,1,1,4]
意味着在第0位你能跳1~2步,到第1位或者第2位,以此类推

尝试

回溯

像我这种小菜鸟第一个想到的就是回溯,回溯思路简单,如果能AC,岂不美滋滋
果然是我想太多了
本人回溯代码

class Solution {
public:
bool whether=false;         //设立标志最后判断是否可达
void perm(vector<int>& nums,int current,int teminate)
{
    if(current==teminate)  //当前位置为数组末端,可达,返回,标志置1
    {
        whether=true;
        return;
    }
    if(current>teminate)   //如果当前位置超出数组界限,返回
    return;
    if(nums[current]==0)  //如果当前可选步数为0,证明无路可走,返回
    return;
    for(int i=1;i<=nums[current];i++)    //从卖出1步到最大步数依次尝试
    {
        if((current+i)<=teminate)    //代码超时后尝试的剪枝操作
        perm(nums,current+i,teminate);
    }
    
}
    bool canJump(vector<int>& nums) {
        int l = nums.size()-1;
        perm(nums,0,l);
        return whether;
    }
};

很明显代码超时了
通过数据 70/75
因此回溯这种方法就很快被否定了
想想也觉得是,回溯差不多把所有情况都罗列出来了,不超时才怪

在没有方法的情况下点进了官方题解
看到官方代码,顿时不禁赞叹起来,太巧妙了

动态规划

动态规划一直是本人的噩梦,因为大部分动态规划的题都不是很会解
但是这题的动态规划我却一眼看懂了(可能因为它是个一维的动态规划)

首先,它定义了三种状态

  • UNKNOWN(未知)
  • GOOD(好,证明可以到终点)
  • BAD(差,无法到达终点)

大体思路就是定义一个状态数组,先将数组所有内容设置为UNKNOWN(未知),将最后一个位置也就是终点设置为GOOD(可达),然后,从后往前扫描数组,扫描到某一个位置
如果该位置的下标加上该位数的最大步数范围内有GOOD位置存在,则将其也设置为GOOD
就好比[2,3,1,1,4]
扫描到倒数第二位
当前下标为3,加上最大步数1为等于4,下标为4的位置是GOOD位置(终点),因此将下标为3的位置设置为GOOD
每次总是将新扫描出来的GOOD位置作为结果位置

然后一遍扫描完成后,如果结果位置刚好是数组开始的位置,则说明可达,返回真,否则不可达
结果位置刚好是数组开始的位置证明从数组开始位置开始,至少存在一种方法可以到达数组末尾

思路清晰,代码就可以开始写了

AC代码(C++ 动态规划)

class Solution {
public:
int situation[100000];                    //状态数组(一定要开的足够大)
    bool canJump(vector<int>& nums) {
        if(!nums.size()||nums.size()==1)   //略去特殊情况
        return true;
        int result=nums.size()+1;          //将结果初始化为非0数
        situation[nums.size()-1]=1;        //将终点设置为可达GOOD
        int length = nums.size();          
      for(int i=nums.size()-2;i>=0;i--)    //从倒数第二个数开始向前扫描
      {
          int dis = ((i+nums[i]+1)>length)?length:(i+nums[i]+1);   //判定范围(超出界限则直接设为数组左界限)
           for(int j=i+1;j<dis;j++)
          {
              if(situation[j]==1)    //如果范围内有可达GOOD位置,则将当前位置也设为可达GOOD,并且设为结果位置
              {
                  situation[i]=1;
                  result=i;
                  break;
              }
          }
      }
      return result==0;                //如果结果位置为0,为true,否则为false
    }
};

更上一层楼

看完动态规划后,发现题解里还有一个方法

贪心

神仙,这最后的王炸竟然是贪心
看完整个人都精神了,这大概就是大佬吧
其实整体思路跟之前动态规划差不多,就是找最后一个GOOD位置
只不过这次不需要状态
直接对下标进行操作与比较就行了

比如你在下标为3的位置,最多可以迈出10步,下标为6是可达GOOD位置,因为(3+10)等于13大于10,证明3也是可达位置,直接将3设为结果位置即可,以此类推,贪到最后结果就出来了

AC代码( C++ 贪心)

class Solution {
public:

    bool canJump(vector<int>& nums) {
        if(!nums.size())              //过滤特殊情况
        return true;
       int result=nums.size()-1;      //将结果位置初始化为终点
       for(int i=nums.size()-2;i>=0;i--)  //从倒数第二个元素开始向前扫描
       {
           if(i+nums[i]>=result)         //如果当前位置可达范围包含先前的结果位置,将结果位置设为当前位置(贪就对了)
           result=i;
       }
       return result==0;
    }
};

真的妙不可言,这个方法用最少的代码量打出了最好的成绩
时间直接战胜了百分之95.11的人

结论

人外有人,山外有山,真的只有想不到,没有做不到

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议