Leetcode - 跳跃游戏(贪心)
发布日期:2021-07-01 00:14:58
浏览次数:2
分类:技术文章
本文共 1374 字,大约阅读时间需要 4 分钟。
题目描述
给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]输出: true解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]输出: false解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。
解题思路
贪心思想:
方法一:从前往后找。我们可以找到第一个可以直接跳到最后一个地方的点,然后把这个地方作为最后一个点(这个点能到最后一个,那么只要能到这个点就能到最后一个),一直循环,看看0这个地方能否作为最后一个点,如果能则输出true,否则输出false。
bool canJump(int* nums, int numsSize) { numsSize--; for (int i = 0; i < numsSize; i++) { if (nums[i] + i >= numsSize) { numsSize = i; i = -1; } } if (numsSize) return false; return true;}
方法二:从后往前找。我们可以找到最后一个可以直接跳到最后一个地方的点,然后把这个地方作为最后一个点(这个点能到最后一个,那么只要能到这个点就能到最后一个),一直循环,看看0这个地方能否作为最后一个点,如果能则输出true,否则输出false。
bool canJump(int* nums, int numsSize) { numsSize--; for (int i = numsSize - 1; i >= 0; i--) if (i + nums[i] >= numsSize) numsSize = i; if (numsSize) return false; return true;}
方法三:用MaxStep存当前跳跃的最大距离,循环遍历出当前跳跃的最大距离。看看最后最大距离是否大于等于n,如果大于等于n则证明能到达最后一个,否则不能。
#define max(a, b) a > b ? a : bbool canJump(int* nums, int numsSize) { int MaxStep = nums[0]; for (int i = 1; i < numsSize; i++) { if (i > MaxStep) return false; MaxStep = max(i + nums[i], MaxStep); if (MaxStep >= numsSize - 1) return true; } return MaxStep >= numsSize - 1;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/84258401 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年04月12日 14时50分28秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
python built-in function summary
2019-05-01
对于git/热部署/创建maven工程的小记录
2019-05-01
在jsp中调用本地外部json文件的解决方法
2019-05-01
ECharts is not Loaded解决方案
2019-05-01
ECharts地图显示不完整,只显示南海诸岛问题
2019-05-01
echarts is not defined解决方案
2019-05-01
echarts切换tab时,第一个图表显示,第二个图表不显示的解决办法
2019-05-01
记一次Hive 行转列 引起的GC overhead limit exceeded
2019-05-01
Scala List的一些常用方法
2019-05-01
FastJson对JSON字符串、JSON对象及JavaBean之间的相互转换
2019-05-01
git常用指令
2019-05-01
shell中获取当前日期,下月1日,上月底,上月同期日期,比较两个日期大小
2019-05-01
java单例模式几种常见实现方式
2019-05-01
shell脚本中$0,$?,$!、$$、$*、$#、$@等的意义
2019-05-01
Linux正则表达式基础入门+扩展
2019-05-01
Java实现生产者消费者模式的三种方法
2019-05-01
Java线程池的四种拒绝策略
2019-05-01