7、编写一个程序,给定一个整数列表 nums,其中 nums[i] 表示从当前位置可以跳到的最大距离,判断是否可以从位置 0 跳到最后一个位置。示例:输入: 输出: 解释: 用python实现
时间: 2024-10-13 21:17:33 浏览: 12
leetcode卡-FirstMissingPositives:第一个缺失的正数
为了判断一个整数列表 `nums` 是否允许从位置 0 跳到最后一个位置,我们可以采用双指针策略。假设一个指针 `start` 代表当前起始位置,另一个指针 `end` 代表到达的最远位置。初始时,`start = 0` 和 `end = nums[0]`。
接下来,我们不断更新 `end` 的值,使其尽可能地向右移动,即 `end = min(end, start + nums[end])`。如果在遍历过程中发现 `end >= len(nums) - 1`,说明可以从位置 0 到达最后一个位置,返回 True;否则,当遍历结束后返回 False。
以下是 Python 代码实现:
```python
def canJump(nums):
if not nums or nums[0] == 0:
return False
start, end = 0, nums[0]
while end < len(nums) - 1:
if start > end:
return False
for i in range(start + 1, min(end + 1, len(nums))):
if i + nums[i] >= len(nums) - 1:
return True
start += 1
end = max(end, start)
return end >= len(nums) - 1
# 示例:
nums = [2, 3, 1, 1, 4]
print(canJump(nums)) # 输出:True
```
阅读全文