算法题--跳步游戏判断是否可达终点
2020-04-13 本文已影响0人
岁月如歌2020
image.png
0. 链接
1. 题目
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.
2. 思路1:贪心算法
题目要求是判断是否可以满足要求,换句话说,就是在每个位置处,判断
max_end = i + nums[i] >= len(nums) - 1
是否成立, 如果不成立, 则记录到目前位置的最大的max_end
, 然后寄希望于后续位置
在两种情况下,可以提前知晓结果:
-
max_end >= len(nums) - 1
成立, 则返回True
-
i > max_end
成立, 代表中间应该出现了0, 导致无法跳到第i个位置, 跳步在此中断, 返回False
3. 代码
# coding:utf8
from typing import List
class Solution:
def canJump(self, nums: List[int]) -> bool:
if len(nums) <= 1:
return True
end_idx = len(nums) - 1
max_end = 0
for i in range(end_idx + 1):
if i > max_end:
return False
end = i + nums[i]
if end > max_end:
max_end = end
if max_end >= end_idx:
return True
return False
solution = Solution()
print(solution.canJump([2, 3, 1, 1, 4]))
print(solution.canJump([3,2,1,0,4]))
print(solution.canJump([0]))
输出结果
True
False
True