leetcode 45. Jump Game II 贪心算法&&DFS深度优先搜索

港控/mmm° 2022-06-09 10:17 125阅读 0赞

Given 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.)

Note:  
You can assume that you can always reach the last index.

题意不说了，这个第一想到的是递归，深度优先搜索，做了一下，发现超时，这个是因为尝试了所有的可能路径，所以会超时； 后来网上看了一下有贪心的做法，于是乎借鉴了一下，还是很简单的。

代码如下：

public class Solution 
    {
        
        /*
         * 这个问题我想到了两种解决方案：
         * 首先就是递归，这个来源于跳阶梯（斐波拉契数列）的递归解决方法，和这个问题
         * 很类似，不过我们是找的跳的次数最小的方案，采用递归解决
         * 不过由于要尝试所有的跳跃方案，最后找到最小的跳跃方案，这个采用递归应该会很费时间
         * 
         * 其二就是贪心算法：也就是每一次跳跃的尽量远，这样可以可以达到最小的跳跃次数，这个
         * 花费的时间就较小了
         */
        public int jump(int[] nums) 
        {
            //特殊情况处理
            if(nums==null || nums.length<=1)
                return 0;
    
            int index=0;
            int step=0;
            while( index < nums.length)
            {
                //当前的覆盖能力可以达到最后一个点，OK，一跳就可以完成任务
                if(nums[index]+index >= nums.length-1)
                {
                    step=step+1;
                    break;
                }else
                {
                    int max=-1;
                    int midIndex=-1;
                    for(int i=1;i<=nums[index];i++)
                    {
                        //衡量最远的跳跃方案
                        if(i+nums[index+i]>=max)
                        {
                            max=i+nums[index+i];
                            midIndex=i+index;
                        }
                    }
                    //记录中转点的index
                    index=midIndex;
                    step=step+1;
                }
            }
            return step;    
        }
    
    
        /*
         * 这个是递归版本，不过很费时
         * */
        static int minJump=Integer.MAX_VALUE;
        private int jumpForDiGui(int[] nums) 
        {
            if(nums==null || nums.length<=1)
                return 0;
    
            minJump=nums.length+2;
            tryJump(nums,0,0);
            return minJump;
        }
    
        private void tryJump(int[] nums, int index,int times)
        {
            if(index==nums.length-1)
                minJump=Math.min(minJump, times);
            else
            {
                //这个是要确定在target之前
                if(nums[index]==0)
                    return ;
                for(int i=1;i<=nums[index];i++)
                {
                    //每一个可能的尝试都做递归处理，不过很可能会超时
                    if(index+i<nums.length)
                        tryJump(nums, index+i,times+1);
                }
            }
        }
    }

下面是C++的做法，这道题是一道非常经典的贪心搜索的算法，

代码如下：

#include <iostream>
    #include <regex>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int jump(vector<int>& nums) 
        {
            if (nums.size() <= 1)
                return 0;
    
            int index = 0 , step = 0;
            while (index < nums.size())
            {
                if (index + nums[index] >= nums.size() - 1)
                {
                    step++;
                    break;
                }
                else
                {
                    int max = -1;
                    int tmp = index;
                    for (int i = 1; i <= nums[index]; i++)
                    {
                        if (i + nums[index + i] >= max)
                        {
                            max = i + nums[index + i];
                            tmp = index + i;
                        }
                    }
    
                    index = tmp;
                    step++;
                }
            }
            return step;
        }
    };