LEETCODE 55. 跳跃游戏

LEETCODE 55. 跳跃游戏

题目描述

给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。

示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳1步,从位置0到达 位置1, 然后再从位置13步到达最后一个位置。

示例 2:
输入: [3,2,1,0,4]输出: false解释: 无论怎样,你总会到达索引为3的位置。但该位置的最大跳跃长度是0, 所以你永远不可能到达最后一个位置。

递归

我们先通过一张图看下递归的运作原理

按照题目的意思nums[0]的值为2,所以它可以跳一步到下标1的位置,也可以跳两步到下标2的位置。
nums[1]的值为3,所以它有三个选择,跳一步到下标2,或者跳两步到下标3,还可以跳三步到下标4。到了下标4也就到了数组的最后一个位置了,所以后面可以不用检测了,为了演示的完整性我把剩余的跳跃步骤也画出来了。
从上图中我们也可以看出,每次跳跃的步数跟数组中具体值有关,nums[1]3所以就有三种跳跃选择,nums[i]k就有k种跳跃选择。
那么大概想到这个递归实现应该是由:循环+递归组合完成的。
注意,每次跳跃的时候至少要大于等于1,否则就等于是原地打转了。

再来看下递归的执行过程:

上图中f是函数名,括号里面的数字就对应了数组的下标。
数组下标1中的值是3,所以可以执行三次跳跃,对应到上图中f(1)就有三个子树。
从这里我们也可以看出,这个调用树是一棵N叉树,子节点的数量由1N不等。
注:递归的代码执行会超时。

java代码:

class Solution {
    public boolean canJump(int[] nums) {
        if(nums==null || nums.length==0) {
            return true;
        }
        return dfs(0,nums);
    }
    
    private boolean dfs(int index, int[] nums) {
        //递归的终止条件
        if(index>=nums.length-1) {
            return true;
        }
        //根据nums[index]表示要循环多少次,index是当前我们能到达的位置,
        //在这个基础上有 index+1,index+2.... index+i种跳跃选择
        for(int i=1;i<=nums[index];++i) {
            if(dfs(i+index,nums)) {
                return true;
            }
        }
        return false;
    }
}	
                                                                                                                                                 

python代码:

class Solution(object):
    def canJump(self, nums):
        if not nums:
            return True				
        n = len(nums)
        def dfs(index):
            # 递归的终止条件
            if index>=n-1:
                return True
        # 根据nums[index]表示要循环多少次,index是当前我们能到达的位置,
        # 在这个基础上有 index+1,index+2.... index+i种跳跃选择
        for i in xrange(1,nums[index]+1):
            if dfs(index+i):
                return True
        return False
    return dfs(0)
                                                                                                                                     

递归+记忆化

递归的性能差因为执行了很多重复计算

如上图中,f(3)就被反复计算了好几次,既然性能不够就加缓存吧,把结果缓存起来,这样时间上可以大幅度提升。

但很遗憾,即使这样优化了,还是会执行超时。

java代码:

class Solution {
    public boolean canJump(int[] nums) {
        if(nums==null || nums.length==0) {
            return true;
        }
        Map<Integer,Boolean> cache = new HashMap<Integer,Boolean>();
        return dfs(0,nums,cache);
    }
    
    private boolean dfs(int index, int[] nums, Map<Integer,Boolean> cache) {
        if(index>=nums.length-1) {
            return true;
        }
        if(cache.containsKey(index)) {
            return cache.get(index);
        }
        for(int i=1;i<=nums[index];++i) {
            if(dfs(i+index,nums,cache)) {
                cache.put((i+index),Boolean.TRUE);
                return true;
            }
        }
        cache.put(index,Boolean.FALSE);
        return false;
    }
}	
                                                                                        

python代码:

class Solution(object):
    def canJump(self, nums):		
        if not nums:
            return True
        n = len(nums)
        cache = dict()
        def dfs(index):
            if index>=n-1:
                return True
            if index in cache:
                return cache[index]
            for i in xrange(1,nums[index]+1):
                if dfs(i+index):
                    cache[index] = True
                    return True
            cache[index] = False
            return False
        return dfs(0)
                                                          

贪心

我们看看下面这个跳跃数组的特点

nums[1]也就是3 可以跳跃到最后一个位置,因为它可以跳一步,跳两步,跳三步。
即以nums[1]为起点,后面三格位置都是可达的,也就是如果某个数组下标i是可达的,那么i+1i+2i+3。。。i+nums[i]这片区域都是可达的。
于是我们只需要维护一个最远可达的下标,然后遍历整个数组,如果数组遍历完后,这个最远可达的下标是大于等于 数组最后一个位置,那么说明最后一个位置是可达的,否则最后一个位置不可达。
如果还是不清楚的话看下面这个图应该就能明白了

上图中浅绿色表示可以扩大的可达范围,深绿色部分表示已知的可达范围。我们在遍历的时候,不断尝试是否可以扩大可达范围,也就是图中的浅绿色部分,一旦可达那么这片区域就变成深绿色的了。
我们不用等到深绿色最右边再判断,比如对于第三排橙色格子10,它没有达到深绿色最右边,但是它所在的位置,可以扩大 绿色边界。
当整个遍历结束后,我们记录的最大可达范围是大于数组最后一个位置,所以这个数组最后一位是可达的,返回true。

再看一个不可达的例子

看完这个图,应该就很明确了,每次更新的时候,看看最大可达范围是否 大于等于当前遍历到的数组下标,如果是才更新。否则说明这个区域是不可达的,当然也就不用更新了。
通过上面的图也可以发现,还有一个优化点,如果当前遍历到的下标最大可达范围大,可以直接跳出判断了。
所以这个算法的空间复杂度是O(1)的,最多需要遍历整个数组也就是O(N)的时间复杂度。

java代码:

class Solution {
    public boolean canJump(int[] nums) {
        if(nums==null || nums.length==0) {
            return true;
        }
        int n = nums.length;
        int ans = 0;
        //遍历数组,尝试扩大最大可达范围
        for(int i=0;i<n;++i) {
            if(ans>=i) {
                ans = Math.max(ans,i+nums[i]);
            }
        }
        if(ans>=n-1) {
            return true;
        }
        return false;
    }
}	
                                                            

python代码:

class Solution(object):
    def canJump(self, nums):		
        if not nums:
            return True
        n = len(nums)
        ans = 0
        # 遍历数组,尝试扩大最大可达范围
        for i in xrange(n):
            if ans>=i:
                ans = max(ans,i+nums[i])
        if ans>=n-1:
            return True
        return False
                                                   

 

(全文完)

2 次阅读

发表评论

电子邮件地址不会被公开。