leetcode 55.跳跃游戏
发布日期:2021-05-12 15:54:43 浏览次数:4 分类:技术文章

本文共 1886 字,大约阅读时间需要 6 分钟。

leetcode 55.跳跃游戏

题目描述:

给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。示例 1:输入: [2,3,1,1,4]输出: true解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。示例 2:输入: [3,2,1,0,4]输出: false解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。

做法一:

最简单的思维,设置一个boolean型的数组dp[],从后往前推,倒数第二个如果不为0,就初始化为true,否则为false,之后的逻辑就是,如果当前能直接走到最后,或者范围内,dp[]有为true的,就设为true,最后返回dp[0]即可

public boolean canJump(int[] nums) {
int length = nums.length; if (length == 1) return true; boolean[] dp = new boolean[length]; Arrays.fill(dp, false); if (nums[length - 2] != 0) dp[length - 2] = true; //because the last num is no use, we just need to judge can we get there, //so i begin at length-2 for (int i = length - 3; i >= 0; i--) {
for (int j = 1; j <= nums[i]; j++) {
if ((i + j) >= length - 1 || dp[i + j] == true) {
dp[i] = true; break; } } } return dp[0]; }

但是这一点儿都不贪心,

方法二:
从前往后遍历,每次记录能到达的最远的下标 maxIndex , 一直遍历到最后,返回maxIndex是否>=数组长度即可

public boolean canJump2(int[] nums) {
if(nums.length <= 1)return true; int mostFar = 0; int startIndex = 0; while (startIndex <= mostFar && mostFar <= nums.length - 1) {
mostFar = Math.max(mostFar, (startIndex + nums[startIndex])); startIndex++; } return mostFar >= nums.length - 1; }

如 \color{#2d85f0}{如} 果 \color{#f4433c}{果} 感 \color{#ffbc32}{感} 觉 \color{#2d85f0}{觉} 写 \color{#0aa858}{写} 的 \color{#f4433c}{的} 还 \color{#2d85f0}{还} 不 \color{#f4433c}{不} 错 \color{#ffbc32}{错} , \color{#2d85f0}{,} 不 \color{#0aa858}{不} 要 \color{#f4433c}{要} 忘 \color{#2d85f0}{忘} 记 \color{#f4433c}{记} 点 赞 \color{#ffbc32}{点赞} 评 论 \color{#2d85f0}{评论} 收 藏 \color{#0aa858}{收藏} 关 注 \color{#f4433c}{关注}

转载地址:https://blog.csdn.net/qq_40666620/article/details/101273572 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:一个年轻程序员的人生感悟
下一篇:leetcode 122 买卖股票的最佳时机 II

发表评论

最新留言

感谢大佬
[***.8.128.20]2024年03月24日 15时35分02秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

mysql5.6 icp mrr bak_【mysql】关于ICP、MRR、BKA等特性 2019-04-21
mysql utf8跟utf8mb4_MySQL utf8 和 utf8mb4 的区别 2019-04-21
docker mysql开机自启动_Docker学习4-学会如何让容器开机自启服务【坑】 2019-04-21
在mysql中删除表正确的是什么_在MySQL中删除表的操作教程 2019-04-21
mysql有3个共同好友_共同好友mysql 2019-04-21
代理查询 mysql_查询数据库代理设置 2019-04-21
mysql dif_mysqldiff实现MySQL数据表比较 2019-04-21
mysql 允许其他主机访问权限_允许其他主机访问本机MySQL 2019-04-21
druid不能close mysql连接_alibaba druid mysql连接问题 2019-04-21
mysql 设置按天分表_MySQL 优化实战记录 2019-04-21
java连接mysql 不推荐_java连接mysql 2019-04-21
mysql数据库 quota_shell脚本抓取用户存储quota写道mysql并展现到grafana面板 2019-04-21
idea测试连接mysql报错08001_IDEA连接MySQL错误 2019-04-21
layui导入模板数据_layui表格-template模板的三种用法 2019-04-21
mysql分组显示行号_mysql 显示行号,以及分组排序 2019-04-21
MySQL常见的主从复制架构_如何搭建经典的MySQL 主从复制架构 2019-04-21
编写python程序、计算账户余额_小明有20w存款存在余额宝中,按余额宝年收益为3.35%计算,用Python编写程序计算,多少年后小明的存款达到30w?... 2019-04-21
python 公众号引流_公众号引流方法有哪些? 2019-04-21
java 减少内存_java中减少内存占用小技巧 2019-04-21
centos 7 mysql图形界面_centos7-vnstat图形界面搭建 2019-04-21