Python程序检查是否可以通过单词列表拼写出目标


假设我们有一个名为 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

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

True

更新于: 2020年10月5日

146 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告