「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每日一题」—— 23. 合并K个排序链表
23. 合并K个排序链表 链接:https://leetcode-cn.com/problems/merge-k-sorted-lists/难度:中等 题目 点击原文链接跳转查看题…
26/04/2020 -
「LeetCode每日一题」—— 466. 统计重复个数
466. 统计重复个数 链接:https://leetcode-cn.com/problems/count-the-repetitions/难度:困难 题目 思路 这是一道困难题,…
19/04/2020 -
「LeetCode每日一题」—— 1248. 统计「优美子数组」
1248. 统计「优美子数组」 链接:https://leetcode-cn.com/problems/count-number-of-nice-subarrays/难度:中等 题…
21/04/2020 -
「LeetCode每日一题」——LCOF.57 – II. 和为s的连续正数序列
面试题57 – II. 和为s的连续正数序列 链接:https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu…
06/03/2020 -
「LeetCode每日一题」—— LCOF.56 – I. 数组中数字出现的次数
LCOF.56 – I. 数组中数字出现的次数 链接:https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-d…
28/04/2020 -
「LeetCode每日一题」——543. 二叉树的直径
543. 二叉树的直径 链接:https://leetcode-cn.com/problems/diameter-of-binary-tree/难度:简单 题目 给定一棵二叉树,你…
10/03/2020 -
「LeetCode每日一题」—— 46. 全排列
46. 全排列 链接:https://leetcode-cn.com/problems/permutations/难度:中等 题目 点击原文链接跳转查看题目 思路 这题算是一个基础…
25/04/2020 -
「LeetCode每日一题」—— LCCI.01.07. 旋转矩阵
LCCI.01.07. 旋转矩阵 题目链接:https://leetcode-cn.com/problems/rotate-matrix-lcci/难度:中等 题目 给你一幅由 N…
07/04/2020 -
「LeetCode每日一题」——322. 零钱兑换
322. 零钱兑换 链接:https://leetcode-cn.com/problems/coin-change/难度:中等 题目 给定不同面额的硬币 coins 和一个总金额 …
08/03/2020 -
「LeetCode每日一题」——836. 矩形重叠
836. 矩形重叠 链接:https://leetcode-cn.com/problems/rectangle-overlap/难度:简单 题目 矩形以列表 [x1, y1, x2…
18/03/2020
您必须登录才能发表评论。