Python 程序：检查从索引 k 开始能否到达列表末尾

假设我们有一个名为 nums 的数字列表和另一个数字 k。如果我们从索引 k 开始，并且在任何索引 i 处，我们都可以向左或向右移动正好 nums[i] 步。我们必须检查我们是否可以到达列表的末尾。

因此，如果输入类似于 nums = [0, 0, 2, 1, 3, 3, 1, 1] k = 2，则输出将为 True，因为如果我们从索引 2 开始，然后跳到索引 4，然后跳到最后一个索引 7。

为了解决这个问题，我们将遵循以下步骤：

• n := nums 的大小

• visited := 一个大小为 n 的列表，并填充 0

• tovisit := 一个大小为 1 的列表，并将 k 插入其中

• 当 tovisit 的大小 < 0 时，执行以下操作

  • i := tovisit 中的最后一个元素，并将其从 tovisit 中删除

  • 如果 i 与 n-1 相同，则

  • 返回 True

• 如果 visited[i] 与 1 不相同，则

  • visited[i] := 1

  • up := i + nums[i]

  • down := i - nums[i]

  • 如果 up < n，则

  • 将 up 插入 tovisit 的末尾

  • 如果 down >= 0，则

  • 将 down 插入 tovisit 的末尾

• 返回 False

让我们看看以下实现以更好地理解：

示例

 在线演示

class Solution:
   def solve(self, nums, k):
      n=len(nums)
      visited = [0]*n
      tovisit = [k]
      while len(tovisit)>0:
         i=tovisit.pop()
         if i==n-1:
            return True
         if visited[i]!=1:
            visited[i]=1
            up=i+nums[i]
            dn=i-nums[i]
         if up=0:
            tovisit.append(dn)
      return False
ob = Solution()
nums = [0, 0, 2, 1, 3, 3, 1, 1]
k = 2
print(ob.solve(nums, k))

输入

[0, 0, 2, 1, 3, 3, 1, 1], 2

输出

True

Arnab Chakraborty

更新于： 2020年10月5日

317 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习