【leetcode】 55 跳跃游戏
2021/10/1 23:40: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 跳跃游戏的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享