「LeetCode每日一题」—— 55. 跳跃游戏
55. 跳跃游戏
链接：https://leetcode-cn.com/problems/jump-game/
难度：中等
题目
思路
这题很容易想到从后面开始往前面跳。如果倒数第一可以达到，那最后就可以达到。
其实我们可以换一种想法，如果某一个作为起跳点的格子可以跳跃的距离是3，那么表示后面3个格子都可以作为起跳点。我们可以对每一个能作为起跳点的格子都尝试跳一次，把能跳到最远的距离不断更新。如果可以一直跳到最后，就成功了。
为什么要保持跳到最远距离，这是因为我们认为，如果能跳到这个点，那其实左边的任何点其实都可以跳到。
代码见解决方案。
方案代码
解决方案：
class Solution:
def canJump(self, nums: List[int]) -> bool:
current = 0
for i in range(len(nums)):
if i > current:
return False
current = max(current, i+nums[i])
return True
原创文章，作者：flypython，如若转载，请注明出处：http://flypython.com/algorithm/leetcode/333.html
微信扫一扫 
支付宝扫一扫 相关推荐
-
「LeetCode每日一题」—— 11. 盛最多水的容器
11. 盛最多水的容器 链接：https://leetcode-cn.com/problems/container-with-most-water/难度：中等 题目 思路 这道题和…
-
「LeetCode每日一题」——LCOF. 40. 最小的k个数
LCOF. 40. 最小的k个数 链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/难度：简单 题目 输入整…
-
「LeetCode每日一题」—— 46. 全排列
46. 全排列 链接：https://leetcode-cn.com/problems/permutations/难度：中等 题目 点击原文链接跳转查看题目 思路 这题算是一个基础…
-
「LeetCode每日一题」——322. 零钱兑换
322. 零钱兑换 链接：https://leetcode-cn.com/problems/coin-change/难度：中等 题目 给定不同面额的硬币 coins 和一个总金额 …
-
「LeetCode每日一题」——836. 矩形重叠
836. 矩形重叠 链接：https://leetcode-cn.com/problems/rectangle-overlap/难度：简单 题目 矩形以列表 [x1, y1, x2…
-
「LeetCode每日一题」—— 56. 合并区间
56. 合并区间 链接：https://leetcode-cn.com/problems/merge-intervals/难度：中等 题目 给出一个区间的集合，请合并所有重叠的区间…
-
「LeetCode每日一题」——LCOF.57 – II. 和为s的连续正数序列
面试题57 – II. 和为s的连续正数序列 链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu…
-
「LeetCode每日一题」—— 151. 翻转字符串里的单词
151. 翻转字符串里的单词 链接：https://leetcode-cn.com/problems/reverse-words-in-a-string/难度：中等 题目 给定一个…
-
「LeetCode每日一题」206. 反转链表
206. 反转链表 题目 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL输出: 5->4->3->2-&g…
-
「LeetCode每日一题」—— LCOF.13. 机器人的运动范围
LCOF.13. 机器人的运动范围 题目链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof…
简体中文
繁體中文
English
日本語
您必须登录才能发表评论。