C/C++教程

【leetcode】 55 跳跃游戏

本文主要是介绍【leetcode】 55 跳跃游戏,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一开始的思路是,用一个二维数组 dp[i][j]  记录从位置 i 是否可以到达位置 j ,然后再遍历从最后一列起从后往前遍历每一列,如果这一列存在 1 则说明该列对应的下标是可达的,继续遍历前一列,如果某一列的值全部为0,说明该列对应的位置是不可达的,整体不可达,返回false,思来想去,觉得这个思路应该没有太大的问题,可能内存不能达到要求,果然,提交后,用例只跑到了第70个,内存超出限制了。

 

 

class Solution {
    public boolean canJump(int[] nums) {
          // n 是行,m是列
        int n = nums.length-1,m = nums.length;
        int dp[][] = new int[n][m];
        // 因为最后一个位置是终点,所以i从0到n-1个位置即可
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j <m; j++) {
                // 某个位置i上加上该位置上的值nums[i]如果大于等于j,则说明i上可以到达j
                dp[i][j] = i+nums[i]>=j?1:0;
                if (dp[i][j]==0)
                    break;
            }
        }

        // 从最后一列开始,遍历每一列的每一个行元素,求该列元素的 |
        for (int i = m-1; i >0 ; i--) {
            int result = 0;
            for (int j = 0; j < n; j++) {
                result |= dp[j][i];
            }
            if (result==0){
                return false;
            }
        }

      return true;
    }
}

 

 解析:

当 i = 0 时,nums[0] = 2 ,说明在 i= 0的位置可以移动2个单位,因此 当 j = 1 , 2 时 dp[i][j] =1;

当 i= 1 时,nums[1] = 1,说明在 i= 1的位置可以移动1一个单位,因此 dp[1][2] = 1

以此类推,最后得到一个dp二维数组

接着从最后一列往前遍历,如果某一列的值全部为0,说明该列对应的下标是不可达的。如下

 

 下标为3时,该列的值全部为0,说明下标为3这个位置不能达到。

(ps:这只是一个不成熟的思考方向,看看就好,用例只通过了70个,内存已经超出限制了,也不知道没有内存的限制下,这个思路是否正确。)


 

 

后来想了想,换了一种写法

class Solution {
    public boolean canJump(int[] nums) {
         int n = nums.length-1,end = nums.length-1;
        for (int i = n-1; i >=0 ; --i) {
            if (i+nums[i]>=end)
                end = i;
        }
        return end==0;
    }
}

 

 初始时,end = 5,for循环从数组倒数第二个位置(i=4)往前遍历

此时有 i + nums[i] = 4+1 =5 >=end,因此在接下来的循环中,终点不再是5,而是 end = i= 4

(因此此时if条件成立,说明 在 位置 i = 4 时,是可以移动到终点end = 5 的,那么接下来只要验证,i = 4前面的位置,可以移动到  4 这个位置即可)

【如果终点end在某个位置 i 时 被验证可达,则接下来只要验证 i 之前的位置是否可以达到 i (end=i) 即可】

如果条件不成立,则终点不变,i 继续往前。

最后for循环结束后,如果end = 0 说明可以到达,否则不行。

 

 

再有这个例子

 

 i从4开始往前遍历,当 i = 4、3、2、1 时都有 i+nums[i] <end = 5

当 i = 0时有 i +nums[0] = 5 >=end;

此时应该修改 end = i 即end = 0;

 

 if i + nums[i] >= end
       继续验证
            i-1 +nums[i-1] >= i (end=i)
    else
        i-1 +nums[i-1] >= end

 

这篇关于【leetcode】 55 跳跃游戏的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!