LeetCodeNo_55

这道题是一个跳跃问题,判断最后能不能到最后一个元素的位置。第一感觉这道题是一个在有限大空间内找解的问题,因此我第一感觉就是使用递归的方法,后来发现递归速度太慢了(应该是自己没写好),尤其是在最后两个问题上超出时间限制了,虽然通过抖机灵的方法骗过了但还是老老实实换了一种方法再做了一遍,这侧效果差强人意,我也接受。
首先贴上递归代码:

public boolean canjump(int[]nums){
        if(nums.length==1)
            return true;
        boolean res = jump(nums, 0, nums[0]);
        return res;
    }

    public boolean jump(int []nums,int current, int step){//current 表示当前的位置,step表示在当前位置下能走多少步
        if(current+step>=nums.length-1)
            return true;
        if(step==0&&current!=nums.length-1)
            return false;
        for(int i=nums[current];i>=1;i--){
            boolean flag=jump(nums, current+i, nums[current+i]);//只要找到一个解就可以返回了
            System.out.println(nums[current+1]);
            if(flag)
                return true;
        }
        return false;
    }

递归的方法比较好理解,但是速度慢,就是抖机灵通过后时间上只打败了10%。接下来介绍我才用的第二种硬钢法。通过递归我发现只要找到一个解就可以了,那我我尝试去寻找他能够走到的那个最远的解只要能超出数组范围即可,这就产生了第二种方法。

public boolean canJump(int[]nums){
        int current=0;
        int old_current=current;
        if(nums[current]>=nums.length-1)
            return true;
        while(current<nums.length-1){
            int temp;
            boolean flag=true;
            for(int i=0;i<=nums[current];i++){
                temp=current+i+nums[current+i];//在小循环内能走的距离
                if(temp>current+nums[current]){//如果在小循环内有一种情况比当前走的还远,那么就更新它,注意这个可能不是最远的那个,如果找到最远的还可以进一步提升速度
                    current=current+i;//更新当前位置
                    if(current+nums[current]>=nums.length-1)
                        return true;
                    flag=false;
                    break;
                }
            }
            if(flag)//这说明当前就是走的最远的,那么重新出发,再在下一位置继续探索
            current=current+nums[current];
            if(current==old_current)//两次都掉到同一位置,说明走不出去了那么返回false
                return false;
            old_current=current;
            System.out.println(current);
        }
        return true;
    }

在这里插入图片描述
接下来我再尝试提升速度,找到小循环内的最大值。

原文链接:加载失败,请重新获取